公開鍵の考え方（鍵交換）

盗み見られている通信路で、なぜ2人だけの秘密の鍵を作れるのか。まず共通鍵で困る場面を見て、次に色で仕組みをつかみ、最後に同じことを数で確かめます。

• 段1 共通鍵の困りごと: 鍵を通信路で送ると、盗聴者にもコピーされてしまいます。これが鍵配送問題です。
• 段2 色で考える: 共通の色に自分の秘密の色を混ぜて送りあい、受け取った色にもう一度自分の秘密の色を混ぜると、2人の手元に同じ色ができます。秘密の色そのものは一度も送っていません。
• 盗聴者が見られるのは、共通の色と送られた2つの混ぜ色だけです。実際に混ぜさせてみると、2人と同じ色にはなりません。
• 段3 数で確かめる: p = 23、g = 5 のような小さい数で、べき乗して余りを取る計算をします。アリスとボブが同じ値にたどり着くことを、手で追える大きさで確認できます。
• この教材の数は小さいので総当たりで解けます。実際の通信で安全なのは、2048ビット以上の大きな素数を使い、総当たりが現実的な時間で終わらないようにしているためです。
• 段4 それでも破られる場合: 通信路の途中に割り込める相手（中間者）がいると、アリスともボブとも別々に鍵を作られてしまい、そのまま読まれます。鍵交換には相手が本人かを確かめる仕組みが無いためで、実際の通信では電子署名と証明書でこれを防いでいます。