On Sunday, April 21, 2002, at 09:53 PM, Joseph Ashwood wrote:
> ----- Original Message -----
> From: <[EMAIL PROTECTED]>
> To: "Tim May" <[EMAIL PROTECTED]>; "Eugen Leitl" <[EMAIL PROTECTED]>
> Cc: <[EMAIL PROTECTED]>
> Sent: Sunday, April 21, 2002 1:33 PM
> Subject: Re: Two ideas for random number generation
>
>
>> Why would one want to implement a PRNG in silicon, when one can
>> easily implement a real RNG in silicon?
>
> Because with a pRNG we can sometimes prove very important things, while
> with
> a RNG we can prove very little (we can't even prove that entropy
> actually
> exists, let alone that we can collect it).
Not to be pedantic, but we cannot _really_ prove that entropy is being
collected from a PRNG, either.
In fact, there really _is_ no entropy from a PRNG: the bits are
deterministic from the PRNG, meaning they actually have no uncertainty,
no entropy. To the person who selected the program and the seed, _he_
certainly sees no randomness, no entropy. Relativity. Usual
Kolmogorov/Chaitin stuff here.
Operationally, when faced with a purported source of "random numbers,"
naive calculations of entropy are often made. This is true for the
output of a Johnson noise diode, or a radioactive decay circuit, or the
RAND Corporation's Table of One Million Random Digits.
But all of the calculated ("measured") entropy numbers collapse to zero
or some small number if and when someone figures out that he knows how
to predict the nth digit.
The usual arguments I hear about why PRNGs are better is that they a)
can give reproducible sequences for testing software (often much more
useful than physically-derived numbers would be, for obvious statistical
reasons), b) in some sense there is more assurance that a BBS generator,
for example, has not been manipulated.
If I wanted a good PGRNG (Pretty Good RNG) I'd favor one that mixes a
physical source, mixes entropy extracted from user actions (keystroke
intervals, mouse movements, over a lot of days), and distills it all
some more with a BBS.
(The meta-solution for good numbers is then to mix different kinds of
RNGs, to take a BBS output and XOR it with a Lava Lamp sequence, to seed
a PRNG with mouse strokes, etc. As with ciphers, composition of many
functors tends to help, unless one of the stages has bad properties,
e.g., avalanche conditions. (Blowfish (3DES (Bassomatic (foo))) will be
at least as strong as (Blowfish (foo)), all other things being equal.)
--Tim May
"You don't expect governments to obey the law because of some higher
moral development. You expect them to obey the law because they know
that if they don't, those who aren't shot will be hanged." - -Michael
Shirley
