16 12
1 NIST NIST Special Publication 800-22[1, 2] SP 800-22 2 DIEHARD [27] SP 800-22Ver.1.516 189 DFT Lempel-Ziv [3, 4, 5] SP 800-22 16 DFT Lempel-Ziv 1
2 SP 800-22 NIST SP800-22[1, 2] NISTNational Institute of Standards and Technology AESAdvanced Encryption Standard 2.1 SP800-22 2 16 1. Frequency (Monobit) Test 2. Frequency Test within a Block 3. Runs Test 4. Test for the Longest Run of Ones in a Block 5.2 Binary Matrix Rank Test 6.DFT Discrete Fourier Transform (Spectral) Test 7. Non-overlapping Template Matching Test 8. Overlapping Template Matching Test 9.Maurer Maurer's Universal Statistical Test 10.Lempel-Ziv Lempel-Ziv Compression Test 11. Linear Complexity Test 12. Serial Test 13. Approximate Entropy Test 2
14. Cumulative Sums (Cusum) Test 15. Random Excursions Test 16. Random Excursions Variant Test 2.2 NIST p-value p-value 2 p-value 0.01 (NIST 1000 ) 1.p-value 2.p-value 0.01 1. p-value [0, 1) [0, 1) 10 2 p-value 0.0001 2. m 0.01 p-value 0:99 ± 3 s 0:99 0:01 m (2.1) 3
3 SP 800-22 Generator-Using SHA-1 NIST Generator-Using SHA-1 SP 800-22 16 4
3.1 3.1.1 0 1 3.1.2 " 0 1 n S n 3.1.3 n n 100 3.1.4 Step1 0 1 " =(" 1 ;" 2 ; ;" n ) (3.1) "-1""+1" X =(X 1 ;X 2 ; ;X n ) X i =2" i 1 (1» i» n) (3.1) Step2 S n = X 1 + X 2 + + X n (3.2) Step3 S n μ =0 ff 2 = n S n (3.3) p-value p-value 0.01 p-value = erfc ψ! jsn j p 2n (3.3) 5
3.1.5 De Moivre-Laplace theorem S n 0 n S n 0 1 NIST SP800-22 3.1.6 Sn n =1001; 00010; 000100; 0001; 000; 000 (3.2) S n μ =0 ff 2 = n 3.1 NIST G Using SHA-1 1000 6
7
8
3.1: S n 9
3.1.7 10
3.2 3.2.1 M 1 M/2 3.2.2 M: n: ":0 1 " =(" 1 ;" 2 ; " n ) χ 2 (obs):m 1 M/2 χ 2 3.2.3 NIST 100 M 20;M > 0:01n; N < 100 3.2.4 Step1 N = bn=mc Step2 1» i» N i 1 ß i ß i = Step3 χ 2 χ 2 (obs) =4M P M j=1 " (i 1)M +j M NX i=1 (3.4) (ß i 1 2 )2 (3.5) 11
Step4 χ 2 (obs) χ 2 χ 2 (obs) χ 2 ( 0.01) P-value P value = igamc( N 2 ; χ2 (obs) ) (3.6) 2 P-value 0.01 3.2.5 1 50 P-value 0 1 1 1 M N 1 ß i (3.5) N χ 2 3.2.6 χ 2 (obs) χ 2 NIST N χ 2 NIST G Using SHA-1 1000 12
1:n=100 M=20 N=5 2:n=1,000 M=20 N=50 13
3:n=10,000 M=200 N=50 4:n=100,000 M=2000 N=50 14
5:n=1,000,000 M=20000 N=50 3.2.7 15
3.3 3.3.1 k k-1 3.3.2 n " "=" 1," 2,," n V n (obs) 3.3.3 NIST n 100bit 3.3.4 Step1 ß ß np " j j=1 n (3.7) Step2 Runs Test jß 1 j fi Frequency test 2 Runs Test 0 Frequency test ß 1/2 fi = p 2 n Step3 V n (obs) X n 1 V n (obs) =f r(k)g +1 (3.8) " k = " k+1 r(k)=0" k 6= " k+1 r(k)=1 (3.8), 1 V n (obs) k=1 16
Step4 V n (obs) V n (obs) 0.01P value P value = erfcf jv n(obs) 2nß(1 ß)j 2 p g (3.9) 2nß(1 ß) P value 0.01 3.3.5 V n μ2nß(1 ß) ff 2 2 p nß(1 ß) lim P Vn 2nß(1 ß) n!1 2 p» z nß(1 ß) Φ(z) = Z z 1 =Φ(z) (3.10) 1 p 2ß e x2 2 dx (3.11) V n NIST Φ(z) erf c(z) = Z 1 z 2 p ß e x2 dx (3.12) P value = erfc( z p 2 ) (3.13) (3.9) 3.3.6 Vn(obs) 100,1000,10 4,10 5,10 6 bit V n (obs) NIST G-Using SHA-1 1000 17
u 3.2: n=100bit u 3.3: n=1000bit 18
u 3.4: n=10 4 bit u 3.5: n=10 5 bit 19
u 3.6: n=10 6 bit 3.3.7 20
3.4 3.4.1 M 3.4.2 n " "=" 1," 2,," n M 1 N χ 2 (obs) n M 128» n 6272 8 6272» n 750000 128 750000» n 10 4 1M n 3.4.3 NIST n 128bit 3.4.4 Step1 n M N = b n M c Step2 2 ν i ν i M=8 M=128 M=10 4 ν 0»1»4»10 ν 1 2 5 11 ν 2 3 6 12 ν 3 4 7 13 ν 4 8 14 ν 5 9 15 ν 6 16 21
2 M ν i Step3 χ 2 (obs) χ 2 (obs) = KX i=0 (ν i Nß i ) 2 Nß i (3.14) K, ß i 3 M K ß i M K ß i 8 3 ν 0 ß 0 =0.2148 10 4 6 ν 0 ß 0 =0.0882 ν 1 ß 1 =0.3672 ν 1 ß 1 =0.2092 ν 2 ß 2 =0.2305 ν 2 ß 2 =0.2483 ν 3 ß 3 =0.1875 ν 3 ß 3 =0.1933 128 5 ν 0 ß 0 =0.1174 ν 4 ß 4 =0.1208 ν 1 ß 1 =0.2430 ν 5 ß 5 =0.0675 ν 2 ß 2 =0.2493 ν 6 ß 6 =0.0727 ν 3 ß 3 =0.1752 ν 4 ß 4 =0.1027 ν 5 ß 5 =0.1124 3M K, ß i Step4 χ 2 (obs) χ 2 (obs) 0.01P value P value = igamcf K 2 ; χ2 (obs) g (3.15) 2 P value 0.01 3.4.5 ν K+1 ν 0 ν K M r M r (ν» ) U = min M r +1; h M j(m+1) M r P (ν» mjr) = 1 ψ M r i! U X j=0 ψ!ψ M r +1 M j(m +1) ( 1) j j M r 22!
P (ν» m) = MX r=0 ψ M r! P (ν» mjr) 1 2 M (3.16) (3.16) χ 2 ν ß (3.14) K P value ψ K igamc 2 ; χ2 (obs) 2! = 1 ( K 2 )2 K 2 Z 1 χ 2 (obs) e u 2 u K 2 1 du (3.17) 3.4.6 ν ß 3 ν i N ν 0 = ν i 3.73.9 n 1288192 N 10 6 bit NIST G-Using SHA-1 23
Š Šš wš 3.7: n=128bit Š Šš wš 3.8: n=8192bit 24
Š Šš wš 3.9: n=10 6 bit 3.4.7 χ 2 (obs) n 128, 8192, 10 6 bit χ 2 (obs) NIST G-Using SHA-1 1000 25
3.10: n=100bit «3.11: n=8192bit 26
«3.12: n=10 6 bit 3.4.8 27
3.5 2 3.5.1 2 3.5.2 n: ":0 1 " =(" 1 ;" 2 ; " n ) M: M=32 Q: Q=32 χ 2 (obs): χ 2 3.5.3 NIST 38912bit 3.5.4 Step1 j k n N = M Q MQ Q M Q Step2 R l (1» l» N) Step3 F M : R l = M F M 1:R l = M 1 N F M F M 1 : 28
Step4 χ 2 χ 2 (obs) = (F M 0:2888N) 2 0:2888N + (F M 1 0:5776N) 2 + (N F M F M 1 0:1336N) 2 0:5776N 0:1336N (3.18) Step5 χ 2 (obs) χ 2 χ 2 (obs) χ 2 ( 0.01) P-value P value = e χ2 (obs)=2 (3.19) P-value 0.01 3.5.5 Kovalenko [9], Marsaglia Tsay [10] M Q 2 r =0; 1; 2; ;m r 1 Y p r =2 r(q+m r) MQ i=1 (1 2 i Q )(1 2 i M ) 1 2 i r (3.20) M N 32 p M ß 1Y j=1 [1 1 ]=0:2888 ::: (3.21) 2j p M 1 ß 2p m ß 0:5776 ::: (3.22) p M 2 ß 4p M 9 ß 0:1284 ::: (3.23) j k M 10 (» 0:05) n N = N M MQ M-1 M-2 3 F M ;F M 1 ;N F M FM 1 (3.18) χ 2 (obs) 2 χ 2 χ 2 29
3.5.6 χ 2 (obs) χ 2 NIST 2 χ 2 NIST G Using SHA-1 1000 30
1:38912bit 2:100,000bit 31
3:1,000,000bit 3.5.7 32
3.6 DFT 3.6.1 DFT 0 1 ±1 Discrete Fourier Transform 3.6.2 " :0 1 n : d :95 3.6.3 n NIST 1000bit 3.6.4 Step1 0 1 n " = " 1 ;" 2 ;:::;" n (" i 20; 1;i = 1; 2; ;n) 1 1 X = x 1 ;x 2 ; ;xx n i =2" i 1 Step2 Step1 X f j = nx k=1 x k exp ψ i 2ß(k 1)j n! i p 1 (3.24) Discrete Fourier Transform f j j = 0; 1; ;n 1f j = μ f n j j =0; n 2 f 0 ; ;f b n 1 2 c Step3 f j jf j j 95 T = p 3n T N 0 =0:95n=2 Step4 jf j j T N 1 N 1 N 0 d = q n(0:95)(0:05)=2 33 (3.25)
d Step5 d d 0.01P value P value = erfc ψ! jdj p 2 (3.26) P value 0.01 3.6.5 DFT [3]Kim [4] [5] 3.6.6 d n 10 3 10 4 10 5 10 6 bit d NIST G-Using SHA-1 1000 34
3.13: n =10 3 bit 3.14: n =10 4 bit 35
3.15: n =10 5 bit 3.16: n =10 6 bit 36
3.6.7 NIST d 2 [3, 4] 1 T f j jf j j F q (x) =1 exp( x2 ) n p T p = (ln 0:05)n = 2:9957323n T NIST T = 3n 3.133.16 2 d 1 d 3.17 3.17 n =10 6 3.17: dn =10 6 bit 3.17 d d 0 (0:7) 2 N 1 50 [5] 37
3.7 3.7.1 N m N χ 2 3.7.2 " 0 1 n m B M N N =2 3 =8 χ 2 (obs) χ 2 3.7.3 m 9 10 n 2 20 =1; 048; 576 3.7.4 Step1 " M N Step2 m B 1 m j(1» j» N) B W j Step3 W j (3.27) μ(3.28) ff 2 χ 2 χ 2 (obs) (3.29) μ = M m +1 2 m (3.27) 38
1 ff 2 = M 2 2m 1 m 2 2m χ 2 (obs) = NX j=1 (W j μ) 2 (3.28) ff 2 (3.29) Step4 χ 2 (obs) N χ 2 χ 2 (obs) (3.30) p-value p-value 0.01 ψ N p-value = igamc 2 ; χ 2 (obs) 2! (3.30) 3.7.5 1 3.7.4 Step2 m W j B =(" 0 1;" 0 2; ;" 0 m) B 6= n j; 1» j» m 1;" 0 j+k = " 0 k;k =1; 2; ;m j o (3.31) M W j (3.27)(3.28) μ ff 2 (3.29) χ 2 (obs) N χ 2 3.7.6 n 2 20 =1; 048; 576 m 9 10 B W j (3.29) χ 2 (obs) m =9 B "000000001" m =10"0000000001" NIST G Using SHA-1 1000 W j W j (3.27)(3.28) μ ff 2 3.18 39
χ 2 (obs) χ 2 (obs) N =8 χ 2 3.19 40
3.18: W j 41
3.19: χ 2 (obs) χ 2 42
3.7.7 43
3.8 3.8.1 N m K +1=6 χ 2 3.8.2 " 0 1 n m B m 1 K K =5 M M =1032 N χ 2 (obs) χ 2 3.8.3 m 9 10 n 1,000,000 3.8.4 Step1 " M N Step2 m B 1 j(1» j» N) W j Step3 0 x 0 1 x 1 2 x 2 3 x 3 4 x 4 5 x 5 Step2 W j x i (0» i» 5) ν i 44
Step4 x i ß i (3.32) ß 0 = e 9 ß 1 = 2 e ß 2 = e ( +2) 8 ψ! ß 3 = e 2 8 ψ 6 + +1! ß 4 = e 3 16 24 + 2 2 + 3 2 +1 ß 5 =1 (ß 0 + ß 1 + ß 2 + ß 3 + ß 4 ) >= >; (3.32) = 2 (3.33) = M m +1 2 m (3.34) Step5 χ 2 χ 2 (obs) (3.35) χ 2 (obs) = 5X i=0 (ν i Nß i ) 2 Nß i (3.35) Step6 χ 2 (obs) K =5χ 2 χ 2 (obs) (3.36) p-valuep-value 0.01 ψ 5 p-value = igamc 2 ; χ 2 (obs) 2! (3.36) 3.8.5 W j [11] U P (U = u) P (U = u) = e 2 u ux l=1 ψ u 1 l 1! l l! (3.37) 45
P (U =0),P (U = 1),,P (U =4) P (U =0)=e 9 P (U =1)= 2 e P (U =2)= e ( +2) 8 ψ! P (U =3)= e 2 8 ψ 6 + +1! P (U =4)= e 3 16 24 + 2 2 + 3 2 +1 >= >; (3.38) ß 0 ;ß 1 ; ;ß 5 (3.32) W j K +1=6 (3.35) χ 2 (obs) 6 1=5 χ 2 3.8.6 χ 2 (obs) n 1; 000; 000 m 9 10 ß i (3.32) (3.35) χ 2 χ 2 (obs) K =5 χ 2 3.20 3.21 NIST G Using SHA-1 1000 46
3.20: ß i 47
3.21: χ 2 (obs) 5 χ 2 48
3.8.7 49
3.9 Maurer 3.9.1 Maurer L 3.9.2 " 0 1 n L Q K f n 3.9.3 L 6» L» 16 Q Q =10 2 L n 6» L» 15 (10 2 L + 1000 2 L )L» n<(10 2 L+1 +1000 2 L+1 )(L +1) L =16 (10 2 L + 1000 2 L )L» n 3.1 3.9.4 Step1 " L Q K Q + K = bn=lc Step2 T j 0 i L 2 j(0» j» 2 L 1) T j = i (1» i» Q) 50
3.1: L n Q =10 2 L 6 387,840904,959 640 7 904,9602,068,479 1280 8 2,068,4804,654,079 2560 9 4,654,08010,342,399 5120 10 10,342,40022,753,279 10240 11 22,753,28049,643,519 20480 12 49,643,520107,560,959 40960 13 107,560,960231,669,759 81920 14 231,669,760496,435,199 163840 15 496,435,2001,059,061,759 327680 16 1,059,061,760 655360 T j j 2 L Step3 sum 0 i L 2 j sum = sum + log 2 (i T j ) (3.39) T j = i (Q +1» i» Q + K) (3.39) sum Q =0 (3.39) 0 sum i = sum i 1 +log 2 (i T j ) (Q +1» i» Q + K) (3:39) 0 Step4 f n = sum K (3.40) Step5 f n 3.2 μ(l)(3.41),(3.42) ff f n (3.43) p-value p-value 0.01 51
3.2: L μ(l) V (L) L μ(l) V (L) 6 5.2177052 2.954 7 6.1962507 3.125 8 7.1836656 3.238 9 8.1764248 3.311 10 9.1723243 3.356 11 10.170032 3.384 12 11.168765 3.401 13 12.168070 3.410 14 13.167693 3.416 15 14.167488 3.419 16 15.167379 3.421 ff = c s V (L) K c =0:7 0:8 4+ L + 32 L p-value = erfc K 3=L 15 ψfi fifififi fi f n μ(l) fifififi! p 2ff (3.41) (3.42) (3.43) 3.9.5 3.2 f n μ(l) [12] 1X μ(l) =2 L (1 2 L ) i 1 log 2 i (3.44) i=1 f n ff (3.41) Coron Naccache c [13] c =0:7 0:8 L + 1:6+ 12:8 L K 4=L (3.45) (3.45) (3.42) 52
3.9.6 fn L 6 7 (3.40) f n 3.2 μ(l)(3.41),(3.42) ff 3.22 L 6 f n (3.45) 3.23 3.3 (3.42) ff (3.45) ff NIST G Using SHA-1 n L =6 500,000L =7 1,000,000 1000 3.3: ff L =6 (3.42) (3.45) ff 0.003399802572 0.003398625966 53
3.22: f n 54
3.23: (3.45) (L=6) 55
3.9.7 (3.42) (3.45) 56
3.10 Lempel-Ziv 3.10.1 Lempel-Ziv 0 1 Lempel-Ziv 3.10.2 " :01 n : W (n) : 3.10.3 n NIST 10 6 bit 3.10.4 Step1 0 1 n " = " 1 ;" 2 ;:::;" n (" i 20; 1;i = 1; 2; ;n) W (n) W (n) E[W (n)] Step2 W (n) ff[w (n)] 0.01P value P value = 1 ψ! E[W (n)] W (n) 2 erfc p 2ff 2 (3.46) P value 0.01 W (n) E[W (n)] ff 2 [W (n)] NIST n E[W (n)] = n!1 lim log 2 n ff 2 [W (n)] ß n[c + ffi(log 2 n)] C =0:26600jffi()j < 10 6 log 3 2 n (3.47) (3.48) 57
3.10.5 n =10 6 bit W (n) E[W (n)] ff 2 [W (n)] (3.47)(3.48) E[W (n)] = 50171:66594ff 2 [W (n)] = 33:59365 [6]NIST G-Using SHA-1 Blum-Blum-Shub E[W (n)] = 69588:20190000 ff 2 [W (n)] = 73:23726011 3.10.6 W (n) n 10 6 bit W (n) NIST G-Using SHA-1 1000 NIST (3.47) (3.48) 58
3.24: n =10 6 bit W(n) NIST 3.25: n =10 6 bit NIST 59
3.10.7 3.243.25 W (n) NIST NIST n =10 6 bit NIST 60
3.11 3.11.1 M 3.11.2 n : " : "=" 1," 2,," n M : K : K 6 χ 2 (obs) : 3.11.3 NIST n 10 6 bit, M 500»M»5000 3.11.4 Step1 n M N = b n M c Step2 Berlekamp-Massey N L i L i i LFSR L i L i +1 Step3 μ μ = M +1 M 9+( 1)M + + 2 3 9 (3.49) 2 36 2 M Step4 1» i» N T i T i =( 1) M (L i μ)+ 2 9 (3.50) Step5 T i 1 ν 0 ν 6 61
ν i T i ν 0 T i» 2:5 ν 1 2:5 <T i» 1:5 ν 2 1:5 <T i» 0:5 ν 3 0:5 <T i» 0:5 ν 4 0:5 <T i» 1:5 ν 5 1:5 <T i» 2:5 ν 6 T i > 2:5 T i ν i Step6 χ 2 (obs) χ 2 (obs) = KX i=0 (ν i Nß i ) 2 Nß i (3.51) ß i ß 0 =0.01047, ß 1 =0.03125, ß 2 =0.125, ß 3 =0.5, ß 4 =0.25, ß 5 =0.0625, ß 6 =0.02078 Step7 χ 2 (obs) χ 2 (obs) 0.01P value P value = igamcf K 2 ; χ2 (obs) g (3.52) 2 P value 0.01 3.11.5 n 2 s n L(s n )=L n n EL(s n ) [18] (L n μ n )=ffi n n 2 1 n T n =( 1) n [L n ο n ]+ 2 9 ο = n 2 + 4+r n 18 (3.53) (3.54) 62
T (3.56) P (T =0)= 1 2 (3.55) P (T = k) = 1 (k =1; 2; ) 22k (3.56) P (T = k) = 1 (k = 1; 2; ) 2jkj+1 2 (3.57) P (T k>0) = k» 0 (3.57) P (T» k) = 1 3 2 2k 2 (3.58) 1 3 2 2jkj 1 (3.59) T obs P-value k [jt obs j]+1p-value 1 3 2 + 1 2k 1 3 2 = 1 (3.60) 2k 2 2 2k 1 P-value n MN n M N (3.53) T M M K +1N T M K +1 ν 0 ;ν 1 ; ;ν K ν 0 + ν 1 + + ν K = N ß 0 ;ß 1 ; ;ß k (3.56) (3.57) (3.56) (3.57) M M 500 500» M» 5000 M χ 2 K P-value 1 ( K 2 )2 K 2 Z 1 χ 2 (obs) ψ! e u K K 2 u 2 1 du = igamc 2 ; χ2 (obs) 2 χ 2 (3.61) Nminß i 5 (i =0; 1; ;K) (3.62) 63
M N (K 6) (T» 2:5)( 2:5 <T» 1:5)( 1:5 <T» 0:5)( 0:5 <T» 0:5) (0:5 <T» 1:5)(1:5 <T» 2:5) (T >2:5) ß 0 =0:0147ß 1 =0:03124ß 2 =0:12500ß 3 = 0:50000ß 5 =0:6250ß 6 =0:020833 0.00410.04320.19440.28630.0135 3.11.6 χ 2 (obs) n 10 6 bit,m 500,1000 χ 2 (obs) NIST G-Using SHA-1 1000 64
«3.26: M=500 «3.27: M=1000 65
3.11.7 66
3.12 3.12.1 m m 3.12.2 m: n: ":0 1 " =(" 1 ;" 2 ; " n ) 5ψ 2 m 52 ψ 2 m: m 3.12.3 NIST m n m<blog 2 nc 2 3.12.4 Step1 " (m-1) " 0 Step2 m i 1 ;i 2 ; i m ν i1 i m (m-1) (m-2) ν i1 i m 1,ν i1 i m 2 Step3 ψ 2 m = 2m n X i 1 ;i 2 ; i m (ν i1 i m n 2 m )2 = 2m n X i 1 ;i 2 ; i m ν 2 i 1 i m n (3.63) 67
ψ 2 m 1 = 2m 1 n ψ 2 m 2 = 2m 2 n X i 1 ;i 2 ; i m 1 X i 1 ;i 2 ; i m 2 Step4 (ν i1 i m 1 n 2 m 1 )2 = 2m 1 n (ν i1 i m 2 n 2 m 2 )2 = 2m 2 n X i 1 ;i 2 ; i m 1 X i 1 ;i 2 ; i m 2 ν 2 i 1 i m 1 n (3.64) ν 2 i 1 i m 2 n (3.65) 5ψ 2 m = ψ 2 m ψ 2 m 1 (3.66) 5 2 ψ 2 m = ψ 2 m 2ψ 2 m 1 + ψ 2 m 2 (3.67) Step5 5ψ 2 m 52 ψ 2 m χ2 5ψ 2 m,52 ψ 2 m χ 2 ( 0.01) P-value P value1=igamc(2 m 2 ; 5ψ 2 m=2) (3.68) P value2=igamc(2 m 3 ; 5 2 ψ 2 m=2) (3.69) P-value 0.01 3.12.5 Serial Test " 0 =(" 1 ;" 2 ; " n ;" 1 ;" 2 ; ;" m 1 ) i 1 ;i 2 ; ;i m 0 1 2 m (i 1 ;i 2 ; ;i m ) ν i1 ;i 2 ; ;i m (3.63) ψm 2 χ2 ν i1 ;i 2 ; ;i m χ 2 χ 2 (3.66),(3.67) 5ψm 2 2m 1 χ 2 5 2 ψm 2 2m 2 χ 2 [16] [17] [18] 5ψm 2 χ2 Good [19] 3.12.6 5ψ 2 m,52 ψ 2 m χ2 NIST G-Using SHA-1 1,000,000 1000 NIST 68
5ψ 2 m 2m 1 5 2 ψ 2 m 2m 2 χ 2 m =23 16 69
m=2 1:5ψ 2 m 2:5 2 ψ 2 m 70
m=3 3:5ψ 2 m 4:5 2 ψ 2 m 71
m=16 k k>30 p 2X p 2k 1 [22] X 5:5ψm 2 6:5 2 ψ 2 m 72
3.12.7 73
3.13 3.13.1 m m 3.13.2 m: n: ":0 1 " =(" 1 ;" 2 ; " n ) χ 2 (obs): ApEn(m) χ 2 3.13.3 NIST m,n m<blog 2 nc 2 3.13.4 Step1 " (m-1) n m Step2 m ]i i m 2 Step3 i Ci m = ]i n Step4 ffi (m) = 2X m 1 i=0 74 C m i log C m i (3.70)
Step5 m=m+1 Step1 Step4 Step6 χ 2 =2n[log 2 ApEn(m)] (3.71) ApEn(m) =ffi (m) ffi (m+1) (3.72) Step7 χ 2 χ 2 χ 2 χ 2 ( 0.01) P-value P value = igamc(2 m 1 ; χ2 2 ) (3.73) P-value 0.01 3.13.5 (1996) Pincus Singer [20]Yi(m) =(" i ; ;" i m 1) C m i = 1 n +1 m ]fj :1» j<n m; Y j(m) =Y i (m)g = ß` (3.74) Φ (m) = X n+1 m 1 n +1 m i=1 log C m i (3.75) Ci m Y i (m) Φ (m) m 2m Φ (m) = 2 m X `=1 ß` log ß` (3.76) ß` ` =(i 1 ;:::;i m ) m(m 1) ApEn ApEn(m) =Φ (m) Φ (m+1) (3.77) 75
ApEn(0) Φ (1) ApEn(m) 1 m ApEn(m) [20] Pincus and Kalman(1997) ApEn(m) m-irregular(m-random) eß p 2 p 3 2 10 ApEn(m)m =0; 1; 2 p 3 ß m () ApEn(m) log 2 n[log 2 ApEn(m)] 2m 2 Rukhin(2000) χ 2 (obs) =n[log2 ApEn(m)] P-value igamc(2 m 1 χ2 (obs) (3.78) 2 (" 1 ;:::;" n " 1 ;:::;" m 1 ) ν i1 :::i m (i 1 ;:::;i m ) ~Φ (m) = X i 1 :::i m ν ii :::i m log ν ii :::i m (3.79) Ap ~ En(m) = ~ Φ (m) ~ Φ (m+1) (3.80) Jensen s m log s Ap ~ En(m) log s<apen(m) (s =2) log s n = S m m n ApEn(m) m n Φ (m) ~Φ (m) Pincus 3.13.6 χ 2 χ 2 NIST G-Using SHA-1 1,000,000 1000 NIST 2 m χ 2 76
1:m=2 2:m=3 77
k k>30 p 2X p 2k 1 [22] X 2 3:m=10 4:m=11 78
5:m=12 6:m=13 79
6:m=14 3.13.7 n =100 m>12 m 2 m n 1 n 2 m m n=100,m=14 NIST m<blog 2 nc 2 m> blog 2 nc 5 n=100 m<12 m<blog 2 nc 7 80
3.14 3.14.1 0 1-11 1 3.14.2 n " 0 1 "=" 1," 2,...," n z -1,+1 3.14.3 n = 100bit 3.14.4 Step1 " 0,1 X i =2" i 1-1 +1 X i Step2 X S i mode=0 X 1 mode=1 X n Step3 z=max 15k5njS k j max 15k5njS k j S k Step4 z (3.84) z ( 0.01) P value P value =1 ( n z X 1)=4 k=( n z +1)=4 Φ( X ( n z 1)=4 k=( n z 3)=4 Φ( (4k +1)z p n ) Φ( (4k 1)z p )+ n (4k +3)z (4k +1)z p ) Φ( p ) n n (3.81) P value 0.01 81
Φ(z) = 1 p 2ß Z z 1 expf u2 gdu (3.82) 2 3.14.5 ±1 1 0 0 1 S 0 k = X n + :::+ X n k+1 max 1»k»n js k j ψ max15k5njs lim P k j p n!1 n! 5 z = p 1 Z z 2ß z 1X = 4 ß j=0 ( ( 1) j 2j +1 exp ) 1X ( 1) k (u 2kz)2 exp ( du 2 ) (2j +1)2 ß 2 = H(z) z >0 8z 2 k= 1 (3.83) max 1»k»n js k j(obs)= p n z P-value (3.84)(3.87) G(z) 1 H(max 1»k»n js k j(obs)= p n)=1 G(max 1»k»n js k j(obs)= p n) (3.83) H(z) z H(z) G(z) G(z) = p 1 Z z ) 1X ( 1) k (u 2kz)2 exp ( du 2ß z 2 = 1X k= 1 =Φ(z) Φ( z)+2 =Φ(z) Φ( z)+2 1X k=1 k= 1 ( 1) k Φ((2k +1)z) Φ((2k 1)z) (3.84) 1X k=1 ( 1) k Φ((2k +1)z) Φ((2k 1)z) 2Φ((4k 1)z) Φ((4k +1)z) Φ((4k 3)z) (3.85) 82
ß Φ(z) Φ( z) 22Φ(3z) Φ(5z) Φ(z) (3.86) ß 1 p 4 expf z2 g z!1 (3.87) 2ßz 2 (z) (3.84) k H(z) = 1X k= 1 Φ((4k +1)z) Φ((4k 1)z) 1X k= 1 Φ((4k +3)z) Φ((4k +1)z) (3.88) Revesz(1990)p.17 2.6 [24] P max 15k5njS k j = z =1 1X k= 1 + P ((4k 1)z <S n < (4k +1)z)) 1X k= 1 P ((4k +1)z<S n < (4k +3)z)) (3.89) (3.81) P-value 1 H(z) (3.89)(3.88) 3.14.6 z n 1001,00010,000100,0001,000,000bit mode=0mode=1 z (3.84) k =1 (3.85) (3.84) k =3 NIST G-Using SHA-1 1000 83
w 3.28: 100bit(mode=0) w 3.29: 100bit(mode=1) 84
w 3.30: 1000bit(mode=0) w 3.31: 1000bit(mode=1) 85
w 3.32: 10000bit(mode=0) w 3.33: 10000bit(mode=1) 86
w 3.34: 100000bit(mode=0) w 3.35: 100000bit(mode=1) 87
w 3.36: 1000000bit(mode=0) w 3.37: 1000000bit(mode=1) 88
3.14.7 89
3.15 3.15.1 0 1-1 1 0 0 1 8 (-4-114) x 3.15.2 n " 0 1 "=" 1," 2,...," n χ 2 (obs) χ 2 3.15.3 n = 10 6 bit 3.15.4 Step1 " 0,1 X i =2" i 1-1 +1 X i Step2 X X 1 S i S =S i Step3 S 0 S 0 S 0 = 0;s 1 ;s 2 ;:::;s n ; 0 Step4 J J S 0 0 J 0 J<500 Step5 8 x( 4 5 x 5 1; 1 5 x 5 4) x Step6 8 x ν k (x) ν k (x) x k (0 5 k 5 5) ν 5 (x) x 5 Step7 8 x χ 2 (obs) 90
χ 2 (obs) = 5X k=0 (ν k (x) Jß k (x)) 2 Jß k (x) (3.90) ß k (x) x k ß k (x) 1 1 jxj ß 0 (x) ß 1 (x) ß 2 (x) ß 3 (x) ß 4 (x) ß 5 (x) 1 0.5000 0.2500 0.1250 0.0625 0.0312 0.0312 2 0.7500 0.0625 0.0469 0.0352 0.0264 0.0791 3 0.8333 0.0278 0.0231 0.0193 0.0161 0.0804 4 0.8750 0.0156 0.0137 0.0120 0.0105 0.0733 Step8 χ 2 (obs) χ 2 χ 2 (obs) χ 2 ( 0.01) P value ψ! 5 P value = igamc 2 ; χ2 (obs) (3.91) 2 P value 0.01 3.15.5 J lim n!1 P ψ Jpn <z! = s 2 Z z e u2 2 du; z>0 (3.92) ß 0 J P value J J<500 J<500 91
x k ß k (x) ß 0 (x) =1 1 2jxj ß k (x) = 1 ψ 1 1! k 1 k =1; 2; 3; 4 (3.93) 4x 2 2jxj ß 5 (x) = 1 ψ 1 1! 4 2jxj 2jxj ß k (x) χ 2 (obs) (3.90) χ 2 (obs) 5 χ 2 P value 1 P (3.91) ψ! 5 2 ; χ2 (obs) 2 (3.94) 3.15.6 χ 2 (obs) χ 2 n 10 6 bit χ 2 (obs) χ 2 NIST G-Using SHA-1 1000 92
3.38: x=-4 3.39: x=-3 93
3.40: x=-2 3.41: x=-1 94
3.42: x=1 3.43: x=2 95
3.44: x=3 3.45: x=4 96
3.15.7 97
3.16 3.16.1 0 1-1 1 18 (-9-1,19) x 3.16.2 n " 0 1 "=" 1," 2,...," n ο(x) 3.16.3 n 10 6 bit 3.16.4 Step1 " 0,1 X i =2" i 1-1 +1 X i Step2 X X 1 S i S =S i Step3 S 0 S 0 S 0 = 0;s 1 ;s 2 ;:::;s n ; 0 S 0 J Step4 ο(x) ο(x) 9» x» 1; 1» x» 9 18 x x S 0 Step5 ο(x) ο(x) ( 0.01) P value P value = erfc 0 @ q 1 jο(x) Jj A (3.95) 2J(4jxj 2) P value 0.01 98
3.16.5 J J<500 J<500 ο(x) J J(4jxj 2) (3.96) 0 1 lim P @ ο J(x) J J!1 qj(4jxj 2) <z A =Φ(z) (3.96) P value (3.95) 3.16.6 ο(x) n 10 6 bit ο(x) NIST G-Using SHA-1 1000 99
u š 3.46: x=-9 u š 3.47: x=-8 100
u š 3.48: x=-7 u š 3.49: x=-6 101
u š 3.50: x=-5 u š 3.51: x=-4 102
u š 3.52: x=-3 u š 3.53: x=-2 103
u š 3.54: x=-1 u š 3.55: x=1 104
u š 3.56: x=2 u š 3.57: x=3 105
u š 3.58: x=4 u š 3.59: x=5 106
u š 3.60: x=6 u š 3.61: x=7 107
u š 3.62: x=8 u š 3.63: x=9 108
3.16.7 x z ο(x) J<500 1000 362 638 x ο(x) x x x -9-8 -7-6 -5-4 -3-2 -1 ο(x) 724320 724656 727084 727097 726615 728543 731701 733840 736210 x 1 2 3 4 5 6 7 8 9 ο(x) 736646 735149 733854 732732 730265 731111 731215 729142 728680 109
4 SP 800-22 16 Generator-Using SHA-1 SP 800-22 ffl Generator-Using SHA-1 ffl DFT Lempel-Ziv DFT Lempel-Ziv 110
1. 2. 3. 4. 5.2 6.DFT 1 7. 8. 9.Maurer 10.Lempel-Ziv 2 11. 12. 13. 3 14. 15. 16. 1 2 3 111
[1] NISTSpecial Publication 800-22 A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications http://csrc.nist.gov/rng/sp800-22b.pdf http://csrc.nist.gov/rng/errata2.pdf [2] NISTSpecial Publication 800-22 NIST Statistical Test Suite http://csrc.nist.gov/rng/sts-1.5.tar http://csrc.nist.gov/rng/rng2.html [3] Randomness Test using Discrete Fourier Transform 6841 15 9 [4] NIST Vol.103 No.499 ISEC2003-872003-12 [5] NIST SP800-22 DFT Vol.104 No.200 ISEC2004-502004-07pp.61-642004 [6] Lempel-Ziv http://www.ipa.go.jp/security/enc/cryptrec/fy15/documents/ rep ID0206.pdf http://cryptrec.nict.go.jp/pdf/wat-rep2003/rep ID0206.pdf [7] http://www.ipa.go.jp/security/enc/cryptrec/fy15/documents /rep ID0207.pdf http://cryptrec.nict.go.jp/pdf/wat-rep2003/rep ID0207.pdf [8] http://www.ipa.go.jp/security/fy14/crypto/pseudo rundum/ 112
rundum inve.pdf [9] I.N.Kovalenko(1972), "Distribution of the linear rank of a random matrix", Theory of Probability and its Applications.17,pp.342-346. [10] G.Marsaglia and L.H.Tsay(1985), "Matrices and the structure of random number sequences", Linear Algebra and its Applications.Vol.67,pp.147-156. [11] O.Chrysaphinou and S.Papastavridis, A Limit Theorem on the Number of Overlapping Appearances of a Pattern in a Sequence of Independent Trials.",Probability Theory and Related Fields,Vol.79(1988),pp.129-143 [12] Ueli M.Maurer, A Universal Statistical Test for Random Bit Generators",Journal of Cryptology.Vol.5,No.2,1992,pp.89-105 [13] J-S Coron and D.Naccache, An Accurate Evaluation of Maurer's Universal Test",Proceedings of SAC'98(Lecture Notes in Computer Science),Berlin:Springer-Verlag,1998 [14] H.Gustafson, E.Dawson, L.Nielsen, and W.Caelli (1994), "A computer package for measuring the strength of encryption algorithms," Computers and Security.13, pp.687-697. [15] R.A. Rueppel, Analysis and Design of Stream Ciphers. New York: Springer, 1986. [16] M.Kimberley(1987), "Comparison of two Statistical tests for keystream sequences", Electronics Letters.23,pp.365-366. [17] D.E.Knuth, "The Art of Computer Programming.Vol.2,3rd ed.reading", Addison-Wesley,Inc.,pp.61-80 [18] A.J.Menezes,P.C.van Oorschot,and S.A.Vanstone(1997), "Handbook of Applied Cryptography.Boca Raton, FL", CRC Press,p.181 [19] I.J.Good(1953), "The serial test for sampling numbers and other tests for randomness", Proc.Cambridge Philos.Soc.. 47,pp.276-284 [20] S.Pincus and B.H.Singer,"Randomness and degrees of irregularity",proc.natl.acad.sci.usa.vol93,march 1996,pp.2083-2088. [21] A.Rukhin(2000),"Approximate entropy for testing randomness",journal of Applied Probably.Vol.37,2000 [22] 113
[23] Frank Spitzer,"Principles of Random Walk"Princceton, Van Nostrand, 1964(especially p.269) [24] Pal Revesz, "Random Walk in Random And Non-Random Environments" Singapore, World Scientific, 1990 [25] NIST Randomness Testing of the Advanced Encryption Standard Candidate Algorithms http://csrc.nist.gov/rng/aes-report2.doc [26] NIST Randomness Testing of the Advanced Encryption Standard Finalist Candidates http://csrc.nist.gov/rng/aes-report-final.doc [27] G.Marsaglia DIEHARD (http://stat.fsu.edu/geo/diehard.html [28] D.E.Knuth The Art of Computer Programming Vol Seminumerical Algorithms Third Edition Addison Wesley [29] [30] NISTFIPS PUB 186-2 Digital Signature StandardDSS http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf, 2000 114