卒研は「疑似乱数生成器から生成される乱数列は、攻撃に使える特性を持つか」というものだったので、乱数の検定を考える必要がありました。
(ChachaはGoogleが標準化を推し進めているぐらいなので、特性が無さそうなのは目に見えてましたが・・・)
1.検定とは
統計的仮説検定とは、確率をもとに結論を導きます。そのため、「仮設を立て、実際に起った結果を確率的に検証し、結論を導く」という手順で行います。
この仮説ですが、帰無仮説(偶然でも生じる)とその逆の対立仮説(偶然では生じにくい)があります。検定のスタートは帰無仮説になります。
帰無仮説の下で統計量を求め、その統計量が偶然生じることではないことがわかれば、帰無仮説が棄却され、対立仮説が採用されます。偶然には生じないとされる領域は、その確率分布グラフの中の棄却域と呼ばれます。棄却域は実験者が任意に決めることができますが、基本的には全体の5%または1%と設定されます。その領域の大きさを決める水準を”有意水準”といい、一般に5%や1%が用いられます。このため、5%水準や1%水準という書き方をすることもあります。
参考:https://lecture.ecc.u-tokyo.ac.jp/~cueda/gengo/4-numeros/doc/n9-kentei.pdf
2.χ2 検定
χ2検定とは、帰無仮説が正しいという下で、検定統計量がχ2分布に従うような仮説検定手法の総称です。様々な方法がありますが、全て同じ式でχ2値は求められます。
その後、χ2 値と自由度を用いてp値を算出し、p値とα(有意水準から求められる)を比較して、帰無仮説が棄却されるかどうかを調べます。
自由度は、何個のデータを定めると他のデータが一意に定まるかの値になります。そのため、行列の分割表なら自由度は
で求められます。
そして、χ2 値と自由度を用いてp値を計算しますが、計算はExcelやPython、Rなどに関数が用意されているのでそれを用います。これらの関数の中身は調べてもわかりませんでした。
また、p値とは”特定の統計モデルに対してデータがどれぐらい整合しないかを示すことができる”ものです。最後までよくわかりませんでしたが、扱い方を間違えると間違った結論に陥るそうです。
p値参考:https://www.editage.jp/insights/is-my-research-significant-why-you-shouldnt-rely-on-p-values
χ2 分布の証明:https://shoichimidorikawa.github.io/Lec/ProbDistr/chiSq.pdf
3.乱数列の検定法(SP800-22)
乱数列の検定法には様々なものが提唱されています。いちばん有名なものは、NISTが提案しているSP800-22です。
これには15個の検定法が記載されています。昔のバージョンでは、DEF検定とLempel-Ziv検定が含まれていましたが、検定法としては疑問点の指摘があり、今は外されています。
論文:https://www.cryptrec.go.jp/exreport/cryptrec-ex-0211-2004.pdf
SP800-22はNISTにより提供されていますが、バグがあったりしてうまく動かないらしいです。そのため、David Johnston氏が作成した検定ツールを用いて検定を行いました。
SP800_22_tests:https://github.com/dj-on-github/sp800_22_tests
また、SP800_22に含まれているテストですが、たまにFAILすることがあります。そして、FAILが出る検定法が決まっていることに気が付きます。
調べると、ランダムウォークの検定法では、サイクル数が500未満だとFAILが返ってきます。そして、その確率は38%ですので、他の検定法と違って結構な確率でFAILが返ってきます。
その他、バイナリの検定法では、p値を調べると0.01(SP800-22での有意水準は1%を採用している)とほぼ差がなく、わずかに下回った状態でFAILとなっているものが殆どであったので、この検定法ではFAILが出たときはp値も確認するべきであると感じました。
補足:SP800_22_testsの使い方
SP800_22_testsをcloneし、makeします。基本的にはREADME.mdを読んでもらえばわかりますが、ちょっとわかりにくい部分があったのでそこだけ補足します。
まず、検定に用いる乱数列ですが、バイナリデータでなければなりません。そのため、バイナリデータを作成する必要があります。
私はC++で乱数列を0と1のテキストデータとして出力したあと、pythonでそれをバイナリデータに変換するコードを書いてバイナリデータを作りました。(暗号機をpythonで実装していたらこんな回りくどい手は使わなくてもよかった)
また、バイナリデータですが1Mbits以上の大きさが必要になります。
バイナリデータを作ったら、SP800_22_testsと同じディレクトリにそのファイルを移動させて、コマンド実行すれば検定してくれます。(windows環境なら、git Bash上でコマンドを打った)
1Mbitsのファイルで約3分ほどかかります。
4.乱数列の検定法(Dieharder)
もっと簡単に手に入るツールはないものかと、卒研後に調べていたら、Dieharderというツールがあるらしいです。apt-getで入ります。
こちらは更に巨大な乱数列が必要で、14GB以上の乱数列がいいそうです。
For a standard test, at least about 14 GB worth of data are needed; more if one of the tests needing large amounts of data returns a suspect result and
dieharderre-tries the same test with more data.
14GBの乱数列を用意するのは骨が折れそうですが、環境構築はSP800-22よりかんたんです。
5.乱数列の検定法(その他)
こちらはやったことはありませんが、以下のサイトで様々な乱数の検証ツールが示されています。
http://no-passwd.net/fst-01-neug-handbook/randomness-tests.html
おすすめとしてはTestU01らしいです。