[1851] in cryptography@c2.net mail archive
testing your RNG
daemon@ATHENA.MIT.EDU (Zooko Journeyman)
Mon Nov 17 14:57:44 1997
Date: Mon, 17 Nov 1997 17:46:10 +0100 (MET)
From: Zooko Journeyman <zooko@xs4all.nl>
To: cryptography@c2.net
Hello, P'sCL:
Any suggestions on statistical methods for testing (P)RNG's?
I know Knuth has lots of relevant ideas, which I am about to
study up on, but I thought I would ask some practical
cryptographers if there are any particularly insidious broken
(P)RNG problems which can appear normal under automated
inspection, and how to improve the automated, perhaps
human-assisted inspection.
What I've got going so far is:
------- begin included pseudocode
// Check whether all possible bytes are produced within reasonable time
Bool a_boFound[256];
Int32 i32Used= 0;
for( i32=0; i32<256; i32++ ) {
a_boFound[i32]= boFALSE;
}
for( i32=0; i32Used < 256 && i32 < 5000; i32++ ) {
str = strNextBytes( 1 );
if( !a_boFound[str[0]] ) {
a_boFound[str[0]]= boTRUE;
i32Used++;
}
}
ASSERTX( i32Used == 256, "Not all bytes found" );
String strSequence = strNextBytes( 10 );
String strStream = "";
for( i32 = 0; i32 < 100; i32++ ) {
strStream += strNextBytes( 2000 );
Int32 i32Index = StringSearch::i32Index( strStream, strSequence );
ASSERTX( i32Index < 0, "Repetition found" );
strStream.vRight( 9 ); // leave this for the next run
}
------- end included pseudocode
These are your basic sanity checks.
Next I need to add some more, um, "scientific" statistical
methods, I think.
Other methods might include displaying statistical data, e.g.
distribution curve, derived from the (P)RNG next to a
statistically perfect curve and ask the human tester to look
for spikes, bumps, and wiggles. Also, just blast the data into
a bit map and ask the tester to look for patterns. (Could make
them crazy or cross-eyed if done too much... :-) )
Thanks, all!
Regards,
Zooko, Journeyman Hacker
P.S. I'm well aware that inspection of the source of the
randomness is probably a superior method for most situations,
but I suppose a combination of both source-inspection and
output-testing would be optimal here...
P.P.S. Then there's always, "XOR'ing a highly valuable ecash
coin with some of the RNG output and posting the results to
cypherpunks"...
