楕円曲線暗号
楕円曲線暗号（だえんきょくせんあんごう、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を解く多項式時間アルゴリズムが見つかっているため、注意が必要である。
主な演算
楕円曲線の方程式を
- <math>E\!:\, y^2 + a_1 x y + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6</math>
とする。 この曲線上の有理点の集合と、以下に示される楕円曲線上の演算は群を成している。
楕円曲線上の加算
楕円曲線E上に位置する2点 <math>P_{\!A}\, (x_1,\, y_1),\, P_{\!B}\, (x_2,\, y_2)</math> の加算は以下の通りである。
<math>P_{\!C} = P_{\!A} + P_{\!B}</math> の加算において点 <math>P_{\!C}</math> は、2点 <math>P_{\!A},\,P_{\!B}</math> を通る直線とEとの（<math>P_{\!A}</math> および <math>P_{\!B}</math> と異なる）交点の、y座標の符号を反転したものである。すなわち <math>P_{\!C}\, (x_3,\, y_3)</math> は以下のようになる。
- <math>x_{3}=\phi^{2}+a_{1}\phi-a_{2}-x_{1}-x_{2},</math>
- <math>y_{3}=-(\phi+a_{1})\,x_{3}-\psi-a_{3}.</math>
ただし <math>\phi,\, \psi</math> は
- <math>\phi=\frac{y_{2}-y_{1}}{x_{2}-x_{1}},</math>
- <math>\psi=\frac{y_{1}x_{2}-y_{2}x_{1}}{x_{2}-x_{1}}.</math>
楕円曲線上での2倍算
楕円曲線E上に位置する点 <math>P_{\!A}\, (x_1,\,y_1)</math> の2倍算は以下の通りである。
<math>P_{\!D} = 2 P_{\!A}</math>の2倍算において点<math>P_{\!D}</math>は、<math>P_{\!A}</math>でのEとの接線とEとの（<math>P_{\!A}</math>と異なる）交点の、y座標の符号を反転したものである。すなわち <math>P_{\!D}\, (x_4,\, y_4)</math> の式は以下のようになる。
- <math>x_{4}=\phi^{2}+a_{1}\phi-a_{2}-x_{1}-x_{2},</math>
- <math>y_{4}=-(\phi+a_{1})\,x_{3}-\psi-a_{3}.</math>
この式は加算の場合と同様のものであるが、<math>\phi,\, \psi</math> を表す式が次のように変わる。
- <math>\phi=\frac{3x^{2}_{1}+2a_{2}x_{1}+a_{4}-a_{1}y_{1}}{2y_{1}+a_{1}x_{1}+a_{3}},</math>
- <math>\psi=\frac{-x^{3}_{1}+a_{4}x_{1}+2a_{6}-a_{3}y_{1}}{2y_{1}+a_{1}x_{1}+a_{3}}.</math>
Scalar Multiplication
Scalar Multiplicationは楕円曲線上における掛け算である。
暗号化・復号の過程において、<math>Q=dP</math>（<math>P,\, Q</math> は楕円曲線上の点）という演算を行う。 ナイーヴな実装としては <math>Q = ( \cdots ( ( P+P ) + P ) + \cdots ) + P</math> というように Pを <math>(d-1)</math> 回加算（1回目は2倍算となる）するが、これでは効率が悪い。
Scalar MultiplicationはちょうどRSA暗号におけるModular Multiplication（冪剰余算）とリンクしており、これの高速化手法もそれから流用できるものが多い。例えば、そのひとつとして有名なBinary法では、dを2進数表記した場合においてdの一部分 <math>d_i</math> が "0" の場合は2倍算のみを行い、"1" の場合は2倍算+加算を行うことによりナイーブな実装と同じ計算をより高速に行なっている。この計算手法では、2倍算はModular Multiplicationにおける自乗算、加算は掛け算にそれぞれ対応している。
この演算は楕円曲線暗号の根幹を成している部分であり、楕円曲線暗号を利用する際の時間の大半を占めている。ゆえに、ICカードなどハードウェア上に演算回路を実装する場合はサイドチャネル攻撃（特にSPA、DPA）のターゲットとなる箇所なので工夫が必要となる。
解読
参考文献
- Blake, Seroussi & Smart 著、Elliptic Curves in Cryptography, CAMBRIDGE UNIVERSITY PRESS, 1999
