[Cryptography] Random numbers for Diffie-Hellman

[Patrick Chkoreff]

On 12/4/24 1:50 AM, Pierre Abbat wrote:
> 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.


1. General case

In general you wish to generate integers X uniformly distributed on the 
range 0 .. k-1.

You choose some number of bits n that you will use.  Compute the bound B 
= k * trunc((2^n) / k).

You roll n bits to get a number W in the range 0 .. 2^n-1.  If W is less 
than the bound B, compute X = (W mod k) and that's your result. 
Otherwise reject W and try again with another n bits.

The probability of a rejection is (2^n - B) / 2^n.  You can "simplify" 
that to 1 - B/2^n, but the original form is easier to deal with because 
(2^n - B) is just some fairly small number.


2. Specific case k = 3

This is the smallest non-trivial case, generating numbers in the set 
{0,1,2}.

2.1 Using 2 bits

The bound B = 3.  Probability of rejection is 1/4.

2.2 Using 3 bits

The bound B = 6.  Probability of rejection is 1/4.  No improvement there.

2.3 Using 4 bits

The bound B = 15.  Probability of rejection is 1/16.  That's an improvement.

2.4 Using 8 bits

The bound B = 255.  Probability of rejection is 1/256.  Another improvement.


3. Any way to "salvage" rejections?

I thought about ways to "make use" of rejections, so those bits aren't 
wasted.  For example in the case of 2 bits above, instead of discarding 
a "11" I might just rotate a counter through 0, 1, 2.  That way if the 
random number generator is broken and generates all 1s, you still have a 
uniformly distributed sequence instead of just hanging forever.

I doubt that's a good idea because if you get "11" interspersed 
normally, it might give a slight bias to 0, 1, or 2.  Or will it?  If 
I'm cycling a counter, maybe not.  It might be indistinguishable from 
simply getting the "00", "01", or "10" at those same points in the sequence.

It still sounds a little dubious, but I haven't thought of a precise 
argument against it yet.


-- Patrick