[pycrypto] Test code - Random
Sergey Chernov
sergey.chernov at thrift.ru
Fri Nov 7 20:29:02 CST 2008
I'm sorry if I'm telling something stupid, since I was not working
with RNGs analysis for about 18 years, but from what I still remember.
There was a test (in fact, series of tests) that surprisingly failed
lot of these old times RNGs. It's sort of N-dimensial bins histogram.
The simplest was easy. Let's talk pairs of N-bit randoms as (x,y)
coordinates in a finite rectangle (using N or mod) and see whether
they would tend to cluster. I've seen in my own eyes that one RNG that
was supposed to be sufficient, was constantly generating a few small
triangles leaving the rest clear :)
So, the general test we were performed was kind of following. Let's
take N-dimensional cube and fill it with RNG series of size L, then
check how even it fills the cube. Simplest case is to divide it to
equal clusters (bins), so there should be, say, L/1000 clusters least,
calculate how many pseudo-random points hit each bin and see how plain
is this histogram. It should not vary too much if the RNG is ok and L
is big. We can, say, check the standard deviation. Better to check
several bins size, using various random primes as factors for bins
sizes. Then increment N and check it again.
I've read in late 80s that such test failed on some very famous RDBMS
system of these old good times (as I remember, all dots filed 64 plans
in the 3(?)D cube or so).
For sure there must be a plenty of better tests by now, but I'm not
familiar with them.
The probability you mentioned should be, as for me, 1e-256. One famous
mathematician, namely Kolmogorov, once said, that there is no such
things as 1e-100 probability, there is only the impossibility :)
Sergey Chernov
sergey.chernov at thrift.ru
08.11.2008, в 1:12, Dwayne C. Litzenberger написал(а):
> I'm not sure what your proposed TestNotAlwaysEqual test offers that
> SimpleTest does. Presumably the purpose of this new test is to
> avoid the case where a correctly-functioning RNG returns two
> identical 128-bit numbers in a row. While that may be possible, I'm
> really not concerned about it, since according to my calculations*,
> the probability that SimpleTest fails is 2**-128.
> TestNotAlwaysEqual adds another test that can fail in the same way,
> but with a probability of 2**-1280. I don't see why that would be
> necessary.
>
> (* Someone please correct me if I'm wrong, since I'm still not very
> good at reasoning with probability.)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2193 bytes
Desc: not available
Url : http://lists.dlitz.net/pipermail/pycrypto/attachments/20081108/35822f32/attachment-0001.bin
More information about the pycrypto
mailing list