NIST SP800-22b test suite

AN4230

6/24

DocIDID024118 Rev 1

2

NIST SP800-22b test suite

2.1

Introduction

The NIST SP800-22b statistical test suite has been carried out using a statistical test suite

(sts) developed by the National institute of standards and technology (NIST) to probe the

quality of random generators for cryptographic applications. A comprehensive description of

the suite was presented in the paper entitled: “A Statistical Test Suite for the Validation of

Random Number Generators and Pseudo Random Number Generators for Cryptographic

Applications”.

2.2

NIST SP800-22b test suite description

The NIST SP800-22b statistical test suite “sts-2.1.1” is a software package which was

developed by the National Institute of Standards and Technology; it can be downloaded

from the NIST web site at the following address:

http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

The source code has been written in ANSI C. The NIST statistical test suite consists of 15

tests that were developed to test the randomness of a binary sequence. These tests focus

on a variety of types of non-randomness that could exist in a sequence. From this point of

view, the test suite can be classified as follows:

Frequency tests

• Frequency (Monobit) test:

To measure the distribution of 0’s and 1’s in a sequence and to check if the result is similar

to the one expected for a truly random sequence.

• Frequency test within a block:

To check whether the frequency of 1’s in an M-bit block is approximately M/2, as would

be expected from the theory of randomness.

• Run tests:

To assess if the expected total number of runs of 1’s and 0’s of various lengths is as

expected for a random sequence.

• Test of the longest run of 1’s in a block:

To examine the long runs of 1’s in a sequence.

Test of linearity

• Binary matrix rank test:

To assess the distribution of the rank for 32x32 binary matrices.

• Linear complexity test:

To determine the linear complexity of a finite sequence.

Test of correlation (by means of Fourier transform)

• Discrete Fourier transform (spectral) test:

To assess the spectral frequency of a bit string via the spectral test based on the discrete

Fourier transform. It is sensitive to the periodicity in the sequence.