Diffie–Hellman鍵共有

同義語：Diffie–Hellman鍵交換ディフィー・ヘルマン鍵共有Diffie–Hellman key exchangeDiffie–Hellman key agreement

概要

前提知識: 離散対数, 巡回群, 原始根, 反復二乗法

離れた 2 人が、誰にでも聞かれている通信路だけを使って、2 人だけが知る秘密の数（鍵）を決めたい。あらかじめ秘密を共有していなければ不可能に思えるが、Diffie–Hellman 鍵共有 はこれを冪の計算で実現する。素数 $p$ と原始根 $g$ を公開しておき、一方が秘密の $x$ を選んで $g^x\bmod p$ を、他方が秘密の $y$ を選んで $g^y\bmod p$ を送る。すると両者とも $g^{xy}\bmod p$ を計算できるが、盗聴者の手元にあるのは $g^x$ と $g^y$ だけである。
この仕組みは、反復二乗法で $g^x$ は速く計算できるのに、$g^x$ から $x$ を求める離散対数問題は一般に速く解く方法が知られていない、という非対称性に頼っている。ただし、安全であることは証明された定理ではなく、使う群の選び方を誤ると情報が漏れることは証明できる。
この記事では、鍵共有の手順と 2 つの Diffie–Hellman 問題を定義し、次を証明する。群の位数が奇数なら、鍵を求める問題は $g^x$ から $g^{x^2}$ を求める問題と同じ難しさであること（thm-dh-square）。群の位数が小さな素因数 $\ell$ をもつと、$g^x$ から $x\bmod\ell$ が漏れ、本物の鍵と無関係な元とが見分けられること（thm-dh-small-prime）。一部の入力でしか鍵を求められない方法も、乱数で入力をずらすとどの入力でも同じ確率で鍵を求められること（thm-dh-self-reduction）。

定義

以下、群は乗法的に書き、単位元を $1$ とする。$\mathbb Z/N\mathbb Z$ を $\mathbb Z_N$ と書く。位数 $N$ の巡回群 $G$ と生成元 $g$ について、$g^x$ は $x\in\mathbb Z_N$ だけで決まる（離散対数の命題「離散対数の基本性質」）。

Diffie–Hellman 鍵共有

位数 $N$ の有限巡回群 $G$ と生成元 $g$ を公開する。2 人の参加者 A、B は次を行う。

A は $x\in\mathbb Z_N$ を一様に無作為に選んで秘密にし、$X=g^x$ を B に送る。
B は $y\in\mathbb Z_N$ を一様に無作為に、$x$ と独立に選んで秘密にし、$Y=g^y$ を A に送る。
A は $K_A=Y^x$ を、B は $K_B=X^y$ を計算する。
この手順を Diffie–Hellman 鍵共有（Diffie–Hellman key exchange）といい、$K=K_A=K_B$ を共有された鍵という。

$G$ としては、素数 $p$ を法とする乗法群 $(\mathbb Z/p\mathbb Z)^\times$（$g$ は原始根）や、その部分群で位数が素数のものがよく使われる。$G$ と $g$ を固定したまま、何組の参加者が使ってもよい。

Diffie–Hellman 問題

位数 $N$ の有限巡回群 $G$ と生成元 $g$ を固定する。

$X=g^x$、$Y=g^y$ から $g^{xy}$ を求める問題を 計算 Diffie–Hellman 問題（computational Diffie–Hellman problem）という。
$x,y\in\mathbb Z_N$ を独立に一様に選んだ三つ組 $(g^x,g^y,g^{xy})$ の分布を $\mathcal D$、$x,y,z\in\mathbb Z_N$ を独立に一様に選んだ $(g^x,g^y,g^z)$ の分布を $\mathcal R$ とする。三つ組を受け取って $0$ か $1$ を出力する手順 $\mathsf A$ について
$$ \operatorname{Adv}(\mathsf A)=\bigl|\Pr[\mathsf A(\mathcal D)=1]-\Pr[\mathsf A(\mathcal R)=1]\bigr| $$
を $\mathsf A$ の 識別の優位度 という。$\mathcal D$ と $\mathcal R$ を見分ける問題を 判定 Diffie–Hellman 問題（decisional Diffie–Hellman problem）という。

$\Pr[\mathsf A(\mathcal D)=1]$ は、三つ組を $\mathcal D$ に従って選んで $\mathsf A$ に渡したとき $1$ が出力される確率である（$\mathsf A$ が乱数を使うなら、その乱数についても確率をとる）。判定問題が難しいとは、どの手順も現実的な時間では優位度を大きくできないことで、これは鍵が盗聴者にとって無作為な元と区別できないことを意味する。

例

法 23 での鍵共有

$p=23$、$g=5$ とする。$5$ の法 $23$ での位数は $22$ なので、$5$ は原始根であり $G=(\mathbb Z/23\mathbb Z)^\times$、$N=22$ である。A が $x=6$ を選ぶと $X=5^6\equiv8$、B が $y=15$ を選ぶと $Y=5^{15}\equiv19\pmod{23}$ である。A は $19^6\equiv2$、B は $8^{15}\equiv2\pmod{23}$ を計算し、鍵 $K=2$ を共有する。実際 $5^{90}\equiv2\pmod{23}$ である。盗聴者が知るのは $p=23$、$g=5$、$8$、$19$ だけである。

足し算の群では破れる

素数 $p$ について、加法群 $\mathbb Z/p\mathbb Z$ も位数 $p$ の巡回群で、$0$ でない $g$ が生成元である。この群で同じ手順を行うと、送られるのは「$g$ の $x$ 倍」$xg\bmod p$ と $yg\bmod p$、鍵は $xyg\bmod p$ になる。ところが $g$ の逆元 $g^{-1}\bmod p$ は拡張 Euclid の互除法で速く求まり、$x\equiv(xg)\,g^{-1}$ から $x$ が分かるので、鍵が誰にでも計算できる。群として同型でも、元の表し方によって離散対数の難しさは変わる（離散対数の例「足し算の群では離散対数はやさしい」）。

基本の性質

鍵の一致と離散対数からの帰着

def-dh-protocol の記号で、次が成り立つ。

$K_A=K_B=g^{xy}$ である。
$X$ の離散対数 $x=\log_gX$ が求まれば、鍵は $K=Y^x$ として求まる。
$G=(\mathbb Z/p\mathbb Z)^\times$ なら、各参加者の計算は法 $p$ の掛け算を $4\operatorname{len}(N)$ 回以下しか使わない（$\operatorname{len}(N)$ は $N$ の 2 進法での桁数）。

1：指数法則により $K_A=(g^y)^x=g^{xy}=(g^x)^y=K_B$ である。
2：1 により $Y^x=g^{xy}=K$ である。
3：$x$ を $0\le x< N$ の代表元にとると、反復二乗法の定理「反復二乗法の正しさと手間」により $g^x$ も $Y^x$ も法 $p$ の掛け算 $2\operatorname{len}(N)$ 回以下で計算できる（$x=0$ なら掛け算は要らない）。B についても同じである。$\square$

2 により、離散対数問題が解ければ計算 Diffie–Hellman 問題も解ける。逆に、計算 Diffie–Hellman 問題が解ければ離散対数問題も解けるかどうかは、一般には知られていない。Diffie と Hellman も、対数が計算できればこの方式は破られるが、その逆は証明できていないと述べている（DH76 §III、p. 649）。

安全性は証明された定理ではない

十分大きな素数位数の群で計算 Diffie–Hellman 問題や判定 Diffie–Hellman 問題が難しいことは、証明されていない仮定である。この記事で証明するのは、仮定が成り立たない場合の具体的な破り方（thm-dh-small-prime）と、問題どうしの関係（thm-dh-square・thm-dh-self-reduction）である。

平方の問題との同値

鍵 $g^{xy}$ を求めるには 2 つの元 $g^x,g^y$ が要るが、群の位数が奇数なら、1 つの元 $g^x$ から $g^{x^2}$ を求める問題に置き換えられる。

平方 Diffie–Hellman 問題との同値

$G$ を位数 $N$ の有限巡回群、$g$ を生成元とし、$N$ は奇数とする。

写像 $S\colon G\to G$ がすべての $x\in\mathbb Z_N$ で $S(g^x)=g^{x^2}$ を満たすなら、すべての $x,y\in\mathbb Z_N$ について、$X=g^x$、$Y=g^y$ とおくと
$$ g^{xy}=\Bigl(S(XY)\,S(X)^{-1}\,S(Y)^{-1}\Bigr)^{(N+1)/2} $$
である。
逆に、写像 $C\colon G\times G\to G$ がすべての $x,y$ で $C(g^x,g^y)=g^{xy}$ を満たすなら、$S(X)=C(X,X)$ は 1 の性質をもつ。

積の 2 倍を平方の差で書く

1：$XY=g^{x+y}$ なので $S(XY)=g^{(x+y)^2}$ であり、
$$ S(XY)\,S(X)^{-1}\,S(Y)^{-1}=g^{(x+y)^2-x^2-y^2}=g^{2xy} $$
である。$N$ が奇数なので $(N+1)/2$ は整数で、$2\cdot\frac{N+1}2=N+1\equiv1\pmod N$ である。$g^N=1$ より $\bigl(g^{2xy}\bigr)^{(N+1)/2}=g^{xy(N+1)}=g^{xy}$ である。
2：$C(g^x,g^x)=g^{x\cdot x}$ である。$\square$

1 の右辺の計算には、$S$ を 3 回使うほかに、$G$ での掛け算・逆元と、反復二乗法による $(N+1)/2$ 乗しか要らない。したがって「$g^x$ から $g^{x^2}$ を求める方法」と「計算 Diffie–Hellman 問題を解く方法」は、群の演算を $O(\operatorname{len}(N))$ 回加えるだけで互いに移り合う。$N$ が偶数だと $g^{2xy}$ から $g^{xy}$ への $(N+1)/2$ 乗の操作が使えず、この証明は通らない。

小さな素因数による情報の漏れ

位数の小さな素因数による漏れ

$G$ を位数 $N$ の有限巡回群、$g$ を生成元、$\ell$ を $N$ の素因数とする。$h=g^{N/\ell}$、$\chi(u)=u^{N/\ell}$（$u\in G$）とおく。

すべての $x\in\mathbb Z_N$ について $\chi(g^x)=h^{\,x\bmod\ell}$ であり、$h^0,h^1,\dots,h^{\ell-1}$ は相異なる。したがって $g^x$ から $x\bmod\ell$ が、$\chi(g^x)$ を $h^0,\dots,h^{\ell-1}$ と比べることで決まる。
三つ組 $(X,Y,Z)$ を受け取り、1 によって $a=\log_gX\bmod\ell$、$b=\log_gY\bmod\ell$ を求め、$\chi(Z)=h^{ab}$ なら $1$、そうでなければ $0$ を出力する手順を $\mathsf A_\ell$ とする。このとき
$$ \Pr[\mathsf A_\ell(\mathcal D)=1]=1,\qquad\Pr[\mathsf A_\ell(\mathcal R)=1]=\frac1\ell $$
であり、識別の優位度は $1-1/\ell\ge1/2$ である。

位数 $\ell$ の部分群への射影

1：$\chi(g^x)=g^{xN/\ell}=h^x$ である。$h$ の位数はちょうど $\ell$ である（$h^k=g^{kN/\ell}=1$ となるのは $N\mid kN/\ell$、すなわち $\ell\mid k$ のとき）。よって $h^x=h^{\,x\bmod\ell}$ であり、$h^0,\dots,h^{\ell-1}$ は相異なる。
2：$\mathcal D$ では $Z=g^{xy}$ なので、1 により $\chi(Z)=h^{xy}$ であり、$xy\equiv ab\pmod\ell$ から $\chi(Z)=h^{ab}$ となって必ず $1$ が出力される。$\mathcal R$ では $Z=g^z$ で、1 により出力が $1$ になるのは $z\equiv ab\pmod\ell$ のときに限る。$\ell\mid N$ なので、$\mathbb Z_N$ の元のうち法 $\ell$ で各剰余類に属するものはちょうど $N/\ell$ 個ずつあり、$z$ を $\mathbb Z_N$ から一様に選ぶと $z\bmod\ell$ は $\mathbb Z/\ell\mathbb Z$ 上で一様である。$z$ は $x,y$ と独立なので、$x,y$ の値ごとに $\Pr[z\equiv ab]=1/\ell$ であり、全体でも $1/\ell$ である。$\square$

手順 $\mathsf A_\ell$ は、$\chi$ の計算（反復二乗法）と $\ell$ 回程度の比較だけでできるので、$\ell$ が小さければ速い。$N$ のすべての小さな素因数について $x$ の剰余を集めれば、中国剰余定理により $x$ を $N$ の小さな素因数の部分を法として決められる。これは離散対数の定理「Pohlig–Hellman の帰着」の第 1 歩にあたる。

法 $p$ の乗法群全体では偶奇が漏れる

$p$ を奇素数、$g$ を法 $p$ の原始根、$G=(\mathbb Z/p\mathbb Z)^\times$ とする。$X=g^x$ が平方剰余であることと $x$ が偶数であることは同値で、判定は $X^{(p-1)/2}\equiv\pm1\pmod p$ の符号で行える。とくに鍵 $g^{xy}$ が平方剰余になる確率は $3/4$ であり、判定 Diffie–Hellman 問題は優位度 $1/2$ の手順 $\mathsf A_2$ で解ける。

$N=p-1$ は偶数なので、thm-dh-small-prime を $\ell=2$ に当てはめる。$h=g^{(p-1)/2}$ は位数 $2$ なので $h\equiv-1$ であり、$\chi(X)=X^{(p-1)/2}\equiv(-1)^x$ である。平方剰余の定理「Eulerの規準」により、$X^{(p-1)/2}\equiv1$ であることと $X$ が平方剰余であることは同値である。$xy$ が奇数になるのは $x,y$ がともに奇数のときで、その確率は $1/4$ なので、鍵が平方剰余になる確率は $3/4$ である。優位度は $1-1/2=1/2$ である。$\square$

法 23 で偶奇が漏れる様子

ex-dh-23 では $X=8$、$Y=19$ が送られた。$8^{11}\equiv1$、$19^{11}\equiv-1\pmod{23}$ なので、盗聴者には $x$ が偶数、$y$ が奇数と分かり、$xy$ は偶数である。よって鍵は平方剰余で、$K^{11}\equiv1$ を満たさなければならない。実際 $2^{11}\equiv1\pmod{23}$ である。一方、鍵の候補として $5$ が示されたとすると、$5^{11}\equiv-1$ なので、$5$ は鍵でないと分かる。

素数位数の部分群を使う

thm-dh-small-prime を避けるため、実際には位数が大きな素数 $q$ の巡回群を使う（Sho08 §11.3、p. 339。効率などほかの理由は pp. 335–336）。このとき $N=q$ の素因数は $q$ だけで、$\ell=q$ の $\mathsf A_q$ は $q$ 回程度の比較を要するので、総当たりより速くはならない。

安全素数と平方剰余のなす部分群

$q$ を奇素数とし、$p=2q+1$ も素数とする。$Q=\{a^2\mid a\in(\mathbb Z/p\mathbb Z)^\times\}$ とおく。

$Q$ は $(\mathbb Z/p\mathbb Z)^\times$ の位数 $q$ の部分群で、素数位数の巡回群である。
$a\not\equiv\pm1\pmod p$ なら、$a^2$ は $Q$ の生成元である。
$(\mathbb Z/p\mathbb Z)^\times$ の各元の位数は $1,2,q,2q$ のどれかである。

2 乗する写像の核と像

1：$a\mapsto a^2$ は $(\mathbb Z/p\mathbb Z)^\times$ からそれ自身への準同型で、像が $Q$ である。核は $a^2\equiv1$ の解で、体 $\mathbb Z/p\mathbb Z$ での 2 次方程式 $a^2-1=0$ の根は $\pm1$ の 2 個だけである。よって $|Q|=(p-1)/2=q$ であり、素数位数の群は単位元以外のどの元でも生成される巡回群である。
2：$a^2\equiv1$ となるのは 1 の核の元 $a\equiv\pm1$ だけなので、$a\not\equiv\pm1$ なら $a^2$ は $Q$ の単位元でなく、1 により生成元である。
3：Lagrangeの定理により、元の位数は群の位数 $p-1=2q$ の約数である。$\square$

3 は Ste17 Proposition 3.2.4（p. 54）である。$q$ と $2q+1$ がともに素数のとき、$p=2q+1$ を 安全素数 という。

法 23 の位数 11 の部分群

$23=2\cdot11+1$ である。平方剰余の集合は $Q=\{1,2,3,4,6,8,9,12,13,16,18\}$ で、$5^2\equiv2$ はその生成元である（$2$ の法 $23$ での位数は $11$）。$g=2$、$N=11$ として、A が $x=3$、B が $y=7$ を選ぶと、$X=8$、$Y=13$、鍵は $13^3\equiv8^7\equiv12\pmod{23}$ である。$Q$ の元はどれも平方剰余なので、cor-dh-legendre の偶奇の情報はここでは何も教えない。

素数位数の群での鍵の分布

$G$ の位数が素数 $q$ のとき、$x,y\in\mathbb Z_q$ を独立に一様に選ぶと、鍵 $K=g^{xy}$ について
$$ \Pr[K=1]=\frac{2q-1}{q^2},\qquad\Pr[K=u]=\frac{q-1}{q^2}\quad(u\ne1) $$
である。とくに $\sum_{u\in G}\bigl|\Pr[K=u]-1/q\bigr|=2(q-1)/q^2<2/q$ である。

積が決まった値をとる組を数える

$\mathbb Z_q$ は体なので、$xy=0$ となるのは $x=0$ または $y=0$ のときで、その組は $2q-1$ 個である。$c\ne0$ について、$xy=c$ となる組は $x\ne0$ を選べば $y=cx^{-1}$ がただ 1 つ決まるので $q-1$ 個である。$u=g^c$ との対応で前半を得る。差の和は $\frac{2q-1}{q^2}-\frac1q=\frac{q-1}{q^2}$ と、$q-1$ 個の $u\ne1$ についての $\frac1q-\frac{q-1}{q^2}=\frac1{q^2}$ の和で、合わせて $2(q-1)/q^2$ である。$\square$

したがって素数位数の群では、鍵そのものは一様分布にきわめて近い。鍵が盗聴者にとって無作為に見えるかどうかは、この分布ではなく、$X,Y$ を見たうえでの判定 Diffie–Hellman 問題の難しさにかかっている。

平均の場合と最悪の場合

鍵を求める方法が「多くの入力で」しか正しくなくても、乱数で入力をずらすと、どの入力に対しても同じ確率で鍵が求まる。暗号では、平均的に難しくないと意味がないので、この性質は計算 Diffie–Hellman 問題の難しさが入力によらないことの根拠になる。

鍵の計算の自己帰着

$G$ を位数 $N$ の有限巡回群、$g$ を生成元とする。$F\colon G\times G\to G$ を任意の写像とし、
$$ \varepsilon=\frac{\#\{(a,b)\in\mathbb Z_N^2\mid F(g^a,g^b)=g^{ab}\}}{N^2} $$
とおく。$X=g^x$、$Y=g^y$ を任意に与え、$r,s\in\mathbb Z_N$ を独立に一様に選んで
$$ W=F\bigl(Xg^r,\;Yg^s\bigr)\,X^{-s}\,Y^{-r}\,g^{-rs} $$
とおく。このとき、$X,Y$ によらず $\Pr[W=g^{xy}]=\varepsilon$ である。

入力を一様にずらす

$(r,s)\mapsto(x+r,\,y+s)$ は $\mathbb Z_N^2$ からそれ自身への全単射なので、$(a,b)=(x+r,y+s)$ は $\mathbb Z_N^2$ 上で一様に分布する。$Xg^r=g^a$、$Yg^s=g^b$ であり、
$$ g^{ab}\,X^{-s}\,Y^{-r}\,g^{-rs}=g^{(x+r)(y+s)-xs-ry-rs}=g^{xy} $$
である。$u\mapsto u\,X^{-s}Y^{-r}g^{-rs}$ は $G$ の単射なので、$W=g^{xy}$ となるのは $F(g^a,g^b)=g^{ab}$ のときに限る。その確率は、$(a,b)$ が一様なので $\varepsilon$ である。$\square$

$W$ の計算には、$F$ を 1 回使うほかに $X^{-s}$ などの冪が要るだけである。独立に $k$ 回くり返すと、得られる $W$ のうち少なくとも 1 つが鍵である確率は $1-(1-\varepsilon)^k$ になる。ただし離散対数問題とちがい、候補 $W$ が本当に $g^{xy}$ かどうかを $X,Y$ から確かめる方法は一般には知られておらず（Sho08 §11.3、p. 338）、それを確かめることがまさに判定 Diffie–Hellman 問題である。離散対数問題の場合は、候補 $t$ が正しいかを $g^t=X$ で確かめられるので、同じ考え方で「多くの入力で解ける方法」から「どの入力でも高い確率で解ける方法」が作れる（この記事では証明しない。同書 Exercise 11.11、p. 337 の演習）。

使い方の注意

中間者攻撃

def-dh-protocol の手順は、受け取った $X$ が本当に A から来たかを確かめない。通信を書き換えられる第三者 E は、A からの $X$ を止めて自分の $g^t$ を B に送り、B からの $Y$ を止めて $g^t$ を A に送る。すると A は E と鍵 $g^{tx}$ を、B は E と鍵 $g^{ty}$ を共有し、E は 2 人の通信を読み書きできる（Ste17 §3.2.3、p. 56）。これを防ぐには、$X,Y$ が本人のものであることを別の手段で確かめる必要がある。DH76 §III（p. 649）は、各参加者の $Y_i=g^{X_i}$ を名前とともに公開の名簿に載せる形で方式を述べており、名簿が書き換えられないことで本人の確認を兼ねている。

指数を小さく選ぶ危険

計算を速くするために $x$ を $0\le x< 2^{2k}$ の範囲に限ると、群の位数 $N$ がどれほど大きくても、$x$ はおよそ $2^{k+1}$ 回の群の演算で求まる。離散対数の定理「Baby-step Giant-step 法」の手順を $m=2^k$ で行えばよい。その証明は、$m\le N$ で $0\le x< m^2$ なら大きい歩みが $j\le\lfloor x/m\rfloor< m$ で止まって正しい $x$ を出すことを示しており、$m=\lceil\sqrt N\,\rceil$ の代わりに $m^2>x$ となる $m$ をとっても同じ議論が通る。Sho08 §11.3（p. 338）は、素数位数でない群で短い指数を使うと、小さな素因数による情報と合わせてさらに速く破られることを指摘し、素数位数の部分群を勧めている。

仮定を外したときの反例

def-dh-protocol を安全に使うために置く条件を 1 つずつ外すと、次のように破れる。

外す条件	反例	成り立たなくなること
群の位数が小さな素因数をもたない	$(\mathbb Z/23\mathbb Z)^\times$ 全体、$g=5$（位数 $22=2\cdot11$）	$X,Y$ から $x,y$ の偶奇が分かり、鍵と無関係な元とを優位度 $1/2$ で見分けられる（cor-dh-legendre、ex-dh-23-parity）
離散対数が難しくなるような元の表し方	加法群 $\mathbb Z/p\mathbb Z$	$xg$ から $x$ が互除法で求まり、鍵が誰にでも計算できる（ex-dh-additive）
指数を $\mathbb Z_N$ 全体から一様に選ぶ	$0\le x< 2^{40}$ に限る	群の位数によらず、約 $2^{21}$ 回の演算で $x$ が求まる（rem-dh-short-exponent）
受け取った元が相手のものと確かめる	通信を書き換える第三者	鍵が第三者と共有され、通信が読まれる（rem-dh-mitm）

補足

他の群と文献

def-dh-protocol は巡回群の演算しか使わないので、有限体上の楕円曲線の有理点の群でも同じ手順が使える（Ste17 §6.4.1、p. 135）。DH76 §III（p. 649）は、$q$ 元の素体 $\mathrm{GF}(q)$ の原始元 $\alpha$ を使い、各参加者が $\{1,\dots,q-1\}$ から一様に選んだ $X_i$ について $\alpha^{X_iX_j}$ を鍵とする形で方式を述べている。Sho08 §11.3（pp. 334–336）は位数が素数 $q$ の部分群を使う形で述べ、thm-dh-square は同書 Exercise 11.10（p. 336）の一部を、thm-dh-small-prime は同書 Exercise 11.18（p. 339）の優位度の部分を、一般の巡回群で $1-1/\ell$ まで求めて証明したものである。