暗号論的擬似乱数生成器のソースを表示

'''暗号論的擬似乱数生成器'''（'''CSPRNG、'''{{lang-en|cryptographically secure pseudo random number generator}}、暗号論的にセキュアな疑似乱数生成器）とは、暗号技術での利用に適した特性を持つ[[擬似乱数]]生成器 (PRNG) である。

暗号の応用では様々な場面で[[乱数]]を必要とする。例えば、以下のようなものがある。
* [[鍵 (暗号)|鍵]]生成
* [[Nonce]] （プロトコル上1度だけ使われる数、number used once）
* Salt （ECDSA、RSASSA-PSS などの署名スキーマで使われる）
* [[ワンタイムパッド]]

その際に必要な乱数の性質は様々である。例えば、何らかの暗号プロトコルで Nonce を生成する際に求められるのは一意性だけである。一方、[[鍵 (暗号)|鍵]]の生成には高い無作為性が求められる。ワンタイムパッドには暗号論的擬似乱数も不適で、高い[[エントロピー]]を持つ真の無作為情報源が必要であり、それにより[[情報理論的安全性]]を得る。

理想的には、暗号プロトコル等に使用する乱数生成には高品質の情報源から得られるエントロピーを利用すべきである。それは、例えば量子論的な乱数生成器や予測不可能な何らかの系のプロセスである。<!-- しかし、表面上は独立したプロセスが、実は予期しない相関関係を持つ場合もある。-->情報理論的観点では、無作為性の程度とは[[エントロピー]]であり、ある系の入力のエントロピー以上のエントロピーは出力できないからである。しかし、実用システムでは、利用可能なエントロピー以上の乱数を必要とすることがある。無作為性を引き出すプロセスには時間が掛かるためである。そのような場合に CSPRNG を使うことがある。CSPRNG は利用可能なエントロピーをより多くのビット数に拡張する。

== 要求仕様 ==
通常のPRNGの要求仕様は、CSPRNG でも満足される。しかし、逆は真ではない。CSPRNG の要求仕様は2つに分類される。第一に、その統計的特性がよいこと（統計的無作為性の試験に合格すること）、第二に、激しい攻撃にも耐えること（初期状態や途中の状態が攻撃者に明らかになっても破られないこと）である。

* 全ての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の将来の状態を予測できない。
::例: [[円周率]]の数列から出力を生成するCSPRNGがあり、2進数化した数列のどこからを使うのか不明であるとする。<!--円周率が[[正規数]]であるという仮定のもとでは、円周率は無作為な数列である。この場合、このアルゴリズムは -->これは<!--正規数だが無作為でない数というのは普通にあるので「正規数であるという仮定のもとでは、円周率は無作為な数列」というのはおかしい-->next-bit testを満足<!--し、したがって統計的に無作為性だと言える。-->するが<!--しかし、このアルゴリズムは-->暗号論的に安全ではない。なぜなら、アルゴリズムの状態にあたる「円周率のどの部分が現在使われているか」を攻撃者が突き止めた場合、その攻撃者は先行するビットをすべて計算できるからである。

多くのPRNGはCSPRNGとしては不適であり、上記の2つを満足しない。第一にPRNGの出力は統計的に無作為に見えるが、[[リバースエンジニアリング]]には耐性がない<!-- ??? --->。従って、アルゴリズムを解析することで特別な統計的試験を設計でき、PRNG の出力が真の乱数ではないことを示すことができる。第二に状態が明らかであれば、過去の乱数列を再現でき、攻撃者が全ての過去のメッセージを読むことが可能となる。当然、将来の暗号も解読可能となる。

CSPRNGは、このような[[暗号解読]]に対抗するものとして設計される。

== 背景 ==
Santha と Vazirani は、無作為性の弱いビット列を複数組み合わせることで高品質な擬似乱数列を生成できることを証明した<ref name=santha-vazirani>{{cite conference| author = Miklos Santha, Umesh V. Vazirani| title = Generating quasi-random sequences from slightly-random sources| book-title = Proceedings of the 25th IEEE Symposium on Foundations of Computer Science| pages = 434&ndash;440| publisher = [[カリフォルニア大学|University of California]]| date = 1984年10月24日| location = | url = http://www.cs.berkeley.edu/~vazirani/pubs/quasi.pdf| doi = | id = ISBN 0-8186-0591-X | accessdate = 2006年11月29日}}</ref>。それ以前に[[ジョン・フォン・ノイマン]]はビット列からバイアスの大部分を除去できる簡単なアルゴリズムがあることを証明し<ref name=neumann-random>{{cite book| author = [[ジョン・フォン・ノイマン|John von Neumann]]| title = The Collected Works of John von Neumann| publisher = Pergamon Press| date = 1963年3月1日| location =| pages = 768&ndash;770| chapter = Various techniques for use in connection with random digits| url =| doi =| id = ISBN 0-08-009566-6}}</ref>、Santha-Vazirani の設計に基づいたCSPRNGでフォン・ノイマンのアルゴリズムを入力ビット列に適用する必要がある。これを ''entropy extraction''（エントロピー抽出）と呼び、研究が盛んな領域である。

== 設計 ==
ここでは、CSPRNGの設計を
# ブロック暗号や暗号学的ハッシュ関数などの暗号プリミティブに基づく設計
# 数学的に解くのが難しい問題に基づく設計
# 特殊な設計
に分けて解説する。

=== 暗号プリミティブに基づく設計 ===
* 安全な[[ブロック暗号]]は、[[暗号利用モード#CTR|CTRモード]]で動作させることでCSPRNGとして使うことができる。これは、[[ランダム]]な鍵を選んで0を暗号化し、次に1を暗号化し、さらに2を暗号化し、というように行う。カウンタを0以外の任意の値から開始することもできる。明らかに、その周期は ''n''-ビットブロック暗号では 2<sup>''n''</sup> であり、鍵と平文の初期値が攻撃者に知られてしまうと、全く安全でなくなる。また、[[誕生日のパラドックス]]から2<sup>''n''/2</sup>の出力で真の乱数と1/2の確率で識別可能である。
* [[暗号学的ハッシュ関数]]もCSPRNGとして利用可能である。カウンタ値のハッシュ値を次々に計算すればよい。しかし、これについて安全ではないとする主張もある<ref>Young and Yung, Malicious Cryptography, Wiley, 2004, sect 3.2</ref>。
* [[ストリーム暗号]]は、[[平文]]を擬似乱数列と（通常 XOR で）結合することで暗号文を生成する。カウンタを平文として暗号文を生成すれば、新たな擬似乱数列が生成され、おそらく内部の疑似乱数列より周期を長くできる。この生成法は、内部で生成する擬似乱数列がCSPRNGであるときだけ安全であるが、一般にそうでないことが多い（[[RC4]]参照）。
* [[ANSI]] X9.17 標準（''Financial Institution Key Management (wholesale)''）<ref>https://nvlpubs.nist.gov/nistpubs/Legacy/FIPS/fipspub171.pdf (Appendix C)</ref>では、ブロック暗号である[[DES]]を用いた疑似乱数の生成法を挙げており、[[Federal Information Processing Standards|FIPS]]にも採用されている。この生成法では、64ビットのシード ''s'' とDESの鍵 ''k''を用いて、次のように64ビット乱数を生成する。まず現在日時情報 ''D'' （可能な限り詳しい値）を使って、中間値 <math>I = DES_k(D)</math> を計算、次に <math>x = DES_k(I \oplus s)</math> を計算して乱数として出力し、シードを <math> s=DES_k(x \oplus I)</math> と更新する。64ビット以上の乱数が必要な場合は、上記の手続きを必要回数繰り返す。DESを別の任意のブロック暗号に置き換えることもでき、[[Advanced Encryption Standard|AES]]の利用が推奨されている<ref>Young and Yung, op. cit., sect 3.5.1</ref>。

=== 数論的設計 ===
* [[Blum-Blum-Shub]] は、[[素因数分解]]の難しさに基づいたCSPRNGであり、条件付きでセキュリティが証明されている。ただし、実装すると他の手法よりも非常に性能が悪い。
* Micali–Schnorr generator, Naor-Reingold pseudorandom function

=== 特殊な設計 ===
以下のような、暗号論的に安全となるよう設計された実用的PRNGがある。

*[http://www.schneier.com/yarrow.html Yarrow algorithm] は入力のエントロピー的品質を評価する。一方[https://web.archive.org/web/20121103190507/http://www.citadelsoftware.ca/fortuna/fortuna.htm Fortuna] はそれをしない。
*[[マイクロソフト]]の[[Cryptographic API|CAPI]]にある関数[http://msdn2.microsoft.com/en-us/library/aa379942.aspx CryptGenRandom]
*[[ISAAC]]（[[RC4]]から派生）

== 標準 ==
標準規格化されたCSPRNGとして、以下のものがある。

* FIPS 186-2
* [https://web.archive.org/web/20070926201210/http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf NIST SP 800-90]: Hash_DRBG, HMAC_DRBG, CTR_DRBG, Dual_EC_DRBG
* ANSI X9.17-1985 Appendix C
* ANSI X9.31-1998 Appendix A.2.4
* ANSI X9.62-1998 Annex A.4, obsoleted by ANSI X9.62-2005, Annex D (HMAC_DRBG)

[[アメリカ国立標準技術研究所|NIST]] では、これに関するよい[http://csrc.nist.gov/CryptoToolkit/tkrng.html リンク集]を管理している。

CSPRNG の統計的試験についての標準もある。

* ''A Statistical Test Suite for Random and Pseudorandom Number Generators'', [http://csrc.nist.gov/rng/SP800-22b.pdf NIST Special Publication 800-22].

== 脚注 ==
{{reflist}}

== 外部リンク ==
* {{IETF RFC|4086}}, Randomness Requirements for Security
* [http://random.hd.org/ Java "entropy pool" for cryptographically-secure unpredictable random numbers.]
* [http://blogs.msdn.com/michael_howard/archive/2005/01/14/353379.aspx Cryptographically Secure Random number on Windows without using CryptoAPI]
* [http://eprint.iacr.org/2006/117 Conjectured Security of the ANSI-NIST Elliptic Curve RNG], Daniel R. L. Brown, IACR ePrint 2006/117.
* [http://eprint.iacr.org/2007/048 A Security Analysis of the NIST SP 800-90 Elliptic Curve Random Number Generator], Daniel R. L. Brown and Kristian Gjosteen, IACR ePrint 2007/048.  To appear in CRYPTO 2007.
* [http://eprint.iacr.org/2006/190 Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator], Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/190.
* [http://eprint.iacr.org/2006/321 Efficient Pseudorandom Generators Based on the DDH Assumption], Reza Rezaeian Farashahi and Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/321.
* [http://eprint.iacr.org/2006/086.pdf Analysis of the Linux Random Number Generator], Zvi Gutterman and Benny Pinkas and Tzachy Reinman.
* [https://web.archive.org/web/20070926201210/http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised)], Elaine Barker, John Kelsey, NIST SP800-90, NIST.

{{cryptography navbox}}

{{デフォルトソート:あんこうろんてききしらんすうせいせいき}}
[[Category:暗号技術]]
[[Category:乱数]]