暗号 論 的 擬似 乱数 生成 器
その
要求 仕様
[全 ての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を満足 するが暗号 論 的 に安全 ではない。なぜなら、アルゴリズムの状態 にあたる「円周 率 のどの部分 が現在 使 われているか」を攻撃 者 が突 き止 めた場合 、その攻撃 者 は先行 するビットをすべて計算 できるからである。
CSPRNGは、このような
背景
[Santha と Vazirani は、
設計
[ここでは、CSPRNGの
- ブロック
暗号 や暗号 学 的 ハッシュ関数 などの暗号 プリミティブに基 づく設計 数学 的 に解 くのが難 しい問題 に基 づく設計 特殊 な設計
に
暗号 プリミティブに基 づく設計
[安全 なブロック暗号 は、CTRモードで動作 させることでCSPRNGとして使 うことができる。これは、ランダムな鍵 を選 んで0を暗号 化 し、次 に1を暗号 化 し、さらに2を暗号 化 し、というように行 う。カウンタを0以外 の任意 の値 から開始 することもできる。明 らかに、その周期 は n-ビットブロック暗号 では 2n であり、鍵 と平文 の初期 値 が攻撃 者 に知 られてしまうと、全 く安全 でなくなる。また、誕生 日 のパラドックスから2n/2の出力 で真 の乱数 と1/2の確 率 で識別 可能 である。暗号 学 的 ハッシュ関数 もCSPRNGとして利用 可能 である。カウンタ値 のハッシュ値 を次々 に計算 すればよい。しかし、これについて安全 ではないとする主張 もある[3]。- ストリーム
暗号 は、平文 を擬似 乱数 列 と(通常 XOR で)結合 することで暗号 文 を生成 する。カウンタを平文 として暗号 文 を生成 すれば、新 たな擬似 乱数 列 が生成 され、おそらく内部 の疑似 乱数 列 より周期 を長 くできる。この生成 法 は、内部 で生成 する擬似 乱数 列 がCSPRNGであるときだけ安全 であるが、一般 にそうでないことが多 い(RC4参照 )。 - ANSI X9.17
標準 (Financial Institution Key Management (wholesale))[4]では、ブロック暗号 であるDESを用 いた疑似 乱数 の生成 法 を挙 げており、FIPSにも採用 されている。この生成 法 では、64ビットのシード s とDESの鍵 kを用 いて、次 のように64ビット乱数 を生成 する。まず現在 日時 情報 D (可能 な限 り詳 しい値 )を使 って、中間 値 を計算 、次 に を計算 して乱数 として出力 し、シードを と更新 する。64ビット以上 の乱数 が必要 な場合 は、上記 の手続 きを必要 回数 繰 り返 す。DESを別 の任意 のブロック暗号 に置 き換 えることもでき、AESの利用 が推奨 されている[5]。
数 論 的 設計
[- Blum-Blum-Shub は、
素因数 分解 の難 しさに基 づいたCSPRNGであり、条件 付 きでセキュリティが証明 されている。ただし、実装 すると他 の手法 よりも非常 に性能 が悪 い。 - Micali–Schnorr generator, Naor-Reingold pseudorandom function
特殊 な設計
[- Yarrow algorithm は
入力 のエントロピー的 品質 を評価 する。一方 Fortuna はそれをしない。 - マイクロソフトのCAPIにある
関数 CryptGenRandom - ISAAC(RC4から
派生 )
標準
[- 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. 434–440. ISBN 0-8186-0591-X. 2006
年 11月29日 閲覧 。 - ^ 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. 768–770. ISBN 0-08-009566-6 - ^ Young and Yung, Malicious Cryptography, Wiley, 2004, sect 3.2
- ^ https://nvlpubs.nist.gov/nistpubs/Legacy/FIPS/fipspub171.pdf (Appendix C)
- ^ 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.