「暗号論的擬似乱数生成器」の版間の差分
削除された内容 追加された内容
編集の要約なし |
m 誤字 |
||
10行目:
理想的には、暗号プロトコル等に使用する乱数生成には高品質の情報源から得られるエントロピーを利用すべきである。それは、例えば量子論的な乱数生成器や予測不可能な何らかの系のプロセスである。<!-- しかし、表面上は独立したプロセスが、実は予期しない相関関係を持つ場合もある。-->情報理論的観点では、無作為性の程度とは[[エントロピー]]であり、ある系の入力のエントロピー以上のエントロピーは出力できないからである。
しかし、実用システムでは、利用可能なエントロピー以上の乱数を必要とすることがある。無作為性を引き出すプロセスには時間が
アルゴリズムを開始する前に全エントロピーを利用可能である場合、[[ストリーム暗号]]が可能である。しかし、暗号の設計によっては実行時にエントロピーを追加することができ、そうなると生成される暗号はストリーム暗号ではなくなる。従って、ストリーム暗号とCSPRNGは密接に関連している。<!-- ??? -->
17行目:
通常のPRNGの要求仕様は、CSPRNG でも満足される。しかし、逆は真ではない。CSPRNG の要求仕様は2つに分類される。第一に、その統計的特性がよいこと（統計的無作為性の試験に合格すること）、第二に、激しい攻撃にも耐えること（初期状態や途中の状態が攻撃者に明らかになっても破られないこと）である。
* 全てのCSPRNGは "next-bit test" に合格する。next-bit test とは、乱数列の最初の <var>k</var> ビットを与えられたとき、<var>k</var>+1 番目のビットの値を多項式時間で2分の1
* 全てのCSPRNGは "state compromise extensions" に耐える。その状態の一部または全部が明らかになっても（あるいは正しく推測されても）、生成される乱数列を別の場所で再現できない。さらに、実行中にエントロピーの入力がある場合、その入力を知っていてもCSPRNGの将来の状態を予測できない。
::例: [[円周率]]の数列から出力を生成するCSPRNGがあり、2進数化した数列のどこからを使うのか不明であるとする。円周率は無作為な数列であり next-bit test を満足するので、無作為性は十分である（これは、円周率が[[正規数]]であるとした場合）。しかし、アルゴリズムの状態が明らかであれば、円周率のどの部分を使っているかがわかるため、後者の要求仕様を満足せず、安全ではない。
| |||