楕円曲線演算
公開鍵暗号を実現する数学的ベースとして楕円曲線を用いることが安全性や暗号演算の高速化の面で有利と言われており,楕円曲線を用いた暗号アルゴリズムが主流になってきている.
楕円曲線を用いた暗号方式の理解に必要な数学的知識や,楕円曲線演算の高速化の手法などについて解説する.
楕円曲線上の離散対数問題
離散対数問題 (Discrete Logarithm Problem: DLP)は,以下のように定義される:
$(G, ・)$ を有限群,$\alpha, \beta \in G$ とする.$\beta = \alpha^x$ なる $x$ が存在するとき,整数 $x$ を求めよ.
この $x$ を離散対数という.
有限群 $(G, ・)$ に対しては,以下の性質が要求される.
- 群演算 ・ が簡明に記述できる.
- 群位数 #$G$ の計算が容易である.
- $G$ 上の離散対数問題が計算量的に困難である.
Diffie-Hellman の公開鍵暗号システムは,有限体の乗法群 ${\mathbb{F}_q}^*$ を用いていた.近年の離散対数問題についてのアルゴリズムの研究の進展と計算機の能力の向上に伴い,乗法群
${\mathbb{F}_q}^*$ を用いた場合の安全性を保持するために必要な $q$ のサイズが大きくなってきている.現在では,$q$ のサイズは最低でも 1024ビット以上必要と言われている.
実用上の観点から,安全性を保持しつつサイズの小さい位数の群により Diffie-Hellman 方式などを実現することが望まれる.それに対応するのが楕円曲線暗号系である.
1986年に V.Miller と N.Koblitz は,有限体上で定義される楕円曲線のヤコビアン群に含まれる有限巡回群が,上記の一方向性の性質を足していることを見出し,楕円曲線に基づく暗号化システムを提唱した.
一般に,体 $K$ 上定義される楕円曲線の場合,その $K$ 有理点はある加法のもとで有限群をなすことが知られている. また,2つの有理点 $P$,$Q$ の加法演算によって得られる有理点 $R$ の各座標は,$P$,$Q$
の各座標の簡単な有理式によって表される.すなわち,以下に示すように有限体上の離散対数問題を楕円曲線上で定義したものである.
- 楕円曲線上の離散対数問題
-
$Y = x G$ の $Y$ から $x$ を求める問題 ($Y$, $G$ は有限体 $\mathbb{F}_q$ 上の楕円曲線上の点,$x G$ は $G$ をスカラー倍($x$ 倍する演算) である.
$Y$ が公開鍵,$x$ が秘密鍵 ($G$ は公開システムパラメータ)に対応する.
- 楕円曲線離散対数
-
楕円曲線 $E$ 上の点 $G$ が素数の位数 $r$ を持つとする(ここで,$r^2$ は楕円曲線の位数 #$E(\mathbb{F}_q)$ を割り切らない). このとき,ある $m$ に対して $P = m G$
が満足されるのは,$r P = {\cal O}$ の時に限られる.係数 $m$ は $P$ の基点 $G$ に関する楕円曲線離散対数と呼ばれる. 楕円曲線離散対数は,法 $r$ の整数である.
楕円曲線の群については,前述の3つの要件のうち 1 の群演算の簡明さについては,楕円曲線上の加法は問題なくこれを満たし,3 の安全性についても一部の曲線を除けば優秀である.
${\mathbb{F}_q}^*$ と比較すると
- 1024 ビットの $q$ に対する ${\mathbb{F}_q}^*$ 上の離散対数問題 (DLP)
- 約160 ビットの位数 $r$ に対する楕円曲線上の離散対数問題 (ECDLP)
がほぼ同等の安全性を持つと言われている.従って,効率面と安全性のバランスとから見ると楕円曲線の方が有利であると言える. 但し,ECDLP が実用的時間では解けないような曲線を選択する必要がある.
暗号方式による解読計算量の相違を計算した例を公開鍵暗号の安全性に示す.
楕円曲線暗号
楕円曲線 $E$ 上の基点 (ベースポイント) $G$ が位数 $r$ を持つとする.このとき,鍵ペアを以下のように定義する.
- 秘密鍵 $s$ は,法 $r$ に基づく整数
- 公開鍵 $W$ は,$W = s G$ で定義される楕円曲線 $E$上の点
公開鍵から対応する秘密鍵を求めるには,楕円曲線離散対数を計算することが必要である.このため,このタイプの公開鍵暗号の安全性は,楕円曲線離散対数問題の困難性に依存する.
楕円曲線の定義
平面曲線は,式 $F(x, y) = 0$ を満足する点の集合で定義される.最も単純な平面曲線は直線(その定義式は $x$ と $y$ の一次式)であり,楕円曲線は次数が3の 3次曲線である.
暗号学的に興味のある楕円曲線は,有限体上で定義された曲線である.すなわち,定義式 $F(x, y) = 0$ の係数が有限体 $\mathbb{F}_q$ の要素であり,曲線上の点 $P = (x, y)$ の座標
$x$,$y$ が $\mathbb{F}_q$ の要素であるものである.
- Weierstrass方程式
-
$K$ を体とするとき,$K$ 上の楕円曲線 $E$ は,以下の Weierstrass標準形と呼ばれる方程式で表される.
\[ y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6 \]
ここで,$a_1,a_2,a_3,a_4,a_6,x,y \in K$ である.
体 $K$ 上の楕円曲線 $E$ の点の集合 $E(K)$ は,アーベル群を成す.Weierstrass方程式で表される非特異3次曲線と無限遠点 ${\cal O}$ と呼ばれる点からなる群である.無限遠点 ${\cal
O}$ 以外の点は,有限点と呼ばれる.ここで,非特異曲線とは,どの点でも接線を1本だけ引ける曲線(楕円曲線の演算の定義に接線を使うので,どの点でも1本の接線が定義できないといけない)である. 曲線の方程式を $f(x,
y)$ とするとき,$(∂f/∂x, ∂f/∂y)$ のある点での値が $(0, 0)$ のときにその点を特異点という $(0, 0)$ でないとき非特異).曲線上のすべての点が非特異のとき,その曲線を非特異という.
Weierstrass方程式の標準系では,全ての体 $K$ 上の楕円曲線を表現することが可能であるが,実用上からは Weierstrass方程式と群構造が同一のより簡略化した同型類の式が利用される.
同型類の方程式は,Weierstrass方程式を線形変換することにより求められる.
- 有限体 $\mathbb{F}_p\ (p \gt 3)$ に対する Weierstrass方程式
\[ y^2 = x^3 + ax + b \]
ここで,$a$ と $b$ は法 $p$ での整数であり,$\bigtriangleup =-16(4a^3 + 27b^2) \ne 0$ である.
- 有限体 $\mathbb{F}_{2^m} \ (a_1 \ne 0)$ に対する Weierstrass方程式
\[ y^2 + xy = x^3 + ax^2 + b \]
ここで, $a$ と $b$ は $\mathbb{F}_{2^m}$ の要素であり,$\bigtriangleup = b \ne 0$ である.
- 有限体 $\mathbb{F}_{3^m} \ (a_1^2 \ne -a_2)$ に対する Weierstrass方程式
\[ y^2 = x^3 + ax^2 + b \]
ここで,$a$ と $b$ は $\mathbb{F}_{3^m}$ の要素であり,$\bigtriangleup = -a^3b \ne 0$ である.
Weierstrass方程式では,$j$ 不変量 ($j$-invariant)と呼ばれる値が存在する.この値は,楕円曲線の同類型集合の不変量であり,次式で与えられる.
\[ j = \frac{(d_2^2 - 24d_4)^4}{\bigtriangleup},\ d_2=a_1^2+4a_2,\ d_4=2a_4+a_1a_3 \]
楕円曲線上の演算
- 加法
楕円曲線上の点に関する加法は,次のように幾何学的に定義できる.
点 $P = (x, y)$ の加法に関する逆元 $-P$ を次の式で定義する.
\[ -P = \left\{
\begin{array}{ll}
(x, -y), & \text{if}\ q = p\ (素数),\\
(x, x + y), & \text{if}\ q = 2^m.\\
\end{array}\right.
\]
このとき,点 $P$ と $Q$ の和の点 $R = P + Q$ は,点 $P$,$Q$ および $-R$ が同一直線上に並ぶ関係にある点である.
また,点 $P$ を2倍する(double) とは,$P$ における接線をとることに対応する.接線が曲線と交わる他の1点を $R$ とするとき,点 $-R$ が点 $P$ の2倍点 $(2P = P + P)$
である.なお,接線が垂直になるとき(y 軸に並行),無限遠点 ${\cal O}$ で交わるものとみなし,$P + P = {\cal O}$ である.
無限遠点 ${\cal O}$ は,通常の加法に関する 零元の役目を果す.すなわち,
\[ P + {\cal O} = P \]
\[ P + (-P) = {\cal O} \]
である.
楕円点の加法
楕円曲線上の点の加法を実装するとき,互いの逆元ではない異なる点の加算(add) と同一点の加算(double) を区別する必要がある.これらは,異なる演算になる.また,無限遠点 ${\cal O}$
を含む特別な場合も考慮する必要がある.
楕円曲線 $E: y^2 = x^3 + ax + b$ 上の相異なる点 $P(x_1, y_1)$ と点 $Q(x_2, y_2)$ の2点を通る直線 $L$ の方程式は,
\[ y - y_1 = \frac{y_1- y_2}{x_1 - x_2} (x - x_1) \]
であり,楕円曲線 $E$ と直線 $L$ との交点は,
\[ \left\{\frac{y_1 - y_2}{x_1 - x_2}(x - x_1)+ y_1\right\}^2 = x^3 + ax + b \]
である.この 3次方程式が3つの根 $x_1, x_2, x_3$ を持つとき,
\[ (x-x_1)(x-x_2)(x-x_3) = 0 \]
であり,3つの根 $x_1, x_2, x_3$ の和は,3次方程式の2次の係数になる.これを上記の楕円曲線 $E$ と直線 $L$ との交点の方程式と比べることにより,
\[ x_3 = \left(\frac{y_1-y_2}{x_1-x_2}\right)^2 - x_1 - x_2 \]
\[ y_3 = y_1 + \left(\frac{y_1-y_2}{x_1-x_2}\right)(x_3 - x_1) \]
が得られる.これより,点 $P$ と点 $Q$ の和 $P + Q$ の座標は,$(x_3, y_3)$ となる.
楕円曲線上の同一点の加算(2倍算) の式は,次のように求められる.
楕円曲線 $E: y^2=x^3+ax+b$ 上の点 $P(x_1, y_1)$ 上の点 $P(x_1, y_1)$ における接線 $L'$ の方程式は,
\[ y - y_1 = f'(x_1) (x - x_1) \]
\[ f'(x) = -F_x(x,y)/F_y(x,y) = (3x^2 + a)/2y \]
であり,楕円曲線 $E$ と直線 $L'$ との交点は,
\[ \left\{\frac{3x_1^2+a}{2y_1}(x - x_1)+ y_1\right\}^2 = x^3 + ax + b \]
である. この 3次方程式が根 $x_1, x_3'$ を持つとき ($x_1$ は重根),
\[ (x-x_1)^2(x-x_3') = 0 \]
であり,3次方程式の 2次の係数を上記の楕円曲線 $E$ と直線 $L'$ との交点の方程式と比べることにより,
\[ x_3' = \left(\frac{3x_1^2+a}{2y_1}\right)^2 - 2x_1 \]
\[ y_3' = y_1 + \left(\frac{3x_1+a}{2y_1}\right)(x_3' - x_1) \]
が得られる. これより,点 $P$ と点 $P$ の和 $2P$ の座標は,$(x_3', -y_3')$ となる.
- スカラー倍算
楕円曲線上の点の加法は可能であるが,乗算は定義されない.しかし,同一の点に対する繰り返しの加算であるスカラー倍算を定義することができる.$n$ を正整数とし,$P$ を楕円曲線上の点とするとき,スカラー倍算 $n P$ は $P$ を $n$ 回加算したものである.
例えば,
\[ 5 P = P + P + P + P + P. \]
である.
スカラー倍算の記法は,${\cal O}$ および負に対しても次のように拡張される.
\[ 0 P = {\cal O}, \quad (-n)P = n(-P) = -n P. \]
また,次の関係が成立つ.
- 結合法則 $(P+Q)+R=P+(Q+R)$ を満たす.
- $Q= -P$ ならば,$P + Q = {\cal O}$ である.
- 無限遠点 ${\cal O}$ に対して,${\cal O} = -{\cal O}$ である.
なお,楕円点のスカラー倍演算 $n P$ の表記は,通常の乗算と区別するため,$[n]P$ のように表記する場合がある.