Diffie-Hellman鍵交換とは

ジャンル: 暗号プロトコル。

嬉しいこと

インターネットにおいて、共通鍵をやりとりしたい相手との間で安全に作成できる。

原理

合同式は全て $mod\ p$ とする。pは大きめの素数とする。
$x ^ y ≡ z$ のとき、一般に(x,y,p)からzを求めるのは簡単
$x ^ y ≡ z$ のとき、一般に(x,z,p)からyを求めるのは難しい

手順

AさんとBさんの間で共通鍵を作成したい。x、pは公開情報（ばれてもいい）とする。

手順１

Aさんは秘密の整数aをランダムに選び、$ E ≡ x ^ a $を計算する。
Bさんは秘密の整数bをランダムに選び、$ F ≡ x ^ b $を計算する。

手順２

AさんはEをBさんに送る。（Eは他人にばれても良い）
BさんはFをAさんに送る。（Fは他人にばれても良い）

手順3

Aさんは$ G ≡ F ^ a $を計算する。（AさんはF、aとも知っている）
Bさんは$ H ≡ E ^ b $を計算する。（BさんはE、bとも知っている）
$ G ≡ x ^ {ab} $
$ H ≡ x ^ {ab} $
とGとHは一致するので、これを共通鍵とすればよい。

ポイント

Aさんの立場から見ると、
i. aを直接送らず、指数にいれることでaを隠蔽（元の式で、z,x,pからyを求めるのが困難なので、E,x,pがばれてもaは短時間ではばれない）。
ii. 送られてきたbの変換後の値のFの使い道として、Fに対して自分の持ってるaを指数部において更に累乗計算することにより$x ^ {ab}$が得られる。結局bは不明だが、（とある数をa乗してからb乗するのと、b乗してからa乗するのが同じという）指数計算の交換法則により、Bさんと同じ結果にたどり着くことができている。

良いところ

EおよびFをどちらも傍受されていても、$G(≡H)$ は得られない。(一瞬、$E * F ≡ x ^ a * x ^ b = x ^ {a + b} $が計算できてしまうと思ったが、共通鍵は$x ^ {ab}$なのでセーフ)

防げない攻撃

中間者攻撃

AさんがBさんだと思ってCさんと
BさんがAさんだと思ってCさんと
やりとりをすると、Cさん（悪い人）は比較的容易にやりとりを仲介しつつ（AさんやBさんは相手から期待するレスポンスが返ってくるので特に違和感を持つことなく）、内容を盗み見ることができる。
なので、認証部分はRSAで行うのが良いらしい。実際にどう組み合わせるのか気になる。

RSA鍵交換で何がダメなの？

RSAだと、「前方秘匿性がない」からだそうです。エンジニアなら知っておきたい、絵で見てわかるセキュア通信の基本#他の公開鍵暗号に書いてありました。なるほどお。

感想

概要だけ知りたかったのでここまで。おもしろかった。

参考

ディフィー・ヘルマン鍵共有(wikipedia)
Diffie-Hellman鍵交換入門(Qiita)
エンジニアなら知っておきたい、絵で見てわかるセキュア通信の基本