楕円曲線
暗号分野においてかなりの強度を持つとされている楕円曲線について紹介する.
楕円曲線は $$ \frac{x^{2}}{a^{2}} + \frac{y^{2}}{b^{2}} = 1 $$ の式で知られている楕円とは違い, グラフのイメージはどちらかというと3次曲線 $$ y = ax^{3} + bx^{2} + cx + d $$ の y >= 0 の領域をx軸を対象に折り返したものに近い.
実際の曲線の式は
$$
y^{2} = x^{3} + Ax + B
$$
である.
楕円曲線上で演算が可能で, ポイント同士の足し算と, あるポイントの2倍が定義されている. また楕円曲線は群構造を持っているため(トーラスとなっている), 暗号分野でも利用されている. 特に明示していないが, 演算は全て素体上で行われることに注意.
ここでは足し算と2倍演算の解説を行う.
Point Addition
曲線上の2つの点P, Qを結ぶ直線と曲線の交点をx軸を対象に折り返した点をP+Qとする.
$$ P := (x_{1}, y_{1}), \, Q := (x_{2}, y_{2}) $$
まずはP, Qを通る直線の式を考える.
1次関数の傾きは変化の割合で求めることができるので, yの差分をxの差分で割ればよく
$$ \lambda := \frac{y_{2} - y_{1}}{x_{2} - x_{1}} $$
傾きがわかれば, 通る点はわかっているので直線の式が得られる.
\begin{eqnarray} y - y_{1} & = & \lambda(x - x_{1}) \newline y & = & \lambda(x - x_{1}) + y_{1} \newline y & = & \lambda x - \lambda x_{1} + y_{1} \newline y & = & \lambda x + \beta; \, \beta = y_{1} - \lambda x_{1} \newline \end{eqnarray}
直線と曲線の交点は上式と曲線の式を等式で結び, $$ y^{2} = (\lambda x + \beta)^{2} = x^{3} + Ax + B $$
$$ x^{3} -\lambda^{2}x^{2} - 2 \lambda x \beta - \beta^{2} + Ax + B = 0 $$
の解を求めることでxが特定できる.
この方程式の解(交点)は点Pのx1, 点Qのx2, そして3つ目の交点x3である.
この事実は以下の式で表すことができ
$$
(x - x_{1})(x - x_{2})(x - x_{3}) = 0
$$
これを展開すると \begin{eqnarray} x^{3} - x^{2} x_{1} - x^{2} x_{2} - x^{2} x_{3} + x_{1}x_{2}x + x_{1}x_{3}x + x_{2}x_{3}x - x_{1}x_{2}x_{3} & = & 0 \newline x^{3} - x^{2}(x_{1} + x_{2} + x_{3}) + x_{1}x_{2}x + x_{1}x_{3}x + x_{2}x_{3}x - x_{1}x_{2}x_{3} & = & 0 \end{eqnarray}
この式と先の方程式のx2の係数から
\begin{eqnarray} \lambda^{2} & = & x_{1} + x_{2} + x_{3} \newline x_{3} & = & \lambda^{2} - x_{1} - x_{2} \newline \end{eqnarray}
x1, x2はそれぞれ点P, Qのx(既知)で, x3が求めようとしている3つ目の交点である. x3がわかったので, 直線の式に代入し
$$ y = \lambda(x_{3} - x_{1}) + y_{1} $$
ただし, y3はx軸に対称なので
\begin{eqnarray} y_{3} = -y & = & -\lambda(x_{3} - x_{1}) - y_{1} \newline & = & \lambda(x_{1} - x_{3}) - y_{1} \end{eqnarray}
$$
x_{3} := \lambda^{2} - x_{1} - x_{2}, \,\, y_{3} := \lambda(x_{1} - x_{3}) - y_{1}
$$
$$ \lambda := \frac{y_{2} - y_{1}}{x_{2} - x_{1}} $$ これでP + Qを求めることができた.
Point Doubling
曲線上のある点における接線と曲線の交点をx軸を対称に折り返した点を2倍値(2P)とする.
点Pに同じ点Pを足したものとしても定義できる. 2つの点が異なるならばPoint Adding, 同じならばPoint Doublingである.
$$ P := (x_{1}, y_{1}), \, Q := (x_{1}, y_{1}) $$
基本的には足し算と同じだが, λの導出が異なる.
足し算では2点間を結ぶ直線を考えたが, ここでは接線を傾きとするので微分を行う.
$$ y^{2} = x^{3} + Ax + B $$
上式をxで微分すると
\begin{eqnarray} (2y)dy & = & (3x^{2} + A) dx \newline \frac{dy}{dx} & = & \frac{3x^{2} + A}{2y} = \lambda \end{eqnarray}
あとは同様に
$$ x_{3} := \lambda^{2} - 2x_{1}, \,\, y_{3} := \lambda(x_{1} - x_{3}) - y_{1} $$
$$ \lambda := \frac{3x^{2} + A}{2y} $$
これで P + Q = 2Pを求めることができた.
Curve25519
X25519として知られているCurve25519は, 同じ楕円曲線でも今回紹介したものと式が異なり, Montgomery Curveと言われる. 足し算や2倍演算も異なるので注意.
Montgomery Curveの一般式は以下のようになる.
$$ By^{2} = x^{3} + Ax^{2} + x $$
To be continued..
安全性や攻撃について
