[Cryptography] Random numbers for Diffie-Hellman

[Christian Huitema]

On 12/5/2024 8:36 AM, Patrick Chkoreff wrote:

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

Wikipedia points to this entry in the Github Swift Language depot: "An 
optimal algorithm for bounded random integers", 
https://github.com/swiftlang/swift/pull/39143. The algorithm is 
described in the comments in the code.

-- Christian Huitema