「暗号論的擬似乱数生成器」の版間の差分
m r2.5.4) (ロボットによる 追加: ru:Криптографически стойкий генератор псевдослучайных чисел |
m ボット: 言語間リンク 7 件をウィキデータ上の (d:Q1790389 に転記) |
||
94行目: | 94行目: | ||
[[Category:暗号技術]] |
[[Category:暗号技術]] |
||
[[Category:乱数]] |
[[Category:乱数]] |
||
[[de:Kryptographisch sicherer Zufallszahlengenerator]] |
|||
[[en:Cryptographically secure pseudorandom number generator]] |
|||
[[es:Generador de números pseudo-aleatorios criptográficamente seguro]] |
|||
[[he:מחולל פסבדו אקראי קריפטוגרפי]] |
|||
[[it:Generatore di numeri pseudocasuali crittograficamente sicuro]] |
|||
[[pt:CSPRNG]] |
|||
[[ru:Криптографически стойкий генератор псевдослучайных чисел]] |
2013年3月19日 (火) 23:09時点における版
暗号論的擬似乱数生成器(英語: cryptographically secure pseudo random number generator、CSPRNG)とは、暗号技術での利用に適した特性を持つ擬似乱数生成器 (PRNG) である。
暗号技術は様々な場面で乱数を必要とする。例えば、以下のようなものがある。
その際に求められる無作為性の質は様々である。例えば、何らかの暗号プロトコルで 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の将来の状態を予測できない。
多くのPRNGはCSPRNGとしては不適であり、上記の2つを満足しない。第一にPRNGの出力は統計的に無作為に見えるが、リバースエンジニアリングには耐性がない。従って、アルゴリズムを解析することで特別な統計的試験を設計でき、PRNG の出力が真の乱数ではないことを示すことができる。第二に状態が明らかであれば、過去の乱数列を再現でき、攻撃者が全ての過去のメッセージを読むことが可能となる。当然、将来の暗号も解読可能となる。
CSPRNGは、このような暗号解読に対抗するものとして設計される。
背景
Santha と Vazirani は、無作為性の弱いビット列を複数組み合わせることで高品質な擬似乱数列を生成できることを証明した[1]。それ以前にジョン・フォン・ノイマンはビット列からバイアスの大部分を除去できる簡単なアルゴリズムがあることを証明し[2]、Santha-Vazirani の設計に基づいたCSPRNGでフォン・ノイマンのアルゴリズムを入力ビット列に適用する必要がある。これを entropy extraction(エントロピー抽出)と呼び、研究が盛んな領域である。
設計
ここでは、CSPRNGの設計を
- ブロック暗号に基づく設計
- 数学的に解くのが難しい問題に基づく設計
- 特殊な設計
に分けて解説する。
暗号プリミティブに基づく設計
- 安全なブロック暗号は、CTRモードで動作させることでCSPRNGとして使うことができる。これは、ランダムな鍵を選んで0を暗号化し、次に1を暗号化し、さらに2を暗号化し、というように行う。カウンタを0以外の任意の値から開始することもできる。明らかに、その周期は n-ビットブロック暗号では 2n であり、鍵と平文の初期値が攻撃者に知られてしまうと、全く安全でなくなる。また、誕生日のパラドックスから2n/2の出力で真の乱数と1/2の確率で識別可能である。
- 暗号学的ハッシュ関数も、場合によってはCSPRNGとして利用可能である。この場合、カウンタの初期値をランダム化して秘密にしなければならない。カウンタが多倍長整数であれば、このCSPRNGはほぼ無限に乱数を生成できる。しかし、これについて安全ではないとする者もいる[3]。
- ストリーム暗号は、平文を擬似乱数列と(通常 XOR で)結合することで暗号文を生成する。カウンタを入力として暗号文を生成すれば、新たな擬似乱数列が生成される。これは、内部で生成する擬似乱数列がCSPRNGであるときだけ安全であり、一般にそうでないことが多い(RC4参照)。
この種の設計として ANSI X9.17 標準(Financial Institution Key Management (wholesale))に採用されたものがあり、FIPS にも採用されている。これは、次のような設計になっている。
- 入力: 64ビットの乱数のシード s と DES の56ビットの鍵 k
毎回、乱数を必要とする。
- 現在日時情報 D (可能な限り詳しい値)を使って、I = DES_k(D) を計算
- x = DES_k(I xor s) を出力し、シード s を DES_k(x xor I) に更新
このアルゴリズムは、DESの代わりにAES暗号を使えば改善されるだろうと指摘されている[4]。
数論的設計
- Blum-Blum-Shub は、強力だが条件付きでセキュリティが証明されている、素因数分解の難しさに基づいたCSPRNG。ただし、実装すると他の手法よりも性能が悪い。
特殊な設計
以下のような、暗号論的に安全となるよう設計された実用的PRNGがある。
- Yarrow algorithm は入力のエントロピー的品質を評価する。一方Fortuna はそれをしない。
- マイクロソフトのCAPIにある関数CryptGenRandom
- ISAAC(RC4から派生)
標準
標準規格化されたCSPRNGとして、以下のものがある。
- FIPS 186-2
- 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)
CSPRNG の統計的試験についての標準もある。
- A Statistical Test Suite for Random and Pseudorandom Number Generators, NIST Special Publication 800-22.
脚注
- ^ Miklos Santha, Umesh V. Vazirani (24 October 1984). "Generating quasi-random sequences from slightly-random sources" (PDF). Proceedings of the 25th IEEE Symposium on Foundations of Computer Science. University of California. pp. pages 434–440. ISBN 0-8186-0591-X. 2006年11月29日閲覧。
{{cite conference}}
:|page(s)=
にp.など余分の文字が入力されています。 (説明) - ^ John von Neumann (1963年3月1日). “Various techniques for use in connection with random digits”. The Collected Works of John von Neumann. Pergamon Press. pp. pages 768–770. ISBN 0-08-009566-6
- ^ Young and Yung, Malicious Cryptography, Wiley, 2004, sect 3.2
- ^ Young and Yung, op cit, sect 3.5.1
外部リンク
- RFC 4086, Randomness Requirements for Security
- Java "entropy pool" for cryptographically-secure unpredictable random numbers.
- Cryptographically Secure Random number on Windows without using CryptoAPI
- Conjectured Security of the ANSI-NIST Elliptic Curve RNG, Daniel R. L. Brown, IACR ePrint 2006/117.
- 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.
- Cryptanalysis of the Dual Elliptic Curve Pseudorandom Generator, Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/190.
- Efficient Pseudorandom Generators Based on the DDH Assumption, Reza Rezaeian Farashahi and Berry Schoenmakers and Andrey Sidorenko, IACR ePrint 2006/321.
- Analysis of the Linux Random Number Generator, Zvi Gutterman and Benny Pinkas and Tzachy Reinman.
- Recommendation for Random Number Generation Using Deterministic Random Bit Generators (Revised), Elaine Barker, John Kelsey, NIST SP800-90, NIST.