楕円曲線演算

公開鍵暗号を実現する数学的ベースとして楕円曲線を用いることが安全性や暗号演算の高速化の面で有利と言われており,楕円曲線を用いた暗号アルゴリズムが主流になってきている.

楕円曲線を用いた暗号方式の理解に必要な数学的知識や,楕円曲線演算の高速化の手法などについて解説する.

楕円曲線暗号の概要

楕円曲線上の離散対数問題

離散対数問題 (Discrete Logarithm Problem: DLP)は,以下のように定義される:

$(G, ・)$ を有限群,$\alpha, \beta \in G$ とする.$\beta = \alpha^x$ なる $x$ が存在するとき,整数 $x$ を求めよ.

この $x$ を離散対数という.

有限群 $(G, ・)$ に対しては,以下の性質が要求される.

  1. 群演算 ・ が簡明に記述できる.
  2. 群位数 #$G$ の計算が容易である.
  3. $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}^*$ と比較すると

がほぼ同等の安全性を持つと言われている.従って,効率面と安全性のバランスとから見ると楕円曲線の方が有利であると言える. 但し,ECDLP が実用的時間では解けないような曲線を選択する必要がある.

暗号方式による解読計算量の相違を計算した例を公開鍵暗号の安全性に示す.

楕円曲線暗号

楕円曲線 $E$ 上の基点 (ベースポイント) $G$ が位数 $r$ を持つとする.このとき,鍵ペアを以下のように定義する.

公開鍵から対応する秘密鍵を求めるには,楕円曲線離散対数を計算することが必要である.このため,このタイプの公開鍵暗号の安全性は,楕円曲線離散対数問題の困難性に依存する.

楕円曲線上の演算

楕円曲線の定義

平面曲線は,式 $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方程式を線形変換することにより求められる.

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 \]

楕円曲線上の演算

inserted by FC2 system