## Introduction

Nowadays, random number generators are commonly used in generating cryptographic keys. As output of a poor generator consists of patterns that may lead to successful cracking of keys, the quality of the generators used must be checked very carefully.

 -click to enlarge the diagrams- Poor random number generator generates random numbers in a pattern. Sophisticated random number generator provides truly random numbers.

Statistical tests are often used to examine whether a sequence of numbers is random. The underlying assumption is that the numbers in the sequence is uniformly distributed and independent. A test uses the numbers in an experiment and checks whether the statistics collected are within reasonable ranges.

For this project, we have developed three very stringent tests of randomness, namely, the Gorilla test, the GCD test and a new version of the Birthday Spacing test. All congruential generators fail at least one of the tests, as do many simple generators, such as shift register and lagged Fibonacci. On the other hand, generators that pass the three tests pass all the tests we have tried, including the Diehard Battery of Tests, the tests in Knuth's collection and the tests recommended in FIPS PUB 140-2. The generators examined in our study include the 57 random number generators in the GNU Science Library.

## Structure of the program

`tuftests.c ` ( `tuftests.c ` ) contains the code of the three tests: gcd, gorilla and birthday spacings test. A test returns a single p-value in [0, 1). A p-value close to 1 (e.g., 0.99) indicates that the numbers are not random. On the other hand, a p-value close to 0 (e.g., 0.01) indicates that the numbers are too evenly spread. tuftests.c contains two sample random generating functions one is iuni64 and the other Kiss. You can use these generating functions for trial runs. Or you can write a C function for your random number generator and use #define IUNI yourfunctionname() to invoke your function. The execution may last half of an hour on a P3-450 PC.

The output of the program is on screen but you can redirect the output to the file.

A compiled binary version using the iuni64 random number generator for the Win32 environment is available here.

## Spectral Test

Linear congruential generators (LCGs) were proved to have a lattice structure (i.e. Random numbers fall mainly in the planes [Marsaglia 1968]). That is given a sequence of random numbers from (0,1) generated with a LCG and transformed them to a sequence of overlapping tuples with d-dimension. The tuples fall mainly inside a family of parallel, equal distanced hyperplanes which cuts the hypercube (0,1)^d. The severity of this problem can be checked by spectral test [Knuth], which measures the distance between any two nearest hyperplanes.

A package of spectral test (with source code and documentation) can be downloaded here.

## Development of Cryptographic Random Number Generators

The key generation module is the most secret component of a cryptosystem. Keys are generated using random number generators (RNGs). In an implementation of a cryptosystem, we may consider developing the RNG component separately by in-house engineers instead of by the main contractor. This document describes an easy-to-follow procedure for the development of highly secure cryptographic RNGs. A checklist for auditing a secure cryptographic RNG is also included.

## References

• Anderson, T.W. and Darling, D.A., 1952, Asymptotic theory of certain 'goodness of fit'criteria based on stochastic processes, Annals of Mathematical Statistics, 23, 193-212.
• Christiansen, H. D., 1975, Inst. Math. Stat. and Oper. Res., Univ. Denmark, (unpublished).
• Knuth, D. E., 1997, The Art of Computer Programming, Vol. 2, 3rd ed., Addison-Wesley.
• Marsaglia, J.C., 1982, Computer Studies of the Anderson-Darling statistic, Technical Report CS-82-096, Computer Science Department, Washington State University.
• Marsaglia, G., 1968, Random Numbers Fall Mainly in the Planes, Proceedings of the National Academy of Sciences of the United States of America, Volume 61, Issue 1 (Sep. 15, 1968), 25-28.
• Marsaglia, G., Zaman, A. and Tsang, W.W., 1990, Toward a universal random number generator, Letters in Statistics and Probability.
• Marsaglia, G. and Zaman, A., 1993, Monkey tests for random number generators, Computers and Mathematics with Applications 26, 9, 1-10.
• Marsaglia, G., 1995, Diehard battery of tests of randomness, The Marsaglia random number CDROM, Department of Statistics, Florida State University.
• Marsaglia, J.C. and Marsaglia, G., 2000, The Anderson-Darling-Savage goddess-of-fit test (Draft).
• G. Marsaglia and W.W. Tsang, "Some difficult-to-pass tests of randomness", Journal of Statistical Software, Vol. 7, Issue 03, 2002.
• Maurer, U., 1992, A universal statistical test for random bit generators, Journal of cryptology 5, No. 2, 89-105.
• W.W. Tsang, L.C.K. Hui, K.P. Chow and C.F. Chong, "Tuning the collision test for stringency" (Draft).