[Cryptography] Random numbers for Diffie-Hellman

[Ray Dillinger]

On 12/17/24 02:52, Jerry Leichter wrote:
>
>> …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….
>>
> Something is missing here.  Probably multiple something’s.
>
You are right.  I responded to my own error above, but to clarify a 
little more, I got the choice step wrong.

It's the choice, not the new value of R, that's R mod K.

The new value of R is R div K, and the new value of C is C div K.

And obviously the choice must be taken before rather than after 
adjusting the value of R.

A classic instance of hitting "send" before actually checking my 
notebooks.  Sorry about that.


There's a generalization of the entropy accumulator that allows adding 
uniform choices of any size instead of just adding bits. If you have a 
generator that generates "random" outputs uniformly distributed from 0 
to N, you would just multiply R and C by N, rather than 2, before adding 
it to the accumulator.  If you use the generalized form you need to be 
sure of the uniformity of the distribution first.

The entropy accumulator is a useful construction in that it limits the 
"waste" of generated bits under a hard constant, no matter how many 
uniformly-distributed random choices you need to make. But it's rarely 
justified because most systems have pseudorandom bit generators that are 
nearly free to operate.

Bear

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