楕円曲線暗号

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

具体的な暗号方式の名前ではなく、楕円曲線を利用した暗号方式の総称である。RSAを楕円曲線上で定義した楕円曲線RSA、DSAを楕円曲線上で定義した楕円曲線DSA (ECDSA)、DH鍵共有を楕円化した楕円曲線ディフィー・ヘルマン鍵共有 (ECDH) などがある。公開鍵暗号が多い。

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=dPP,\, 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カードなどハードウェア上に演算回路を実装する場合はサイドチャネル攻撃(特にSPADPA)のターゲットとなる箇所なので工夫が必要となる。

解読[編集]

参考文献[編集]

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

関連項目[編集]