乱数検定: NIST SP 800-22
概要
NIST SP 800-22 [1] (または単に NIST 検定) は NIST が 2001 年に刊行した論文による (疑似) 乱数生成器のランダム性を検定するための検定スイートである。この検定プログラムは NIST のサイト [2] からダウンロードできる。
この検定スイートは 15 の検定で構成され、指定されたビット列にランダム性があるかを 0 と 1 の出現頻度や偏在性、周期性、振動速度など様々な観点から統計的に検定する。すべての検定は統計的仮説検定に基づき、結果として「真にランダムなビット列である」を帰無仮説 \(H_0\) とした \(p\) 値を算出する。そして、この \(p\) 値が検定実施者が事前に定めた有意水準 \(\alpha=0.01\) より大きければ「入力ビット列がランダムであることを疑う理由は見つからなかった」と結論づけることができる (一般的な仮説検定とは異なり帰無仮説の採用を目的とすることに注意)。
検定を行うには (疑似) 乱数生成器の生成したビット列のファイルを検定プログラムに入力する。乱数生成器の他にも、システムの特定の動作がランダムであることを検証するためにも使うことができる。例えば、ある役割のノードが一様にランダムに選ばれるシステムにおいてその動作をシミュレーションし、得られた選択履歴から生成したビット列がランダム性を持つかを検定することができるだろう。
ただし、この検定スイートは暗号論的疑似乱数のような「強い」ランダム性を評価することを目的としていることから、自然科学や社会学での観測値に対しては、そのデータの性質や量の観点から適用は難しいかもしれない。
この検定スイートはヒューリスティックな観点で集められたものである。また指標や方法にヒューリスティックさを持つ検定も多い。このような理由から、現在ではいくつかの検定は結果の質に疑問がある・参考にならないとする考え方もあり、NIST SP 800-22 に関連する論文を検索すると改善方法や代替、検定の追加といった提案が多く見つかる。ただし、いずれにしても致命的な欠陥があるというわけではなく、ランダム性の世界的な評価基準を適用するという観点で利用することに問題があるわけではない。
なお、統計的仮説検定の性質から、棄却された検定があったとしても必ずしもビット列のランダム性に欠陥があるという結論にはならず、逆にすべて受理されたとしてもランダム性に欠陥がないことの確証にはならないことに注意する必要がある。
Table of Contents
検定プログラムの実行と評価
検定プログラムは NIST のサイト [2] からダウンロードすることができる。以降は Ubuntu 22.04 環境で検定プログラム assess を実行し結果を評価するまでの流れである。Windows では WSL や cygwin で実行することができる。
検定プログラムのビルド
まずアーカイブを解凍して検定プログラムのビルドを行う。ビルドには make と gcc が必要であるためあらかじめ build-essential などをセットアップしておく。
torao@lazurite:~$ unzip sts-2.1.2.zip
torao@lazurite:~$ cd sts-2.1.2/sts-2.1.2
torao@lazurite:~/sts-2.1.2/sts-2.1.2$ make -f makefile
/usr/bin/gcc -o obj/assess.o -c ./src/assess.c
/usr/bin/gcc -o obj/frequency.o -c -Wall ./src/frequency.c
/usr/bin/gcc -o obj/blockFrequency.o -c -Wall ./src/blockFrequency.c
...
ビルドに成功するとカレントディレクトリに assess という実行ファイルが生成される。
テストデータの作成
検定プログラムを使った検定には 2 つの方法がある。一つは疑似乱数生成器が生成した乱数列を入力する方法で、もう一つは検定プログラムに疑似乱数生成器を組み込む方法である。後者はテストデータがストレージ容量に大きく影響する時代の方法であり、現在ならテストデータのファイルを入力する方法で良いだろう。
まず検定対象の疑似乱数生成器を使って検定用のビット列データ \(\epsilon\) を作成する。各検定で最低何ビットの入力が推奨されているかは検定によって異なるが、すべての検定を考慮するのであれば \(n \ge 10^6\) ビットのシーケンスが推奨値となる。また検定項目ごとの総括的な \(p\) 値が意味のある値となるには最低 \(t=55\) 回のイテレーションを行う必要がある。したがって、少なくとも \(55\times 10^6\) ビット (6,875,000 バイト) 以上のビット列データを準備することを推奨する。
以下の例では Python 標準の乱数関数を使用して \(55\times 10^6\) ビット列を作成している。この例では検定対象のビット列をバイナリデータとして保存しているが、これは '0' と '1' で構成される ASCII データでも良い。
import random
bytes = random.randbytes(1000000 * 55 // 8)
with open("random.bin", "wb") as f:
f.write(bytes)検定プログラムの実行
検定プログラムの起動はビルドした assess コマンドに 1 回のイテレーションで検定するするビット長 \(n\) (=sequenceLength) を指定する。次のような対話形式が開始する。
- 検定対象は [0] 入力ファイルか、[1-9] 組み込みの疑似乱数生成器か。
- [0] 一部の検定のみを行うか、[1] すべての検定を行うか。
- いくつかの検定に対するパラメータの設定。
- 検定のイテレーション回数 \(t\) (=
bitstreams)。 - 入力ファイルは [0] ASCII か [1] バイナリか。
以下は実際に assess を起動して前述の random.bin の検定を行った例である。入力が必要な箇所に ✅ マークを付けている。
$ ./assess 1000000G E N E R A T O R S E L E C T I O N ______________________________________ [0] Input File [1] Linear Congruential [2] Quadratic Congruential I [3] Quadratic Congruential II [4] Cubic Congruential [5] XOR [6] Modular Exponentiation [7] Blum-Blum-Shub [8] Micali-Schnorr [9] G Using SHA-1 Enter Choice: 0 ✅ User Prescribed Input File: random.bin ✅ S T A T I S T I C A L T E S T S _________________________________ [01] Frequency [02] Block Frequency [03] Cumulative Sums [04] Runs [05] Longest Run of Ones [06] Rank [07] Discrete Fourier Transform [08] Nonperiodic Template Matchings [09] Overlapping Template Matchings [10] Universal Statistical [11] Approximate Entropy [12] Random Excursions [13] Random Excursions Variant [14] Serial [15] Linear Complexity INSTRUCTIONS Enter 0 if you DO NOT want to apply all of the statistical tests to each sequence and 1 if you DO. Enter Choice: 1 ✅ P a r a m e t e r A d j u s t m e n t s ----------------------------------------- [1] Block Frequency Test - block length(M): 128 [2] NonOverlapping Template Test - block length(m): 9 [3] Overlapping Template Test - block length(m): 9 [4] Approximate Entropy Test - block length(m): 10 [5] Serial Test - block length(m): 16 [6] Linear Complexity Test - block length(M): 500 Select Test (0 to continue): 0 ✅ How many bitstreams? 55 ✅ Input File Format: [0] ASCII - A sequence of ASCII 0's and 1's [1] Binary - Each byte in data file contains 8 bits of data Select input mode: 1 ✅ Statistical Testing In Progress......... Statistical Testing Complete!!!!!!!!!!!!
Ryzen 7 5700X 環境でこの検定プログラムの実行は \(55 \times 10^6\) ビット列に対して 3 分弱で終了した。
検定結果の評価
検定プログラムが終了すると experiments/AlgorithmTesting/finalAnalysisReport.txt というファイルが作成されている。
実行では、各統計検定ごとに "How many bitstreams?" で指定したイテレーション回数 \(t\) が実施され、ぞれぞれで \(p\) 値が算出される。得られた \(p\) 値はその値の区間 \([0.0,0.1)\), \([0.1,0.2)\), \(\ldots\), \([0.9,1.0)\) に振り分けられてカウントされる。
C1 から C10 カラムはそれぞれの区間に入った \(p\) 値の数を表している (つまり \(t=\sum_{i=1}^{10}c_i\))。例えば C10 が 5 であれば \(t\) 回のイテレーションのうち \(0.9 \le P\mbox{-}{\it value} \lt 1.0\) となった検定が 5 回あったことを意味する。\(p\) 値の性質から、ビット列が真にランダムであれば C1-C10 間に一様に分布するはずである。
P-VALUE カラムはイテレーションによって得られた \(t\) 個の \(p\) 値が \(0.1\times 10\) 区間に一様に分布していると仮定したときの \(p\) 値 (つまり \(p\) 値の \(p\) 値) であり、この統計検定の代表値と見なすことができる。ただし、このカラムの値は処理するシーケンス数が 55 未満では意味のある結果とならず、10 未満では未定義となることに注意。
PROPORTION カラムはイテレーションを行った検定のうちランダム性が受理されたビット列の割合を表しているいる。
$ cat experiments/AlgorithmTesting/finalAnalysisReport.txt------------------------------------------------------------------------------ RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES ------------------------------------------------------------------------------ generator is <random.bin> ------------------------------------------------------------------------------ C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST ------------------------------------------------------------------------------ 1 11 4 7 9 5 3 4 6 5 0.071177 55/55 Frequency 5 2 9 4 7 7 8 5 5 3 0.401199 55/55 BlockFrequency 3 6 6 8 5 4 8 10 3 2 0.181557 55/55 CumulativeSums 2 8 10 7 2 5 6 3 10 2 0.025193 55/55 CumulativeSums 4 9 5 7 5 9 5 4 4 3 0.474986 55/55 Runs 6 5 6 6 4 5 4 5 7 7 0.978072 53/55 LongestRun 7 2 8 1 3 9 4 5 11 5 0.025193 53/55 Rank 6 2 4 7 5 5 7 5 5 9 0.637119 54/55 FFT 7 7 1 5 7 7 7 4 3 7 0.437274 55/55 NonOverlappingTemplate 5 5 4 7 5 4 11 5 5 4 0.474986 55/55 NonOverlappingTemplate 6 5 6 4 6 8 4 4 6 6 0.946308 54/55 NonOverlappingTemplate 4 5 7 7 5 8 4 4 5 6 0.897763 55/55 NonOverlappingTemplate 6 4 9 8 6 5 4 5 4 4 0.719747 55/55 NonOverlappingTemplate 9 8 6 1 3 8 4 4 7 5 0.202268 55/55 NonOverlappingTemplate 4 7 6 10 7 2 4 5 7 3 0.304126 54/55 NonOverlappingTemplate 6 10 7 2 8 4 4 7 2 5 0.181557 55/55 NonOverlappingTemplate 8 4 4 7 3 9 11 3 5 1 0.032923 55/55 NonOverlappingTemplate 5 6 7 8 5 4 9 3 6 2 0.437274 55/55 NonOverlappingTemplate 7 6 5 5 10 4 3 7 3 5 0.474986 54/55 NonOverlappingTemplate 7 5 7 4 6 4 6 2 6 8 0.719747 55/55 NonOverlappingTemplate 8 5 3 2 7 3 6 6 7 8 0.437274 53/55 NonOverlappingTemplate 3 2 6 8 6 9 5 6 7 3 0.366918 55/55 NonOverlappingTemplate 5 7 1 3 3 5 12 7 6 6 0.055361 54/55 NonOverlappingTemplate 5 5 8 3 6 4 5 4 10 5 0.514124 55/55 NonOverlappingTemplate 6 8 6 9 0 5 5 8 1 7 0.062821 55/55 NonOverlappingTemplate 10 8 3 4 8 2 5 5 5 5 0.249284 54/55 NonOverlappingTemplate 3 9 4 2 6 7 6 2 11 5 0.062821 55/55 NonOverlappingTemplate 3 7 7 6 5 8 3 7 5 4 0.719747 55/55 NonOverlappingTemplate 2 2 9 6 10 6 3 7 4 6 0.115387 55/55 NonOverlappingTemplate 5 4 4 6 5 6 5 3 8 9 0.678686 55/55 NonOverlappingTemplate 7 10 6 7 6 1 8 3 1 6 0.062821 55/55 NonOverlappingTemplate 2 5 8 4 4 11 4 2 6 9 0.055361 55/55 NonOverlappingTemplate 3 5 6 8 7 5 5 4 7 5 0.867692 55/55 NonOverlappingTemplate 6 5 10 3 8 4 6 3 5 5 0.437274 55/55 NonOverlappingTemplate 6 5 6 5 5 3 3 9 9 4 0.474986 54/55 NonOverlappingTemplate 4 3 9 5 2 6 9 3 6 8 0.202268 54/55 NonOverlappingTemplate 9 7 5 4 6 6 6 3 4 5 0.759756 55/55 NonOverlappingTemplate 5 6 8 3 6 5 5 8 4 5 0.834308 54/55 NonOverlappingTemplate 7 3 5 2 4 8 4 7 7 8 0.437274 53/55 NonOverlappingTemplate 12 7 1 5 3 6 6 10 3 2 0.007160 55/55 NonOverlappingTemplate 8 3 6 2 3 6 4 6 10 7 0.224821 54/55 NonOverlappingTemplate 10 5 8 3 2 3 7 8 5 4 0.162606 52/55 NonOverlappingTemplate 0 6 10 5 10 4 8 2 5 5 0.025193 55/55 NonOverlappingTemplate 9 5 3 7 6 5 1 5 11 3 0.062821 55/55 NonOverlappingTemplate 4 6 2 8 3 9 4 6 9 4 0.224821 55/55 NonOverlappingTemplate 8 7 6 5 4 4 2 7 9 3 0.366918 54/55 NonOverlappingTemplate 8 6 3 5 6 6 2 7 6 6 0.719747 52/55 NonOverlappingTemplate 5 6 4 5 6 8 4 9 4 4 0.719747 54/55 NonOverlappingTemplate 2 4 12 7 3 5 7 6 2 7 0.048716 55/55 NonOverlappingTemplate 6 5 4 6 6 5 1 5 6 11 0.249284 55/55 NonOverlappingTemplate 6 11 7 8 6 2 2 2 6 5 0.071177 55/55 NonOverlappingTemplate 4 4 8 4 6 5 4 2 9 9 0.275709 53/55 NonOverlappingTemplate 3 5 6 4 4 3 8 8 6 8 0.554420 55/55 NonOverlappingTemplate 3 3 4 6 8 4 9 10 2 6 0.115387 55/55 NonOverlappingTemplate 3 5 9 5 5 7 7 5 4 5 0.759756 55/55 NonOverlappingTemplate 6 8 5 5 5 3 4 9 4 6 0.678686 54/55 NonOverlappingTemplate 6 6 9 5 8 7 6 2 5 1 0.249284 54/55 NonOverlappingTemplate 8 4 6 1 6 9 6 7 2 6 0.224821 54/55 NonOverlappingTemplate 7 2 7 6 2 12 2 5 5 7 0.037566 54/55 NonOverlappingTemplate 4 6 5 7 4 5 2 7 5 10 0.437274 53/55 NonOverlappingTemplate 2 2 10 7 6 2 8 7 6 5 0.115387 55/55 NonOverlappingTemplate 6 4 5 11 6 3 1 6 5 8 0.129620 53/55 NonOverlappingTemplate 11 7 3 6 4 7 6 6 1 4 0.129620 54/55 NonOverlappingTemplate 9 3 6 6 3 6 5 9 1 7 0.181557 55/55 NonOverlappingTemplate 5 9 8 6 5 6 2 7 1 6 0.249284 54/55 NonOverlappingTemplate 5 5 5 9 6 4 8 7 3 3 0.554420 52/55 NonOverlappingTemplate 2 3 4 7 5 5 8 5 6 10 0.304126 54/55 NonOverlappingTemplate 4 5 6 4 10 3 10 4 5 4 0.224821 55/55 NonOverlappingTemplate 10 8 3 3 10 6 2 4 4 5 0.071177 53/55 NonOverlappingTemplate 5 3 7 4 3 11 4 8 4 6 0.202268 55/55 NonOverlappingTemplate 6 4 4 6 9 4 7 3 6 6 0.719747 54/55 NonOverlappingTemplate 6 3 11 3 6 4 3 6 7 6 0.249284 55/55 NonOverlappingTemplate 10 5 6 6 7 5 4 3 2 7 0.366918 52/55 NonOverlappingTemplate 8 3 4 7 5 4 8 7 5 4 0.678686 55/55 NonOverlappingTemplate 8 5 5 10 4 7 4 5 3 4 0.437274 55/55 NonOverlappingTemplate 2 6 8 10 6 4 5 6 3 5 0.334538 55/55 NonOverlappingTemplate 7 2 8 4 5 5 6 7 6 5 0.759756 55/55 NonOverlappingTemplate 4 7 6 7 3 6 7 3 4 8 0.678686 55/55 NonOverlappingTemplate 2 8 4 5 7 7 10 4 6 2 0.181557 55/55 NonOverlappingTemplate 4 4 5 4 7 5 7 5 11 3 0.334538 54/55 NonOverlappingTemplate 3 5 8 6 4 8 5 8 3 5 0.595549 55/55 NonOverlappingTemplate 6 7 8 6 10 1 4 4 5 4 0.224821 55/55 NonOverlappingTemplate 7 6 2 5 7 7 7 4 3 7 0.637119 55/55 NonOverlappingTemplate 6 4 3 3 7 9 8 4 4 7 0.437274 55/55 NonOverlappingTemplate 5 2 4 6 7 3 6 8 7 7 0.595549 55/55 NonOverlappingTemplate 6 3 8 9 3 9 8 3 3 3 0.115387 55/55 NonOverlappingTemplate 7 8 3 5 7 4 6 2 6 7 0.595549 54/55 NonOverlappingTemplate 3 13 8 4 6 6 3 3 6 3 0.028817 55/55 NonOverlappingTemplate 6 5 5 6 4 6 6 7 6 4 0.987896 54/55 NonOverlappingTemplate 5 4 6 7 6 3 7 3 5 9 0.637119 53/55 NonOverlappingTemplate 7 13 5 2 7 6 6 4 3 2 0.021999 54/55 NonOverlappingTemplate 3 3 6 4 8 8 8 5 6 4 0.554420 55/55 NonOverlappingTemplate 8 2 5 12 6 4 2 3 6 7 0.042808 55/55 NonOverlappingTemplate 5 2 6 6 6 7 10 5 4 4 0.474986 55/55 NonOverlappingTemplate 2 6 7 5 2 6 4 6 8 9 0.334538 55/55 NonOverlappingTemplate 4 4 6 4 11 6 4 9 3 4 0.181557 55/55 NonOverlappingTemplate 5 7 6 1 6 5 7 4 5 9 0.474986 55/55 NonOverlappingTemplate 5 4 9 6 2 5 9 2 2 11 0.021999 54/55 NonOverlappingTemplate 4 4 6 5 9 5 7 9 3 3 0.401199 55/55 NonOverlappingTemplate 2 7 3 5 9 3 7 9 4 6 0.224821 55/55 NonOverlappingTemplate 9 8 5 3 4 6 5 5 5 5 0.719747 54/55 NonOverlappingTemplate 5 10 6 7 5 2 4 3 5 8 0.304126 54/55 NonOverlappingTemplate 5 6 3 4 2 4 5 7 13 6 0.048716 55/55 NonOverlappingTemplate 4 6 5 2 7 6 3 6 5 11 0.249284 54/55 NonOverlappingTemplate 7 6 5 6 6 4 5 2 8 6 0.798139 55/55 NonOverlappingTemplate 4 8 6 4 5 3 4 8 9 4 0.474986 55/55 NonOverlappingTemplate 6 7 9 3 4 5 4 3 5 9 0.401199 54/55 NonOverlappingTemplate 3 4 8 2 4 4 8 12 6 4 0.048716 55/55 NonOverlappingTemplate 9 3 7 6 2 2 5 8 5 8 0.202268 55/55 NonOverlappingTemplate 8 4 10 5 3 6 6 4 4 5 0.474986 55/55 NonOverlappingTemplate 8 4 7 8 2 3 8 3 7 5 0.304126 54/55 NonOverlappingTemplate 7 5 4 5 4 6 3 12 6 3 0.162606 55/55 NonOverlappingTemplate 4 3 8 5 7 5 2 6 7 8 0.514124 54/55 NonOverlappingTemplate 6 10 3 7 2 2 7 6 6 6 0.224821 55/55 NonOverlappingTemplate 8 4 7 9 3 7 2 3 8 4 0.202268 54/55 NonOverlappingTemplate 7 5 3 7 8 7 3 8 0 7 0.145326 54/55 NonOverlappingTemplate 5 3 7 2 7 5 6 5 7 8 0.637119 53/55 NonOverlappingTemplate 6 4 7 5 3 5 4 8 6 7 0.834308 55/55 NonOverlappingTemplate 5 7 8 1 5 11 5 4 5 4 0.145326 55/55 NonOverlappingTemplate 4 10 5 6 6 8 4 8 2 2 0.162606 55/55 NonOverlappingTemplate 3 3 4 9 3 6 11 3 7 6 0.090936 54/55 NonOverlappingTemplate 2 5 6 9 6 8 5 4 4 6 0.554420 55/55 NonOverlappingTemplate 5 4 4 7 3 5 10 4 5 8 0.437274 55/55 NonOverlappingTemplate 5 6 2 7 3 5 5 6 8 8 0.595549 54/55 NonOverlappingTemplate 9 7 5 3 8 4 3 6 5 5 0.554420 54/55 NonOverlappingTemplate 3 5 8 7 2 4 8 7 4 7 0.437274 55/55 NonOverlappingTemplate 5 6 10 7 6 6 3 5 3 4 0.514124 54/55 NonOverlappingTemplate 6 8 7 4 7 3 5 6 4 5 0.834308 54/55 NonOverlappingTemplate 3 2 6 6 4 7 7 5 7 8 0.595549 54/55 NonOverlappingTemplate 5 2 1 9 4 7 7 10 4 6 0.080519 55/55 NonOverlappingTemplate 9 5 8 5 4 4 6 4 4 6 0.719747 54/55 NonOverlappingTemplate 9 3 3 6 2 2 7 8 5 10 0.062821 55/55 NonOverlappingTemplate 3 9 2 7 6 5 5 5 7 6 0.554420 55/55 NonOverlappingTemplate 1 6 5 10 5 8 6 4 5 5 0.304126 54/55 NonOverlappingTemplate 7 3 3 3 5 6 4 7 5 12 0.115387 54/55 NonOverlappingTemplate 7 5 6 9 4 5 7 6 3 3 0.637119 54/55 NonOverlappingTemplate 7 3 8 4 6 5 3 10 4 5 0.366918 55/55 NonOverlappingTemplate 6 1 6 4 4 5 5 6 7 11 0.202268 55/55 NonOverlappingTemplate 5 8 6 7 3 11 6 3 3 3 0.145326 55/55 NonOverlappingTemplate 5 6 5 3 3 11 7 5 4 6 0.334538 54/55 NonOverlappingTemplate 7 4 4 9 7 1 5 6 9 3 0.181557 55/55 NonOverlappingTemplate 4 6 10 3 4 6 9 3 4 6 0.275709 55/55 NonOverlappingTemplate 7 10 5 9 2 3 10 8 1 0 0.001628 55/55 NonOverlappingTemplate 3 7 9 5 5 2 6 3 7 8 0.334538 54/55 NonOverlappingTemplate 6 6 4 4 6 2 9 6 8 4 0.514124 54/55 NonOverlappingTemplate 5 13 6 4 5 5 6 2 5 4 0.080519 55/55 NonOverlappingTemplate 2 6 8 7 3 5 7 4 8 5 0.514124 55/55 NonOverlappingTemplate 1 8 9 5 3 5 9 5 6 4 0.181557 55/55 NonOverlappingTemplate 6 5 2 4 5 8 7 9 3 6 0.437274 55/55 NonOverlappingTemplate 4 5 5 5 7 7 7 3 9 3 0.595549 55/55 NonOverlappingTemplate 5 1 1 6 6 6 3 6 12 9 0.012650 55/55 NonOverlappingTemplate 2 5 6 6 3 4 9 4 11 5 0.129620 55/55 NonOverlappingTemplate 3 9 3 5 5 6 4 7 7 6 0.637119 53/55 NonOverlappingTemplate 3 6 6 6 5 7 5 7 4 6 0.946308 55/55 NonOverlappingTemplate 6 6 2 10 7 4 4 7 6 3 0.334538 54/55 NonOverlappingTemplate 6 7 8 6 10 1 4 4 5 4 0.224821 55/55 NonOverlappingTemplate 6 5 4 5 7 6 5 4 8 5 0.946308 54/55 OverlappingTemplate 6 2 8 8 7 5 3 4 7 5 0.514124 55/55 Universal 3 5 6 3 9 4 6 5 8 6 0.595549 54/55 ApproximateEntropy 3 5 2 6 6 3 5 2 3 1 0.299251 36/36 RandomExcursions 3 2 4 3 6 6 2 3 5 2 0.468595 36/36 RandomExcursions 1 5 2 2 1 5 8 7 3 2 0.017912 36/36 RandomExcursions 3 1 5 6 3 4 5 2 4 3 0.534146 36/36 RandomExcursions 2 4 2 1 4 8 5 2 4 4 0.148094 36/36 RandomExcursions 7 0 3 3 4 3 2 4 4 6 0.178278 36/36 RandomExcursions 3 4 3 3 4 4 2 7 3 3 0.671779 36/36 RandomExcursions 1 5 7 4 1 3 3 5 5 2 0.178278 35/36 RandomExcursions 6 4 4 0 4 6 4 4 2 2 0.253551 35/36 RandomExcursionsVariant 6 4 2 3 5 3 3 3 4 3 0.804337 36/36 RandomExcursionsVariant 5 4 4 2 4 3 4 4 4 2 0.911413 36/36 RandomExcursionsVariant 5 5 2 3 5 5 3 6 1 1 0.253551 35/36 RandomExcursionsVariant 4 6 5 3 1 6 4 2 3 2 0.350485 34/36 RandomExcursionsVariant 4 6 5 5 1 1 2 4 3 5 0.299251 34/36 RandomExcursionsVariant 5 5 6 3 2 3 2 3 4 3 0.671779 35/36 RandomExcursionsVariant 7 3 3 4 0 3 3 2 4 7 0.100508 35/36 RandomExcursionsVariant 5 2 5 5 2 2 1 4 5 5 0.407091 36/36 RandomExcursionsVariant 2 1 3 6 4 1 6 3 6 4 0.178278 35/36 RandomExcursionsVariant 3 2 2 3 4 7 4 5 2 4 0.468595 35/36 RandomExcursionsVariant 4 3 3 3 5 5 2 6 0 5 0.299251 36/36 RandomExcursionsVariant 3 3 5 3 1 4 7 3 3 4 0.468595 36/36 RandomExcursionsVariant 3 4 3 6 1 4 4 7 2 2 0.253551 36/36 RandomExcursionsVariant 3 6 3 4 3 4 5 1 2 5 0.534146 36/36 RandomExcursionsVariant 3 2 5 3 5 6 3 1 2 6 0.299251 36/36 RandomExcursionsVariant 2 4 1 7 6 6 4 1 1 4 0.054199 36/36 RandomExcursionsVariant 2 2 4 9 4 5 2 4 3 1 0.054199 36/36 RandomExcursionsVariant 6 5 5 8 3 7 7 4 6 4 0.834308 53/55 Serial 6 5 9 3 7 5 3 9 3 5 0.366918 55/55 Serial 4 9 5 4 4 7 7 4 4 7 0.678686 55/55 LinearComplexity - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - The minimum pass rate for each statistical test with the exception of the random excursion (variant) test is approximately = 52 for a sample size = 55 binary sequences. The minimum pass rate for the random excursion (variant) test is approximately = 33 for a sample size = 36 binary sequences. For further guidelines construct a probability table using the MAPLE program provided in the addendum section of the documentation. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
統計的仮説検定は仮説の蓋然性を推し量る手法であり「仮説は正しい」と明確な結論が得られる性質のものではない。したがって検定プログラムによって得られた結果の解釈はやや難しい。実際、上記の例では Python 標準の Mersenne-Twister アルゴリズムによる疑似乱数生成器を使っているにもかかわらず、P-VALUE\(\le 0.01\) となった検定や棄却されたビット列の存在が散見される。棄却された検定結果の解釈は意見の分かれるところでここで明確な指針は出せないが、個人的には次のようなことが起きているとき、そのビット列のランダム性の低さ、あるいは生成プロセスの欠陥を疑うべきと考える。
繰り返し検定しても
PROPORTIONが低い値となる検定項目がある。これはビット列が検定に対して違反する性質を持っていることを表している。これはC1への偏りとしても現れるだろう。繰り返し検定すると
P-VALUE\(\le 0.01\) が再現しやすい検定項目がある。これはC1-C10の分布に偏りがあることを示しており、C1に偏っているなら検定に反する方向、C10に偏っているなら検定に過剰適合 (オーバーフィット) する方向にランダム性の欠陥があることを意味する。
\(p\) 値は仮説 (この場合、ビット列がランダムであるという主張) が真であるときに \([0,1]\) 区間で一様に分布する統計量である。言い換えると、仮説が真であるならば有意水準 \(\alpha\) の確率で棄却が現れなければならない。したがって、例えば \(\alpha=0.01\) に対して 100 回の試行で 1 回程度の棄却が現れることはむしろ仮説が正しいことの健全な裏付けと考える必要がある。故に、棄却に対してはまず有意な再現性があるかを確認する必要がある。
また冒頭で述べたようにこれらの検定はヒューリスティックな側面を含んでいる。このため、実用には十分だが指標や手法との相性の悪さで棄却されやすい可能性や、一見ランダムだが 15 の検定では検出できない別の非ランダム性を含んでいる可能性も考慮すべきである。
有意水準の変更とグローバル定数
検定プログラムが PROPORTION で棄却と判断する有意水準 \(\alpha\) (および検定実施者によって変更可能な他の定数) は include/defs.h に定義されている。NIST はこの ALPHA 値を \([0.001,0.01]\) の範囲にすることを推奨している。
#define ALPHA 0.01 /* SIGNIFICANCE LEVEL */
#define MAXNUMOFTEMPLATES 148 /* APERIODIC TEMPLATES: 148=>temp_length=9 */
#define NUMOFTESTS 15 /* MAX TESTS DEFINED */
#define NUMOFGENERATORS 10 /* MAX PRNGs */統計検定の動作
検定スイートに含まれる 15 の検定がそれぞれどのようなことに焦点を当てて検定を行っているかを [1] に基づいて Table 1 に示す。1 回の検定イテレーションで評価の対象となる \(n\) ビット列を \(\epsilon\) とする。ここで "妥当" とは統計的仮説検定の観点で \(p\) 値が有意水準 \(\alpha\) より大きいという意味である。
| # | 検定 | 推奨パラメータ | 評価の焦点 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 入力ビット列 \(\epsilon\) の評価方法 | |||||||||||
| 1. | \(n \ge 100\) | 全体で 0 と 1 が同程度出現するか。 | |||||||||
| 全体で 1 の出現回数が妥当 (\(\simeq n/2\)) か。 | |||||||||||
| 2. | \(n \ge MN \ge 100\), \(M \ge 20\), \(N \lt 100\) |
局所的に 0 または 1 が偏在していないか。 | |||||||||
| 全体を \(N\) 個の \(M\) ビットブロックに分割しそれぞれの 1 の出現回数が妥当 (\(\simeq n/2\)) か。 | |||||||||||
| 3. | \(n \ge 100\) | 0 と 1 との振動間隔が妥当か。 | |||||||||
| \(\epsilon\) を構成する 0 と 1 の連の個数が妥当か。 | |||||||||||
| 4. |
|
局所的に妥当でない 0, 1 の振動が偏在していないか。 | |||||||||
| 全体を \(N\) 個の \(M\) ビットブロックに分割しそれぞれの 1 の最長連の長さの分布が妥当か。 | |||||||||||
| 5. | \(n \ge 38,912\) \(\mbox{ (in $M=Q=32$)}\) | 特定の周期で 0, 1 が出現していないか。 | |||||||||
| ビット列から構築した行列の階数が妥当か。 | |||||||||||
| 6. | \(n \ge 1000\) | 周期的な反復パターンを持っていないか。 | |||||||||
| ビット列を離散フーリエ変換し算出したピークが妥当か。 | |||||||||||
| 7. | \(m \ge 2\), \(N \le 100\), \(N=\lfloor n/M \rfloor\) | 特定のビットパターンが頻出していないか。 | |||||||||
| 全体を \(N\) 個の \(M\) ビットブロックに分割しそれぞれで規定の \(m\) ビットパターンの出現回数が妥当か。 | |||||||||||
| 8. | \(n \ge 106\) | 特定のビットパターンが頻出しているか。 | |||||||||
| 7. との違いは一致した場合に次の評価を 1 ビットスライドさせた位置から開始すること。 | |||||||||||
| 9. | \(\) | 著しく圧縮可能でないか。 | |||||||||
| 一致したパターン間のビット数の長さ (圧縮可能なビット列の長さに関連する指標) は妥当か。 | |||||||||||
| 10. | \(n \ge 10^6\), \(500 \le M \le 5000\), \(N \ge 200\) | ランダムと見なすのに十分な複雑さか。 | |||||||||
| 全体を \(N\) 個の \(M\) ビットブロックに分割し算出した線形帰還シフトレジスタが妥当な長さか。 | |||||||||||
| 11. | \(m \lt \lfloor \log_2 n \rfloor - 2\) | 任意の \(m\) ビットパターンが頻出していないか。 | |||||||||
| 全体を \(N\) 個の \(M\) ビットブロックに分割して \(m\) ビットの取り得るすべてのパターンに対して出現回数を取得し、他のパターンと比較して特出するパターンがないか (\(m=1\)のとき頻度検定と等価)。 | |||||||||||
| 12. | \(m \lt \lfloor \log_2 n \rfloor - 2\) | 任意の \(m\) ビットパターンが頻出していないか。 | |||||||||
| 連続/隣接する長さ\(m\)ビットと\(m+1\)ビットのブロックが重なる頻度が妥当か。 | |||||||||||
| 13. | \(n \gt 100\) | ランダムウォークの結果が妥当か。 | |||||||||
| ビットを \(\pm 1\) に変換して算出した累積和が妥当か。 | |||||||||||
| 14. | \(n \ge 10^6\) | ランダムウォークの結果が妥当か。 | |||||||||
| 累積和の累積過程で 0 から再び 0 に戻る単位を 1 サイクルとし、1 サイクル内で各状態 \((\pm 1, \ldots, \pm 4)\) の訪問回数が妥当か。 | |||||||||||
| 15. | \(n \ge 10^6\) | ランダムウォークの結果が妥当か。 | |||||||||
| 累積和の累積過程で 0 から再び 0 に戻る単位を 1 サイクルとし、1 サイクル内で各状態 \((\pm 1, \ldots, \pm 9)\) の訪問回数が妥当か。 |
マウラーの普遍統計検定
マウラーの普遍統計検定 (Maurer's universal statistics) は「正しい乱数生成器の生成するビット列は (情報劣化なしに) 大幅に圧縮することはできない」という考えに基づく (広範囲の統計的欠陥を検出することができるため "普遍" (Universal) であると考えられている)。もしビット列 \(\epsilon\) が大幅に圧縮できるようであれば、そのビット列を生成した乱数生成器には欠陥があるもの見なされるべきである。
この普遍統計検定はビット列 \(\epsilon\) を実際に圧縮する代わりに圧縮可能なビット列に関連する統計量を算出する。より具体的には、もし入力データ列がランダムであればそのランダム性を判断できる最小の長さを予測し、その長さを超えてもランダム性を確認できなければランダムではないと判断する。この普遍統計量は暗号論的乱数生成器のみならず圧縮アルゴリズムの評価にも利用されている。
参照
- RUKHIN, Andrew, et al. A statistical test suite for random and pseudorandom number generators for cryptographic applications. Booz-allen and hamilton inc mclean va, 2001.
- NIST SP 800-22: Download Documentation and Software