Path: illuminati.io.com!uunet!spool.mu.edu!bloom-beacon.mit.edu!pad-thai.aktis.c
om!la-jiao.aktis.com!not-for-mail
From: don@cam.ov.com (Donald T. Davis)
Newsgroups: sci.crypt
Subject: Re: Random Number Analysis Code.
Date: 14 May 1994 10:29:51 -0400
Organization: OpenVision Technologies, Inc.
Lines: 32
Message-ID: <2r2n8v$45j@la-jiao.aktis.com>
References: <1994May11.211423.13674@ns.network.com> <16FB51441FS86.C445585@mizzo
u1.missouri.edu>
NNTP-Posting-Host: la-jiao.aktis.com
>hughes@network.com (James P. Hughes) writes:
>>
>>I am looking to find code for analyzing a true random number stream.
>>
john kelsey responded:
>
> Maurer wrote an article in the procedings of either Eurocrypt 90 or
>Eurocrypt 91 that outlined an algorithm to analyse the statistics of a
>random bit stream.
the citation is: ueli maurer, "a universal statistical test for
random bit generators," crypto '90 conf. proc., springer-verlag
lecture notes in computer science #537, 1991. pp. 408-420.
the paper is very interesting, and pretty easy and clear if you're
familiar with information entropy. essentially, maurer points out
that in calculating H = -1 * sum(p*log2p), you can replace p, a
bitstring's probability of appearance, with the interarrival time
between repetitions of the bitstring. this works because if a bit
string has probability .001 of appearing, then on average, 1000
other bitstrings will appear between recurrences, and except for
the sign bit, the logarithms are the same.
the advantage of this approach is that it's somewhat more sensitive
to long-term dependencies, so that you can get a slightly better
entropy estimate without increasing the lengths of the bitstrings
you're assaying. maurer's paper includes some pseudocode and a
formal calculation of the measure's expected variance. warning: my
summary is not complete, because i've left some constants and other
stuff out, that you'll need if you want to do the calculation. read
maurer's paper to get the real scoop.
-don davis