Migrating from `num-bigint(-dig)` to `crypto-bigint`

[tarcieri]

There are a couple issues related to this (#19, #51), but no specific discussion issue for it, so I thought I'd open one.

crypto-bigint v0.6.0-pre.0 now includes more fully featured heap-allocated types which are fixed-precision, can be easily padded to the modulus size, and are (almost) completely implemented in terms of constant-time algorithms:

• BoxedUint
• BoxedResidue
• BoxedResidueParams

Notably it should be possible to represent the RSA modulus using BoxedResidueParams which precomputes the constants needed to translate in and out of the Montgomery domain.

The BoxedResidue type supports modular pow and invert, and BoxedUint supports inv_mod (though the implementation on BoxedResidue should be more efficient, since it can rely on an odd modulus). All of these are implemented using constant-time algorithms, although lingering bits of timing variability may remain in certain places (notably the BoxedResidueParams constructor presently uses a non-constant-time remainder function, though since the RSA modulus is a public parameter this shouldn't be an issue).

That should be the core functionality required. There are probably still gaps as this functionality was somewhat hastily implemented, though it should all be fairly well tested.

To start I think we can focus on rsa::hazmat::rsa_decrypt, perhaps converting num_bigint::BigUint to crypto_bigint::BoxedResidue internally. If we can get that to work, we may be able to ship a mitigation without breaking changes to the public API.

A full conversion will require much more work. We'll need to add Boxed* support to crypto-primes, for example: https://github.com/entropyxyz/crypto-primes

cc @dignifiedquire

[dignifiedquire]

work on this is happening on #394

[StackOverflowExcept1on]

Hi, I'm looking for stack-allocated RSA library in Rust. crypto-bigint seems to be able to do this. Although I can't see modpow in crypto-bigint.

[sosthene-nitrokey]

Hi, I'm looking for stack-allocated RSA library in Rust. crypto-bigint seems to be able to do this. Although I can't see modpow in crypto-bigint.

See https://github.com/RustCrypto/RSA/pull/394#issuecomment-1980060208 and https://github.com/RustCrypto/RSA/pull/394#issuecomment-1980922832

[tarcieri]

51 is the tracking issue for "heapless" support