情報処理学会研究報告 IPSJ SIG Technical Report Vol.2012-MPS-88 No /5/17 RMT テストの性能検証 ~NIST 乱数検定との比較 ~ 三賀森悠大 1,a) 楊欣 1 糸井良太 1 田中美栄子 1,b) 概要 : 我々が以前に提案した,R

RMT

テストの性能検証

～

NIST

乱数検定との比較～

三賀森 悠大

1,a)

楊 欣

1

糸井 良太

1

田中 美栄子

1,b) 概要：我々が以前に提案した，RMTとの比較による乱数度計測法，すなわちRMTテストの誤差基準を NIST検定との比較によって再考察した結果を報告する．様々な乱数度の数列を用意するため，完全規則 列から出発してそれにシャッフルをかけることにより，異なる乱数度のデータ列を作成し，RMTテスト によりその乱数度を測定すると共に，15種類の検定法を持つNIST乱数検定の結果を用いてRMTテスト との比較実験を行なった．その結果，NIST乱数検定で良い乱数と見なせるシャッフル度に対応するデー タ列では，RMTテストによる誤差が0.69%以下となり，先に擬似乱数列や物理乱数を用いて作成した乱 数度評価基準よりも厳しい基準となる．NIST検定に掛けるために2進列に変換していることや，両テス トにおけるデータ列の制限等を考慮すると，矛盾しているとまでは言えないが，RMTテストの誤差基準 値の選定に対する新たな知見を得たと言える． キーワード：乱数度評価基準，RMTテスト，NIST乱数検定

Performance Verification of RMT-Test

～

Comparison with the NIST Randomness Test

～

Yuta Mikamori

1,a)

Xin Yang

1

Ryota Itoi

1

Mieko Tanaka-Yamawaki

1,b)

Abstract: In this article, we report a new result of the error limit to be used for the RMT test, which we

have proposed earlier in order to measure the randomness of one-dimensional data sequence based on the comparison to the theoretical value derived by the random matrix theory (RMT). This new limit is obtained by comparing the error level of RMT-test to the result of NIST test. We prepared data sequences of various levels of randomness by shuffling a regular sequence many times. The result shows that the RMT error must be less than 0.69% in order to satisfy the requirement of the NIST test. This new limit is severer than the limit that we have obtained in the study of pseudo-random sequences. Although we need to consider the fact that NIST test is applied only binary sequences and the conditions to apply the two tests are not the same, this result suggests us to reconsider the error limit of the RMT test in more detail.

Keywords: Evaluation criteria of randomness, RMT-test, NIST randomness test

1.

はじめに

乱数度とは，如何に数の並び方の予測や再現が難しいか の具合で，これが高いほど良い乱数とされる．しかし実際 1 _{鳥取大学大学院工学研究科情報エレクトロニクス専攻}

Tottori University, Graduate School of Engineering, Depart-ment of Information and Electronics

a) _{[email protected]} b) _{[email protected]} にデータ列の乱数度の測定をしようとすると，JISで推奨 される手法[1]や，暗号分野で使われるNISTツール[2]の ように，複数の基準を併用するものが多い上，データ形式 に対しても，2進数，整数，実数のいずれかを指定し，デー タ長も決められていて使いにくい事が多い． 以前に我々が提案した，乱数度評価のためのRMTテス ト[3][4]は，単一の評価基準であらゆるデータ形式の数列 の乱数度を測ることができる便利な手法であり，直観性に

優れた定性評価[3]と，客観性に優れた定量評価[4]を併 用することで，様々な種類のデータの乱数度を簡便に測定 するツールを提供するものである．問題点としては，第一 に，データとして非常に長い数列を必要とし，社会科学や 医学の分野に応用する際に十分なデータ数を確保すること が必ずしも可能でない場合があること，また，第二には， 定量評価基準を定める際に，乱数度のかなり高いことが自 明の，擬似乱数列や物理乱数列を用いたため，乱数度が高 いと判定する基準値の選定に任意性を排除できなかったこ とがある[4]．すなわち，擬似乱数列や物理乱数列に対し ては，局所的には誤差が1-2%程度と小さく，データ間の ゆらぎを考慮して100サンプルの平均をとった場合の誤差 の最大値が5%以下であれば擬似乱数と同等の乱数度を保 証できる，という観察に基づいて「RMT理論値との誤差 5%以下なら乱数」という基準を決めた一方で，乱数列から 作成した対数収益列のように，明らかに乱数度の低いデー タに対しては，RMT理論値との誤差が20%程度となるた め，これらの中間にある，擬似乱数列や物理乱数列よりは 乱数度が低いが，対数収益列よりは乱数度が高い，という 場合の評価があまり良く解らなかった．原因はそのような データを入手できなかったことにある． 本稿では，完全規則列にシャッフルをかけることにより， 様々な乱数度を持つと予想されるデータを作成し，RMT テストによりその乱数度を測定すると共に，NIST検定と の比較を行い，RMTテストの評価基準値について再考す ることにしたい．

2.

RMT

テストの概要

RMTは半世紀以上前から原子核物理学の分野で応用 されてきた[5]が，ここでは1998年∼2002年にかけて文 献[6][7][8]により株式市場に応用された文脈に基づいて提 案されたRMT乱数度評価法[3][4]を用いる． 相関行列の固有値分布の理論は，データ長L，乱数列の 個数N，理論の最大固有値及び最小固有値(λ+及びλ−)を 用いて， Q = L N (1) λ_±= 1 + 1 Q± 2 √ 1 Q (2) PRM T(λ) = Q 2πλ √ (λ+− λ)(λ − λ−) (3) で表される． この時，固有値分布の理論は式（1）のみに依存する関数 となる．条件として，L→∞，N→∞で，かつL/N >1 となるように行列を作成する． 乱数から行列を構成する為に，予め一つの長い乱数列を 生成しておき，図1のようにデータ長Lで区切る．この作 業をN回繰り返すことにより，相関行列を作成していくの に必要なデータを得ることができる．行列を作成する際，i 行j列目の要素Ai,jは，数列の（i×L+j）番目の数字と なる． 図1 乱数列の分割方法

Fig. 1 How to divide the random number sequence

相関行列作成の過程として，まず2.2.1節で用意した乱

数列データを図2のように並べ，N行L列の行列を作成

する．

図2 乱数列データの並べ方

Fig. 2 Arrangement of the data sequence of random numbers

次に，この行列を列ごとに平均0，分散1で正規化する． 正規化する際には次の式（4）を使い，求めた数値を正規化 行列Gに代入する（式（5））． gi,j= Ai,j− ⟨Ai⟩ √ ⟨Ai2⟩ − ⟨Ai⟩2 (4) G =     g1,1 · · · g1,L .. . . .. ... gN,1 · · · gN,L     (5) さらに，式（6）のように正規化行列Gとその転置行列 GT_{の積をとることにより，相関行列Cを求める．} C = 1 LGG T ₍₆₎ 乱数度の評価方法は，モーメント法によって固有値のk 次モーメントを求め，その理論値で割って数値化すること により，乱数度をより細かく分析できる定量評価を用いる． 1つのサンプル（データ長100万）からN×Lを決定して 相関行列を作成する．今回は，N =500，L=2000の条件の もとで乱数度評価を行っている．その後，定量評価を行う ことにより，乱数度を数値で判定する． 最初に，式（6）で求めた相関行列Cから対角要素の平 均をとることにより，次式を用いてk次モーメントの実測

値mkを求める． mk= 1 N N ∑ i=1 (Ck)i,i (7) kに対応する理論値は次式により計算する． µk= ∫ λ+ λ− λkPRM T(λ)dλ (8) さらに，求めたk次モーメントmkを，そのkに対する RMT理論値µkで割ることによって，誤差を数値で表す． 誤差を表す数値は， 誤差(%) = (mk µk − 1) × 100 (9) で求める．これは，RMTが完全にランダムと見なす理論 からどの程度ずれているかを表すもので，誤差の値が大き いものほど乱数度が低く，逆に誤差が0%に近いものほど 乱数度が高いと判断する．

3.

NIST

乱数検定の概要

様々な視点で検定を行うことで，乱数の良し悪しをより 細かく調査することができる．その為，今回は乱数検定の 道具として，米国国立標準技術研究所（NIST）で開発さ れた，NIST SP 800-22を使用した．NIST SP 800-22は， 複数の検定法からなる米国標準の統計的乱数検定であり， 1つの数列を読み込むことで，様々な検定をまとめて素早 く行うことができる．NISTのホームページにて，ソース コードが提供されている[2]．また，NIST乱数検定は暗号 として使用できるかどうかの検定として広く使用されてお り，合格と判断された検定の数が多いほど乱数度は高くな り，その数列は「暗号に相応しい程度の良い乱数」として 判断できる． NIST SP 800-22では，0と1からなるASCII形式の乱 数データを対象として，乱数の検定を行う．採用されてい る検定法は全部で15種類である． 文献[9][10]によると，NIST SP 800-22によって検定す る数列の対象として，長さ100万の数列が推奨されている． また，統計的に有意な結果を得る為には，少なくとも55サ ンプルの数列を用意する必要がある．これは，サンプル数 または1サンプルあたりのデータ長が過度に少なければ， 合否判定が不可能な検定が存在するからである．

4.

検証に用いた乱数データの作成方法

NIST乱数検定により良い乱数として見なされる基準を 探るにあたり，RMTテストで求めた乱数度と照合して解 析を行なっていく為，様々な乱数度の数列データを用意し たい． そこで，ランダム性が極めて低い規則的な数列デー タをシャッフルさせることにより，徐々に乱数度を高くし つつ，2種類の評価の比較を行なっていく．NIST乱数検 定の条件に合わせる為，本研究で扱うデータとして，全要 素数100万の数列を55サンプル用意する．元の規則的な 数列の生成及びシャッフル作業は全てコンピュータによっ て行われる為，研究の目的に合った乱数列を高速で用意す ることが可能である．5.1節では，RMTテストにより，実 際にシャッフル回数に応じて乱数度に変化が生じることを 確認する． シャッフルを行う前のデータ，つまり初期の数列データ として，0∼99の100個を昇順に並べていき，その数列1 セットを1万個連結させることでデータ長100万，かつ 0∼99のそれぞれの度数が全て均一の規則的な数列を構成 する． シャッフルは，数列データにある全要素数100万の要素 の中から2要素をそれぞれランダムに選び，お互いの順番 を入れ替えるというアルゴリズムで行う．この作業を1回 としてカウントし，繰り返す．シャッフル作業が一定の回 数（N回とおく）に達すれば，シャッフルN回分の乱数 列としてRMTテスト及びNIST乱数検定で扱う．

5.

実験

5.1 RMTテストによる結果 まず，RMTテストを用いて，規則的な数列をシャッフ ルしたものの乱数度を調査することにより，シャッフル回 数に応じて乱数度に変化が生じることを確認する． シャッフル回数100万∼500万回での，それぞれの終了 時点の乱数列の定量評価結果を図3のグラフにまとめる． ここで，縦軸の数値は式（9）により求めた誤差の数値（絶 対値）であり，55サンプルの平均値を示す．なお，1次モー メントについては，どのシャッフル回数においても限りな く誤差0%に近似しているので省略する．

0.001

0.01

0.1

1

10

100

1000

10000

1 1.5 2 2.5 3 3.5 4 4.5 5

error [%]

shuffle [million times]

k=2 k=3 k=4 k=5 k=6 図3 シャッフルによる誤差(k=2～6)の推移

Fig. 3 Changes in error due to shuffle(k=2～6)

図3を見ると，シャッフル回数が少ない場合では，他

の回数の場合と比べて誤差が膨大な数値である．しかし， シャッフル回数の増加とともに誤差の絶対値が減少し，一

定の誤差以下で遷移していることが分かる． よって以上のことから，RMTテストを用いて，シャッ フル回数の増加に応じて乱数度が高くなっていることが確 認できた． 5.2 NIST乱数検定による結果 NIST SP 800-22では，検定対象は0と1からなるASCII 形式の乱数データという制約がある為，出現範囲の中央値 を境目にして，乱数データを0と1のデータに変換して扱 う．例として，データが全て整数で出現範囲が0∼99の場 合，中央値が49.5なので，0∼49を0，50∼99を1として変 換する．NIST乱数検定の全検定においては，Proportion 評価を行った上で合否を判断する． ※Proportion評価 乱数列の全サンプル中，その検定に合格したサンプル数 の比率を見ている．比率が一定基準以上であれば，検定に 総合的に合格したと判断される． シャッフル回数100万∼500万回での，それぞれの終了 時点の乱数列の検定結果を表1にまとめる．ここで，NIST 乱数検定に用いたデータは，5.1節の定量評価で使用した 乱数列データと同一のものである． 表1 NIST乱数検定における結果

Table 1 Result in the NIST randomness test

シャッフル数(万回) 合格率 シャッフル数(万回) 合格率 100 5/15 310 15/15 110 6/15 320 15/15 120 7/15 330 15/15 130 7/15 340 14/15 140 10/15 350 15/15 150 10/15 360 15/15 160 12/15 370 14/15 170 14/15 380 14/15 180 14/15 390 14/15 190 15/15 400 15/15 200 15/15 410 15/15 210 15/15 420 15/15 220 15/15 430 15/15 230 15/15 440 15/15 240 15/15 450 15/15 250 15/15 460 15/15 260 14/15 470 15/15 270 15/15 480 15/15 280 14/15 490 15/15 290 14/15 500 15/15 300 15/15 シャッフル回数170万回以降を10万回区切りで見ると， 15種類全ての検定に合格してProportion評価で合格と見 なされたものや，特定の検定であと数サンプルだけが検定 に合格しなかった為，基準を満たさずProportion評価で 不合格と見なされたものばかりである． 5.3 RMTテストとNIST乱数検定の比較 RMTテストとNIST乱数検定の結果を比較する為，先程 の5.1節及び5.2節での検証結果を表2にまとめる．RMT による乱数度評価の結果はk=2∼6の中でも，6次モーメ ントを扱う．6次モーメントはk=2∼6の中でも誤差が最 も大きくなりやすく，他と比べて特徴が出やすい．表2の 表示の形式としては，図1の誤差の絶対値をとってソート し，NIST乱数検定結果との比較を示している．表中に同 じ誤差の値が複数出ることがあるが，シャッフル回数が異 なる為，偶然同じ誤差の列が生成されただけで，数列の中 の要素は別物である． 表2 RMTテスト(左)とNIST乱数検定(右)の結果

Table 2 Result of RMT-test(left) and NIST randomness test(right) RMTテスト NIST乱数検定 RMTテスト NIST乱数検定 誤差 合格率 誤差 合格率 29359.22 5/15 0.23 14/15 3801.86 6/15 0.22 15/15 574.22 7/15 0.22 15/15 104.59 7/15 0.20 15/15 23.36 10/15 0.19 15/15 6.16 10/15 0.18 14/15 2.02 12/15 0.14 15/15

0.69

14/15

0.14 15/15 0.49 14/15 0.14 15/15 0.48 15/15 0.13 15/15 0.46 15/15 0.13 14/15 0.46 14/15 0.11 14/15 0.40 15/15 0.10 15/15 0.35 15/15 0.10 14/15 0.35 15/15 0.09 15/15 0.35 15/15 0.09 15/15 0.33 14/15 0.08 15/15 0.29 15/15 0.07 15/15 0.24 15/15 0.04 15/15 0.24 15/15 0.03 15/15 0.24 15/15 表2より，NIST乱数検定の結果が，誤差の絶対値0.69% （太字）以下の全ての乱数列において合格率14/15以上と 高いのに対し，誤差が大きい（乱数度が低い）乱数列ほど， 合格率が低いことが分かる． 5.4 乱数度が高い例・低い例 擬似乱数及び物理乱数を用いて検証した例を表3に示 す．RMTテストでは6次モーメントの誤差を用いる．以

下の乱数は先行研究により，乱数度が高いとされている．

表3 擬似乱数(LCG)及び物理乱数3種類を用いた比較

Table 3 Comparison using Pseudo-random number(LCG) 

and Three types of physical random number

乱数の種類 RMTテスト NIST乱数検定 誤差 合格率 LCGによる擬似乱数 -0.2831 14/15 日立製作所製物理乱数 -0.1597 15/15 東芝製物理乱数 0.0026 15/15 東京エレクトロンデバイス製 -0.1194 15/15 物理乱数 また，対数収益をとることによって乱数度を低くした数 列についても比較を行った．比較結果を表4に示す． 表4 対数収益をとることにより乱数度を下げた数列に対する結果 Table 4 Results for the sequences which were reduced there

level of randomness by log-return

乱数の種類 RMTテスト NIST乱数検定 誤差 合格率 LCGによる擬似乱数 99.3042 5/15 日立製作所製物理乱数 98.8686 5/15 東芝製物理乱数 99.2463 5/15 東京エレクトロンデバイス製 98.7580 5/15 物理乱数 表3，表4を比較すると，対数収益をとった場合の方が， RMTテストから求まる乱数度低下と同時に，NIST乱数検 定における合格率も低下していることが分かる．実際に， 5.3節での比較結果でも同様の傾向が見られる．このこと から，NIST乱数検定の結果は，RMTテストの結果と並行 していると考えられる．

6.

考察

乱数度の向上にも関わらず，誤差0.69%以下で合格検定 数が14，15で遷移しているが，調査の結果，合格率14/15 の乱数列全てにおいて「重なりのないテンプレート適合検 定」が不合格と判定されていることが分かる．これより， 重なりのないテンプレート適合検定とRMTテストで求め た乱数度との関連性が，NIST乱数検定の他の検定14種類 に比べて薄いと考えられる． 先行研究では，RMTテストにより求めた6次モーメン トとRMT理論値の誤差の値が5%を下回れば，良い乱数 として判断した．しかし，以上のことと，5.3節の比較結 果が安定していることを考慮すると，RMTテストで求め た誤差の値が0.69%を下回っていれば，NIST乱数検定の 基準で良い乱数として判断できると考えられる． また，シャッフル回数を増やして乱数度を向上させた乱 数列ほど，NISTが定めた乱数検定で合格しているものが 多いことが分かる．実際，NISTが定めた乱数検定は暗号 として使用できるかの検定として広く使われており，検定 の合格率が高い数列ほど，暗号として相応しいとされてい る．以上のことを考慮すると，乱数度を示す，6次モーメ ントとRMT理論値の誤差の値が0.69%以下である乱数列 のように，NIST乱数検定において合格率が14/15または 15/15のものは，「暗号として相応しい程度の良い乱数」と 判断できると考えられる．

7.

終わりに

規則的な数列をシャッフルして作成した乱数データを RMTテスト及びNIST乱数検定で検証した結果，どちらも シャッフル回数に応じた乱数度の向上を確認できた．この ことを踏まえて両者の結果を比較したところ，6次モーメ ントの誤差0.69%以下で，NIST乱数検定において14/15 以上の合格率を確認できた．RMTテストのより詳細な精 度を追求する為には，数列のサンプル数や初期データの 様々な場合についても検証する必要がある．また，NIST 乱数検定に使用できる数列の種類に制限があることを考慮 すると，0-1データに関してもRMTテストで検証するこ とで，より詳しい分析が可能であると考えられる． その他，今後の課題として，シンボル数及びNIST乱数 検定用の0-1変換方法の工夫，境界線0.69%付近の精密化 などがある． 参考文献 [1] 日本規格協会，“JIS Z 9031乱数発生及びランダム化の手 順”，2001年改正． [2] NIST: http://csrc.nist.gov/groups/ST/toolkit/ rng/documentation_software.html [3] 楊欣，田中美栄子，“ランダム行列理論を用いた乱数度評 価法の提案”，情報処理学会研究報告，Vol.2011-MPS-83 No.2(2011年5月17日)．

[4] X. Yang, R.Itoi, M. Tanaka-Yamawaki, “Testing Ran-domness by Means of Random Matrix Theory”, Progress of Theoretical Physics, Supplement, 2012, accepted. [5] E. P. Wigner, Ann. Math., Vol. 67, pp. 325-327, 1958. [6] L. Laloux, P. Cizeaux, J. Bouchaud, M. Potters, ”Noise

Dressing of Financial Correlation Matrices”, Physical Review Letters, Vol.83 , pp.1467-1470, 1998.

[7] V. Plerou, P. Gopikrishnan, B. Rosenow, L. A. N. Ama-ral, H. E. Stanley, Physical Review Letters, Vol. 83, pp. 1471-1474, 1999.

[8] V. Plerou, P. Gopikrishnan, B. Rosenow, L. Amaral, H. Stanley, ”Random Matrix Approach to Cross Cor-relation in Financial Data”, Physical Review E, Vol. 65 no.066126, 2002.

[9] 情報処理振興事業協会 セキュリティセンター，“電子政府 情報セキュリティ技術開発事業 擬似乱数検証ツールの調 査開発 調査報告書”，pp. 1-45，(平成15年2月) [10] Andrew Rukhin他，“A Statistical Test Suite for

Ran-dom and PseudoranRan-dom Number Generators for Cryp-tographic Applications” ，pp. 5-1∼ 5-8，(April 2010)