A Statistical Test Suite for Random and
Pseudorandom Number Generators for
Cryptographic Application
This contribution discusses some aspects of testing random and pseudorandom
number generators. A Statistical Test Suite for Random and Pseudorandom
Number Generators for Cryptographic Applications (NIST Special Publication) is
presented. The software implementation of the test suite with output protocols and
presents experiences from testing some random and pseudorandom generators.
Jiří Sobotík and Václav Plátěnka
[email protected]
Department of Special Communication Systems
Military Academy in Brno
Brno, Czech Republic
and
The Military Technical Institute of Electronic
Prague, Czech Republic
1
Applicability
Cryptographic applications lay great emphasis on the statistical
properties of random and pseudorandom number generators.
The sequences generated by these generators must be
indistinguishable from the sequences generated by “true
random generators”. Any non-randomness in the generated
sequences rapidly degrades the security of cryptographic
systems as a whole.
The test suite should be applied in the first steps of an
evaluation process of generator. If the generator or other
primitives do not pass the test suite then they are not suitable
for cryptographic application.
Tests Suite cannot substitute a detailed
cryptanalysis.
2
The NIST Test Suite consists of 16 statistical tests that were
developed to test the randomness of binary sequences.
1.
2.
3.
4.
5.
6.
7.
8.
The Frequency (Monobit) Test
Frequency Test within a Block
The Runs Tests
Test for the Longest-Run-of-Ones
in a Block
The Binary Matrix Rank Test
The Discrete Fourier Transform
(Spectral) Test
The Non-overlapping Template
Matching Test
The Overlapping Template
Matching Test
9. Maurer’s “Universal
Statistical” Test
10. The Lempel-Ziv Compression
Test
11. The linear Complexity Test
12. The Serial Test
13. The approximate Entropy Test
14. The Cumulative Sums
(Cusums) Test
15. The Random Excursion Test
16. The Random Excursion Variant
Test
3
The General Structure of the Statistical Test
Each test is based on a calculated test statistic value, which is a
function of the testing sequence. The test statistic value is use to
calculate a Pvalue
Pvalue is the probability that the perfect random number
generator would have produced a sequence less random
than the sequence that was tested.
Example (Frequency test):
Statistic:
S n  x 0 , x1 , ... , x n  1  
1
n
n 1

 2  x
i
 1
i0
Summationa statistic
Decision rule:
Pvalue :
Pvalue
 Sn 
 erfc 

 2
Complemntary error function
If Pvalue   then accept otherwise reject.
Significant level
[0.001 – 0.01]
The hypothesis about randomness of tested sequences is
accepted on significant level .
The hypothesis about randomness of tested sequences is
rejected on significant level .
4
Software Implementation of Test Suite
In publication, each test from the test suite is described in detail and
an elementary example is done. The verification examples of tests of
known sequences (binary expansion of e number,  number, 2 , 3 )
are included so that it is not difficult to program the all tests in
mathematically-oriented programming languages; e.g. MATLAB,
MATHCAD or MATEMATICA.
X  floor ( runif ( 1000000  0  2) )
FreqBlock Test
( X  M ) 
N  floor



length ( X )
M



RunsTest ( X ) 
for i  0  N  1
N 1
chi 

i  0
1  pgamma
FreqTest ( X )  0.35652857566362
length ( X )  2  mean ( X )  1

2
( n  length ( X )
( return
 M 1
i 

X
i M 
M 
 j0
1

FreqTest ( X )  erfc 

  
 i

2 

1


j

2
p  0.5

2
a  submatrix ( X  0  n  2  0  0 )
b  submatrix ( X  1  n  1  0  0 )
erfc
( X  100 )  0.767510993360868
if
p  mean ( X ) )
n
V obs  1 
 2  M  chi  N 


2 

FreqBlockTest
0.0 )



 


(a  b)

 V obs  2  n  p  ( 1  p ) 


2 2 n  p  ( 1  p )


RunsTest ( X )  0.061601739016221
5
V ýb ě r so u b o ru k te sto v á n í
Návod a popis testù
Náhledy testovaného souboru:
P a n e l v st u p ů
T estov aný soubor :
D :\ Sobotík \ Publik ac e\ Sada statististic k ýc h testů pro k ryptologic k é aplik ac e
v erze 2002\ Sada testů podle N IST v erze 2002\ e.bit
D élk a souboru :
1000000
H ladina v ýznamnosti :
Spustit testov ání
Označ it v še
Z rušit v še
0.01
Parametry :
T est v yv áženosti
T est č etností uv nitř blok u
Parametry :
M aurerův " univ erzální statistic k ý" test
100
Lempel - Z iv ův k omprimač ní test
T est shluk ů
T est lineárního rozp ě tí
T est nejdelšíc h shluk ů v bloc íc h
Sériov ý test
T est hodností binárníc h matic
32
Spek trální test
T est č etnosti nepř ek rýv ajíc íc h se v zork ů
T est č etnosti př ek rýv ajíc íc h se v zork ů
T est aproximač ní entropie
500
5
5
T est č ásteč nýc h souč tů
000000001
T est náhodné proc házk y
Alternativ ní test náhodné proc házk y
6
The Statistical Test Suite Protocol
C:\Documents and Settings\platenka\Dokumenty\Testování
Sobotík\Testování pomocí NIST\e.bit
File length:
1000000
Significance level:
0,01
Description of generator (sequence): The binary expansion of Euler number.
e = 10.1011011111100001010100010110001010001010111…
File name:
Test No. Test name:
parametr/
variant/state
1
2
3
4
5
6
7
8
9
10
11
12
The Frequency Test
Frequency Test within a Block
100
Run Test
Test for the Longest-Run-of-Ones in a Block
The Binary Matrix Rank Test
32
The Discrete Fourier Transform Test
The Non-Overlapping Template Matching Test 000000001
The Overlapping Template Matching Test
Mauerer' "Universal Statistical" Test
The Lempel - Ziv Compression Test
The Linear Complexity Test
500
The Serial Test
5
13
14
The Approximate Entropy Test
The Culmulative Sum Test
15
Random Excursion Test
16
Random Excursion Variant Test
5
forward
backward
-4
-3
-2
-1
1
2
3
4
-9
-8
-7
-6
-5
-4
-3
-2
-1
1
2
3
4
5
6
7
8
P value
Acceptation
0,953749
0,619340
0,561917
0,769568
0,306156
0,443864
0,078790
0,110434
0,282568
0,000584
0,826335
0,225783
0,057499
0,361688
0,669886
0,724265
0,573306
0,197996
0,164011
0,007779
0,786868
0,440912
0,797854
0,778186
0,858946
0,794755
0,576249
0,493417
0,633873
0,917283
0,934708
0,816012
0,826009
0,137861
0,200642
0,441254
0,939291
0,505683
0,445935
0,512207
0,538635
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
7
Thank you for your attention
8
Descargar

Document