[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: Mok-Kong Shen <[email protected]>*Subject*: Re: PRNGs and testers.*From*: David Honig <[email protected]>*Date*: Fri, 23 Oct 1998 14:54:54 -0700*Cc*: [email protected]*In-Reply-To*: <[email protected]>*References*: <[email protected]><[email protected]>*Sender*: [email protected]

At 09:00 AM 10/23/98 +0200, Mok-Kong Shen wrote: >David Honig wrote: > >> Recall that Ueli's Universal Statistical Test >> is valid only for real sources of entropy. >> PRNGs have zero entropy asymptotically ;-) > >Sorry that I haven't yet understood. Could you explain a bit more >from the entropy point of view? In my opinion, a statistical >test does not and should not take into account how a sequence >being tested is obtained. Given is simply a sequence and no other >information and the test should give an answer. > >M. K. Shen A *sequence* isn't random; a process is. A sequence may be the result of some process, but its always a sample of a process. When you ask, "Is some process random", you *must* define "random" operationally, thus, finitely. A test for structure, such as Marsaglia's "Diehard" suite, measures various statistics (structure) of a sample and compares them to the measurements you'd get for (abstractly modelled, "real") randomness. If the particular tests you've chosen don't see some structure that's present in the sample, you'll mistakenly accept the process as "random". Diehard is nice because it includes complex stats and some Monte Carlo evaluations. Marsaglia's test was designed to find problems in PRNGs, which he was working on. Maurer suggests a way to compute the entropy of the data, taken as N-bit blocks, and computes the value you'd compute for random data. His test consumes a lot more data, and is Now, a PRNG has a finite amount of (unknown) initial internal state. This state is expanded into the output stream, which goes on forever, thus the finite initial entropy is spread infinitestimally thin. A true RNG, even an imperfect one, generates a constant amount of entropy per symbol ("bit per baud" averaged over any sufficiently large window). ----------------- An experiment Run a block cipher in a feedback mode, generating a large data file. Any good cipher will pass Diehard's tests for structure. So will a true random file. (I've posted directions for producing decent true randomness from a detuned FM radio, soundcard, and 8->1 parity-reduction filtering.) Now run Maurer's test; I've posted a version for blocksize = 16. The cipher-PRNG output will not have the entropy expected for randomness. The physical-random file will. ----------------------------- D. Honig "When horsemeat is outlawed, only outlaws will eat horsemeat" --California Voter Information Pamphlet

**Follow-Ups**:**Re: PRNGs and testers.***From:*Mok-Kong Shen <[email protected]>

**References**:**PRNGs and testers.***From:*X1 <[email protected]>

**Re: PRNGs and testers.***From:*David Honig <[email protected]>

**Re: PRNGs and testers.***From:*Mok-Kong Shen <[email protected]>

- Prev by Date:
**IP: Data Encryption and the First Amendment: Pete duPont** - Next by Date:
**Irony** - Prev by thread:
**Re: PRNGs and testers.** - Next by thread:
**Re: PRNGs and testers.** - Index(es):