[Cryptography] Random numbers for Diffie-Hellman

[Ray Dillinger]

On 11/27/24 22:57, Pierre Abbat wrote:
> How would you pick random numbers from 1 to k, where k is not a power of 2, to
> minimize wastage of random bits?

You will need:

Register R containing bits from a random source and Register C the same 
size as R which records the number of random options that can be 
discriminated among by the bits in R.  Both R and C should be big enough 
to record the size of the largest set you want to choose between (eg, if 
you want to choose among 65536 options, R and C should be at least 16 
bits).


Start by initializing R with one "random" bit and initializing C to the 
value 2.


Whenever you append a new randombit 'r' from the random source, do

R = R*2 + r and C = C*2.


Whenever you make a choice between K options,

R = R mod K and C = C div K.


After initializing once, you can use R and C to generate as many 
"random" choices as needed in any set of ranges, whenever enough bits 
have been appended that R exceeds the range currently being chosen.  The 
final wastage is equal to one less than the logarithm mod 2 of the final 
value of C.   If the minimum number of bits has been appended, wastage 
is either one or zero no matter how many range choices have been made or 
what size the ranges were.

Bear


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20241216/762e46de/attachment.htm>