Computer Security and Cryptography

5.3 NIST'S PROPOSED STATISTICAL TESTS

The National Institution of Standards (NIST) proposed a number of statistical tests [NIST, 1994] when they solicited a successor to the Data Encryption Standard in 1996.

If a cryptographic algorithm generates a random number generator, the algorithm's output of 20,000 consecutive output bits y₀, y₁,…, y₁₉₉₉₉ must pass the following four statistical tests.

• The Monobit Test – Count the number N₁ of ones in the 20,000 output bits. The test is passed if 9654 < N₁ < 10,346.
• The Poker Test – Divide the 20,000 bitstream into four blocks of 5000 bits each.

Count the number f_i of (column) vectors (x_0,j, x_1,j, x_2,j, x_3,j) for which i = 8x_0,j + 4x_1,j + 2x_2,j + x_3,j and evaluate the χ²-value

The test is passed if 1.03 < χ² < 57.4.

TABLE 5.1 Intervals for the Runs Test

Length of Run	Interval
1	2267–2733
2	1079–1421
3	502–748
4	223–402
5	90–223
6+	90–223

• The Runs Test – A run is a maximal length sequence of either bits with value one or zero:

  

  The test is passed if the number of runs R_ℓ[i] of i(i = 0, 1) lies in the intervals listed in Table 5.1.

• The Long Run Test – A long run is defined to be a run of ones or zeros of length 34 or more. ...