まとめ

現実逃避に、DH鍵交換を手でやってました。
手で試すと、運悪く不思議なケースを引きました。
調べると、DH鍵交換がうまく行かないケースは次の2つがあるようです。

パラメータpが安全素数でないこと。
p-1を共有してしまうこと。

失敗した手計算を共有します。
安全素数が良い理由については、まだ理解していないので書いてません。
理解していない部分を課題の形で置いてあります。

DH鍵交換とは?

DH(Diffie–Hellman)鍵交換は、2人で秘密の値を共有する方法です。
秘密の値は、秘密鍵暗号の鍵として利用されることが多いです。

https(TLS)でも利用できる手法です。
手順のわかりやすさから、RSAに並ぶおなじみの暗号手法です。

DH鍵交換の方法

DH鍵交換の方法をAさん、 Bさんの二人が行う様子で簡単に書きます。

巡回群 ${\mathbb Z}/p{\mathbb Z}$ というのは、pで割った余りの世界を考えるということです。
群 ${\mathbb Z}/p{\mathbb Z}$ において元 $x$ の次数は、 $x^ n = 1 \ ({\rm mod \ } p)$ を満たす最小の $n$ のことを言います。
群 ${\mathbb Z}/p{\mathbb Z}$ において元 $x$ が生成元であるとは、次数がpであることを言います。

パラメータをAさんとBさんで共有する
- $p$ は素数
- $g$ は巡回群 ${\mathbb Z}/p{\mathbb Z}$ の生成元
整数 $a$ をAさんは $p$ 未満の数でランダムに決める
$g^ a {\rm \ mod\ }p$ をAさんはBさんに共有する
整数 $b$ をBさんは $p$ 未満の数でランダムに決める
$g^ b {\rm \ mod\ } p$ をBさんはAさんに共有する
Aさんは受け取った $g^ b$ を $a$ 乗して、 $K=(g^ b)^ a {\rm \ mod\ } p$ を得る
Bさんは受け取った $g^ a$ を $b$ 乗する、 $K'=(g^ a)^ b {\rm \ mod\ } p$ を得る

$K = (g^ b)^ a = g^ { a b } = (g^ a)^ b = K'$ なので、AさんとBさんで同じ値を共有できました。

この通信を見ていたCさんは、 $g^ a$ と $g^ b$ を見ることができます。
これ同士を掛けてみても、得られるのは $g^ {a + b}$ です。 $g^ {ab}$ を求めたいのですが、行き詰まってしまいます。

Cさんは、 $g^ a$ から $a$ を求めるのが難しいという、離散対数問題に直面するわけです。

手計算でやってみる

パラメータの決定

とりあえず適当に素数と巡回群を決めればいいんだろうと、 p=83とg=2としました。
g=2はDH鍵交換で一般的なパラメータのようです。

2のn乗(mod 83)を求めていくと83乗で初めて1になります。 2は83の巡回群の生成元にちゃんとなっていました。

このp=83とg=2を通信先と共有しました。

$g^ a$ を求める

僕は乱数を振ってa=46としました。
$g^ a = 2^ {46} \ ({\rm mod\ }p)$ を計算しましょう。
繰り返し2乗法的なテクニックのおかげで、46乗は手でも簡単に求まります。

初めに $2^ 1, 2^ 2, 2^ 4, 2^ 8, 2^ {16}, 2^ {32}$ を計算します。
前の数を自乗していけば求まります。
$2^ 1 = 2,\ 2^ 2=4,\ 2^ 4=16,\ 2^ 8=256=7,\ 2^ {16}=49,\ 2^ {32}=2401=77$ です。

そして、46を二進数に展開して掛けます。
$g^ a = 2^ {46} = 2^ {2 + 4 + 8 + 32} = 2^ 2 * 2^ 4 * 2^ 8 * 2^ {32} = 4 * 16 * 7 * 77 = 51$

$g^ a$ が求まったので通信先に共有します。

$K=(g^ b)^ a$ を求める

通信先からは $g^ b = 82$ が帰ってきました。
$K=(g^ b)^ a=82^ {46}$ を求めればDH鍵交換が完了します。

完了するはずでした。

82の46乗を同じテクニックで求めます。
すると、 $82^ 2=1$ になってしまうことに気づきます。
そうなると、前の数を自乗して求めるので、 $82^ 4, 82^ 8, 82^ {16}$ ‥‥全部が1 になってしまいます。
つまり、82の偶数乗は1だし、奇数乗は $82^ 1$ だけになってしまい82です。
今回はa=46で偶数なのでK=1となりました。