楕円曲線暗号

楕円曲線暗号（だえんきょくせんあんごう、Elliptic Curve Cryptography: ECC）とは、楕円曲線上の離散対数問題 (EC-DLP) を安全性の根拠とする暗号。1985年頃に ビクタ・ミラー (Victor Miller) とニール・コブリッツ (Neal Koblitz) が各々発明した。

具体的な暗号方式の名前ではなく、楕円曲線を利用した暗号方式の総称である。RSA暗号を楕円曲線上で定義した「楕円RSA」や、DSAを楕円曲線上で定義した楕円DSA (EC-DSA) や、DH鍵共有を楕円化した楕円DHなどがある。公開鍵暗号が多い。

EC-DLPを解く準指数関数時間アルゴリズムがまだ見つかっていないため、それが見つかるまでの間は、RSA暗号などと比べて、同レベルの安全性をより短い鍵で実現でき、処理速度も速いことをメリットとして、ポストRSA暗号として注目されている。ただしP=NPが成立した場合、EC-DLPを多項式時間で解くアルゴリズムが存在するということになり、ECCの安全性は崩壊する（公開鍵暗号自体が崩壊）。また、送信者が暗号化時に適当な乱数（公開鍵とは違うモノ）を使うので鍵が同じでも平文と暗号文の関係が1対1でない点にも注意（ElGamal暗号でも同様）。

一部の楕円曲線には、DLPを解く多項式時間アルゴリズムが見つかっているため、注意が必要である。

主な演算

楕円曲線の方程式を

$E\!:\, y^2 + a_1 x y + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6$

とする。 この曲線上の有理点の集合と、以下に示される楕円曲線上の演算は群を成している。

楕円曲線上の加算

楕円曲線E上に位置する2点 $P_{\!A}\, (x_1,\, y_1),\, P_{\!B}\, (x_2,\, y_2)$ の加算は以下の通りである。

$P_{\!C} = P_{\!A} + P_{\!B}$ の加算において点 $P_{\!C}$ は、2点 $P_{\!A},\,P_{\!B}$ を通る直線とEとの（$P_{\!A}$ および $P_{\!B}$ と異なる）交点の、y座標の符号を反転したものである。すなわち $P_{\!C}\, (x_3,\, y_3)$ は以下のようになる。

$x_{3}=\phi^{2}+a_{1}\phi-a_{2}-x_{1}-x_{2},$

$y_{3}=-(\phi+a_{1})\,x_{3}-\psi-a_{3}.$

ただし $\phi,\, \psi$ は

$\phi=\frac{y_{2}-y_{1}}{x_{2}-x_{1}},$

$\psi=\frac{y_{1}x_{2}-y_{2}x_{1}}{x_{2}-x_{1}}.$

楕円曲線上での2倍算

楕円曲線E上に位置する点 $P_{\!A}\, (x_1,\,y_1)$ の2倍算は以下の通りである。

$P_{\!D} = 2 P_{\!A}$の2倍算において点$P_{\!D}$は、$P_{\!A}$でのEとの接線とEとの（$P_{\!A}$と異なる）交点の、y座標の符号を反転したものである。すなわち $P_{\!D}\, (x_4,\, y_4)$ の式は以下のようになる。

$x_{4}=\phi^{2}+a_{1}\phi-a_{2}-x_{1}-x_{2},$

$y_{4}=-(\phi+a_{1})\,x_{3}-\psi-a_{3}.$

この式は加算の場合と同様のものであるが、$\phi,\, \psi$ を表す式が次のように変わる。

$\phi=\frac{3x^{2}_{1}+2a_{2}x_{1}+a_{4}-a_{1}y_{1}}{2y_{1}+a_{1}x_{1}+a_{3}},$

$\psi=\frac{-x^{3}_{1}+a_{4}x_{1}+2a_{6}-a_{3}y_{1}}{2y_{1}+a_{1}x_{1}+a_{3}}.$

Scalar Multiplication

Scalar Multiplicationは楕円曲線上における掛け算である。

暗号化・復号の過程において、$Q=dP$（$P,\, Q$ は楕円曲線上の点）という演算を行う。 ナイーヴな実装としては $Q = ( \cdots ( ( P+P ) + P ) + \cdots ) + P$ というように Pを $(d-1)$ 回加算（1回目は2倍算となる）するが、これでは効率が悪い。

Scalar MultiplicationはちょうどRSA暗号におけるModular Multiplication（冪剰余算）とリンクしており、これの高速化手法もそれから流用できるものが多い。例えば、そのひとつとして有名なBinary法では、dを2進数表記した場合においてdの一部分 $d_i$ が "0" の場合は2倍算のみを行い、"1" の場合は2倍算+加算を行うことによりナイーブな実装と同じ計算をより高速に行なっている。この計算手法では、2倍算はModular Multiplicationにおける自乗算、加算は掛け算にそれぞれ対応している。

この演算は楕円曲線暗号の根幹を成している部分であり、楕円曲線暗号を利用する際の時間の大半を占めている。ゆえに、ICカードなどハードウェア上に演算回路を実装する場合はサイドチャネル攻撃（特にSPA、DPA）のターゲットとなる箇所なので工夫が必要となる。

解読

• 2004年4月10日: ECC2 109ビットの解読に成功 (certicom)。
• 2009年7月8日: ECC 112ビットの解読に成功（SONY・PS3使用）[1]

参考文献

• Blake, Seroussi & Smart 著、Elliptic Curves in Cryptography, CAMBRIDGE UNIVERSITY PRESS, 1999

関連項目

• 暗号理論
• 楕円曲線暗号の特許