PRNG i GMP
Niels Möller
nisse at lysator.liu.se
Mon Apr 15 18:01:06 UTC 2019
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.
More information about the gmp-devel
mailing list