PRNGs and testers.

Hi,

A few questions on Pseudo Random Number Generators...

1. Which are the best software PRNG's available today? 

2. Are there any software implementations to test the randomness of a
   PRNG ? I've looked at Diehard - is there anything else?

Thanks,
R Sriram.

At 11:30 AM 10/21/98 +0100, Mok-Kong Shen wrote:
>
>Not answerable.  (Reason: substitute car, HIFI, medical doctor, etc. 
>for 'software PRNG').

Nice metaphors.

>> 2. Are there any software implementations to test the randomness of a
>>    PRNG ? I've looked at Diehard - is there anything else?
>
>There are tests that one can implement with reasonable effort.
>A test relevant in cryptology is Maurer's test.

Recall that Ueli's Universal Statistical Test
is valid only for real sources of entropy.
PRNGs have zero entropy asymptotically ;-)

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

David Honig wrote:
> 

> 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.
>

I don't see you have answered my question of whether a test has to
take into consideration how a sequence of numbers has been obtained.
Also what you wrote above seems to be less than clear. Do you suggest
that Mauerer's test is extremely good in deciding whether a sequence 
is TRULY random? (I think Maurer's test is good for investigating 
PRNG squences but maybe not used as a criterion between pseudo-
randomness and true randomness (whatever that may be defined)). 
What if some PRNGs pass Maurer's test?

M. K. Shen

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

At 09:47 AM 10/26/98 +0100, Mok-Kong Shen wrote:
>David Honig wrote:
>> 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.
>>
>
>I don't see you have answered my question of whether a test has to
>take into consideration how a sequence of numbers has been obtained.

A test measures only what it measures.

You never know if this is sufficient.

A sample of a non-random process may pass your tests
if they don't measure the right thing.

>Also what you wrote above seems to be less than clear. Do you suggest
>that Mauerer's test is extremely good in deciding whether a sequence 
>is TRULY random? (I think Maurer's test is good for investigating 

I only find it interesting that the test can distinguish between
the two data samples.  To the eye, or ear, or Diehard, they appear the same.

>What if some PRNGs pass Maurer's test?
>
>M. K. Shen

I'd find it surprising if any did, given what I described.

DH

David Honig wrote:
> 
> At 09:47 AM 10/26/98 +0100, Mok-Kong Shen wrote:

> >What if some PRNGs pass Maurer's test?

> I'd find it surprising if any did, given what I described.

I believe that there are quite a number. If I am allowed to cite 
my own stuff, a PRNG of my design did pass Maurer's test. See

     http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper1
and
     http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper9

M. K. Shen

X1 wrote:
> 
> Hi,
> 
> A few questions on Pseudo Random Number Generators...
> 
> 1. Which are the best software PRNG's available today?

Not answerable.  (Reason: substitute car, HIFI, medical doctor, etc. 
for 'software PRNG').

> 
> 2. Are there any software implementations to test the randomness of a
>    PRNG ? I've looked at Diehard - is there anything else?

There are tests that one can implement with reasonable effort.
A test relevant in cryptology is Maurer's test. See Menezes et al.,
Handbook of Applied Cryptography.

M. K. Shen