Path: illuminati.io.com!uunet!news.mathworks.com!yeshua.marcam.com!charnel.
+     ecst.csuchico.edu!psgrain!ticsa.com!cstatd.cstat.co.za!not-for-mail
From: cstevens@iaccess.za (Charles Stevens)
Newsgroups: sci.crypt

Subject: Randomness Testing Code
Date: 18 Oct 1994 16:07:37 +0200
Organization: Internet Access public-access service
Lines: 55
Message-ID: 
NNTP-Posting-Host: 192.96.87.12

I have produced some programs to analyise the "randomness" properties
of a binary sequence.  The programs measure the deviation/bias from a
binary symmetric sequence. The chi-square probability function is
computed so no tables need be consulted. The z-score results are also
produced.

The tests are:
1.  Frequency, serial, runs and poker test.
    The runs test measures Golomb's postulate R2, the poker test is
    limited to 8 bits.
    Filenames: rndtest.cpp & gamma.cpp

2.  Maurer's Universal Bit test (adapted from post of Mike Scott)
    Filename : mtest.cpp

3.  Binary derivative test
    Filename : binderv.cpp

4.  Bob Jenkins random number generator for testing
    Filename : rndgen2.c

5.  Peter Boucher's chi-square frequency analysis, adapted for a PC
    Filename : chisq.cpp

The files can be ftp'd or can be accessed by WWW from directory
/pub/unisa-software at osprey.unisa.ac.za

The file alltests.zip is the above source files zipped by PKZIP 2.04g.
There is also a version gzipped and tarred, alltests.tar
Although the extensions are .cpp, the source is C compilible by BC 3.1

The tests are based on the book Cipher Sytems by H.Beker & F.Piper;
Crypto 90 article Using Binary Derivatives as an enhancement to DES by
J.Carrol & L.Robbins; A Universal Statistical Test for Random Bit
Generators by U.Maurer and the numerous postings on the subject on
sci.crypt.

I would still like to try to implement the complexity test.
Any comments will be appreciated (good or bad). I do have a report on
the results of the tests but it is not yet complete.
To briefly sum the result of testing up, the results show:
1. If the absolute difference between number of ones and zeros divided by
   the number of bits * 100 is grater then 0.4%, the sequence is biased.
2. Number of runs > 19 bits, indicate a bias.
3. Maurer's universal test works well and picks up all the biases that the
   standard tests show.
4. The binary derivative test was inconclusive.

Unpredicatability Paradox: If a deterministic function is unpredicatable,
then it is difficult to prove anything about it, in particular, to prove
that it is unpredictable:  J.C. Lagarias.

----------------------------------------------------------------------
Charles Stevens      c.stevens@ieee.org -> cstevens@iaccess.za
+2711 468-2311       Box 782094, Sandton, South Africa