ディフィー・ヘルマン鍵共有の仕組み

２人の間で秘密の暗号通信を行うには、まず最初に２人だけが知っている共通のキーワード〜鍵を取り交わす必要がある。
しかし、２人が遠く離れていて、盗聴の危険性のあるインターネットでしか通信できないとしたら、
どうやって最初の鍵を取り交わすことができるか？
この難問を解決するアルゴリズムとして「ディフィー・ヘルマン鍵共有」が知られています。
>> wikipedia:ディフィー・ヘルマン鍵共有
あからさまに盗聴されている通信路だけを使って、２人だけの秘密を共有する・・・
そんな一見不可能に思える離れ業を、どのようにして実現するのでしょうか？

ディフィー・ヘルマン鍵共有（以下、ＤＨ法と略）の基本となる考え方は、以下の図から出発します。
いま、アリスとボブの２人が、２人だけの秘密の数字を共有したかったとしましょう。

まず、アリスが数字Ａを、ボブが数字Ｂを決めて、お互いに交換します。
そして、お互いに交換し合った数字を掛け合わせて、共通の数字を保有するのです。
例えばアリスが３、ボブが４なら、共通の数字は３ｘ４＝１２です。
ただ、このままでは何も暗号化されてはいません。
通信路上の数字が盗聴されてしまえば、秘密の数字もバレバレです。

何とかもう一工夫して、数字がバレないようにしたい。
そこで、「一方向性関数」という仕組みを導入します。
一方向性関数とは、順方向の計算は簡単だけれど、逆方向の計算は難しい関数のことです。
一方向性関数をうまく使えば、「暗号をかける人にとっては簡単だが、解く人にとっては難しい」状況が作れるわけです。
ＤＨ法で用いられている一方向性関数は、以下のものです。

式の上で「mod P」とあるのは、「P で割ったときの余り」という意味です。
ある整数Ｇをｘ乗して、それをＰで割ったときの余りを求めるのはやさしい（計算手順が一本道）。
しかし、その逆に、余りがｙだったとき、元のｘを求めるには？
試しに数字を入れてやってみましょう。

　５^３ ÷ ７ = 125 ÷ 7 = 17 余り 6
これはやさしい。
では、逆に
　５^ｘ ÷ ７ = ？ 余り 3
だったとき、ｘは幾つになるか？
この答を得るには、ｘに１つ１つ順番に数字を代入して、確かめてみるしかありません。
つまりこの「G^x mod P」という計算は「行きはよいよい帰りは怖い」のです。

この「G^x mod P」という一方向性関数を使って、当初、アリスとボブが交換したかった２つの数、ＡとＢを隠すことを考えます。
　・Ａを直接送る代わりに「G^A mod P」を、
　・Ｂを直接送る代わりに「G^B mod P」を、
互いに交換すれば、たとえ途中の数字が盗聴されたとしても、そこから盗聴者がもとの数ＡとＢを求めることは極めて難しい。

一方、お互いに数字を交換し合った、アリスとボブはどうするか。
例えばアリスは、もらってきた数字 (G^B mod P) を、自分の持っている数字Ａでべき乗した後、Ｐで割った余りを求めます。
　(G^B mod P)^A mod P = (G ^ (BxA)) mod P
ボブも同じ計算を施します。
　(G^A mod P)^B mod P = (G ^ (AxB)) mod P
結果として、２人の手元には同じ数字が残るのです。
なぜ同じになるのか。
それは、２人の手元で行っている計算が、本質的には「Ｇの肩の上で行っている掛け算」だからです。
　(G ^ A) ^ B = (G ^ (AxB))
Ｇの指数が、ＡｘＢという掛け算になっていることに注目。
つまり、ＤＨ法とは、
「単純に数字を交換して掛け算する手順を、G^x mod P という一方向性関数によって隠したもの」
だったのです。

しかし、ＧとＰは、どのようにして２人の間で交換すればよいのでしょうか？
もしＧとＰを秘密に送らなければならないとしたら、何の解決にもなっていないではありませんか。
実は、たとえＧとＰを盗聴者に盗まれたとしても、数字の秘密はちゃんと守られているのです。
一方向性関数による困難な計算、例えば
　５^ｘ ÷ ７ = ？ 余り 3
で、５と、７と、３が知られたとしても、ｘを知ることは難しいでしょう。
なので、ＧとＰは秘密にすることなく、堂々と交換しても大丈夫なのです。

こうして種明かしをすれば、ＤＨ法は、一見ささいなアイデアであるようにも思えます。
ところが、このＤＨ法が世に出るまでは、鍵交換問題は解決不可能と信じられていた時代さえあったのです。
ネット上を検索すると、ＤＨ法のアルゴリズムを解説したページはたくさんヒットします。
しかし「なぜＤＨ法で鍵交換ができるのか」という疑問に答えてくれるページは（私が探したところ）見当たりませんでした。
仕方なく自分の頭で考えて、上の説明にたどり着くまで、私は１週間くらいかかりました。
最初にＤＨ法を編み出したヘルマンは、こう言ったそうです。

オリジナルな研究をやるということは、愚か者になることなのです。
諦めずにやり続けるのは愚か者だけですからね。
第一のアイディアが湧いて大喜びするが、そのアイディアはコケる。
第二のアイディアが湧いて大喜びするが、そのアイディアもコケる。
九十九番目のアイディアが湧いて大喜びするが、そのアイディアもコケる。
百番目のアイディアが湧いて大喜びするのは愚か者だけです。
しかし、実りを得るためには、百のアイディアが必要かもしれないでしょう？
コケてもコケても大喜びできるぐらい馬鹿でなければ、動機だってもてやしないし、やり遂げるエネルギーも湧きません。
神は愚か者に報いたまうのです。
　　　　-- 暗号解読より

暗号解読―ロゼッタストーンから量子暗号まで