Hi @tarcieri and the other contributors! For the scicrypt crate I was working on constant-time big integers by wrapping GMP, but the interface was extremely clumsy. I decided to switch to this crate (which looks awesome!) and added the necessary methods for modular arithmetic.

I implemented the following functionality:

• Shifting left and right by 1 and returning the overflow as a Choice
• Neg for Wrapping<Uint<LIMBS>>
• Modular multiplicative inverse
• Computing parameters for the Montgomery form (MF)
• Going to and from MF
• Modular addition (in MF)
• Modular multiplication (in MF)
• Modular exponentiation (in MF)

In my opinion, there are at least two large issues right now that I would like to hear your opinion on.

• [x] The Modular interface is not satisfying to me because it copies the MontgomeryParameters and does not assert that two Modular integers indeed share the same modulus.
• [x] None of the functions are currently const fn.

Still, I thought it was good to already make a PR to bring this to your attention. I am happy to put in the effort to bring this to a point where it is mergeable! :)

Edit: The modulus is now a constant and the struct is called Residue rather than Modular.

Uses the dudect-bencher crate, a wrapper for the dudect C library:

https://github.com/oreparaz/dudect

Example output:

running 1 bench
bench reduce seeded with 0x2311ed8a8b8e6544
bench reduce ... : n == +0.100M, max t = +1.98296, max tau = +0.00628, (5/tau)^2 = 634328

dudect benches complete

The important part here is max t = +1.98296. If t were to exceed 10, then the code is likely not constant time. Since it's well below 10, reduce appears to be OK.

cc @andrewwhitehead @mikelodder7 @rozbb

Implemented serde::Deserialize and serde::Serialize for all types. This might be a bit overkill, implementing it for UInt might have been enough.

As serde currently doesn't support const generics (serde-rs/serde#1937), I used serde-big-array for the UInt implementation. The dependency is quiet minimal, this PR also spawned est31/serde-big-array#14 to make sure that the dependency is as minimal as possible.

I hope the tests are appropriate enough.

https://github.com/RustCrypto/utils/blob/710abc8c83a13def1c01958909405976f915e5a5/crypto-bigint/src/uint/rand.rs#L34-L42

If modulus is small compared to the full size ("number of limbs * size of limb") then it can take "forever".

The correct method is to mask off the top bits of the random number to match the size of modulus. This leads to a worst case of a 50% chance of failing and needing to generate another random number. The average for this worst case is needing to generate 2 random numbers.

Not sure about adding neg():

• Should there be a separate NegResidue trait, or should it be a part of SubResidue?
• The default implementation (via SubResidue) would require an access to zero, and therefore an additional trait bound, which DynResidue does not implement.

Based on https://gmplib.org/~tege/division-paper.pdf . This works ~100x faster than div_rem() for U256.

For reviewers:

• Suggestions on how exactly to expose the API (including the method naming) are welcome.
• Should div_rem() and related methods take NonZero<Self> too, and this way avoid returning a CtOption?

Changes:

• Added public Uint methods: ct_div_rem_limb_with_reciprocal(), div_rem_limb_with_reciprocal(), div_rem_limb().
• Added Div, Rem, DivAssign, and RemAssign implementations for the division by Limb.
• Added public Reciprocal type (exported at the root level).
• Added Limb::ct_lt() and ct_le() (constant time < and <=), with the return value applicable in ct_select().
• Separated Uint::shl_vartime() into shl_vartime() proper (that only shifts by whole limbs and calls shl_limb()) and shl_limb() (shifts within one limb, constant-time).
• Added benchmarks (division only for now).
• Removed Uint<LIMBS>: Integer bound from Div, Rem, DivAssign, and RemAssign of Uint by Uint.
• Division methods of Uint now take NonZero-wrapped arguments.

TODO:

• There are suggestions for implementing schoolbook division in the paper, so I think it may be worth it to try to compare that to the currently used algorithm. But that's better left for another PR.

When using self.bits() instead of the full field width, run time could vary drastically depending on the input, for a modulus significantly smaller than the UInt size.

Const generics and no-std are great features, both for performance and for interoperability. The down side is that some protocols require a dynamic moduli, and maybe even dynamic sizes, for example RSA sizes(2048/3072/4096/8192 etc), or DSA moduli sizes, and more.

This gets more obvious with something like #28, which makes the type generic over the field, then you have to support a dynamic field to be able to support RSA, dynamic DSA moduli, groups with unknown order etc.

My question is is it possible to win both worlds, and somehow both allow const generics for arrays, but also allow dynamic generation over vectors?

Confused about why this isn't working. Am i breaking some assumption?

        for (n, d, q, r) in &[
            (27,13,2,1),
            (26,13,2,0),
            (14,13,1,1),
            (13,13,1,0),
            (12,13,0,12), // reminder returns = 0
            (1,13,0,1), // reminder returns = 0
        ] {
            let lhs = U64::from_u8(*n);
            let rhs = U64::from_u8(*d);
            let expected_q = U64::from_u8(*q);
            let expected_r = U64::from_u8(*r);
            let (quot,rem) = lhs.div_rem(&rhs).unwrap();
            assert_eq!(expected_q, quot);
            assert_eq!(expected_r, rem);
        }

As noted in #115, both of these functions compute values and then pass them as the rhs to UInt::shl_vartime.

• https://github.com/RustCrypto/crypto-bigint/blob/ed8d96b/src/uint/div.rs#L24
• https://github.com/RustCrypto/crypto-bigint/blob/ed8d96b/src/uint/div.rs#L63

cc @andrewwhitehead @mikelodder7

For a project of mine where the modulus can be chosen to be close to UInt::MAX, I created optimized implementations of modular operations. I thought maybe others can benefit from them, too, so I ported my implementation to the crypto-bigint crate.

This commit implements modulo operations (neg, add, sub, mul) for special moduli that are so close to MAX that the difference to overflow fits in a single Limb. For such moduli, these new implementations are much faster than the existing generic modulus implementations. (For mul there's no comparison since there's no corresponding generic modulus implementation, yet.)

For U256, I benchmarked the generic against the specialized implementations using criterion-rs on Intel Core i7-8565U @ 1.80GHz and obtained the following average times. Note that I used a const modulus known at compile-time, which enables some compiler optimizations after inlining. With a modulus known only at runtime, times might differ.

| | U256::add_mod | U256::sub_mod | U256::mul_mod | |-|-|-|-| | generic (after #109 got merged) | 10.857 ns | 9.6262 ns | not implemented | | _special | 3.8276 ns | 4.1339 ns | 20.188 ns |

• Break long lines in comments and tests and fix some hardcoded bit sizes
• Fix the hardcoded Limb size in inv_odd_mod() - was set to 64 (did not cause errors, just made the inversion twice as slow on 32-bit targets)
• Added inv_odd_mod_bounded() for cases of argument/modulus known to be small
• Removed inv_odd_mod_option() - we do not provide such interface for other constant functions

Tangentially related: what should we return as is_some in constant functions that can fail - Limb or Word? There are cases of both in the codebase.

Currently num-traits is only in dev-dependencies.

As originally suggested here it would be useful to have some support for traits for abstracting across bignum libraries, which would make it possible for e.g. the rsa crate to use either crypto-bigint or num-bigint-dig.

Though num-traits probably lacks all of the requisite functionality to do that, it would get us quite a bit of the way there.

Here I have three numbers

    let p = U256::from_be_hex("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF");
    let a = U256::from_be_hex("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC");
    let b = U256::from_be_hex("28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93");

So how to calculate (a * b) mod p?

I found this function:

pub const fn mul_mod_special(&self, rhs: &Self, c: Limb) -> Self {
   ... 
}

But I don't know how to determine the value of parameter c。

Could you help me?

Reading through some code, I unrelatedly noticed that pub const fn split(&self) is unconditionally implemented for U192. This doesn't seem to be correct on 64-bit platforms where U192 has an odd number of limbs.

I would argue that it's the user's decision whether they want a cryptographically safe RNG used or not; there can be applications which do not require that restriction, and CryptoRng is just a marker trait and does not provide any additional functionality.

The rust docs say the following about overflowing shift:

If the shift value is too large, then value is masked (N-1) where N is the number of bits, and this value is then used to perform the shift. (Source: https://doc.rust-lang.org/std/primitive.u64.html#method.overflowing_shl) And you can see this via the following code:

#[allow(arithmetic_overflow)]
fn main() {
    let a: u64 = 500;
    let b = a << 119;
    println!("{}", b);
}

Which prints 18014398509481984000.

On the other hand in the implementation here zeros will be returned: https://github.com/RustCrypto/crypto-bigint/blob/36dbb69a73cfdba1eef90e10a8424cde39602e3b/src/uint/shl.rs#L18