Universal Program Test

From DiceLock.org

Ueli M. Maurer - "An Universal Statistical Test for Random Bit Generators"

Contents 1 Description 1.1 Program implementation 1.2 Table of values 1.3 Thresholds 2 References

Description

Having as input the bit succession s = s₀, s₁,..., s_n-1

The steps to check that a sequence satisfies Maurer´s test are:

1. The sequence s is divided in L bit length blocks, where L can be from 1 to 16. It is recommended to make the check for 6 <= L <= 16. The remaining bits from dividing n between L can be ignored, it is the tail of the sequence.

The resulting blocks are classified in two parts: the first Q blocks and the remaining K blocks. Q must be chosen from at least 10·2^L blocks, as different 2^L blocks of length L exist, it is supposed that in a chain of 10 times this number there should be at least a block from the different 2^L .Q is the initialisation chain.

The remaining K blocks is the part of the check, it is recommended that K should be at least 1000·2^L, that is to say, expecting that the device generates each different block 1000 times.

In practice, the aforementioned recommended parameters imply that a bit series must be for L=8 at least of 258.560 bits and for L=16 at least of 66.191.360 bits.

3. The test is done using the table tab[block[n]], in which the index of the last appearance of block[n] is stored, where block[n] is the number whose binary representation is in the block block[n].

Exactly the table tab, is initialised with the first Q blocks making 1 <= i <= Q tab[block[n]] = n.

Then the test K blocks are scanned incrementing for each block the sum variable for natural logarithm of the distance between the index of the block[n] current occurrence and the last previous occurrence of the same block[n]. Updating then the table which maintains the index of the last appearance of block[n] through tab[block[n]] := n.

Then ( sum / K )/ ln ( 2.0 ) is calculated, resulting in the test parameter fTU.

Program implementation

Listing of a PASCAL program implementing "Universal Statistical Test" appearing in Journal of Cryptology vol.5, no.2,1992, pp 89-105

program UniversalTest (input, output);
const L = 8; V = 256; Q = 2000; K = 20000;
var i, n: integer; sum, fTU: real;
    tab: array[0..V-1] of integer;
    block: array[1..max] of integer;
begin;
    for i := 0 to V-1 do tab[i] := 0;  (* initialization *)
    for n := 1 to Q do tab[block[n]] := n;  (* initialization *)
    sum := 0.0;
    for n := Q+1 to Q+K do begin
      sum := sum + ln ( n - tab[block[n]] );
      tab[block[n]] := n;
    end;
    fTU := ( sum / K )/ ln ( 2.0 );
    writeln ( fTU );
end.

Having as output the test parameter fTU which is normally distributed with variance s ² = c ( L, K )² ( s ₁)² / K, where c ( L, K ) » 0.7 – (0.8/L) + ( 4 + (32/L) ) K^{(- 3/L)} / 15 for K >= 2 ^L.

Table of values

Table obtained from Journal of Cryptology vol.5, no.2,1992, pp 89-105, for m and ( s ₁ ) ²:

Table L, m, ( s ₁ ) ²

L	m	( s 1 ) 2	L	m	( s 1 ) 2
1	0.7326495	0.690	9	8.1764248	3.311
2	1.5374383	1.338	10	9.1723243	3.356
3	2.4016068	1.901	11	10.170032	3.384
4	3.3112247	2.358	12	11.168765	3.401
5	4.2534266	2.705	13	12.168070	3.410
6	5.2177052	2.954	14	13.167693	3.416
7	6.1962507	3.125	15	14.167488	3.419
8	7.1836656	3.238	15	15.167379	3.421

Thresholds

With the standard deviation obtained s, the expected mean value m taken from the aforementioned table and the number of standard deviations y that fTU is allowed to be away from the mean value, the thresholds t₁ and t₂ are calculated as:
  t₁ = m - y s
  t₂ = m + y s where y is obtained from the normal distribution function N(0,1) table depending on the rejection rate p that is chosen.

A rejection rate of p » 0.001 ... 0.01 is recommended. For example to obtain a rejection rate of p=0.01 we have that y=2.58, and for p=0.001 is y=3.30.

The sequence s = s₀, s₁,..., s_n-1 passes the test if:

t₁ <= fTU <= t₂

The sequence s = s₀, s₁,..., s_n-1 does not pass the test if:

t₁ > fTU   o   fTU > t₂

References

[NIST] National Institute of Standards and Technology.

[NIST RNGT] NIST Random Number Generation and Testing.

---