package testu01

Bbattery

This module contains predefined batteries of statistical tests for sources of random bits or sequences of uniform random numbers in the interval [0,1). To test a RNG for general use, one could first apply the small and fast battery SmallCrush. If it passes, one could then apply the more stringent battery Crush, and finally the yet more time-consuming battery BigCrush.The batteries Alphabit and Rabbit can be applied on a binary file considered as a source of random bits. They can also be applied on a programmed generator. Alphabit has been defined primarily to test hardware random bits generators. The battery PseudoDIEHARD applies most of the tests in the well-known DIEHARD suite of Marsaglia. The battery FIPS-140-2 implements the small suite of tests of the FIPS-140-2 standard from NIST.

The batteries described in this module will write the results of each test (on standard output) with a standard level of details (assuming that the boolean switches of module Swrite have their default values), followed by a summary report of the suspect p-values obtained from the specific tests included in the batteries. It is also possible to get only the summary report in the output, with no detailed output from the tests, by setting the boolean switch Swrite.set_basic to false.

Some of the tests compute more than one statistic using the same stream of random numbers and these statistics are thus not independent. That is why the number of statistics in the summary reports is larger than the number of tests in the description of the batteries.

SmallCrush

Both functions applies SmallCrush, a small and fast battery of tests, to a RNG. The function small_crush_file applies SmallCrush to a RNG given as a text file of floating-point numbers in [0,1); the file requires slightly less than 51320000 random numbers. The file will be rewound to the beginning before each test. Thus small_crush applies the tests on one unbroken stream of successive numbers, while small_crush_file applies each test on the same sequence of numbers. Some of these tests assume that the generator returns at least 30bits of resolution; if this is not the case, then the generator is most likely to fail these particular tests.

The following tests are applied:

1. Smarsa.birthday_spacings with N = 1, n = 5×10⁶, r = 0, d = 2³⁰, t = 2, p = 1.
2. Sknuth.collision with N = 1, n = 5×10⁶, r = 0, d = 2¹⁶, t = 2.
3. Sknuth.gap with N = 1, n = 2×10⁵, r = 22, Alpha = 0, Beta = 1/256.
4. Sknuth.simp_poker with N = 1, n = 4×10⁵, r = 24, d = 64, k = 64.
5. Sknuth.coupon_collector with N = 1, n = 5×10⁵, r = 26, d = 16.
6. Sknuth.max_oft with N = 1, n = 2×10⁶, r = 0, d = 10⁵, t = 6.
7. Svaria.weight_distrib with N = 1, n = 2×10⁵, r = 27, k = 256, Alpha = 0, Beta = 1/8.
8. Smarsa.matrix_rank with N = 1, n = 20000, r = 20, s = 10, L = k = 60.
9. Sstring.hamming_indep with N = 1, n= 5×10⁵, r = 20, s = 10, L = 300, d = 0.
10. Swalk.random_walk_1 with N = 1, n = 10⁶, r = 0, s = 30, L₀ = 150, L₁ = 150.

repeat_small_crush gen rep applies specific tests of SmallCrush on generator gen. Test numbered i in the enumeration above will be applied rep[i] times successively on gen. Those tests with rep[i] = 0 will not be applied. This is useful when a test in SmallCrush had a suspect p-value, and one wants to reapply the test a few more times to find out whether the generator failed the testor whether the suspect p-value was a statistical fluke. Restriction: Array rep must have one more element than the number of tests in SmallCrush.

Crush

BigCrush

Rabbit

Applies the Rabbit battery of tests to the first nb bits (or less, if nb is too large) of the binary file filename. For each test, the file is reset and the test is applied to the bit stream starting at the beginning of the file. The bits themselves are processed in nearly all the tests as blocks of 32 bits (unsigned integers); the two exceptions are Svaria.appearance_spacings, which uses blocks of 30 bits (and discards the last 2 bits out of each block of 32), and Sstring.periods_in_strings which uses blocks of 31 bits (and discards 1 bit out of 32). The parameters of each test are chosen automatically as a function of nb, in order to make the test reasonably sensitive. On a PC with an Athlon processor of clock speed 1733 MHz running under Linux, Rabbit will takeabout 5 seconds to test a stream of 220bits, 90 seconds to test a stream of 225bits, and 28 minutes to test a stream of 230bits. Restriction: nb ≥ 500.

1. Smultin.multinomial_bits_over
2. Snpair.close_pairs_bit_match in t = 2 dimensions
3. Snpair.close_pairs_bit_match in t = 4 dimensions.
4. Svaria.appearance_spacings
5. Scomp.linear_comp
6. Scomp.lempel_ziv
7. Sspectral.fourier_1
8. Sspectral.fourier_3
9. Sstring.longest_head_run
10. Sstring.periods_in_strings
11. Sstring.hamming_weight with blocks of L = 32 bits.
12. Sstring.hamming_corr with blocks of L = 32 bits.
13. Sstring.hamming_corr with blocks of L = 64 bits.
14. Sstring.hamming_corr with blocks of L = 128 bits.
15. Sstring.hamming_indep with blocks of L = 16 bits.
16. Sstring.hamming_indep with blocks of L = 32 bits.
17. Sstring.hamming_indep with blocks of L = 64 bits.
18. Sstring.auto_cor with a lag d = 1.
19. Sstring.auto_cor with a lag d = 2.
20. Sstring.run
21. Smarsa.matrix_rank with 32×32 matrices.
22. Smarsa.matrix_rank with 320×320 matrices.
23. Smarsa.matrix_rank with 1024×1024 matrices.
24. Swalk.random_walk_1 with walks of length L= 128.
25. Swalk.random_walk_1 with walks of length L= 1024.
26. Swalk.random_walk_1 with walks of length L= 10016.

Alphabit

alphabit_file filename nb applies the Alphabit battery of tests to the first nb bits (or less, if nb is too large) of the binary file filename. Unlike the alphabit function above, for each test, the file is rewound and the test is applied to the bit stream starting at the beginning of the file. On a PC with an Athlon processor of clock speed 1733 MHz running under Linux, Alphabit takes about 4.2 seconds to test a file of 2²⁵ bits, and 2.3 minutes to test a file of 2³⁰ bits. Alphabit and AlphabitFile have been designed primarily to test hardware random bits generators. The four multinomial_bits_over tests should detect correlations between successive bits by applying a serial_over test to overlapping blocks of 2, 4, 8 and 16 bits. The hamming_* tests should detect correlations between the successive bits of overlapping blocks of 16 and 32 bits, and the random_walk tests consider blocks of 64 and 320 bits.

1. Smultin.multinomial_bits_over with L = 2.
2. Smultin.multinomial_bits_over with L = 4.
3. Smultin.multinomial_bits_over with L = 8.
4. Smultin.multinomial_bits_over with L = 16.
5. Sstring.hamming_indep with blocks of L = 16 bits.
6. Sstring.hamming_indep with blocks of L = 32 bits.
7. Sstring.hamming_corr with blocks of L = 32 bits.
8. Swalk.random_walk_1 with walks of length L = 64.
9. Swalk.random_walk_1 with walks of length L = 320.

BlockAlphabit

Apply the Alphabit battery of tests repeatedly to the generator gen or to the binary file filename after reordering the bits as described in the filter Unif01.create_bit_block_gen. Alphabit will be applied for the different values of w ∈ {1,2,4,8,16,32}. If s < 32, only values of w≤s will be used. Each test uses at most nb bits. See the description of the tests in alphabit_file.

PseudoDIEHARD

Applies the battery PseudoDIEHARD, which implements most of the tests in the popular battery DIEHARD or, in some cases, close approximations to them. We do not recommend this battery as it is not very stringent (we do not know of any generator that passes the batteries Crush and BigCrush, and fails PseudoDIEHARD, while we have seen the converse for several defective generators). It is included here only for convenience to the user. The DIEHARD tests and the corresponding tests in PseudoDIEHARD are:

1. The Birthday Spacings test. This corresponds to Smarsa.birthday_spacings with n = 512, d = 224, t = 1 and r = 0,1,2,3,4,5,6,7,8,9 successively. The test with each value of r is repeated 500 times and a chi-square test is then applied.
2. The Overlapping 5-Permutation test. This test is not implemented in TestU01.
3. The Binary Rank Tests for Matrices. This corresponds to Smarsa.matrix_rank.
4. The Bitstream test. Closely related to Smulti.multinomial_bits_over with Delta = −1, n = 221, L = 20.
5. The OPSO test. This corresponds to Smarsa.collision_over with n = 221, d = 1024, t = 2 and all values of r from 0 to 22.
6. The OQSO test. This corresponds to Smarsa.collision_over with n = 221, d = 32, t = 4 and all values of r from 0 to 27.
7. The DNA test. This corresponds to Smarsa.collision_over with n = 221, d = 4, t = 10 and all values of r from 0 to 30.
8. The Count-the-1's test is not implemented in TestU01. It is a 5-dimensional over-lapping version of Sstring.hamming_indep.
9. The Parking Lot test is not implemented in TestU01.
10. The Minimum Distance test. Closely related to Snpair.close_pairs with N = 100, n = 8000, t = 2, p = 2, m = 1.
11. The 3-D Spheres test. Closely related to Snpair.close_pairs with N = 20, n = 4000, t = 3, p = 2, m = 1.
12. The Squeeze test. Closely related to Smarsa.savir_2.
13. The Overlapping Sums test is not implemented in TestU01.
14. The Runs test. This corresponds to Sknuth.run.
15. The Craps test is not implemented in TestU01.

NIST

The NIST (National Institute of Standards and Technology) of the U.S. federal government has proposed a statistical test suite for use in the evaluation of the randomness of bitstreams produced by cryptographic random number generators. The test parameters are not predetermined. The NIST tests and the equivalent tests in TestU01 are:

1. The Monobit test. This corresponds to Sstring.hamming_weight_2 with L = n.
2. The Frequency test within a Block. Corresponds to Sstring.hamming_weight_2.
3. The Runs test. Is implemented as Sstring.run.
4. The test for the Longest Run of Ones in a Block. Is implemented as the test Sstring.longest_head_run.
5. The Binary Matrix rank test. Is implemented as Smarsa.matrix_rank.
6. The Discrete Fourier Transform test. Is implemented as Sspectral.fourier_1.
7. The Non-overlapping Template Matching test. Is implemented as the test Smarsa.cat_bits.
8. The Overlapping Template Matching test. This test does not exist as such in TestU01, but a similar and more powerful test is Smultin.multinomial_bits_over.
9. Maurer’s Universal Statistical test. This test is implemented as Svaria.appearance_spacings.
10. The Lempel-Ziv Compression test. Is implemented as Scomp.lempel_ziv.
11. The Linear Complexity test. Is implemented as part of Scomp.linear_comp.
12. The Serial test. Corresponds to Smultin.multinomail_bits_over with Delta = 1.
13. The Approximate Entropy test. Corresponds to Smultin.multinomial_bits_over with Delta = 0, and to Sentrop.entropy_disc_over or Sentrop.entropy_disc_over_2.
14. The Cumulative Sums test. This test is closely related to the M statistic in Swalk.random_walk_1.
15. The Random Excursions test. This test does not exist in TestU01, but closely related tests are in Swalk.random_walk_1.
16. The Random Excursions Variant test. This test does not exist in TestU01, but a closely related test is based on the R statistic in Swalk.random_walk_1.

FIPS-140-2

These functions apply the four tests described in the NIST document FIPS PUB 140-2, Security Requirements for Cryptographic Modules, page 35, with exactly the same parameters (see the WEB page at http://csrc.nist.gov/rng/rng6_3.html). They report the values of the test statistics and their p-values (except for the runs test) and indicate which values fall outside theintervals specified by FIPS-140-2. The first function applies the tests on a generator gen, and the second applies them on the file of bits filename. First, 20000 bits are generated and putin an array, then the tests are applied upon these. The tests applied are:

1. The Monobit test. This corresponds to Smultin.multinomal_bits with s = 32, L = 1, n = 20000.
2. The “poker” test, which is in fact equivalent to Smultin.multinomial_bits with s = 32, L = 4, n = 5000.
3. The Runs test, which is related to Sstring.run.
4. The test for the Longest Run of Ones in a Block, which is implemented as Sstring.longest_head_run.