3.1.4 Statistical Test Suite for the Validation of Cryptographic Random Number Generators

Andrew Rukhin, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert
Statistical Engineering Division, ITL

Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, James Dray, San Vo
Computer Security Division, ITL

Modern secure communications make essential use of encryption technology. The need for random and pseudorandom numbers arises in many cryptographic applications. Cryptosystem keys, digital signatures, and authentication protocols all use binary random or pseudorandom inputs at various points. The integrity of such systems is contingent upon both the fairness (equiprobable distribution) and randomness (nonpredictability) of the Bernoulli streams used.

In response to a perceived need for a credible and comprehensive set of tests for binary (not uniform) random number generators, the Computer Security and Statistical Engineering Divisions have collaborated 2 years on the development of a test suite making use of both existing algorithms culled from the literature and newly developed tests. The package adheres to a high standard in insisting that all algorithms represented be based upon provable, and documented, mathematical results. Issues of independence and comprehensive coverage of tests have also been considered.

The test suite currently includes frequency, block frequency, runs, longest run of ones, random binary matrix rank, spectral (discrete Fourier transform), overlapping and non-overlapping template matching, Maurer's ``universal'', Lempel-Ziv compression, linear complexity, serial, approximate entropy, Cusum, random excursions and random walk variant tests. Public release of the test suite is expected in 2000.

The current version of the test suite is being employed by the Computer Security Division for the screening of Advanced Encryption Standard algorithms submitted by groups from around the world as candidates to replace the current Data Encryption Standard.

Figure 4: The plot depicts the serial behavior of P-values of a randomness test based on approximate entropy. The corresponding P-values are plotted against the first 400 digits of binary expansions of $\sqrt{3}$ (red), $\sqrt{2}$ (blue) and e (green). According to these results, P-values corresponding to $\sqrt{3}$ are smaller than those of e and $\sqrt{2}$. However, the smallest P-values for $\sqrt(3)$, which occur in the block from the 130-th to 150-th digits, are of order 0.006. They lack statistical significance to reject the random nature of these digits because of the multiple comparisons aspect of the testing problems.

       

Date created: 7/20/2001
Last updated: 7/20/2001
Please email comments on this WWW page to sedwww@nist.gov.