自然界を観察すると、
いたるところに
ランダムな揺らぎがある。
「ノイズ」というランダムな揺らぎを
計測することで、完全にランダムな数列を得られる。
ノイズを抽出(計測)することで、
数列を得るのだ。
例えば、
TVのノイズの電流をずっと計測すると、
完全にランダムな数列が作られる。
ランダムな数列を視覚化するには
軌道を描き、その方向を
数字によって変えれば良い。
これを「ランダム・ウォーク」という。
数列のどの範囲にも、どの部分にも
規則が現れないことに注目しよう。
次の動きは絶対に予測できないのだ。
ランダムな過程は
あらかじめ予測できないので、
「非決定的」と呼ばれる。
一方で、機械は「決定的」だ。
その動作は予測でき、繰り返しになる。
1946年、ジョン・フォン・ノイマン は
コンピュータを軍事目的に使おうとしていた。
特に水素爆弾の設計に関わっていた。
ENIAC というコンピュータを用い、
核融合の方法に関する計算を
何度も行おうとした。
しかし、そのためには
繰り返しのあるランダムな数列に
必要なだけ素早くアクセスする必要があった。
しかし ENIAC の内部メモリは
ひどく限られていたので、
長いランダム数列を記憶することができなかった。
そこで ノイマンは、次の方法で
ランダムのゴチャゴチャ具合を
機械で再現するアルゴリズムを開発した:
まず「シード」と呼ばれる
完全にランダムな数字を選択する。
この数字は ノイズの計測や、
現在時刻のミリ秒によって決める。
次に この数字を計算機に入力し、
簡単な処理をする。
シードを 2乗 して、
結果の まんなか を出力する。
出力は次のシードとして用いられる。
これを 必要な回数だけ繰り返す。
これが「平方採中法」だ。
乱数生成の方法は、
他にも沢山ある。
数列のランダムさは、
初期シードのみに依存する。
シードが同じなら、数列は同じ。
さて、完全なランダムと
擬似ランダムの違いは何だろう。
各 数列を ランダム・ウォーク で表してみよう。
似たように見えるが、スピードを上げると?
擬似ランダムは 結局 繰り返しになる。
これはアルゴリズムが
以前と同じシード値を
生成すると発生し、
そこから 周期的になる。
擬似ランダムが繰り返しになるまでの
数列の長さをー
「ピリオド」という。
ピリオドは初期シードの桁数に強く制限される。
例えば 2桁のシードを用いると、
アルゴリズムが 同じシードを生成し、
繰り返しになるまで
多くて 100通り の数字を生成できる。
3桁のシードなら、
繰り返しまでの数を
1000通りに拡大できる。
4桁のシードなら、
繰り返しまでの数字の個数は
1万まで広がる。
しかし もしシードが十分に大きければ、
繰り返しまで 数兆、数京もの数列を
生成できる。
しかしキーの違いには注意が必要だ。
擬似ランダム数を生成する時、
起こり得る数列はかなり制限される。
例えば、
アリスが完全ランダムで
20個のシフト数を生成したとする。
これは あり得るシフト数列が書かれた、
均一な紙の山から
1枚を選ぶのに等しい。
この山には 26^20 ものページがあるから、
天文学的な大きさになる。
山の元に立って、光を上に向けて放つと、
頂上にいる人間が光を目にするのは
2億年先になる。
これと比べて、アリスが 20桁の擬似ランダム数列を、
4桁のシードで生成した場合は、
10,000 通りの初期シードから
1つを選ぶに等しい。
つまり 彼女が生成できる数列は 10,000 通りしかなく、
全数列のうちの
ごく小さな 1部分にすぎない。
シフト数をランダムから擬似ランダムに置き換えた時、
鍵空間を ごくごく小さな シード空間にまで
縮めることになる。
だから 擬似ランダムをー
完全なランダムのように見せかけるには、
コンピュータが 全てのシードを試みるのを
現実的に不可能にする必要がある。
ここで 情報工学の世界では、
次の2つがハッキリと区別される。
「可能」と
「現実的な時間内で可能」 の違い。
例えるなら、自転車のダイヤル鍵と同じ理屈だ。
全ての番号を試せば、
誰でも簡単に解除の番号が分かると
知られている。
しかし それには何日も掛かるので、
8時間くらいなら、事実上 安全と考えられる。
擬似ランダムの生成では、
シードの桁数が増えるほど
強固なセキュリティになる。
最も速いコンピュータが
全てのシードを試すまでに 何百年も掛かるのなら、
完璧に強固ではなくても、
事実上 安全とみなして
差し支えない。
コンピュータが速くなるのに従い、
シードの大きさを増やす必要がある。
擬似ランダムのお陰で、
アリスとボブは
前もって全てのランダムシフト数を
共有しなくてよくなった。
代わりに、それより短いランダムなシードを共有し、
ランダムに見える数列を
必要な時に 生成すれば
よい。
しかし もし、
彼らが二度と会えず、シードを共有できなくなったら
どうなるだろう?