こちらの本に公開鍵暗号の起源が書かれていました。それは1974年の秋、マークル木（マークルツリー）の発明者であるラルフ・マークルがＵＣバークレイ大学院生の時に計算機のセキュリティの講義を受けていた時に、共通鍵暗号の大前提である「共通鍵の事前合意」を回避する方法はないだろうかと考え始めたことに起源します。鍵の合意を事前に行うことなく、中間者の盗聴があっても安全に鍵交換できる方法は無いか考えたのです。はい、天才的なアイデアです。それは、マークルのパズルと呼ばれているものです。
それは、こういう手順のやりとりです。
- アリスが素因数分解などの一定時間で解決できるパズルを多数（例えば１万個）作成し、ボブにメール送信する。パズルを解くと、パズル番号と、秘密鍵が出てくる。
- パズルを１万個受領したボブは、ランダムに選んだ１つのパズルを例えば５分で解決し、識別番号と秘密鍵候補を取得し、アリスにメールを送信する「今後の通信で使う秘密鍵は、識別番号ＸＸの鍵にしませんか？」
- アリスとボブのメールを中間点で盗聴できるイブもパズルを解こうとするが、１万個もあるので、１個５分として全部解くには５００００分、つまり８３３時間、つまり３４日間掛かってしまうので、上記ボブのメールの秘密鍵をすぐに取得することはできない。
- ボブのメールを受領したアリスは、ボブに返事する「分かった。その識別番号の秘密鍵を使って暗号通信しましょう」。ボブは、アリスの返事を確認し、秘密鍵候補だったものを秘密鍵に確定し、アリスとの間で暗号通信を始める。
- 中間盗聴者であるイブも時間を掛ければ上記の秘密鍵が何であるか解読できるが、１か月以上掛かるので、アリスとボブの通信が数日以内に終了する場合は、その時点では解読できないということになる。アリスとボブは暗号通信を通じてイブの盗聴を回避する方法も連絡できる。
最初にアリスからボブに送信したパズルは、盗聴者に見られても構わないものなので、これが公開鍵の起源になるわけです。
※参考記事
Diffie-Hellman鍵合意
コメントを残す