-
こんなゲームを考えてみましょう。
-
イヴがボブに部屋に行くように指示しました。
-
部屋には、いくつかの鍵と、空っぽの箱、
-
一組のトランプカードの他には
-
何もありません。
-
イヴはボブにカードを1枚選んで
-
思いつく最高の隠し方で隠せと言いました。
-
ルールは簡単。
-
ボブは部屋の外に何かを持ちだしてはいけません。
-
カードと鍵は全て部屋の中になければいけません。
-
また、箱の中にカードを1枚しか入れてはいけません。
-
イヴは鍵を持っていません。
-
イヴが、隠されたカードが分からないならボブの勝ちです。
-
どうするのが最善でしょう?
-
ボブはダイヤの6を選びました。
-
そして箱に入れました。
-
最初、彼は何種類かある鍵を見て
-
南京錠でカードの入った箱に鍵をしようと考えました。
-
しかし、イヴはピッキングできます。
-
そこで、彼はダイヤル錠を選びました。
-
ダイヤル番号は鍵の後ろに書いてありますが、
-
それさえ消してしまえばピッキングは困難です。
-
これは最もいい選択のように思えます。
-
しかし、彼は問題点に気づきました。
-
テーブルの上に残されたカードを見て
-
どのカードが無いのか考えれば、
-
選んだカードがわかってしまいます。
-
箱の鍵はおとりでした。
-
選んだカードを山と別の場所におくべきでないのです。
-
ボブはカードを山に戻しました。
-
しかし、彼は選んだカードがどこにあったかわかりません。
-
なのでシャッフルして、十分にまぜました。
-
混ぜることが一番の隠し方なのです。
-
なぜなら、何を選んだかの情報がどこにも残らないからです。
-
混ぜたことで選ばれたカードは他のカードと
「同様に確からしく」なりました。
-
あとはカードの山を堂々と置いておけばよいのです。
-
これでボブの勝ちです。
-
イブはどんな情報も得られないので、
-
彼女にできることは、ただの推測しかありません。
-
最も重要なのは、
-
どんなに強力な計算能力を持っていたとしても、
-
イヴは推測以上のことはできないということです。
-
このことを、「完全秘匿(ひとく)」といいます。
-
1945年9月1日、29歳のクロード・シャノンが
-
このことを取り扱った論文を発表しました。
-
シャノンはどうしてワンタイムパッドがどうして解読不可能かを
-
始めて数学的に証明しました。
-
シャノンは暗号化の方法についてこのように考えました。
-
アリスが20字の文をボブに送る
という場面を考えてみましょう。
-
これはある一枚の紙を
-
「平文空間」から選び出すのと同じ事です。
-
ここでの「平文空間」とは、
-
20文字でできる全ての組み合わせの集合体です。
-
考えられるどんな20文字の文章も、
-
このなかに含まれています。
-
つぎにアリスは、1~26の数を20個使った
-
全ての組み合わせの表を用いて
-
「鍵空間」を作ります。
-
「鍵空間」は、あり得るすべての暗号の寄せ集めです。
-
つまり、暗号の鍵を作るのはこの「鍵空間」から
-
どれか1枚を無作為に選ぶのと同じ事です。
-
アリスが文章を暗号化し終えると、
-
最初の平文の代わりに「暗号文」が残ります。
-
「暗号文空間」は、ある暗号化を施した時の
-
あり得るすべての結果を表しています。
-
アリスが暗号の鍵を使うと、
-
全ての山の中から特定のページを指し示すことができます。
-
このとき、
「平文空間」 と 「鍵空間」 と 「暗号文空間」
-
このとき、
「平文空間」 と 「鍵空間」 と 「暗号文空間」
-
3つの大きさはすべて同じになります。
-
これが、「完全秘匿(ひとく)」です。
-
もし誰かが、「暗号文空間」のみに
アクセスできたとしても、
-
知ることができるのは、
-
あらゆる文章が「同様に確からしい」ということだけです、
-
どんなに計算能力があったとしても、
-
元の文を探る推測の助けにはなりません。
-
ワンタイムパッドの問題は、
-
膨大な長さの暗号化表を
-
共有しておかなければならないという点です。
-
この問題を解決するためには、
-
「秘匿性」について少し妥協して、
-
「疑似乱数」を使うことになります。