[Cryptography] Random numbers for Diffie-Hellman

[Pierre Abbat]

On Monday, December 16, 2024 8:21:55 PM EST Ray Dillinger wrote:
> 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).

We're talking about Diffie-Hellman; K is a prime hundreds or thousands of bits 
long and doesn't fit in a computer register.

> 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.

How much bigger is C than K? What happens if R before this is in the 
remainder, i.e. R÷K == C÷K? What do you do with R÷K?

Pierre

-- 
The Black Garden on the Mountain is not on the Black Mountain.