ディフィ・ヘルマン鍵交換（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$ となる暗号鍵が、ＡとＢで共有することができます。
実際に簡単な例として、$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$ と $\beta$ は適当な整数です。
$$(\alpha n+q)^x\pmod{n}=(\alpha^xn^x+\cdots+\beta n+q^x)\pmod{n}$$$$=q^x\pmod{n}$$
これにより、⑥が成り立つことが分かります。
同様に、⑦も成り立つことが分かります。
404 NOT FOUND | 理数の散策路
www.sansakuro.com
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論
www.sansakuro.com
2021.03.24
