num-bigint-dig dependency

[darconeous]

num-bigint-dig (used here) seems like a a suboptimal dependency. It doesn't appear to be actively developed and it has a few bugs related to prime number calculation that don't appear to be going away any time soon. There also doesn't appear to be any effort to upstream the changes into num-bigint.

The bugs in the prime number calculation appear to be causing primes to be skipped (rather than non-primes being marked as prime), but the presence of these bugs doesn't inspire a lot of confidence.

[tarcieri]

It would be nice to be able to migrate to crypto-bigint which is maintained by the @RustCrypto organization and used in our other cryptography projects, namely our elliptic curve implementations. Notably it implements algorithms in constant time, whereas num-bigint(-dig) does not (#19), which is a major security concern. There's also a well-maintained prime number generation library for it crypto-primes.

The main reason why we can't do that today is crypto-bigint primarily supports stack-allocated big integers. That's good news for heapless no_std users who can't currently use rsa, but many RSA users depend on the ability to support multiple different key sizes at runtime, and in such a case would benefit from heap-allocated big integers whose sizes can be determined at runtime.

We recently added some very much preliminary support for that in the form of BoxedUint, but it is more PoC stage and nowhere close to being ready for rsa to use (nor can crypto-primes use it yet).

Ideally we could allow heapless no_std users to use stack-allocated Uints which are specialized to a particular size, and alloc-friendly users can use BoxedUint, with the rsa algorithm implementations written in terms of traits that abstract over the distinction.

[darconeous]

What about switching to standard num-bigint and num-prime?

I realize that num-bigint isn't necessarily cryptography related, but it feels like cryptography-important features could be added behind a feature flag if there is a need to close that gap.

I guess I'm just not familiar enough with what problems num-bigint-dig was trying to address. The big thing I noticed was the inclusion the primality testing. If num-prime could do that, then maybe it makes sense to go back to the canonical num-bigint?

[tarcieri]

If it's possible to do so with a small change it's something we could consider. I too am not super familiar with what is preventing rsa from using upstream num-bigint.

I'd still propose an eventual migration to crypto-bigint as a migration to num-bigint will not address heapless use and bignum libraries which haven't been written from the ground-up to use constant time algorithms are punji pits full of sidechannels. Trying to bolt on cryptographic functionality as an afterthought tends not to be a particularly promising approach.

[dignifiedquire]

When I forked, both speed and a series of algorithms needed for RSA were missing from num-bigint (with little chance of upstreaming the APIs I needed, which is the reason for the fork). Last time I checked the speed had improved, but the general API and algorithm issues where still there.

I don't think it makes sense to migrate to anything other than crypto-bigint at this point, given how close it is to providing what we need.

[dignifiedquire]

Also note, the issue around next_prime does not affect this crate, as it is not used in the actual RSA implementation.

[darconeous]

Seems reasonable to me.

Is crypto-bigint ever going to support non-stack arbitrary-sized bigints?

[tarcieri]

@darconeous if you mean arbitrary precision like num-bigint, then no. We're currently only supporting a fixed precision chosen at runtime, which is fine for the purposes of RSA.

[darconeous]

I'll go ahead and close this, reopen if you want to use it to track migration to crypto-bigint.

[tarcieri]

51 is probably the best tracking issue for crypto-bigint right now as one of the main motivations is core-only support.

See this comment: https://github.com/RustCrypto/RSA/issues/51#issuecomment-1521118138