はじめに
現在幅広く利用されている公開鍵暗号の一つに楕円曲線暗号があります。これは楕円曲線の性質を利用した暗号です。RSA暗号よりも短い鍵長で安全性が担保されるという強みを持ちます。
今回は楕円曲線暗号の元である楕円曲線について解説します。
楕円曲線とは？
楕円曲線の定義
楕円曲線は代数曲線の一つです。代数曲線は $x,y$ の多項式 $F(x, y)$ を考えるときに $F(x, y)=0$ によって決まる曲線のことを言います。 楕円曲線の定義は「$y^2 = x^3+ax+b$ で表せるような曲線」です。ただし楕円曲線は重根を持ちません。
楕円曲線暗号に使う楕円曲線は有限体 $F_P$ 上で定義されます。
楕円曲線の零点とグラフ
零点とは $y=0$ となる点のことです。
$$ \begin{align} 0&= x^3+ax+b…(1)\\ &= (x-\alpha)(x-\beta)(x-\gamma)…(2) \end{align} $$
楕円曲線は重根を持たないので、必ず上式のように $\alpha, \beta, \gamma$ 三つの零点を見つけることができます。
ではここで具体的な二つの式で楕円曲線がどのような形になるのか見てみましょう。
- $y^2 = x^3+5x$
- $y^2 = x^3-x$
(1)の式は $(0, \pm \surd{5i}$)、(2)の式は $(0, \pm 1)$ がそれぞれの零点になります。
この２式を作図すると以下のようになります。
楕円曲線は $x$ 軸について対称な図になります。また $y＝0$ で実数零点を通ることがわかります。
楕円曲線で $x, y$ が共に有理数になる点を”有理点”と呼びます。楕円曲線上の有理点の有理点の数は楕円曲線によって異なり、有限個の場合も無限個の場合もあります。
無限遠点
楕円曲線では無限遠点と呼ばれる点を考えます。無限遠点は $O=(\infty, \infty)$ で表わされ、楕円曲線上の任意の点と結んだ直線が $y$ 軸と並行になります。
無限遠点は二次元ユークリッド空間（$\mathbb{R}^2$）ではイメージがつかみにくいですが、三次元に拡張するとわかりやすいです。無限遠点は $\mathbb{R}^2$ の射影平面になります。
楕円曲線と加法群
楕円曲線上の加法群を考える前にまずは加法を定義します。
有限体 $F_p$ 上の楕円曲線に無限遠点 $O=\{ \infty, \infty \}$ を加えた曲線を $E:\{y^2=x^3+ax+b\mod{q}\} \cup \{O\}$ 、$E$ 上の有理点 $P,Q$ として定義します。
$P,Q$ を結んだ直線は楕円曲線上の点 $G$ で交わり、$G$ を $x$ 軸について対称移動した点を $G’$ とします。
ここで楕円曲線上の加法を次のように定義します。
$$ \begin{align} P+Q+G &=O \\ P+Q &=-G \\ &= G’ \end{align} $$
つまり $P$ と $Q$ の楕円曲線上の足し算をした結果は、 $P,Q$ を結んだ直線が楕円曲線と交わる（ $P,Q$ 以外の）点 $G$ を x 軸に対象移動した点 $G’$ になります。
$P=Q$ の場合、つまり $P+P$ を求める場合には楕円曲線の接線を使います。まず接線を求めるために$y^2=x^3+ax+b$ を微分します。
$$ \begin{align} \frac{dy}{dx}2y &= 3x^2+a \\ \frac{dy}{dx} &= \frac{3x^2+a}{2y} \end{align} $$
ここで $P$ の座標を $P=\{x_P, y_P\}$ とすると、式(7)にこれを代入すると接線の傾きがわかります。さらに傾きと $P$ より接線を求めることができます。接線がわかれば、接線と楕円曲線の $P$ 以外の交点 $G$ を先ほどと同じように $x$ 軸について対象移動した $G’$ が $P+P$ の答えになります。
楕円曲線上の点は無限遠点 $O$ と楕円曲線上の有理点の集合は加法に対して群になります。群の単位元は $O$ で、$P+O=O+P=P$ が成り立ちます。$P\in E$ に対して $P+P+\cdots+P=kP=O$ となる最小の正整数 $k$ 、$k$ が存在しない場合は $\infty$ を $P$ の位数とよびます。
楕円曲線上の離散対数問題（ECDLP）
最後に暗号を構成するために使用される、楕円曲線上の離散対数問題を紹介します。
楕円曲線上の任意の点 $P$ を $k$ 回足した結果が $G$ だったとします。つまり $G=kP$ となるような点が $G$ です。$P$ と $G$ が与えられたとき整数 $k$ を求める問題を楕円曲線の離散対数問題と呼びます。これは $P$ を $k$ 回足すことが容易なのに対して、その結果である$G$ から $P$ を何回足したかを求めることが難しいことに基づいた問題です。また、 $k$ の桁数が大きければ大きいほど解くことが困難になることで知られています。
この問題の代表的な解法として全数探索や$ρ$法などがありますが、いずれも結果を得るのに大きな計算量が必要になります。一方で一般的な離散対数問題と同程度以上に困難であるかどうかは現在も議論されています。また、一部の楕円曲線では多項式時間でこの問題を解くアルゴリズムが存在することが知られています。そのため、暗号や署名などでこの問題を応用する場合にはNISTやSECG（The Standards for Efficent Cryptography）が推奨するパラメータを利用することが多くあります。
まとめ
- 楕円曲線は $y^2 = x^3+ax+b$ で表される
- 楕円曲線上の有理点集合は加法群である
- 楕円曲線上で離散対数問題を構成できる
参考文献
- 清水祐太郎、藤原祐大、前田優人、米内貴志、渡部祐（2021）『詳解セキュリティコンテスト~CTFで学ぶ脆弱性攻略の技術』マイナビ出版
- IPUSIRON（2018）『暗号技術の全て』株式会社翔泳社
- N. コブリッツ著 ; 櫻井幸一訳（1997）『数論アルゴリズムと楕円暗号理論入門』ュプリンガー・フェアラーク東京
