ディフィ・ヘルマン鍵交換とは

/情報・暗号

ディフィ・ヘルマン鍵交換(Diffie–Hellman key exchange、以下、DH鍵交換)とは、暗号化に用いる共通秘密鍵(対象秘密鍵)を生成・共有するためのプロトコルです。離散対数問題が困難であることに基づいています。

DH鍵交換の流れ

AとBの間での、DH鍵交換の手順は以下になります。

AとBの間で、予め $n$ と $c$ を共有する
このとき、$n$ は素数で、$c$($\lt n$)は整数とする
Aは、乱数 $x$ を基に、$p$ を生成し、Bに送信する $p=c^x\pmod{n}$
Bは、乱数 $y$ を基に、$q$ を生成し、Aに送信する $q=c^y\pmod{n}$
Aは、Bから受信した $q$ より、$K_A$ を生成する $K_A=q^x\pmod{n}$
Bは、Aから受信した $p$ より、$K_B$ を生成する $K_B=p^y\pmod{n}$

この手順により、$K_A=K_B$ となる暗号鍵が、Aと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 | 理数の散策路
散策路TOP
数学、応用数学、古典物理、量子力学、物性論、電子工学、IT、力学、電磁気学、熱・統計力学、連続体力学、解析学、代数学、幾何学、統計学、論理・基礎論、プラズマ物理、量子コンピュータ、情報・暗号、機械学習、金融・ゲーム理論

Wikipedia

 

タイトルとURLをコピーしました