PRNGs and testers.
Hi, A few questions on Pseudo Random Number Generators... 1. Which are the best software PRNG's available today? 2. Are there any software implementations to test the randomness of a PRNG ? I've looked at Diehard - is there anything else? Thanks, R Sriram.
David Honig wrote:
At 09:47 AM 10/26/98 +0100, Mok-Kong Shen wrote:
What if some PRNGs pass Maurer's test?
I'd find it surprising if any did, given what I described.
I believe that there are quite a number. If I am allowed to cite my own stuff, a PRNG of my design did pass Maurer's test. See http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper1 and http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper9 M. K. Shen
X1 wrote:
Hi,
A few questions on Pseudo Random Number Generators...
1. Which are the best software PRNG's available today?
Not answerable. (Reason: substitute car, HIFI, medical doctor, etc. for 'software PRNG').
2. Are there any software implementations to test the randomness of a PRNG ? I've looked at Diehard - is there anything else?
There are tests that one can implement with reasonable effort. A test relevant in cryptology is Maurer's test. See Menezes et al., Handbook of Applied Cryptography. M. K. Shen
At 11:30 AM 10/21/98 +0100, Mok-Kong Shen wrote:
Not answerable. (Reason: substitute car, HIFI, medical doctor, etc. for 'software PRNG').
Nice metaphors.
2. Are there any software implementations to test the randomness of a PRNG ? I've looked at Diehard - is there anything else?
There are tests that one can implement with reasonable effort. A test relevant in cryptology is Maurer's test.
Recall that Ueli's Universal Statistical Test is valid only for real sources of entropy. PRNGs have zero entropy asymptotically ;-)
David Honig wrote:
Recall that Ueli's Universal Statistical Test is valid only for real sources of entropy. PRNGs have zero entropy asymptotically ;-)
Sorry that I haven't yet understood. Could you explain a bit more from the entropy point of view? In my opinion, a statistical test does not and should not take into account how a sequence being tested is obtained. Given is simply a sequence and no other information and the test should give an answer. M. K. Shen
At 09:00 AM 10/23/98 +0200, Mok-Kong Shen wrote:
David Honig wrote:
Recall that Ueli's Universal Statistical Test is valid only for real sources of entropy. PRNGs have zero entropy asymptotically ;-)
Sorry that I haven't yet understood. Could you explain a bit more from the entropy point of view? In my opinion, a statistical test does not and should not take into account how a sequence being tested is obtained. Given is simply a sequence and no other information and the test should give an answer.
M. K. Shen
A *sequence* isn't random; a process is. A sequence may be the result of some process, but its always a sample of a process. When you ask, "Is some process random", you *must* define "random" operationally, thus, finitely. A test for structure, such as Marsaglia's "Diehard" suite, measures various statistics (structure) of a sample and compares them to the measurements you'd get for (abstractly modelled, "real") randomness. If the particular tests you've chosen don't see some structure that's present in the sample, you'll mistakenly accept the process as "random". Diehard is nice because it includes complex stats and some Monte Carlo evaluations. Marsaglia's test was designed to find problems in PRNGs, which he was working on. Maurer suggests a way to compute the entropy of the data, taken as N-bit blocks, and computes the value you'd compute for random data. His test consumes a lot more data, and is Now, a PRNG has a finite amount of (unknown) initial internal state. This state is expanded into the output stream, which goes on forever, thus the finite initial entropy is spread infinitestimally thin. A true RNG, even an imperfect one, generates a constant amount of entropy per symbol ("bit per baud" averaged over any sufficiently large window). ----------------- An experiment Run a block cipher in a feedback mode, generating a large data file. Any good cipher will pass Diehard's tests for structure. So will a true random file. (I've posted directions for producing decent true randomness from a detuned FM radio, soundcard, and 8->1 parity-reduction filtering.) Now run Maurer's test; I've posted a version for blocksize = 16. The cipher-PRNG output will not have the entropy expected for randomness. The physical-random file will. ----------------------------- D. Honig "When horsemeat is outlawed, only outlaws will eat horsemeat" --California Voter Information Pamphlet
David Honig wrote:
An experiment
Run a block cipher in a feedback mode, generating a large data file. Any good cipher will pass Diehard's tests for structure. So will a true random file.
(I've posted directions for producing decent true randomness from a detuned FM radio, soundcard, and 8->1 parity-reduction filtering.)
Now run Maurer's test; I've posted a version for blocksize = 16. The cipher-PRNG output will not have the entropy expected for randomness. The physical-random file will.
I don't see you have answered my question of whether a test has to take into consideration how a sequence of numbers has been obtained. Also what you wrote above seems to be less than clear. Do you suggest that Mauerer's test is extremely good in deciding whether a sequence is TRULY random? (I think Maurer's test is good for investigating PRNG squences but maybe not used as a criterion between pseudo- randomness and true randomness (whatever that may be defined)). What if some PRNGs pass Maurer's test? M. K. Shen
At 09:47 AM 10/26/98 +0100, Mok-Kong Shen wrote:
David Honig wrote:
Now run Maurer's test; I've posted a version for blocksize = 16. The cipher-PRNG output will not have the entropy expected for randomness. The physical-random file will.
I don't see you have answered my question of whether a test has to take into consideration how a sequence of numbers has been obtained.
A test measures only what it measures. You never know if this is sufficient. A sample of a non-random process may pass your tests if they don't measure the right thing.
Also what you wrote above seems to be less than clear. Do you suggest that Mauerer's test is extremely good in deciding whether a sequence is TRULY random? (I think Maurer's test is good for investigating
I only find it interesting that the test can distinguish between the two data samples. To the eye, or ear, or Diehard, they appear the same.
What if some PRNGs pass Maurer's test?
M. K. Shen
I'd find it surprising if any did, given what I described. DH
participants (3)
-
David Honig -
Mok-Kong Shen -
X1