公開鍵暗号の起源


ジョシュアホールデン、暗号の数学

こちらの本に公開鍵暗号の起源が書かれていました。それは1974年の秋、マークル木(マークルツリー)の発明者であるラルフ・マークルがUCバークレイ大学院生の時に計算機のセキュリティの講義を受けていた時に、共通鍵暗号の大前提である「共通鍵の事前合意」を回避する方法はないだろうかと考え始めたことに起源します。鍵の合意を事前に行うことなく、中間者の盗聴があっても安全に鍵交換できる方法は無いか考えたのです。はい、天才的なアイデアです。それは、マークルのパズルと呼ばれているものです。

Screenshot of ja.wikipedia.org

それは、こういう手順のやりとりです。

  1. アリスが素因数分解などの一定時間で解決できるパズルを多数(例えば1万個)作成し、ボブにメール送信する。パズルを解くと、パズル番号と、秘密鍵が出てくる。
  2. パズルを1万個受領したボブは、ランダムに選んだ1つのパズルを例えば5分で解決し、識別番号と秘密鍵候補を取得し、アリスにメールを送信する「今後の通信で使う秘密鍵は、識別番号XXの鍵にしませんか?」
  3. アリスとボブのメールを中間点で盗聴できるイブもパズルを解こうとするが、1万個もあるので、1個5分として全部解くには50000分、つまり833時間、つまり34日間掛かってしまうので、上記ボブのメールの秘密鍵をすぐに取得することはできない。
  4. ボブのメールを受領したアリスは、ボブに返事する「分かった。その識別番号の秘密鍵を使って暗号通信しましょう」。ボブは、アリスの返事を確認し、秘密鍵候補だったものを秘密鍵に確定し、アリスとの間で暗号通信を始める。
  5. 中間盗聴者であるイブも時間を掛ければ上記の秘密鍵が何であるか解読できるが、1か月以上掛かるので、アリスとボブの通信が数日以内に終了する場合は、その時点では解読できないということになる。アリスとボブは暗号通信を通じてイブの盗聴を回避する方法も連絡できる。

最初にアリスからボブに送信したパズルは、盗聴者に見られても構わないものなので、これが公開鍵の起源になるわけです。


コメントを残す

メールアドレスが公開されることはありません。