True Random Number Generators

[ultrafilter]

*Originally posted by micco *
**

*Originally posted by ultrafilter *
**What exactly are these statistical tests of randomness? I’ve always wondered that. **

Statistical tests like Chi-square and Kolmogorov-Smirnov can be used to get measures of randomness. Knuth’s second volume, The Art of Computer Programming, Seminumerical Algorithms has a whole chapter on random number generation and testing, so I’ll defer to that rather than citing a bunch of math. It’s pretty much the bible for algorithms, so you should be able to find it in any good library. **

I’ll check that out.

[micco]

*Originally posted by Chas.E *
**

*Originally posted by micco *
To quote Bruce Schneier in Applied Cryptography, a pseudo-random sequence is one that “looks random”. It is non-periodic over the length of series needed and it passes statistical tests of randomness, it is unpredictable, and it cannot be reliably reproduced even with the same algorithm and input. He refers to more rigorous mathematical definitions, but this is the gist.

I think you missed something there. The way it was taught to me, the whole point of pseudorandom algorithms is that you can supply the same seed and generate the exact same sequence of numbers. Computers are deterministic, given the same inputs to the same algorithms, they will arrive at the same results every time. This is essential for debugging, and also the weakness of pseudorandomness. **

You’re right, I did miss something. Schneier lists three properties of randomness:

1. It looks random. This means it passes all the statistical test of randomness that we can find.
2. It is unpredictable. It must be computationally infeasible to predict what the next random bit will be, given complete knowledge of the algorithm or hardware generating the sequence and all of the previous bits in the stream.
3. It cannot be reliably reproduced. If you run the sequence generator twice with the exact same input (at lease as exact as humanly possible), you will get two completely unrelated random sequences.

Pseudo-random only has to meet #1. Cryptographically secure pseudo-random has to meet #1 and 2. Truly random has to meet #3.

I apologize for incorrectly summarizing.