2929


暗号に使える乱数と使えない乱数があるようですが、なぜそのようになるのかわかりません 例えば、円周率からN番目の値をMだけ取り出したものは使え
漸化式で初期値MでN回実行した結果は使えないというような例だったと思います。 どちらも結果的には予測可能だと思うのですが


CC BY-SA 3.0
2014-12-31T18:11:58.737
2873
2015-01-06T22:47:11.327
2015-01-05T13:35:54.467
5575
question
アルゴリズム security
暗号に使える乱数と使えない乱数


まず重要なポイントとして、擬似乱数のシードとなる真の乱数 (質問の場合は円周率のほうではN, 漸化式の方ではM)
は十分に広い空間からランダムに選ばれなくてはなりません。
どんな擬似乱数生成器を使っていたとしてもシードが高々1億程度では総当たりで(比較的)簡単にシードがみつかってしまい生成される乱数が再現できてしまいます。
円周率の先頭100万桁のどこかから選ぶなどは問題外です。 シードはRSA/DSAなどの鍵長に合わせて 1000 bit 程度 (10進数で300桁程度)
は欲しいかと思います。

質問にある円周率を擬似乱数として使う方法ですが、円周率の N桁目からの数列がある長さ与えられた時に N 自体を逆算したり, 次の出力を推測する高速な
(Nのビット数の多項式時間で実行可能な) アルゴリズムは知られていないかと思います。 そのため N
が十分に大きければある時点までの出力が攻撃者に漏洩したとしても、そこから先の出力を攻撃者が予測することはできません。 そういう意味で
_"円周率からN番目の値をMだけ取り出したものは使え"_ るというのが質問者が読んだ文献の例の意図だったのかと思います。 ([Wikipedia の
CSPRNG の Requirements の項目の it may well satisfy the next-bit
test](http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Requirements)
も同じことを言っているのだと思います)

一方で、現実にこの方法で円周率から擬似乱数を作るためには円周率のN (e.g. 2^1000)
桁目からを高速に計算する方法が必要です。円周率は1桁目から順番に計算するよりは効率のよいアルゴリズムが知られているようですが、 それでも高々8000兆
(== 2^53) 桁程度らしいので 円周率のN桁目からを高速に求めるのは現状では不可能なようです。
なので円周率のN桁目からを使う擬似乱数はNが十分に大きければ next-bit test には耐える安全性がある
(それまでの出力からそこから先の出力が予測できない)けれども、 そもそもN桁目からを高速に求める方法もないので現実的には使えません。

他方の漸化式を使う方法は例えば v0 = シード, v1 = f(v0), v2 = f(v1), .... のようになっているので、 出力の一部 (vn)
が漏洩してしまうと、シードの大きさに関係なく、それ以降の出力は vn+1 = f(vn), vn+2 = f(vn+1)
と攻撃者が簡単に推測できてしまいます。 そのため _"漸化式で実行した結果"_ は暗号には使えません。
(現代的な暗号では暗号化手法や乱数の生成方法は攻撃者に公開されているものとして考えて安全性を評価するので、この場合 f
は攻撃者にも知られているものと考えます) ちなみに擬似乱数として有名な Mersenne Twister
も漸化式を使っているので、出力が漏洩するとそこから先の出力を予測することが可能で暗号には使えませんが、[Mersenne Twister
の出力を暗号学的ハッシュ関数で適切に変換したものは安全なようです。ただその際もシード 32bit 整数
などではなくもっと広い空間から取らなくてはならない点は変わりません。](http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/faq.html)

ここまで触れていなかった CSPRNG の Requirements のもう１つの項目の _"state compromise extensions"_
ですが、 これはある時点で擬似乱数生成の内部状態が攻撃者に漏洩してもそれ以前の出力は推測できてはならないということです。
円周率を使った擬似乱数はある時点で内部でi桁目を使っていることが攻撃者に漏洩してしまうとそれより前の出力は i-1, i-2,
i-3桁目だったことが分かってしまうので "state compromise extensions" の要求を満たしません。そのため例え N
が十分に大きかったとしても円周率を使った方法では next-bit test は通るけど state compromise extensions
は通らないので、CSPRNGの要求はみたしません。
逆に漸化式を使った方法は漸化式が暗号学的ハッシュ関数のような一方向関数なら、ある時点での内部状態が攻撃者に漏洩してもそれ以前の状態を復元するのは困難なので
"state compromise extensions" の要件を満たすことは可能だと思います。


CC BY-SA 3.0
2015-01-02T03:15:53.903
2929
2015-01-02T03:15:53.903
5575
2873
answer


本題とは外れますが、円周率の数字を擬似乱数として使ってよいかは全くの未保証です。
例えば（ほとんどの人はそう信じていますが）2と3が同程度で出現するかどうかも数学的には証明できていません。
よって特に暗号分野では決して使用できないと思われます。

参考とされたWikipediaの文献にも[非常にわかりづらく書いてあります](http://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7%E8%AB%96%E7%9A%84%E6%93%AC%E4%BC%BC%E4%B9%B1%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8)が、質問文から誤解を受けてしまう可能性を考えてあえて補足いたしました。


CC BY-SA 3.0
2015-01-06T22:47:11.327
3220
2015-01-06T22:47:11.327
5492
2873
answer