Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:35 ADT
Enzo Michelangeli (em@who.net)
Sat, 18 Jul 1998 09:09:50 +0800
-----Original Message-----
From: Mike Rosing <eresrch@msn.fullfeed.com>
Date: Saturday, July 18, 1998 2:54 AM
>On 17 Jul 1998, Cicero wrote:
>
>> Statistical tests can demonstrate failure, but not success. Any good
>> PRNG will pass all such tests, with a seed of 0, and you know there is
>> no entropy there. If Murry has a test that will distinguish a RNG
>> from a PRNG I would be surprised.
>
>That shouldn't be too hard really. A real random bit generator has to
>fail when the frequency of data collection is too high, you can run a
>pseudo generator on faster machines and get good stats out. I'd also
>expect a RNG to fail stats tests more often, a PRNG should be pure white.
"Pure whiteness" cannot be tested in a finite time, as this would require to
compute the autocorrelation over an infinite interval. Over finite intervals
which are not multiple of the period, all PRNG will show some discrepancy
from constant autocorrelation (just like all RNG, no matter how good, over
any interval).
Besides, spectral tests (as any test based on estimates of the parameters of
n-th order distributions) only spot a small subset of dependencies of each
sample on the others, or on constant values. Most non-linear dependencies
will escape such tests.
[...]
>> I can run specific test vectors to gain some confidence that my PRNG
>> is the one that I think it is, but no tests that you can run will
>> distinguish a correct RNG from a PRNG, or distinguish one RNG from
>> another (unless one is broken), or give you confidence that your RNG
>> is the one that you thought it was. If I switch your chip with one
>> that produces 3DES OFB output, you can never find out without
>> inspecting the hardware. The output will not differ from what you
>> would expect.
>
>That's part of my experiment. It will be very interesting to see what
>the differences are. I suspect they are subtle, but visible. Real
>measurement is better than conjecture :-)
So, you are in a _double_ state of sin: you think that algorithms can do
better than real random generator! :-)
Actually, the entropy of a source cannot be "measured": you can only get
(probabilistic!) upper bounds on it. This, often, also requires some
assumptions on the generator. A simple example: no statistical test will
ever tell you that "932384626433832" belongs to the (perfectly
deterministic) decimal expansion of pi, as it actually does. If your suite
had an ad-hoc test for "pi-ness detection" (supposing that it's feasible),
it would still miss the sequences of digit of "e", or any other in the
infinity of computable Borel numbers. Measurement is useful to ring alarms,
but is no replacement for thoughtful design and (when available)
mathematical proof.
Besides, a RNG can internally include a PRNG as a "whitener", making it
impossible for a RNG to be statistically worse than a PRNG.
Enzo
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:35 ADT