暗号論的擬似乱数生成器

暗号論的擬似乱数生成器（、暗号論的にセキュアな疑似乱数生成器、CSPRNG）とは、暗号技術での利用に適した特性を持つ擬似乱数生成器 (PRNG) である。
暗号の応用では様々な場面で乱数を必要とする。例えば、以下のようなものがある。
その際に必要な乱数の性質は様々である。例えば、何らかの暗号プロトコルで Nonce を生成する際に求められるのは一意性だけである。一方、鍵の生成には高い無作為性が求められる。ワンタイムパッドには暗号論的擬似乱数も不適で、高いエントロピーを持つ真の無作為情報源が必要であり、それにより情報理論的安全性を得る。
理想的には、暗号プロトコル等に使用する乱数生成には高品質の情報源から得られるエントロピーを利用すべきである。それは、例えば量子論的な乱数生成器や予測不可能な何らかの系のプロセスである。情報理論的観点では、無作為性の程度とはエントロピーであり、ある系の入力のエントロピー以上のエントロピーは出力できないからである。しかし、実用システムでは、利用可能なエントロピー以上の乱数を必要とすることがある。無作為性を引き出すプロセスには時間が掛かるためである。そのような場合に CSPRNG を使うことがある。CSPRNG は利用可能なエントロピーをより多くのビット数に拡張する。
要求仕様.
通常のPRNGの要求仕様は、CSPRNG でも満足される。しかし、逆は真ではない。CSPRNG の要求仕様は2つに分類される。第一に、その統計的特性がよいこと（統計的無作為性の試験に合格すること）、第二に、激しい攻撃にも耐えること（初期状態や途中の状態が攻撃者に明らかになっても破られないこと）である。
多くのPRNGはCSPRNGとしては不適であり、上記の2つを満足しない。第一にPRNGの出力は統計的に無作為に見えるが、リバースエンジニアリングには耐性がない。従って、アルゴリズムを解析することで特別な統計的試験を設計でき、PRNG の出力が真の乱数ではないことを示すことができる。第二に状態が明らかであれば、過去の乱数列を再現でき、攻撃者が全ての過去のメッセージを読むことが可能となる。当然、将来の暗号も解読可能となる。
CSPRNGは、このような暗号解読に対抗するものとして設計される。
背景.
Santha と Vazirani は、無作為性の弱いビット列を複数組み合わせることで高品質な擬似乱数列を生成できることを証明した。それ以前にジョン・フォン・ノイマンはビット列からバイアスの大部分を除去できる簡単なアルゴリズムがあることを証明し、Santha-Vazirani の設計に基づいたCSPRNGでフォン・ノイマンのアルゴリズムを入力ビット列に適用する必要がある。これを "entropy extraction"（エントロピー抽出）と呼び、研究が盛んな領域である。
設計.
ここでは、CSPRNGの設計を
に分けて解説する。
暗号プリミティブに基づく設計.
この種の設計として ANSI X9.17 標準（"Financial Institution Key Management (wholesale)"）に採用されたものがあり、FIPS にも採用されている。これは、次のような設計になっている。
毎回、乱数を必要とする。
このアルゴリズムは、DESの代わりにAESを使えば改善されるだろうと指摘されている。
特殊な設計.
以下のような、暗号論的に安全となるよう設計された実用的PRNGがある。
標準.
標準規格化されたCSPRNGとして、以下のものがある。
NIST では、これに関するよいリンク集を管理している。
CSPRNG の統計的試験についての標準もある。