[Cryptography] Random numbers for Diffie-Hellman

[Pierre Abbat]

On Monday, December 2, 2024 7:42:18 PM EST Jerry Leichter wrote:
> There's quite a bit of published work on this going back years.  I don't
> have any references off-hand, but it shouldn't be hard to find.
> 
> Here's an observation to start with:  Assume you can generate uniform random
> n-bit values.  You want values uniformally distributed from 0 to (2^n)-k. 
> When k is small, your best bet is to just generate a random value.  If it
> happens to be more than (2^n)-k, discard it and generate another. 
> Obviously, the larger k is, the more values you have to discard.  So as k
> gets large you want to use a different strategy.  There's one that's
> obvious once you think of it ... but at the moment it won't come back to
> me!  But you play some games between at least two strategies.
> 
> You seem to be heading in somewhat the same direction, but I don't follow
> all the details of what you propose. -- Jerry

Assume you can generate uniform random values in the range [0,n), where n is 
7-smooth. You can then generate uniform random values in the range [0,n-k) by 
discarding anything that's at least n-k. Since k/n→0 as n-k→∞, the fraction 
you have to waste because the number was too big is vanishingly small when n-k 
is huge.

What I outlined for 5 and 7 and detailed for 3 is the method of generating 
uniform numbers in [0,n) where n is a power of a small prime, given uniform 
bits. Given uniform numbers in [0,2^8), [0,3^17), [0,5^31), and [0,7^11), you 
can generate uniform numbers in [0,n), where n is any 7-smooth number.

Pierre
-- 
li ze te'a ci vu'u ci bi'e te'a mu du
li ci su'i ze te'a mu bi'e vu'u ci