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

/情報・暗号

ディフィ・ヘルマン鍵交換(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=5$、$c=4$、$x=3$、$y=2$ とします。

②⇒ $p=4^3\pmod{5}=2$
③⇒ $q=4^2\pmod{5}=3$
④⇒ $K_A=3^3\pmod{5}=4$
⑤⇒ $K_B=2^2\pmod{5}=4$

以上のように、確かに $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}$$

これは、⑥の左辺(④)であるため、⑥が成り立つことが分かります。

同様に、⑦も成り立つことが分かります。

 

情報・応用数学
リターン&リスク、ポートフォリオ理論、効率的フロンティア、資本資産価格モデル、先物取引、スワップ取引、ゲーム理論、ナッシュ均衡
数理の散策路
力学、電磁気・相対論、熱・統計力学、量子力学、物性物理、機械学習、情報処理、金融、物理数学

Wikipedia

 

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