「暗号論的擬似乱数生成器」の版間の差分
削除された内容 追加された内容
Claw of Slime (会話 | 投稿記録) m編集の要約なし |
Miyakawataku (会話 | 投稿記録) "state compromise extensions" の要件に関する記述を、英語版にしたがい訂正しました。 |
||
18行目:
* 全てのCSPRNGは "next-bit test" に合格する。next-bit test とは、乱数列の最初の <var>k</var> ビットを与えられたとき、<var>k</var>+1 番目のビットの値を多項式時間で2分の1をこえる確率で予測するアルゴリズムが存在しないことを確認する試験である。[[アンドリュー・チーチー・ヤオ]]は[[1982年]]、next-bit test に合格した生成器は、無作為性に関する他の多項式時間統計試験にも合格することを証明した。
* 全てのCSPRNGは "state compromise extensions" に耐える。その状態の一部または全部が明らかになっても（あるいは正しく推測されても）、明らかにされた状態より以前に生成され
::例: [[円周率]]の数列から出力を生成するCSPRNGがあり、2進数化した数列のどこからを使うのか不明であるとする。円周率が[[正規数]]であるという仮定のもとでは、円周率は無作為な数列であ
多くのPRNGはCSPRNGとしては不適であり、上記の2つを満足しない。第一にPRNGの出力は統計的に無作為に見えるが、[[リバースエンジニアリング]]には耐性がない<!-- ??? --->。従って、アルゴリズムを解析することで特別な統計的試験を設計でき、PRNG の出力が真の乱数ではないことを示すことができる。第二に状態が明らかであれば、過去の乱数列を再現でき、攻撃者が全ての過去のメッセージを読むことが可能となる。当然、将来の暗号も解読可能となる。
| |||