DH鍵交換とは
ディフィ・ヘルマン鍵交換（Diffie–Hellman key exchange、以下、DH鍵交換）とは、暗号化に用いる共通秘密鍵（対称秘密鍵、以下、暗号鍵）を生成・共有するためのプロトコルです。離散対数問題が困難であることに基づいています。
暗号鍵を計算する途中のデータはネットワーク上を流れますが、仮にそれが漏えいしてもそこから暗号鍵を知る手段は今のところ知られていないため、暗号鍵の安全性が守られることになります。
DH鍵交換の流れ
ＡとＢの間での、DH鍵交換の手順は以下になります。
| ① | ＡとＢの間で、予め $n$ と $c$ を共有する このとき、$n$ は素数で、$c$（$\lt n$）は整数とする |
－ |
| ② | Ａは、乱数 $x$ を基に、$p$ を生成し、Ｂに送信する | $p=c^x\pmod{n}$ |
| ③ | Ｂは、乱数 $y$ を基に、$q$ を生成し、Ａに送信する | $q=c^y\pmod{n}$ |
| ④ | Ａは、Ｂから受信した $q$ より、$K_A$ を生成する | $K_A=q^x\pmod{n}$ |
| ⑤ | Ｂは、Ａから受信した $p$ より、$K_B$ を生成する | $K_B=p^y\pmod{n}$ |
この手順により、$K_A=K_B$ となる暗号鍵が、ＡとＢで共有することができます。仮に、$p$ と $q$ が漏えいしたとしても、それから暗号鍵 $K_A,K_B$ を計算する手法は今のところ知られていないため、安全性が担保されています。
実際に簡単な例として、$n=7$、$c=5$、$x=4$、$y=3$ とします。
| ②⇒ | $p=5^4\pmod{7}=625\pmod{7}=2$ |
| ③⇒ | $q=5^3\pmod{7}=125\pmod{7}=6$ |
| ④⇒ | $K_A=6^4\pmod{7}=1296\pmod{7}=1$ |
| ⑤⇒ | $K_B=2^3\pmod{7}=8\pmod{7}=1$ |
以上のように、確かに $K_A=K_B$ となりますが、これば偶然でないことが以下のように示すことができます。
DH鍵交換の仕組み
③と④より、
$$K_A=(c^y\pmod{n})^x\pmod{n}=(c^y)^x\pmod{n} －⑥$$
②と⑤より、
$$K_B=(c^x\pmod{n})^y\pmod{n}=(c^x)^y\pmod{n} －⑦$$
が示されれば、$K_A=K_B$ であることが導けます。
まず、③より $c^y=\alpha n+q$ と表すことができるため、④を計算すると以下になります。ここで、$\alpha$ は適当な整数です。
$$(\alpha n+q)^x\pmod{n}=(\alpha^xn^x+\cdots+\alpha nxq^{x-1}+q^x)\pmod{n}$$$$=q^x\pmod{n}$$
これにより、⑥が成り立つことが分かります。一方、⑦についても、同様の計算で成り立つことが分かります。
