SED navigation bar go to SED home page go to SED publications page go to NIST home page SED Home Page SED Contacts SED Projects SED Products and Publications Search SED Pages


contents     previous     next


3.1.5 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, ITLJuan 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, 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 allocated 2 years to 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, random walk variant, and moving averages tests. Future updated and expanded public release versions of the test suite are contemplated.

The current version of the test suite is being employed by the Computer Security Division for preliminary screening of Advanced Encryption Standard algorithms submitted by groups from around the world as candidates to replace the current Data Encryption Standard. Distribution of the test suite for its first offsite testing is scheduled for Spring of 1999. First release codes and documentation are scheduled for public release by the end of 1999. It is highly probable that the first release test suite will be incorporated whole into the new developmental ANSI X9.82 Standard on Random Number Generation.


\begin{figure}
\epsfig{file=/proj/sedshare/panelbk/99/data/projects/it/des.ps,width=6.0in}\end{figure}

Figure 4: Plot profiles the performance of the Data Encryption Standard generator against tests of the Cryptographic Test Suite at a nominal 1% significance level. Tests are arranged by increasing percentage of accepted sequences.



contents     previous     next

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