|
暗号論的擬似乱数生成器（、暗号論的に安全な疑似乱数生成器、CSPRNG）とは、暗号技術での利用に適した特性を持つ擬似乱数生成器 (PRNG) である。 暗号技術は様々な場面で乱数を必要とする。例えば、以下のようなものがある。 * 鍵生成 * Nonce （プロトコル上1度だけ使われる数、number used once） * Salt （ECDSA、RSASSA-PSS などの署名スキーマで使われる） * ワンタイムパッド その際に求められる無作為性の質は様々である。例えば、何らかの暗号プロトコルで Nonce を生成する際に求められるのは一意性だけである。一方、鍵の生成には高い無作為性が求められる。ワンタイムパッドの場合、鍵が高いエントロピーを持つ真の無作為情報源から作られることで、情報理論的に完全な秘密性が保証される。 理想的には、暗号プロトコル等に使用する乱数生成には高品質の情報源から得られるエントロピーを利用すべきである。それは、例えば量子論的な乱数生成器や予測不可能な何らかの系のプロセスである。情報理論的観点では、無作為性の程度とはエントロピーであり、ある系の入力のエントロピー以上のエントロピーは出力できないからである。 しかし、実用システムでは、利用可能なエントロピー以上の乱数を必要とすることがある。無作為性を引き出すプロセスには時間が掛かるためである。そのような場合に CSPRNG を使うことがある。CSPRNG は利用可能なエントロピーをより多くのビット数に拡張する。 アルゴリズムを開始する前に全エントロピーを利用可能である場合、ストリーム暗号が可能である。しかし、暗号の設計によっては実行時にエントロピーを追加することができ、そうなると生成される暗号はストリーム暗号ではなくなる。従って、ストリーム暗号とCSPRNGは密接に関連している。 == 要求仕様 == 通常のPRNGの要求仕様は、CSPRNG でも満足される。しかし、逆は真ではない。CSPRNG の要求仕様は2つに分類される。第一に、その統計的特性がよいこと（統計的無作為性の試験に合格すること）、第二に、激しい攻撃にも耐えること（初期状態や途中の状態が攻撃者に明らかになっても破られないこと）である。 * 全てのCSPRNGは "next-bit test" に合格する。next-bit test とは、乱数列の最初の k ビットを与えられたとき、k+1 番目のビットの値を多項式時間で2分の1をこえる確率で予測するアルゴリズムが存在しないことを確認する試験である。アンドリュー・チーチー・ヤオは1982年、next-bit test に合格した生成器は、無作為性に関する他の多項式時間統計試験にも合格することを証明した。 * 全てのCSPRNGは "state compromise extensions" に耐える。その状態の一部または全部が明らかになっても（あるいは正しく推測されても）、明らかにされた状態より以前に生成された乱数列は再現できない。さらに、実行中にエントロピーの入力がある場合、その入力を知っていてもCSPRNGの将来の状態を予測できない。 ::例: 円周率の数列から出力を生成するCSPRNGがあり、2進数化した数列のどこからを使うのか不明であるとする。円周率が正規数であるという仮定のもとでは、円周率は無作為な数列である。この場合、このアルゴリズムは next-bit test を満足し、したがって統計的に無作為性だと言える。しかし、このアルゴリズムは暗号論的に安全ではない。なぜなら、アルゴリズムの状態にあたる「円周率のどの部分が現在使われているか」を攻撃者が突き止めた場合、その攻撃者は先行するビットをすべて計算できるからである。 多くのPRNGはCSPRNGとしては不適であり、上記の2つを満足しない。第一にPRNGの出力は統計的に無作為に見えるが、リバースエンジニアリングには耐性がない。従って、アルゴリズムを解析することで特別な統計的試験を設計でき、PRNG の出力が真の乱数ではないことを示すことができる。第二に状態が明らかであれば、過去の乱数列を再現でき、攻撃者が全ての過去のメッセージを読むことが可能となる。当然、将来の暗号も解読可能となる。 CSPRNGは、このような暗号解読に対抗するものとして設計される。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「暗号論的擬似乱数生成器」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Cryptographically secure pseudorandom number generator 」があります。 スポンサード リンク
|