1970年代までは、「秘密鍵」をもとに 暗号化が行われていた。
秘密鍵では、送信者が固有の鍵を用いて メッセージを暗号化し、
受信者は同一の鍵を用いて復号する。
暗号化とは、固有の鍵を用いた 平文と 暗号文のー
対応付けである事を思い出そう。
暗号文を復号するには、同じ鍵を用いて 逆の対応付けをすれば良い。
よって、アリスとボブが秘密の通信をするには、
最初に同一の鍵を共有する必要がある。
しかし 鍵の共有は不可能な場合が多い。
アリスとボブが直接 会えない場合や、
ディフィー・ヘルマン鍵共有のために 追加の通信が必要な場合、
さらに アリスが複数の人と通信する場合、 例えば銀行員だとー
1人毎に異なる鍵を交換する必要があるだろう。
すると 彼女は これらの鍵を全て管理し、
通信を維持するための やり取りを重ねなければならない。
もっとシンプルな方法はないのだろうか？
1970年、イギリスの技術者 兼 数学者である ジェームス・エリスは
「公開鍵暗号」を生み出そうと思案していた。
シンプルながら 賢い発想に基づいたものだ。
施錠と解錠は逆の操作だ。
アリスは南京錠を買い、
開いた状態で本体のみを送る。
次にボブはメッセージをロックし、 アリスに送り返す。
鍵のやり取りは不要だ。
これにより 彼女は南京錠の本体を公開でき、
世界中の誰でも それを使ってアリスにメッセージを 送ることができる。
アリスが保持する鍵は 1つで済むようになる。
エリスは その感覚的な方法について述べたが、
数学的な解決は導けなかった。
そのアイデアの要は 鍵を次のように2つに分けることだ。
暗号鍵と復号鍵。
暗号鍵で出来た暗号文を 逆操作、つまり元に戻すために、
復号鍵を用いる。
逆操作の鍵の働き方を見るために、 色で簡略化された例を示そう。
通信を傍受しているイヴに分からないように、
ボブがアリスへ特定の色を送るにはどうするか？
ある色の反対の色を「補色」と言い、
それらを足すと白になり、 元の色味は失われる。
この例では 色の混合を一方向性関数とする。
何故なら 色を混ぜるのは簡単だが、 元に戻すには時間が掛かるからだ。
アリスは まず秘密鍵としてランダムな色を作る。 赤色としよう。
次にアリスは 秘密の色の機械 を用いて
選んだ赤色の正確な補色を作る。
機械には誰もアクセスできないとする。
結果のシアン色を、 共有鍵としてボブに送信する。
ボブは秘密裏に黄色をアリスに送りたいとする。
ボブは アリスの共有色と黄色と混ぜ、 できた色をアリスに送り返す。
そして、アリスは秘密色とボブが作った色を足す。
これで共有色の色味は打ち消され、
ボブの秘密色だけが残る。
イヴは アリスの秘密色(赤) を知らないので、
送られた色が簡単には分からない。
これが共有鍵の仕組みだ。
しかし、これを実用にするには 数学的な解決が必要だった。