[Cryptography] Random numbers for Diffie-Hellman

[Pierre Abbat]

On Friday, November 29, 2024 7:54:45 AM EST Viktor Dukhovni wrote:
> AFAIK, this sort of thing should be OK for (EC)DH, but is definitely NOT
> OK for ECDSA (Schnorr signing in general), where non-uniformity in the
> nonce generation is problematic.

So how would you generate a uniform random number from an arbitrary large 
range with minimum waste? Here's my idea:

Set up random generators in [0,2), [0,3), [0,5), and [0,7). The random bit 
generator is trivial because the computer's random number generator returns 
bytes. The trit generator is like this:

Pick a random number in [0,0x8000000), which is [0,310488088_9). If it's in
* [0,300000000_9)=[0,0x7b285c3), you get 17 trits.
* [300000000_9,310000000_9)=[0x7b285c3,0x7fb813c), you get 14 trits.
* [310000000_9,310300000_9)=[0x7fb813c,0x7fe3537), you get 11 trits.
* [310300000_9,310400000_9)=[0x7fe3537,0x7ff1be0), you get 10 trits.
* [310400000_9,310460000_9)=[0x7ff1be0,0x7ffb5a6), you get 9 trits and 1 bit.
* [310460000_9,310480000_9)=[0x7ffb5a6,0x7ffe8e8), you get 8 trits and 1 bit.
* [310480000_9,310486000_9)=[0x7ffb5a6,0x7fff9fe), you get 7 trits and 1 bit.
* [310486000_9,310488000_9)=[0x7fff9fe,0x7ffffb0), you get 6 trits and 1 bit.
* [310488000_9,310488060_9)=[0x7ffffb0,0x7ffffe6), you get 3 trits and 1 bit.
* [310488060_9,310488080_9)=[0x7ffffe6,0x7fffff8), you get 2 trits and 1 bit.
* [310488080_9,310488086_9)=[0x7fffff8,0x7fffffe), you get 1 trits and 1 bit.
* [310488086_9,310488088_9)=[0x7fffffe,0x8000000), you get 1 bit.
The efficiency of this is 99.0678%, so the wastage is 0.9322%.

Similar generators for 5 and 7 can be constructed with 2^72>5^31 and 
2^31>7^11. They will both at times produce extra trits and bits.

Next, find the smallest 7-smooth number that's at least the size of the range, 
and generate a number less than the 7-smooth number. If it's at least the size 
of the range, discard it and try again. If the size of the range is big enough 
(don't try it with 11), you will hardly ever have to discard a number.

Pierre
-- 
.i toljundi do .ibabo mi'afra tu'a do
.ibabo damba do .ibabo do jinga
.icu'u la ma'atman.