乱数検定: NIST SP 800-22

Takami Torao 2001年の論文 #NIST検定 #Randomness
  • このエントリーをはてなブックマークに追加

概要

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

  1. 概要
  2. 検定プログラムの実行と評価
    1. 検定プログラムのビルド
    2. テストデータの作成
    3. 検定プログラムの実行
    4. 検定結果の評価
    5. 有意水準の変更とグローバル定数
  3. 統計検定の動作
    1. マウラーの普遍統計検定
  4. 参照

検定プログラムの実行と評価

検定プログラムは NIST のサイト [2] からダウンロードすることができる。以降は Ubuntu 22.04 環境で検定プログラム assess を実行し結果を評価するまでの流れである。Windows では WSL や cygwin で実行することができる。

検定プログラムのビルド

まずアーカイブを解凍して検定プログラムのビルドを行う。ビルドには makegcc が必要であるためあらかじめ 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) を指定する。次のような対話形式が開始する。

  1. 検定対象は [0] 入力ファイルか、[1-9] 組み込みの疑似乱数生成器か。
  2. [0] 一部の検定のみを行うか、[1] すべての検定を行うか。
  3. いくつかの検定に対するパラメータの設定。
  4. 検定のイテレーション回数 \(t\) (=bitstreams)。
  5. 入力ファイルは [0] ASCII か [1] バイナリか。

以下は実際に assess を起動して前述の random.bin の検定を行った例である。入力が必要な箇所に ✅ マークを付けている。

$ ./assess 1000000
           G 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\) より大きいという意味である。

Table 1. それぞれの検定で行っている評価。
# 検定 推奨パラメータ 評価の焦点
入力ビット列 \(\epsilon\) の評価方法
1. 頻度(Frequency) \(n \ge 100\) 全体で 0 と 1 が同程度出現するか。
全体で 1 の出現回数が妥当 (\(\simeq n/2\)) か。
2. ブロック頻度(Block Frequency) \(n \ge MN \ge 100\),
\(M \ge 20\), \(N \lt 100\)
局所的に 0 または 1 が偏在していないか。
全体を \(N\) 個の \(M\) ビットブロックに分割しそれぞれの 1 の出現回数が妥当 (\(\simeq n/2\)) か。
3. (Runs) \(n \ge 100\) 0 と 1 との振動間隔が妥当か。
\(\epsilon\) を構成する 0 と 1 の連の個数が妥当か。
4. ブロック内最長連(Longest Run of Ones)
最小\(n\) \(M\)
128 8
6272 128
750,000 10⁴
局所的に妥当でない 0, 1 の振動が偏在していないか。
全体を \(N\) 個の \(M\) ビットブロックに分割しそれぞれの 1 の最長連の長さの分布が妥当か。
5. 2 値行列階数(The Binary Matrix Rank) \(n \ge 38,912\) \(\mbox{ (in $M=Q=32$)}\) 特定の周期で 0, 1 が出現していないか。
ビット列から構築した行列の階数が妥当か。
6. 離散フーリエ変換(The Discrete Fourier Transform (Spectral)) \(n \ge 1000\) 周期的な反復パターンを持っていないか。
ビット列を離散フーリエ変換し算出したピークが妥当か。
7. 重なりのないテンプレート適合(Non-overlapping Template Matching) \(m \ge 2\), \(N \le 100\), \(N=\lfloor n/M \rfloor\) 特定のビットパターンが頻出していないか。
全体を \(N\) 個の \(M\) ビットブロックに分割しそれぞれで規定の \(m\) ビットパターンの出現回数が妥当か。
8. 重なりのあるテンプレート適合(Overlapping Template Matching) \(n \ge 106\) 特定のビットパターンが頻出しているか。
7. との違いは一致した場合に次の評価を 1 ビットスライドさせた位置から開始すること。
9. マウラーの普遍統計(Maurer's Universal Statistic) \(\) 著しく圧縮可能でないか。
一致したパターン間のビット数の長さ (圧縮可能なビット列の長さに関連する指標) は妥当か。
10. 線形複雑度(The Linear Complexity) \(n \ge 10^6\), \(500 \le M \le 5000\), \(N \ge 200\) ランダムと見なすのに十分な複雑さか。
全体を \(N\) 個の \(M\) ビットブロックに分割し算出した線形帰還シフトレジスタが妥当な長さか。
11. 系列(The Serial) \(m \lt \lfloor \log_2 n \rfloor - 2\) 任意の \(m\) ビットパターンが頻出していないか。
全体を \(N\) 個の \(M\) ビットブロックに分割して \(m\) ビットの取り得るすべてのパターンに対して出現回数を取得し、他のパターンと比較して特出するパターンがないか (\(m=1\)のとき頻度検定と等価)。
12. 近似エントロピー(The Approximate Entropy) \(m \lt \lfloor \log_2 n \rfloor - 2\) 任意の \(m\) ビットパターンが頻出していないか。
連続/隣接する長さ\(m\)ビットと\(m+1\)ビットのブロックが重なる頻度が妥当か。
13. 累積和(Cumulative Sums) \(n \gt 100\) ランダムウォークの結果が妥当か。
ビットを \(\pm 1\) に変換して算出した累積和が妥当か。
14. ランダム偏差(The Random Excursions) \(n \ge 10^6\) ランダムウォークの結果が妥当か。
累積和の累積過程で 0 から再び 0 に戻る単位を 1 サイクルとし、1 サイクル内で各状態 \((\pm 1, \ldots, \pm 4)\) の訪問回数が妥当か。
15. ランダム偏差変種(The Random Excursions Variant) \(n \ge 10^6\) ランダムウォークの結果が妥当か。
累積和の累積過程で 0 から再び 0 に戻る単位を 1 サイクルとし、1 サイクル内で各状態 \((\pm 1, \ldots, \pm 9)\) の訪問回数が妥当か。

マウラーの普遍統計検定

マウラーの普遍統計検定 (Maurer's universal statistics) は「正しい乱数生成器の生成するビット列は (情報劣化なしに) 大幅に圧縮することはできない」という考えに基づく (広範囲の統計的欠陥を検出することができるため "普遍" (Universal) であると考えられている)。もしビット列 \(\epsilon\) が大幅に圧縮できるようであれば、そのビット列を生成した乱数生成器には欠陥があるもの見なされるべきである。

この普遍統計検定はビット列 \(\epsilon\) を実際に圧縮する代わりに圧縮可能なビット列に関連する統計量を算出する。より具体的には、もし入力データ列がランダムであればそのランダム性を判断できる最小の長さを予測し、その長さを超えてもランダム性を確認できなければランダムではないと判断する。この普遍統計量は暗号論的乱数生成器のみならず圧縮アルゴリズムの評価にも利用されている。

参照

  1. 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.
  2. NIST SP 800-22: Download Documentation and Software