Akito Niwa Kouya Tochikubo ( ) SI Systems Integration Technology Center, Toshiba Solutions Corporation 1 [1-10] IPA FIPS $[2,

Size: px

Start display at page:

Download "Akito Niwa Kouya Tochikubo ( ) SI Systems Integration Technology Center, Toshiba Solutions Corporation 1 [1-10] IPA FIPS $[2,"

たしろうこいたばし
5 years ago
Views:

1 Akito Niwa Kouya Tochikubo ( ) SI Systems Integration Technology Center, Toshiba Solutions Corporation 1 [110] IPA FIPS 1402 $[2, 3]$ FIPS 1402 NIST Special Publication 80022(SP80022) $[5,6]$ NIST SP T 5 21 The Art of Computer programming, / Knuth The Art of Computer programming, / [1] 12 Kl (frequency test) K2 (2 )(seri test) K3 (gap test) K4 (poker test)

2 81 K5 \ddagger L (coupon collector s test) K6 (permutation test) K7 (run test) K8 $t$ $t$ (maximumof test) K9 (collosion test) K1O (serial correlation test) Kll K12 [1] $[0, 1)$ $<u_{n}>=0,$ $u_{1},$ $u_{2},$ $\cdots$ 0 $d1$ $<u_{n}>$ $U_{\dot{*}}>=\lfloor du_{i}\rfloor$ $<U_{n}>=U_{0},$ $U_{1},$ $U_{2\prime}\cdots$ $[0, 1)$ $u_{n}>$ 0 $d1$ $<U_{n}>$ 2 $<U_{n}>$ ( ) 0 1 $(d=2)$ 22 FIPS PUS 1402 FIPS PUS 1402 [2] $\text{ }$ 4 Fl 1 (monobit test) F2 (poker test) F3 (runs test) F4 (longest runs test) [2] FIPS PUS 1402 Change Notice 2[3] 23 [4] 7 Rl 1 R2 2 R3 R4 OPSO R6

3 $\sigma^{2}$ 82 R7 [4] [1] $[0, 1)$ $<u_{\iota},>$ 0 $d1$ $<U_{n}>$ 2 24 NIST Special Publication NIST Special Publication 80022[5] 16 Nl 1 (frequency test) N2 (frequency test within ablock) N3 (runs test) N4 (test for longest run of ones in ablock) N5 2 (binary matrix rank test) N6 (discrete fourier transform (spectral)test) N7 (nonoverlapping template matching test) N8 (overlappiug template match $\mathrm{g}$ test) N9 Maurer (Maurer s universal statistical test) N1O LempelZiv (LempelZiv compression test) Nll (linear complexity test) N12 (serial test) N13 (approximate entrow test) N14 (cumulative sums (cusums) test) N15 (random excursions test) N16 (random excursions variant test) NIST 0 1 NIST $p$value $0$ $p$value pvalue $X_{1},$ $X_{2_{\mathit{1}}}\cdots,$ $X_{n}$ 1 $1,$ 1 $n$ $S_{1},=X_{1}+X_{2}+=\cdot\cdot+Xn$ 2 $\mu$ $=$ 0 $=$ $n$ $n arrow!\mathrm{f}\mathrm{f}\mathrm{i}p(\frac{s_{n}}{\sqrt{n}}\leq z)=\phi$ (z) $\Phi(z)=\int_{\infty}^{z}\frac{1}{\sqrt{2\pi}}e^{x^{2}/2}dx$

4 Using 83 3 $s= S_{n} /\sqrt{n}$ $P(s\leq z)=2\phi(z)1$ $\Psi \mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}=2[1\phi(s)]$ NIST $\Phi(z)$ $erfc(z)= \int_{\sim^{\nu}}$ $\frac{2}{\sqrt{\pi}}e^{x^{2}}d\prime x$ $I^{\succ \mathrm{v}\mathrm{a}1\mathrm{u}\mathrm{e}=erfc(s}/\sqrt{9})$ $;t$ $r\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{u}\mathrm{e}<001$ NIST 2 pvalue $\int_{\mathrm{z}}^{\infty}\frac{1}{2\gamma(\frac{n}{2})}(\frac{t}{2})^{\kappa}\tau^{1}e^{\#}dt$ $N$ $\chi^{2}$ $\Gamma(\alpha)=\int_{0}^{\infty}x^{\alpha1}e^{x}dx$ NIST 1 $\mathrm{a}^{\mathrm{a}_{\text{ }}}$ (NIST 10 ) 1 $p$value $A?\cdot p$value $p$value $[0, 1)$ $[0, 1)$ $p$value $m$ 001 $p$value $099\pm\sqrt{\frac{099\mathrm{x}001}{m}}$ $\iota NIST 0$ 1 ASCII NIST NIST 1 $\mathrm{g}$ SHAI(FIPS 186 SHAI ) 2 Linear Congruential 3 BlumBlumShub 4 MicaliSchnorr 5 Modular Exponentiation 6 Quadratic Congruential I 7 Quadratic Congruential II 8 Cubic Congruential 9 XOR

5 Using ANSI X917 (3DES) DES(FIPS 186 DES ) 11 $\mathrm{g}$ 1 (1 ) , 6 ( ) finalanalysisreport 25 DIEHARD DIEHARD [7] T 18 Dl (b hday spacings test) D2 OPERM5 (overlapping 5 permutation test) D3(3lx31) 2 (binary rank test for matrices) $31\mathrm{x}31$ D4 $(32\mathrm{x}32)$ D5 $(6\mathrm{x}8)$ D6 2 (binary rank test for matrices) $32\mathrm{x}32$ $6\mathrm{x}8$ 2 (binary rank test for (bitstream Test) matrices) D7 OPSO (OPSO(OverlappingPairsSparseOccupancy) test) D8 OQSO (OQSO( test) D9 DNA (DNA test) D1O 8 (countthel s test on astream of bytes) Dll 8 (countthel s test for specific bytes) D12 (parking lot test) D13 (minimum distance test) D14 $3\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{H}\mathrm{E}\mathrm{R}\mathrm{E}\mathrm{S}$ ( $3\mathrm{d}$spheres test) D15 (squeeze test) D16 (overlapping sums test) D17 (runs test) D18 (cra test) DIEHARD 0 1 lombyte llmbyte DIEHARD $\mu$value r ue $[0, 1)$ $\}^{}$ pvalue DIEHARD rvalue DIEHARD 1 2 3, DIEHARD 0 1 ASCII

6 generator \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{h}rightarrow \mathrm{b}\mathrm{o}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{w}$ (SWB) 85 1 Mulfiplywithcarry (MWC) generator (MWC generator) $1\mathrm{C}$ 2 4 on pairs of 16 bits(mwc1616 generator) 3 :Mother of all random number generators (MOTHER generator) 4 KISS generator 5 Simple but very good generator COMBO (COMBO generator) 6 Lagged FibonacciMWC combination ULTRA (ULTLA generator) $\mathrm{m}\mathrm{w}\mathrm{c}/\mathrm{s}\mathrm{w}\mathrm{b}$ $\mathrm{m}\mathrm{w}\mathrm{c}/\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{t} 7 Combination generator ( generator) 8 Extended congruential generator (EXCONG generator) 9 SuperDuper generator (SUPERDUPER generator) 10 Subtractwithborrow generator (SWB generator) 11 Specified congruential generator 12 31bit generator ran2 from Numerical Recipes (RAN2 generator) 13 Specified shiftregister generator 14 System generator in Microsofi Fortran ( MSRAN generator) 15 LaggedFibonacci generator 16 Inverse congruential generator (INVCONG generator) 3 2 $ $ ( (SP80022) 0 1 $\{X_{i}\}$ $X_{:}\neq X_{:+1}$ $d1$ 5 $(1)5$ $(2)3$ 4 (3) 2 3 (4) 1 (5) 5 2 FIPS 14&2 4

7 $m$ $m$ $m$ 6 2 $\mathrm{y}$ $u=\mathrm{y}/2^{32}$ $[0, 1)$ $k$ $k=2^{31}$ $karrow\lfloor k\mathrm{x}u\rfloor$ $k=1$ 43 2 $\mathrm{y}$ $u=\lfloor \mathrm{y}/2^{32}\mathrm{x}6\rfloor+1$ $u$ Craps Craps , OPERM $(6\mathrm{x}8)$ $(31 $(32\mathrm{x}32)$ 2 $(6\mathrm{x}8)$ \mathrm{x}31)$ $(31\mathrm{x}31)$ $(32\mathrm{x}32)$ $M$ 7 2 $M$ FIPS $m$ 1

8 $\mathrm{y}_{1}$,, Y4 ), $[0, 1)$ $[0, 1)$ $k$ $k$ 2 $\mathrm{y}$ u=l Y/ $\mathrm{y}$ $u=10000\mathrm{y}/2^{32}$ $3\mathrm{D}\mathrm{S}\mathrm{P}\mathrm{H}\mathrm{E}^{1}$RES $\mathrm{y}$ $u=1000\mathrm{y}/2^{32}$ $2^{21}$ $(X_{1}, X_{2}, \cdots, X_{20})_{\text{ }}2$ $(X_{2}, X_{3}, \cdots, X_{21})$ 1 OPSO $\mathrm{y}$ $2^{21}1\mathrm{H}$ $(\mathrm{y}_{1}, \mathrm{y}_{2})$ $\mathrm{y}_{2},$ $\cdots$ $(\mathrm{y}_{2}, \mathrm{y}_{3}),$ $\cdots$, OQSO $Y$ $\mathrm{y}_{1},$ $\rangle$ $\mathrm{y}$2 $(\mathrm{y}_{1}, \mathrm{y}_{2}, \mathrm{y}_{3}, Y_{4}),$ $\mathrm{y}_{2}$ $\mathrm{y}_{3\mathrm{t}}$ $\mathrm{y}_{5}$ $\cdots$ (, 4 5, 4 $^{21}$ 5 DNA $\mathrm{y}$ $\mathrm{y}_{2},$ $\cdots$ $(\mathrm{y}_{1}, \mathrm{y}_{2}, \cdot\cdot\sim, \mathrm{y}_{10}),$ $(\mathrm{y}_{2}, \mathrm{y}_{3}, \cdots, \mathrm{y}_{11}),$ $\cdots$ }1, 10 2 $2^{21}$ $d1$ $n$ 0 $d1$

9 $\cdot$ 88 0 $d1$ 0 $d1$ $Z$ $Z_{\dot{\iota}}$ $\{\mathrm{y}_{1}\}$ $Z_{1},$ $Z_{2},$ $\cdots,$ $Z_{1024}$ 1,023 $Y_{i}$ $s$ $t$ $[0, 1)$ $l$ $Y_{1},$ $\mathrm{y}$2, $(\mathrm{y}_{1},$, $\mathrm{y}_{100})$ $\rangle$ $\mathrm{y}$2, (Y2, $\mathrm{y}$3i, ), $\mathrm{y}_{101}$ $\cdots$ $X_{1},$ $X_{2},$ $\cdots X_{r\iota}$ $S_{\dot{l}}= \sum_{j=1}^{\dot{\iota}}(2x_{j}1)$ 1) $(1 \leq i\leq n)$ $S_{\dot{l}} = \sum_{j= \iota:+1}^{n}$(2x 0 1 $X_{1},$ $X_{2},$ $\cdots X_{n}$ $ 4\sim 1_{\text{ }}$ $S_{1}$ $=0$ 0 1 $1\sim 4$ 8 $S_{\dot{*}}= \sum \mathrm{j}_{=\iota}(2x_{j}1)(1\leq i\leq n)$ 0 1 $X_{1},$ $X_{2,}\ldots \mathrm{y}_{n}$ $S_{i}= \sum_{j=1}^{\dot{ }}(2X_{j}1)(1\leq i\leq \mathrm{z})$ 9 $\sim$ 1 1\sim E Maurer $L$ 0 1 kmpelziv 0 1 mpleziv 0 1 $m$ $m1$ $m2$ 0 1 $m$ $m+1$

10 $\text{ }$ $\text{ }$ $\text{ }$ $\mathrm{d}\backslash$ 0 1 $M$ \iota $\mathrm{a}_{\text{ }}$ 36 $U_{j+1}$ $U_{j}$ $c= \frac{n(u_{0}u_{1}+u_{1}u_{2}+\cdots+u_{n2}u_{n1}+u_{n1}u_{n})(u_{0}+u_{1}+\cdots+u_{n1})^{2}}{n(u_{0}^{2}+u_{1}^{2}+\cdots+u_{n1}^{2})(u_{0}+u_{1}+\cdots+u_{n1})^{2}}$ (1) $1\leq C\leq 1$ $C=0$ $<U_{n}>$ $\mathrm{c}$ NIST DIEHARD NIST DIEHARD $\mathrm{s}\mathrm{p}8w2$ 2 DIEHARD 8 8 $\mathrm{o}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{m}5$ OPSO OQSO

11 $\lceil \mathrm{i}\mathrm{p}\mathrm{a}$ 80 2 $X_{:}=aX_{\dot{\mathrm{s}}1}+c\mathrm{m}$od $M$ (Linear Congruential) [1117] FIPS1402 FIPS SP80022 SP IPA $\mathrm{t}1$ 0 ASCII 2 52 GUI <GUI ( 3) (GUD ( )

12 $\mathrm{s}$ ) $\mathrm{t}$ $\dagger$ 81 $\cdot$ $\wedge^{\ulcorner}=,_{} $ $\mathrm{t}$ bf $\mathrm{t}$ $\mathrm{t}$ $\mathrm{t}$ JAPA \dagger 1: 2: (PDS) 6 NIST [5] DIEHARD [7]

13 \mathrm{o}\mathrm{u}\mathrm{r}\mathrm{c}\mathrm{e}/\mathrm{c}\mathrm{r}y\mathrm{p}\mathrm{t}\mathrm{x}/$ \mathrm{i}\mathrm{c}\mathrm{a}\mathrm{l}$ Jgorithms, mat 92 3: (IPA) 13 $\mathrm{s}\mathrm{e}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{u}\mathrm{m}\alpha [1] D Knuth, The art of computer programming, [2] NIST, FIPS PUB 1402, Security requirements for cryptographic modulae, [3] NIST, FIPS PUB 1402, Change Notice 2, 2002 [4],, [5] NIST, Special Publication 80022, A Statistical Test Suite For Random and Pseudorandom Number Generators for Cryptographic Applications, 2001 [6] NIST, Special Publication $ $ NIST Statistical Suite, $800\cdot 22,$ $//\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{t}\mathrm{f}\mathrm{s}\mathrm{u}\mathrm{e}\mathrm{d}\mathrm{u}/\mathrm{g}\mathrm{e}\mathrm{o}/\mathrm{d}\mathrm{l}\mathrm{e}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{d}$ [7] G Marsaglia, $ $(DIEHARD, (http: html, $\mathrm{f}\mathrm{s}\mathrm{u}\mathrm{e}\mathrm{d}\mathrm{u}/\mathrm{p}\mathrm{u}\mathrm{b}/\mathrm{d}\mathrm{l}\mathrm{e}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{d}/$ ) $//\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{m}$ $\mathrm{a}\mathrm{t}/\mathrm{t}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{s}/$ [8] P Hellekalek, Tests for random numbers, (http: sbg ac ) [9] J Walker, A Pseudorandom Number Sequence Test Program, (http: $//\mathrm{w}\mathrm{w}\mathrm{w}$ fouznilab $\mathrm{c}\mathrm{h}/\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{o}\mathrm{n}/$) [10] The Information Security Research Centre at Queensland University of Technoloy, CryptX, $//\mathrm{w}\mathrm{w}\mathrm{w}$ $\mathrm{a}\mathrm{u}/\mathrm{r}\mathrm{e}\epsilon (http: isrc qut edu ) [11] J A Reeds, Cradcing multiplocative congruential encryption algorithm, in Information Linkage Between Applied Mathematics and Industry, PCC Wang, ed, Academic Press, pp467472, 1979

14 $\iota\lceil 15]$ H 93 [12] J A Reeds, Solution of challenge cipher, Cryptologia, $\mathrm{v}\mathrm{o}\mathrm{l}$ $3,$ No 2, pp8395, 1979 $23\mathrm{r}\mathrm{d}$ [13] J B Plumstread, Inferring a sequence generated by a linear congruence, Proceedings of the IEEE Symposium on the Foundatiorls of Computer Science, pp153159, 1982 $\mathrm{j}\mathrm{c}$ [14] Lagarias and J Reeds, Unique extrapolation of polynomial recurrences, SIAM Joumal on Computing, Vol 17 No 2, pp342362, 1988 Krawczyk, How to predict congruential generators,, Advances in CryptologyCRYPTO 89, pp138153, 1990 $\mathrm{a}\mathrm{m}$ [16] Frieze, J Hastad, R Kannan, J C Lagarias and A Shamir, Reconstracting truncated integer variables satisfying linear congruences, SIAM Journal on Computing, Vol 17, No 2, pp262280, 1988 [17] J Stern, Secret linear congruential generators are not cryptographically Secure, Proceedings of the 28th Symposium on the Foundations of Computer Science, pp421426, 1987

Microsoft Word - HM-RAJ doc

Microsoft Word - HM-RAJ doc NIST 及び DIEHARD テストによる RPG100 乱数評価 FDK( 株 )RPG 推進室 2003/12/16 導入 RPG100 から生成される乱数を 2 つの有名なテストを用いて評価します一方は米国機関 NIST により公開されている資料に基づくテストで他方は Marsaglia 博士により提供されているテストです乱数を一度テストしただけではそれが常にテストを満足する乱数性を持っていることを確認できないことから