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.
Back to toptuftests.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.
The program is released under GNU General Public License Please follow this link to download the package.
A compiled binary version using the iuni64 random number generator for the Win32 environment is available here.
Back to topLinear 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.
Download
A package of spectral test (with source code and documentation)
can be downloaded here.
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.
Back to top