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