■

みなさんこんです。ゲームです。
今回は、サマーウォーズという本に書かれている、「疑似乱数」という言葉に触れてみます。

サマーウォーズ (角川文庫)

上記の本は、私が持っている、角川文庫さんの本です。
疑似乱数について、書かれたwiki↓
擬似乱数 - Wikipedia

疑似乱数とは、一見乱数列のように見えるが、
確定的な計算をして求めている数列に含まれている、文字を指す。
真の乱数は、予測不可能（例えば、サイコロを振ったとき、４の目が出たとする。次にでる目の数は、予測不可能。）なのに対し、
疑似乱数は、作り方がわかれば、理論的に予測可能。
では、ここからは、引用です。
>> 一般の擬似乱数は、その方式と過去の出力が既知であれば、未来の出力を予測可能であるため、暗号の用途には不適（暗号学的に安全ではないと言う）である。
暗号理論では擬似乱数（生成器）に明確な定義がある。すなわち、多項式時間の計算機が乱数列と識別不能な列を出力する機器のことを、暗号論的擬似乱数生成器と呼び、この列に含まれる数を暗号論的擬似乱数という。 いかなる数列であれば乱数列であるか、議論のあるところではあるが、一様分布であることと過去の数から次の数が予測不能であることは同値であることが示されている（Yao）。そこで過去の数から次の数が予測不能であるかで、暗号論的擬似乱数か否かを区別する。
暗号理論では擬似乱数に厳密な定義が与えられている。Σ = {0,1}とする。自然数 k に対し、Σk 上の一様分布を Uk と表す。確率変数の族 {Xk}k∈N が、一様分布の族 {Uk}k∈N と計算量的識別不能な時、族 {Xk}k∈N は暗号論的擬似乱数であるという。
次に暗号論的擬似乱数生成器の厳密な定義をする。l(k) を l(k) > k を満たす多項式とする。G を多項式時間アルゴリズムで、G に k ビットのビット列を入力をすると l(k) ビットの出力を返すものとする。すると G(Uk) は Σl(k) 上の確率分布である。確率分布の族 {G(Uk)}k∈N が暗号論的擬似乱数である時、多項式時間アルゴリズム G を暗号論的擬似乱数生成機という。
一方向性関数が存在すれば暗号論的擬似乱数生成機が存在する事が知られている。
実際の生成法としては、一般の擬似乱数列を暗号学的ハッシュ関数に通す、という、簡単な構成法がある。 <<

暗号プリミティブに基づく設計
>>安全なブロック暗号は、CTRモードで動作させることでCSPRNGとして使うことができる。これは、ランダムな鍵を選んで0を暗号化し、次に1を暗号化し、さらに2を暗号化し、というように行う。カウンタを0以外の任意の値から開始することもできる。明らかに、その周期は n-ビットブロック暗号では 2n であり、鍵と平文の初期値が攻撃者に知られてしまうと、全く安全でなくなる。また、誕生日のパラドックスから2n/2の出力で真の乱数と1/2の確率で識別可能である。<<
>> 暗号学的ハッシュ関数も、場合によってはCSPRNGとして利用可能である。この場合、カウンタの初期値をランダム化して秘密にしなければならない。カウンタが多倍長整数であれば、このCSPRNGはほぼ無限に乱数を生成できる。しかし、これについて安全ではないとする者もいる。 <<
>> ストリーム暗号は、平文を擬似乱数列と（通常 XOR で）結合することで暗号文を生成する。カウンタを入力として暗号文を生成すれば、新たな擬似乱数列が生成される。これは、内部で生成する擬似乱数列がCSPRNGであるときだけ安全であり、一般にそうでないことが多い。 <<
>> この種の設計として 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暗号を使えば改善されるだろうと指摘されている。 <<

数論的設計
>> Blum-Blum-Shub は、強力だが条件付きでセキュリティが証明されている、素因数分解の難しさに基づいたCSPRNG。ただし、実装すると他の手法よりも性能が悪い。 <<

特殊な設計
>> 以下のような、暗号論的に安全となるよう設計された実用的PRNGがある。 <<
>> Yarrow algorithm は入力のエントロピー的品質を評価する。一方Fortunaはそれをしない。 <<
>> マイクロソフトのCAPIにある関数CryptGenRandom <<
>> ISAAC（RC4から派生） <<

ということです。
とにかく、これを解いた、・・・あの人・・・はすごい（最後間違えてたけどねｗ）。
では。