PRNG i GMP

[Pedro Gimeno]

Torbjörn Granlund wrote on 15/04/2019 13.55:
> Since long, I have intended to implement AES-based PRNGs in GMP.  The
> idea being that if AES is a good encryption algorithm, the sequence
> AES_encrypt(cnt,key) for cnt=0,1,... will be simply great.  :-)

It will be OK, for a relatively low number of draws. The problem of this approach is that every N-bit number you draw won't repeat again until the cycle starts again. As you keep drawing numbers, the bias will become more apparent, because in a long enough purely random sequence you do expect some duplicates.

"Relatively low" here means probably around 2^(bitlength/2) draws, i.e. in the range where the birthday paradox starts to be detectable. That's likely to be the reason behind re-keying in NIST's recommendations.

It should not be a problem for AES256. It's kinda unusual to need something around 2^136 random bits, to say the least. For AES128, it should be mostly fine, but it might introduce a slight bias in some applications. For any 64-bit cipher, this method would clearly be defective without re-keying.

Alternatively, instead of AES_seed(ctr++), I don't know how viable it is to use AES_ctr++(seed). I presume that the speed would be drastically reduced, but I haven't looked into hardware AES. Several hashes including MD5 and SHA-1 are cryptographic encryption functions which use the input data as key, and a constant IV as plaintext, instead of the opposite.