Search NIST's ICAT
By Elaine B. Barker
Random and pseudorandom numbers are needed for many cryptographic applications. For example, common cryptosystems employ keys that must be generated in a random fashion. Many cryptographic protocols also require random or pseudorandom inputs at various points, e.g., for auxiliary quantities used in generating digital signatures or for generating challenges in authentication protocols.
NIST Special Publication (SP) 800-22, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications, discusses the randomness testing of random number and pseudorandom number generators (RNGs and PRNGs) that may be used for many purposes including cryptographic, modeling, and simulation applications. Co-authors of the document from ITL's Computer Security and Statistical Engineering Divisions include Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid, Elaine Barker, Stefan Leigh, Mark Levenson, Mark Vangel, David Banks, Alan Heckert, James Dray, and San Vo. The publication and the associated tests are intended for individuals who are responsible for the testing and evaluation of random and pseudorandom number generators, including (P)RNG developers and testers.
The document focuses on those applications where randomness is required for cryptographic purposes such as the generation of keying material. A set of statistical tests for randomness is described; the statistical tests and NIST SP 800-22 are available at http://csrc.nist.gov/rng/.
There are two basic types of generators used to produce random sequences: random number generators and pseudorandom number generators. A random number generator uses a non-deterministic source (i.e., some unpredictable physical source) to produce random bits. A pseudorandom number generator produces a sequence of bits from an initial value called a seed using a known algorithm.
Various statistical tests can be applied to a sequence produced by such generators to compare and evaluate the sequence for randomness. The distribution of outcomes of statistical tests, when applied to a truly random sequence, is known a priori and can be described in probabilistic terms. However, no set of statistical tests, including these tests, is sufficient to certify the randomness of a generator; the analysis of the generator’s design (e.g., cryptanalysis) is also required.
The Statistical Tests
The NIST Statistical Test Suite is a package of 16 tests that were developed to test the randomness of (arbitrarily long) binary sequences produced by random or pseudorandom number generators. The tests focus on a variety of different types of non-randomness that could exist in a sequence.
Each test is based on a calculated test statistic value, which is a function of the tested sequence. The test statistic is used to calculate a P-value that summarizes the strength of the evidence for randomness. Each P-value can be interpreted as the probability that a perfect random number generator would have produced a sequence less random than the sequence that was tested, given the kind of non-randomness assessed by the test. The use of P-values is intended to allow an individual testing a generator to easily and objectively interpret the test results and assess the quality of the generator.
NIST SP 800-22 provides a high-level description and examples for each of the 16 tests in the test suite, along with the mathematical background for each test. In addition, the document provides guidance for specifying the parameters required for the tests and for interpreting the test results, both on a single sequence for a given test and for multiple sequences for that test.
The 16 statistical tests contained in the test suite are:
The Test Code
The source code for the tests was developed in ANSI C on a SUN™ workstation running under the Solaris™ operating system. Other systems may require modifications to the source code to run properly.
Instructions are provided in NIST SP 800-22 for installing, modifying, and operating the test code and interpreting the results. Sample generators are provided along with the test code that can be used to run with the tests and compare against the expected results that are provided in the document.
Over the course of this project, several empirical studies were conducted to ascertain whether the statistical tests were properly developed and implemented. These studies were employed to demonstrate the usefulness of each of the statistical tests. Both “good” and “bad” generators were used to assess the quality of the tests. Codes for these generators have been made available with the test code. In addition, the tests were used to ascertain the randomness of the algorithm candidates for the Advanced Encryption Standard (AES). An appendix to NIST SP 800-22 describes results for the generators provided with the test code, while NISTIR 6390 and NISTIR 6483 describe the results of testing algorithm candidates for the AES. All documents are available at http://csrc.nist.gov/rng.
Disclaimer: Any mention of commercial products or reference to commercial organizations is for information only; it does not imply recommendation or endorsement by the National Institute of Standards and Technology nor does it imply that the products mentioned are necessarily the best available for the purpose.
Sun™ and Solaris™ are trademarks of Sun Microsystems, Inc. in the United States and other countries.