[pycrypto] Test code - Random
Sam Phippen
samphippen at googlemail.com
Sat Nov 8 05:05:41 CST 2008
The first test I wrote may be a minor improvement on the simple test, as it
merely ensures that the value returned by the rng is not always the same.
(it is plausible that an rng might return the same data twice).
For the second test I chose a large sample so that the average of all the
data would be roughly 128, I chose the large variation sort of out of the
air, although the average of a large sample should (statistically speaking)
be very close to 128. After running about 10 tests the values were never
outside of 128 +/- 2.
I might try plotting a graph of (x,y) byte pairs and try calculating
correlation co-efficients.
2008/11/8 Sergey Chernov <sergey.chernov at thrift.ru>
> 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.)
>>
>
>
> _______________________________________________
> pycrypto mailing list
> pycrypto at lists.dlitz.net
> http://lists.dlitz.net/cgi-bin/mailman/listinfo/pycrypto
>
>
--
Sam Phippen
Please avoid sending me Word or PowerPoint attachments.
See http://www.gnu.org/philosophy/no-word-attachments.html
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.dlitz.net/pipermail/pycrypto/attachments/20081108/98650707/attachment.htm
More information about the pycrypto
mailing list