楕円曲線暗号
楕円曲線暗号（だえんきょくせんあんごう、Elliptic Curve Cryptography: ECC）とは、楕円曲線上の離散対数問題 (EC-DLP) の困難性を安全性の根拠とする暗号。1985年頃に ビクタ・ミラー (Victor Miller) とニール・コブリッツ (Neal Koblitz) が各々発明した。
具体的な暗号方式の名前ではなく、楕円曲線を利用した暗号方式の総称である。DSAを楕円曲線上で定義した楕円曲線DSA (ECDSA)、DH鍵共有を楕円化した楕円曲線ディフィー・ヘルマン鍵共有 (ECDH) などがある。公開鍵暗号が多い。
EC-DLPを解く準指数関数時間アルゴリズムがまだ見つかっていないため、それが見つかるまでの間は、RSA暗号などと比べて、同レベルの安全性をより短い鍵で実現でき、処理速度も速いことをメリットとして、ポストRSA暗号として注目されている。ただしP=NPが成立した場合、EC-DLPを多項式時間で解くアルゴリズムが存在するということになり、ECCの安全性は崩壊する（公開鍵暗号自体が崩壊）。また、送信者が暗号化時に適当な乱数（公開鍵とは違うモノ）を使うので鍵が同じでも平文と暗号文の関係が1対1でない点にも注意（ElGamal暗号でも同様）。
一部の楕円曲線には、DLPを解く多項式時間アルゴリズムが見つかっているため、注意が必要である。
歴史
暗号理論に楕円曲線を利用しようというアイディアは、1985年にニール・コブリッツ (Neal Koblitz)[1] と ビクタ・ミラー (Victor Miller)[2] によって独立に提案された。楕円曲線暗号は、2004～2005年ごろから広く使用されるようになっている。
理論
暗号における楕円曲線とは、ある有限体 K 上の式
- [math]y^2 = x^3 + ax + b \, [/math]
を満たす全ての点 P=(x,y) の集合に、無限遠点と呼ばれる特別な点 O を加えたものである。ここで、 x と y は有限体 K の要素である。（K の標数が2または3の場合、上式では不都合が生じるため、標数は2と3以外であるとする。）
この集合と楕円曲線上の群演算は、無限遠点を単位元とするアーベル群となる。群演算は楕円加算と呼ばれる。群構造は、代数多様体の因子群から引き継がれる。
楕円曲線上の加算
楕円曲線E上に位置する2点 [math]P_{\!A}\, (x_1,\, y_1),\, P_{\!B}\, (x_2,\, y_2)[/math] の加算は以下の通りである。
まず、無限遠点を [math]O[/math] とすると、[math]P_{\!A} + O = O + P_{\!A} = P_{\!A}[/math] である。すなわち、[math]O[/math] が単位元である。
もし [math] x_1 = x_2, y_1 = - y_2 [/math] ならば、[math]P_{\!A} + P_{\!B} = O [/math] である。
それ以外の場合、[math]P_{\!C} = P_{\!A} + P_{\!B}[/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}-x_{1}-x_{2},[/math]
- [math]y_{3}=-\phi x_{3}-\psi.[/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]2P_{\!A} =P_{\!A}+P_{\!A}[/math] は、以下のように求められる。
[math]y_1 = 0[/math] のとき、[math]2P_{\!A} = O[/math] である。また、[math]2O = O+O = O[/math] である。
それ以外の場合は、[math]P_{\!D} = 2 P_{\!A}[/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}-2x_{1},[/math]
- [math]y_{4}=-\phi x_{4}-\psi.[/math]
この式は異なる二点の加算の場合と同じであるが、[math]\phi,\, \psi[/math] の計算式が次のように変わる。
- [math]\phi=\frac{3x^{2}_{1}+a}{2y_{1}},[/math]
- [math]\psi=\frac{-3x^{3}_{1}-a x_{1}+2y_{1}^2}{2y_{1}}.[/math]
スカラー倍算
スカラー倍算（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倍算となる）するが、これでは効率が悪い。
スカラー倍算はRSA暗号などにおけるべき乗剰余演算とリンクしており、これの高速化手法もそれから流用できるものが多い。例えば、そのひとつとして有名なBinary法では、dを2進数表記し、dの各ビット [math]d_i[/math] が "0" の場合は2倍算のみを行い、"1" の場合は2倍算と加算を行うことにより、ナイーブな実装と同じ計算をより高速に行なっている。この計算手法では、2倍算はべき乗剰余演算における自乗算、加算は掛け算にそれぞれ対応している。
この演算は楕円曲線暗号の根幹を成している部分であり、楕円曲線暗号を利用する際の時間の大半を占めている。ゆえに、ICカードなどハードウェア上に演算回路を実装する場合はサイドチャネル攻撃（特にSPA、DPA）のターゲットとなる箇所なので工夫が必要となる。
離散対数と離散対数問題
ある楕円曲線上の点 [math]G[/math] から、[math]2 G, 3 G, 4 G, \ldots [/math] を計算していくと、次々と異なる（楕円曲線上の）点が得られ、いずれは無限遠点 [math]n G = O[/math] が得られる。（その後は、[math](n+1)G = G, (n+2) G = 2GP, (n+3) G = 3 G, \ldots [/math] と繰り返される。）このように [math]G[/math] からスカラー倍算によって得られる点の集合を [math]\langle G \rangle = \{ G, 2 G, 3 G , \ldots, O \}[/math] と書くことにすると、[math]\langle G \rangle[/math] は巡回群となる。巡回群の位数は [math]n[/math] であり、[math]\langle G \rangle[/math] を生成する元 [math]G[/math] はベースポイントとも呼ばれる。
巡回群 [math]\langle G \rangle[/math] の任意の要素（楕円曲線上の点）[math]X[/math] に対し、[math]X = aG[/math] を満たす [math]a[/math] が [math]\{0,1,\ldots , n-1\} [/math] の中に常にただ一つ存在する。このような [math]a[/math] を [math]X[/math] の離散対数と呼ぶ。また、[math]\langle G \rangle[/math] から無作為に選らばれた [math]X[/math] を与えられ、その離散対数を求めよという問題を、楕円曲線上の離散対数問題 と呼ぶ。
また、[math]\langle G \rangle[/math] から無作為に選らばれた二つの点 [math]X = aG, Y = bG[/math] を与えられ、[math]abG[/math] を求めよという問題を、楕円曲線上のディフィー・ヘルマン問題 と呼ぶ。
最もポピュラーな離散対数問題は、[math]p, g[/math] と [math]y = g^x \bmod p[/math] から [math]x[/math] を求めよ、という問題であり、[math]g \isin Z_p^* (=Z/pZ)^{\times}[/math] から生成される乗法群の上で定義されている。これに対して、楕円曲線は加法群であるため、[math]Y = aP[/math] を満たす [math]a[/math] を離散対数と呼ぶという、奇妙なことになっている。
巡回群の位数 [math]n[/math] が小さければ、離散対数問題やディフィー・ヘルマン問題が容易に解けてしまうため、位数が巨大な素数になるようなベースポイント（と楕円曲線）が使用される。
解読
参考文献
- Blake, Seroussi & Smart 著、Elliptic Curves in Cryptography, CAMBRIDGE UNIVERSITY PRESS, 1999
関連項目
脚注
- ↑ Koblitz, N. (1987). “Elliptic curve cryptosystems”. Mathematics of Computation 48 (177): 203?209. doi:10.2307/2007884. JSTOR 2007884.
- ↑ Miller, V. (1985). “Use of elliptic curves in cryptography”. CRYPTO. Lecture Notes in Computer Science 85: 417?426. doi:10.1007/3-540-39799-X_31. ISBN 978-3-540-16463-0.