[Cryptography] Random numbers for Diffie-Hellman

[Ray Dillinger]

Ergh.  I misspoke.  Corrected version below.

Nothing like seeing what you actually sent to others to trigger your 
"even though I wrote it, that's wrong" reflex.

This is just an entropy accumulator to prevent wastage of bit generator 
output.   Using the accumulator wastes at most one bit, no matter how 
many choices you use the accumulator to make.

WARNING:  It's for use when your bit generator is highly trusted but you 
want to get absolutely the smallest number of bits from it that will 
serve your purposes (typically because it exhausts a limited resource).  
Note that if you use such a non-discarding accumulator, an adversary who 
has knowledge of what size fields you chose from and in what order 
(typical for open source code) will be able to reconstruct the entire 
stream 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, C must be greater than K.

Choice = R mod K.  K = R div K. C = C div K.

Where mod and div are the integer remainder and quotient functions 
respectively.


Bear