totoBIGで超低い確率の現象が起きた件に関連して調べたことの記録。
自分でtotoBIGのようなものを実装すと考える。ハードウェア乱数は持ってないし信頼性に関する情報も持ってないので、擬似乱数での実装を考える。
安全に擬似乱数を使うには、
・優れた擬似乱数生成アルゴリズムを
・シードに高品質な乱数で
・十分な量で初期化する
ことが必要。
調べた結果、
p 14.times.map{rand(3)}
これだけでもかなり、安全な実装になる。
優れた擬似乱数アルゴリズム
このサイトが素晴らしい。やはりメルセンヌツイスターが最強。RubyはMTなのでこの点は問題なし。
https://ja.wikipedia.org/wiki/メルセンヌ・ツイスタ
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
https://github.com/ruby/ruby/blob/trunk/random.c
シードにする乱数
最近のOSは/dev/randomのように乱数を提供する仕組みを持ってるのでこれを使う。
Linuxの乱数インターフェースについては下記が詳しい。
http://man7.org/linux/man-pages/man7/random.7.html
/dev/randomと/dev/urandomについての参考。
http://news.mynavi.jp/news/2014/03/11/037/
Rubyではこれらを使ってrand用にシードを与えてる。
https://bugs.ruby-lang.org/projects/ruby-trunk/repository/revisions/57384
https://github.com/ruby/ruby/blob/trunk/random.c
十分な量のシード
さっきの
http://man7.org/linux/man-pages/man7/random.7.html
によると、暗号的な用途では、256bit与えれば十分であるように読める。
Rubyの場合、random.cにDEFAULT_SEED_CNTが4と定義されてて、これは32bit*4の意味になる。よって128bitがシードとして与えられ、この部分に関しては十分であるかの判断がつきかねる。とはいえ2**128の状態を持ちうると考えると早々問題は起きにくそうではある。
ここが不満であれば以下のようにして、Random.raw_seed(もしくはurandom)を使ってより大きな数字をシードにできる。
seed = Random.raw_seed(256).unpack("H*") #trunkだとRandom.urandom(256)
srand(seed)
シードを初回化するタイミングに関して
シードが高品質であれば、どんなタイミングで何回初期化しようとも問題はないはず。
低品質、もしくは乱数ではないようなシードは生成器を使いまわした方がマシ。
その他
メルセンヌツイスターは
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html
にあるように、十分な出力からはその後の出力が予測できる。
適切に初期化しなおか、CSPRNG
https://ja.wikipedia.org/wiki/暗号論的擬似乱数生成器
の利用が必要。