暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器き

暗号あんごう論ろん的てき擬似ぎじ乱数らんすう生成せいせい器き（CSPRNG、英語えいご: 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 とは、乱数らんすう列れつの最初さいしょの 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は、このような暗号あんごう解読かいどくに対抗たいこうするものとして設計せっけいされる。

背景はいけい

Santha と Vazirani は、無む作為さくい性せいの弱よわいビット列びっとれつを複数ふくすう組くみ合あわせることで高こう品質ひんしつな擬似ぎじ乱数らんすう列れつを生成せいせいできることを証明しょうめいした^[1]。それ以前いぜんにジョン・フォン・ノイマンはビット列びっとれつからバイアスの大だい部分ぶぶんを除去じょきょできる簡単かんたんなアルゴリズムがあることを証明しょうめいし^[2]、Santha-Vazirani の設計せっけいに基もとづいたCSPRNGでフォン・ノイマンのアルゴリズムを入力にゅうりょくビット列びっとれつに適用てきようする必要ひつようがある。これを entropy extraction（エントロピー抽出ちゅうしゅつ）と呼よび、研究けんきゅうが盛さかんな領域りょういきである。

設計せっけい

ここでは、CSPRNGの設計せっけいを

ブロック暗号あんごうや暗号あんごう学がく的てきハッシュ関数かんすうなどの暗号あんごうプリミティブに基もとづく設計せっけい
数学すうがく的てきに解とくのが難むずかしい問題もんだいに基もとづく設計せっけい
特殊とくしゅな設計せっけい

に分わけて解説かいせつする。

暗号あんごうプリミティブに基もとづく設計せっけい

安全あんぜんなブロック暗号あんごうは、CTRモードで動作どうささせることでCSPRNGとして使つかうことができる。これは、ランダムな鍵かぎを選えらんで0を暗号あんごう化かし、次つぎに1を暗号あんごう化かし、さらに2を暗号あんごう化かし、というように行おこなう。カウンタを0以外いがいの任意にんいの値ねから開始かいしすることもできる。明あきらかに、その周期しゅうきは n-ビットブロック暗号あんごうでは 2ⁿ であり、鍵かぎと平文へいぶんの初期しょき値ちが攻撃こうげき者しゃに知しられてしまうと、全まったく安全あんぜんでなくなる。また、誕生たんじょう日びのパラドックスから2^n/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 （可能かのうな限かぎり詳くわしい値ね）を使つかって、中間なかま値ち $I=DES_{k}(D)$ を計算けいさん、次つぎに $x=DES_{k}(I\oplus s)$ を計算けいさんして乱数らんすうとして出力しゅつりょくし、シードを $s=DES_{k}(x\oplus I)$ と更新こうしんする。64ビット以上いじょうの乱数らんすうが必要ひつような場合ばあいは、上記じょうきの手続てつづきを必要ひつよう回数かいすう繰くり返かえす。DESを別べつの任意にんいのブロック暗号あんごうに置おき換かえることもでき、AESの利用りようが推奨すいしょうされている^[5]。

数かず論ろん的てき設計せっけい

Blum-Blum-Shub は、素因数そいんすう分解ぶんかいの難むずかしさに基もとづいたCSPRNGであり、条件じょうけん付つきでセキュリティが証明しょうめいされている。ただし、実装じっそうすると他たの手法しゅほうよりも非常ひじょうに性能せいのうが悪わるい。
Micali–Schnorr generator, Naor-Reingold pseudorandom function

特殊とくしゅな設計せっけい

以下いかのような、暗号あんごう論ろん的てきに安全あんぜんとなるよう設計せっけいされた実用じつよう的てき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)

NIST では、これに関かんするよいリンク集しゅうを管理かんりしている。

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.

[santha-vazirani-1] 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日にち閲覧えつらん。

[neumann-random-2] 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

[3] Young and Yung, Malicious Cryptography, Wiley, 2004, sect 3.2

[4] ttps://nvlpubs.nist.gov/nistpubs/Legacy/FIPS/fipspub171.pdf (Appendix C)

[5] Young and Yung, op. cit., sect 3.5.1

[1]

[2]

[3]

[4]

[5]