楕円曲線暗号
概要
楕円曲線暗号（elliptic curve cryptography）とは、有限体 $\mathbb{F}_p$ 上の楕円曲線の有理点のなす群で、点 $G$ と $[n]G$ から $n$ を求める離散対数問題が難しいことを使う暗号の総称で、鍵共有 ECDH や署名 ECDSA がある。点の $n$ 倍は約 $2\log_2 n$ 回の足し算で計算でき、点は $x$ 座標と 1 ビットで表せる。ECDSA の署名は検証で受け入れられるが、乱数を使い回すと秘密鍵が復元され、曲線上にない点を受け入れると秘密鍵の情報が漏れる。多くの曲線では指数計算法の類似が知られず、法 $p$ の乗法群より小さな鍵で済むと考えられている。
前提知識: 楕円曲線, 有限体, 離散対数, Diffie–Hellman鍵共有
素数 $p=97$ の上の曲線 $y^2=x^3+7$ は、無限遠点を含めてちょうど $79$ 個の点をもち、点の足し算で位数 $79$ の巡回群になる。点 $G=(5,36)$ を $13$ 倍した点と $29$ 倍した点を 2 人が交換すれば、どちらも $13\cdot29$ 倍の点 $(68,16)$ を計算でき、これを共有の秘密にできる。一方、$G$ とその $n$ 倍の点から $n$ を求める問題は、曲線を大きくすると、知られている最良の算法でも群の位数の平方根ほどの手間がかかる。
このように、有限体上の 楕円曲線 の有理点のなす群で離散対数を求めるのが難しいことを使う暗号を、楕円曲線暗号（elliptic curve cryptography）という。法 $p$ の乗法群を使う Diffie–Hellman鍵共有 や ElGamal 暗号（公開鍵暗号）を、楕円曲線の群に置き換えたものである。
この記事では、楕円曲線の離散対数問題と、鍵共有・署名の方式（ECDH・ECDSA）を定義し、次を証明する。点の $n$ 倍が $2\log_2n$ 回以下の足し算で計算できること（prop-ecc-double-add）。点は $x$ 座標と 1 ビットで決まること（prop-ecc-compression）。ECDSA の検証が正しく働くことと、署名に使う乱数を使い回すと秘密鍵が分かること（thm-ecc-ecdsa、thm-ecc-nonce）。受け取った点が曲線上にあることを確かめないと秘密鍵の情報が漏れること（thm-ecc-invalid）。
定義
以下、$p>3$ を素数とし、$a,b\in\mathbb F_p$ は $4a^3+27b^2\ne0$ を満たすとする。楕円曲線 $E\colon y^2=x^3+ax+b$ の $\mathbb F_p$ 有理点の集合 $E(\mathbb F_p)$ は、無限遠点 $O$ を単位元とし、弦と接線で定める足し算によってアーベル群になる（楕円曲線 の定義「弦と接線による加法」と定理「群構造と因子類群」）。足し算の式は次のとおりである（BS23 §15.2、p. 618）。$P=(x_1,y_1)$、$Q=(x_2,y_2)$ について、$x_1=x_2$ かつ $y_1=-y_2$ なら $P+Q=O$ であり、そうでなければ
$$
\lambda=\begin{cases}\dfrac{y_2-y_1}{x_2-x_1}&(x_1\ne x_2)\\[2mm]\dfrac{3x_1^2+a}{2y_1}&(P=Q,\ y_1\ne0)\end{cases},\qquad
x_3=\lambda^2-x_1-x_2,\quad y_3=\lambda(x_1-x_3)-y_1
$$
として $P+Q=(x_3,y_3)$ である。逆元は $-(x_1,y_1)=(x_1,-y_1)$ である。整数 $n$ と点 $P$ について、$P$ の $n$ 倍を $[n]P$ と書く。
点の個数は Hasse の定理により $\lvert\#E(\mathbb F_p)-(p+1)\rvert\le2\sqrt p$ を満たす（楕円曲線 の定理「Hasse の定理」）。
$G\in E(\mathbb F_p)$ を位数 $N$ の点とする。$Q\in\langle G\rangle$ が与えられたとき、$Q=[n]G$ を満たす $n\in\mathbb Z/N\mathbb Z$ を求める問題を、楕円曲線の離散対数問題（ECDLP）という。
これは巡回群 $\langle G\rangle$ での 離散対数 問題そのものである。
曲線 $E/\mathbb F_p$ と位数 $N$ の点 $G$ を公開する。Alice は秘密の整数 $d_A$ を選んで $A=[d_A]G$ を、Bob は秘密の整数 $d_B$ を選んで $B=[d_B]G$ を相手に送る。Alice は $[d_A]B$ を、Bob は $[d_B]A$ を計算する。この手順を 楕円曲線 Diffie–Hellman 鍵共有（ECDH）という。
$[d_A]B=[d_Ad_B]G=[d_B]A$ なので、2 人は同じ点を得る（Sil09 §XI.4.2、p. 378）。盗聴者が知るのは $G,[d_A]G,[d_B]G$ であり、そこから $[d_Ad_B]G$ を求めるのが楕円曲線の Diffie–Hellman 問題である。
$E/\mathbb F_p$ と、素数位数 $N$ の点 $G$ を公開する。点 $R\ne O$ の $x$ 座標の $\{0,\dots,p-1\}$ の代表を $N$ で割った余りを $\bar x(R)\in\mathbb Z/N\mathbb Z$ と書く。
- 鍵：秘密鍵 $d\in\{1,\dots,N-1\}$、公開鍵 $Q=[d]G$。
- 署名：文書から計算した値（ハッシュ値）$h\in\mathbb Z/N\mathbb Z$ に対し、乱数 $k\in\{1,\dots,N-1\}$ を選び、$r=\bar x([k]G)$、$s=k^{-1}(h+dr)\bmod N$ とする。$r=0$ か $s=0$ なら $k$ を選び直す。署名は $(r,s)$ である。
- 検証：$r,s\in\{1,\dots,N-1\}$ を確かめ、$w=s^{-1}$、$u_1=hw$、$u_2=rw$（法 $N$）として $X=[u_1]G+[u_2]Q$ を計算し、$X\ne O$ かつ $\bar x(X)=r$ なら受け入れる。
この形は Sil09 §XI.4.6（pp. 380–381）と BS23 §19.3（pp. 770–771）による。
計算の基本
倍算
$n\ge1$ を整数、$n=\sum_{i=0}^{L-1}n_i2^i$（$n_i\in\{0,1\}$、$n_{L-1}=1$）を 2 進展開とする。$R_{L-1}=P$、$R_{i}=2R_{i+1}+n_iP$（$i=L-2,\dots,0$）と定めると $R_0=[n]P$ であり、計算に使う足し算（2 倍を含む）は $2(L-1)=2\lfloor\log_2n\rfloor$ 回以下である。
$m_i=\sum_{j\ge i}n_j2^{j-i}$（$n$ を $2^i$ で割った商）とおくと、$m_{L-1}=1$、$m_i=2m_{i+1}+n_i$、$m_0=n$ である。$R_i=[m_i]P$ を $i$ の降順に示す。$i=L-1$ では $R_{L-1}=P=[1]P$。$R_{i+1}=[m_{i+1}]P$ なら $R_i=[2m_{i+1}]P+[n_i]P=[m_i]P$ である。よって $R_0=[n]P$。各段で 2 倍を 1 回と、$n_i=1$ のとき足し算を 1 回行うので、合計は $L-1$ 段で $2(L-1)$ 回以下である。$2^{L-1}\le n<2^L$ より $L-1=\lfloor\log_2n\rfloor$ である。$\square$
これは乗法群の 反復二乗法 を足し算で書いたものである（BS23 p. 618）。たとえば $17=10001_{(2)}$ では、$P$ を 4 回 2 倍して $16P$ を作り、最後に $P$ を足す（5 回）。
点の圧縮
$x_0\in\mathbb F_p$ について、$E$ の点で $x$ 座標が $x_0$ のものは高々 2 個であり、2 個あるときは $(x_0,y_0)$ と $(x_0,-y_0)$（$y_0\ne0$）である。さらに $y$ 座標を $\{0,\dots,p-1\}$ の代表で表すと、この 2 点の $y$ 座標の偶奇は異なる。したがって $E(\mathbb F_p)\setminus\{O\}$ の点は、$x$ 座標と $y$ 座標の偶奇の 1 ビットで決まる。
$c=x_0^3+ax_0+b$ とおく。$x$ 座標が $x_0$ の点は $y^2=c$ の解 $y$ と対応する。$y_0^2=c$ なら $y^2=c$ は $(y-y_0)(y+y_0)=0$ と同値で、$\mathbb F_p$ は体なので $y=\pm y_0$ である。よって点は高々 2 個で、2 個なのは $y_0\ne-y_0$、すなわち $y_0\ne0$（$p$ は奇数）のときである。そのとき代表 $y_0\in\{1,\dots,p-1\}$ に対し $-y_0$ の代表は $p-y_0$ であり、$y_0+(p-y_0)=p$ は奇数なので、2 つの偶奇は異なる。$\square$
$y^2=c$ の解を実際に求めるには、法 $p$ の平方根を計算する算法を使う（Sil09 Remark XI.4.3.5、p. 378）。たとえば $y^2=x^3+7$（$p=97$）で $x=5$ なら $c=132\equiv35$ で、解は $y=36$（偶数）と $y=61$（奇数）である。
ECDSA
def-ecc-ecdsa の手順で作った署名 $(r,s)$ は、検証で受け入れられる。さらに $(r,N-s)$ も同じ $h$ に対する署名として受け入れられる。
$G$ の位数は $N$ なので、$[u]G$ は $u$ の法 $N$ の剰余類だけで決まる。$Q=[d]G$ だから
$$
X=[u_1]G+[u_2]Q=[u_1+du_2]G=[w(h+dr)]G
$$
であり、$s=k^{-1}(h+dr)$ より $w(h+dr)=s^{-1}sk=k$ なので $X=[k]G$ である。$1\le k\le N-1$ で $N$ は $G$ の位数だから $X\ne O$ であり、$\bar x(X)=\bar x([k]G)=r$ となって受け入れられる。
$(r,N-s)$ では、$w'=(-s)^{-1}=-w$ なので $u_1'=-u_1$、$u_2'=-u_2$ となり、検証で計算する点は $-[k]G$ である。$-[k]G$ は $[k]G$ と $x$ 座標が同じ点なので（足し算の式の直後の注意）、$\bar x(-[k]G)=r$ であり、やはり受け入れられる。$N-s\in\{1,\dots,N-1\}$ も満たされている。$\square$
後半は、ECDSA の署名から同じ文書の別の署名が誰にでも作れることを示している（BS23 p. 771）。
同じ秘密鍵 $d$ と同じ乱数 $k$ で、法 $N$ で異なるハッシュ値 $h_1,h_2$ に署名した $(r,s_1)$、$(r,s_2)$ が得られたとする。このとき $s_1\ne s_2$ であり、
$$
k\equiv\frac{h_1-h_2}{s_1-s_2},\qquad d\equiv\frac{s_1k-h_1}{r}\pmod N
$$
によって $k$ と $d$ が公開の値だけから計算できる。
$r=\bar x([k]G)$ は $k$ だけで決まるので、2 つの署名の $r$ は同じである。署名の式から $ks_1\equiv h_1+dr$、$ks_2\equiv h_2+dr\pmod N$ であり、引き算すると $k(s_1-s_2)\equiv h_1-h_2\not\equiv0$ となる。よって $s_1\ne s_2$ で、$N$ は素数だから $s_1-s_2$ は可逆であり、$k$ の式が得られる。$r\ne0$ も可逆なので、第 1 式から $d\equiv(ks_1-h_1)r^{-1}$ である。$\square$
この攻撃は実際の機器で起き、秘密鍵が知られた例がある（BS23 p. 771）。乱数 $k$ は署名ごとに新しく一様に選ぶ必要がある。
$p=97$、$E\colon y^2=x^3+7$、$N=\#E(\mathbb F_{97})=79$（素数）、$G=(5,36)$ とする。秘密鍵 $d=17$ の公開鍵は $Q=[17]G=(71,52)$ である。$k=11$ とすると $[11]G=(32,59)$ で $r=32$ である。$11^{-1}\equiv36\pmod{79}$ なので、$h_1=23$ では $s_1=36\cdot(23+17\cdot32)=36\cdot567\equiv36\cdot14\equiv30$、$h_2=41$ では $s_2=36\cdot585\equiv36\cdot32\equiv46\pmod{79}$ である。
検証：$h_1=23$、$s_1=30$ では $w=30^{-1}\equiv29$、$u_1\equiv23\cdot29\equiv35$、$u_2\equiv32\cdot29\equiv59$ で、$[35]G+[59]Q=(32,59)$ となり $\bar x=32=r$ である。
同じ $k$ を使った 2 つの署名から、$k\equiv(23-41)/(30-46)=18/16\equiv18\cdot5=90\equiv11$（$16\cdot5=80\equiv1$）、$d\equiv(30\cdot11-23)/32\equiv70\cdot42\equiv17\pmod{79}$（$32\cdot42=1344\equiv1$）と、秘密鍵が復元される。
受け取った点の確認
足し算の式には $a$ は現れるが $b$ は現れない。このため、曲線上にない点を足し算の式に入れると、別の曲線の上で計算したことになる。
$P=(x_0,y_0)\in\mathbb F_p^2$ とし、$b'=y_0^2-x_0^3-ax_0$ とおく。$4a^3+27b'^2\ne0$ なら $E'\colon y^2=x^3+ax+b'$ は楕円曲線で $P\in E'(\mathbb F_p)$ であり、$E$ の足し算の式で prop-ecc-double-add の手順を $P$ に行った結果は、$E'$ の群での $[n]P$ に等しい（途中で $O$ が現れる場合も、$O$ を単位元として扱う限り同じ）。
$b'$ の定め方から $y_0^2=x_0^3+ax_0+b'$ なので $P\in E'(\mathbb F_p)$ である。上の足し算の式（$\lambda$、$x_3$、$y_3$ と、和が $O$ になる条件）は $a$ と 2 点の座標だけで書かれ、$b$ を含まないので、$E$ の式と $E'$ の式は同じである。手順の途中の点は $R_i=[m_i]P$ で、prf-ecc-double-add の帰納法は $E'$ の群の中でそのまま成り立つ。各段で使う式が $E'$ の群の足し算の式と一致するので、手順の結果は $E'$ での $[n]P$ である。$\square$
ex-ecc-ecdsa-97 の曲線 $y^2=x^3+7$（$p=97$、$a=0$）で、秘密鍵 $d=17$ をもつ相手に、点 $P=(0,1)$ を送り、$[d]P$ を返させるとする。$1\ne0^3+7$ なので $P$ は $E$ の上にないが、$b'=1$ の曲線 $E'\colon y^2=x^3+1$ の上にある。$E'$ では 2 倍の傾きが $(3\cdot0^2+0)/(2\cdot1)=0$ なので $[2]P=(0,-1)=-P$、$[3]P=O$ であり、$P$ の位数は $3$ である。thm-ecc-invalid により、返ってくる点は $[17]P=[2]P=(0,96)$ なので、$d\equiv2\pmod3$ が分かる。小さな位数の点を使ってこれをいくつかの法で行えば、中国剰余定理 で $d$ が求まる。受け取った点が $E$ の上にあるかを確かめれば防げる（BS23 §15.3.2、p. 623）。
安全でない曲線
点の個数や構造によっては、楕円曲線の離散対数問題が易しくなる。次の表の 3・4 行目は曲線を選ぶときに守る条件であり（BS23 §15.3、pp. 619–620）、1・2 行目は方式を使うときに守る条件である。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 署名ごとに新しい乱数 $k$ を選ぶ | ex-ecc-ecdsa-97 で同じ $k=11$ を 2 度使う | 秘密鍵 $d$ が公開の値から分からない |
| 受け取った点が $E$ の上にあることを確かめる | ex-ecc-invalid-97 の点 $(0,1)$ | 返した点から $d$ の情報が漏れない |
| $\#E(\mathbb F_p)\ne p$ | $p=97$、$E\colon y^2=x^3+x+1$（$97$ 個の点） | 離散対数の計算がおよそ $\sqrt N$ 回の演算を要する |
| 群の位数が大きな素因数をもつ | $p=97$、$E\colon y^2=x^3+1$（$84=2^2\cdot3\cdot7$ 個の点） | 離散対数の計算がおよそ $\sqrt N$ 回の演算を要する |
1 行目は thm-ecc-nonce、2 行目は thm-ecc-invalid による。3 行目：$4\cdot1^3+27\cdot1^2=31\ne0$ なので $y^2=x^3+x+1$ は $\mathbb F_{97}$ 上の楕円曲線で、点を数えると $O$ を含めて $97$ 個ある。$\#E(\mathbb F_p)=p$ の曲線（anomalous な曲線）では、$\mathbb Q_p$ 上の曲線への持ち上げを使って離散対数が多項式時間で解ける（Sil09 Proposition XI.6.5、p. 389、BS23 p. 620。この記事では証明しない）。4 行目：$4\cdot0^3+27\cdot1^2=27\ne0$ で、点を数えると $84$ 個ある。$84$ の最大の素因数は $7$ なので、位数の素因数ごとに問題を分ける Pohlig–Hellman の帰着（離散対数 の定理「Pohlig–Hellman の帰着」）により、どの点の離散対数も位数 $2,3,7$ の群での離散対数に帰着し、手間は群の位数 $84$ ではなく最大の素因数 $7$ の大きさで決まる。実用では $N$ が大きな素数か、その小さな倍数になる曲線を使う。このほか、$N$ が $p^\tau-1$ を割る小さな $\tau$ がある曲線では、Weilペアリング によって問題が有限体 $\mathbb F_{p^\tau}$ の乗法群の離散対数に帰着される（$N$ が素数で $\gcd(p-1,N)=1$ のとき Sil09 Proposition XI.6.1、p. 387。BS23 p. 620 も参照）。$p\ge5$ 上の超特異な曲線では $\tau=2$ になる（Sil09 Example XI.6.4、p. 388）。
補足
法 $p$ の乗法群では、整数の素因数分解を使う 指数計算法 により離散対数が準指数時間で解ける。楕円曲線の群では、多くの曲線について指数計算法の類似が知られておらず、最良の算法は Baby-step Giant-step 法などの衝突を探す算法で、およそ $\sqrt N$ 回の演算を要する（Sil09 Example XI.4.1、p. 377、Ste17 §6.4.3、p. 139）。そのため、同じ安全さを得るのに必要な $p$ の大きさがずっと小さく、鍵や署名が短くて済む（Sil09 p. 377）。これは知られている算法についての比較であり、楕円曲線の離散対数問題が難しいことは証明されていない。
広く使われる曲線に、$y^2=x^3-3x+b$ の形の secp256r1（P-256）、$y^2=x^3+7$ の形の secp256k1、Montgomery 形 $y^2=x^3+486662x^2+x$ の Curve25519 があり、いずれも $2^{256}$ 程度の大きさの素数 $p$ の上で定義される（BS23 §15.3.1・§15.3.3、pp. 620–624）。この記事の例の曲線 $y^2=x^3+7$ は secp256k1 と同じ形の式を小さな $p$ で考えたものである。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
