random_mod can take a very long time

[Sc00bz]

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.

[Sc00bz]

Oh right obviously this can run forever if called with a modulus of zero. For this case it should error similarly to a divide by zero.

[tarcieri]

For now we can add a debug_assert! that the modulus is non-zero.

It'd be nice to eventually capture these sort of cases using the type system so we can ensure implementations are panic free.

[newpavlov]

I think that ideally modulus should be a const parameter for a higher-level bigint type. This would allow us to either reject such edge cases on the type level or insert branches which would be eliminated at compile time.

[tarcieri]

@newpavlov yep, exactly, unfortunately min_const_generics are nowhere near that expressive

[tarcieri]

Regarding a non-zero modulus, we recently added a NonZero wrapper (#13) which can ensure the modulus is non-zero at the type level, although switching to it would be a breaking change.

It might be good to make some breaking changes soon though and release a v0.3.

[ashWhiteHat]

I changed the random_mod method here.
modulo is calculated here.

[tarcieri]

That approach introduces a bias into the output distribution. For cryptographic applications, the distribution of possible outputs needs to be uniformly random, which is why it's using rejection sampling.

[Sc00bz]

P.S. That modulo can take a very long time and literally forever if used for after multiply. While also not being time constant (leaks x from x*divisor+remainder, but in the case of random x is worthless).