[1893] in cryptography@c2.net mail archive
Re: summary Re: testing your RNG
daemon@ATHENA.MIT.EDU (Nick Szabo)
Wed Nov 26 11:10:22 1997
From: Nick Szabo <szabo@best.com>
In-Reply-To: <199711242322.AAA20504@xs2.xs4all.nl> from Zooko Journeyman at "Nov 25, 97 00:22:35 am"
To: zooko@xs4all.nl (Zooko Journeyman)
Date: Tue, 25 Nov 1997 11:39:57 -0800 (PST)
Cc: cryptography@c2.net
> Nick Szabo mentioned that it was impossible.
Summary is the art of lossy compression. :-).
Specifically, statistical tests of a PRNG's ouptut are necessarily
incomplete: they can find certain kinds of regularities, but not
others. The general problem of proving that a string is random is
uncomputable.
Because the most general statistical tests are brute-force searches,
a powerful opponent can test for regularities that the designer has
not tested for, given access to sufficient PRNG output. Statistical
tests of output can catch some bad designs, but they are
not sufficient to demonstrate the quality of a cryptographic PRNG.
Nick Szabo
szabo@best.com
http://www.best.com/~szabo/
