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