PRNG i GMP

[Niels Möller]

Pedro Gimeno <gmpdevel at formauri.es> writes:

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

Interesting. To get around this, one could perhaps use

  AES_encrypt(cnt, key) + cnt

which no longer is a permutation (viewed as a function of cnt).

If P(x) is a random-looking permutation, then P(x) + x is a
random-looking function. Chacha also uses this same trick, to make its
kind-of hash function hard to invert.

If I'm not mistaken, so does the compression function of sha1 and
similar hash functions, compression is

   state <-- state + P(data, state)

where the function state --> P(data, state) in itself is a
random-looking permutation, easily invertible for any fixed data input.

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

The key is kind-of fixed, so it should be the cipher's *block size* that
matters, not the key size, right?

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

You'd have to derive the subkeys for each call, which I think would add
significant overhead. Even if I think there are some special
instructions to help. My implementation doesn't use anything special for
key setup, since it's usually not that performance critical.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.