Diffie-Hellman鍵交換
概要
発信者と受信者で同じ鍵を使う共有鍵暗号は暗号化方式の一つ.
鍵を共有するには安全に送付しないといけない, という問題がある. 安全な送付問題への回答の一つがこのアルゴリズム.
(鍵交換という名は付いているが)そのものを交換しなくても, 断片的な情報だけを送り合って, 計算で手元に同じ数が現れれば良いじゃないか, という考え方をする.
通信で飛び交った断片的な情報だけを拾い集めても肝心の共有鍵を逆算することが出来ないのがこのアルゴリズムのキモ.
例
AさんとBさんがそれぞれ秘密の値a, bを定義
a=7(秘密)
b=12(秘密)
PとGを決めて共有する.
P=13, G=3 を共有, 交換する(公開)
Aさん, Bさんはそれぞれ以下の計算を行い, 結果を相手に送る(第三者に見られても良い)
[A->Bに送信(公開)] G^a mod P = 3 // ((3 ** 7) % 13)
[B->Aに送信(公開)] G^b mod P = 1 // ((3 ** 12) % 13)
Aは G^b mod P = 1 を受け取った. ここから鍵を計算する.
(G^b mod P)^a mod P
= (1)^7 mod 13 = 1 = 共有鍵
Bは G^a mod P = 3 を受け取った. ここから鍵を計算する.
(G^a mod P)^b mod P
= (3)^12 mod 13 = 1 = 共有鍵
以上でAさん, Bさんは共有鍵(= 1)を得ることが出来た.
P=13, G=3, (G^b mod P)=1, (G^a mod P)=3
この4つを盗聴していた人間がいたとしてもa,b, 共有鍵を求めることは出来ない.
// お手頃な数字を使ったためかいまいち感覚がつかめない. もうちょっと大きな数でやったほうがよかったかも