|
3.1.5 Statistical Test Suite for the Validation of Cryptographic Random Number GeneratorsAndrew Rukhin, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan HeckertStatistical 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.
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.
Date created: 7/20/2001 |