情報セキュリティマネジメント試験 用語辞典

だえんきょくせんあんごう
楕円曲線暗号
シラバス外
【Elliptic Curve Cryptography】
楕円曲線の点の演算を用いた公開鍵暗号方式。楕円曲線によって定義された有限可群上の離散対数問題を解く際の計算量の多さを安全性の根拠とする。同じ強度を想定した場合、RSAより鍵長を短くできる利点がある。
↓ 用語データを見る
分野:
情報セキュリティ
暗号技術
重要度:
(Wikipedia 楕円曲線暗号より)

楕円曲線暗号(だえんきょくせんあんごう、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) と ビクタ・ミラー (Victor Miller) によって独立に提案された。楕円曲線暗号は、2004〜2005年ごろから広く使用されるようになっている。

理論

暗号における楕円曲線とは、ある有限体 K 上の式

\(y^2 = x^3 + ax + b \, \)

を満たす全ての点 P=(x,y) の集合に、無限遠点と呼ばれる特別な点 O を加えたものである。ここで、 xy は有限体 K の要素である。(K の標数が2または3の場合、上式では不都合が生じるため、標数は2と3以外であるとする。)

この集合と楕円曲線上の群演算は、無限遠点を単位元とするアーベル群となる。群演算は楕円加算と呼ばれる。群構造は、代数多様体の因子群から引き継がれる。

楕円曲線上の加算

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

まず、無限遠点を \(O\) とすると、\(P_{\!A} + O = O + P_{\!A} = P_{\!A}\) である。すなわち、\(O\) が単位元である。

もし \( x_1 = x_2, y_1 = - y_2 \) ならば、\(P_{\!A} + P_{\!B} = O \) である。

それ以外の場合、\(P_{\!C} = P_{\!A} + P_{\!B}\) は、2点 \(P_{\!A},\,P_{\!B}\) を通る直線とEとの(\(P_{\!A}\) および \(P_{\!B}\) と異なる)交点の、y座標の符号を反転したものである。すなわち \(P_{\!C}\, (x_3,\, y_3)\) は以下のようになる。
\(x_{3}=\phi^{2}-x_{1}-x_{2},\)
\(y_{3}=-\phi x_{3}-\psi.\)
ただし \(\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倍した点 \(2P_{\!A} =P_{\!A}+P_{\!A}\) は、以下のように求められる。

\(y_1 = 0\) のとき、\(2P_{\!A} = O\) である。また、\(2O = O+O = O\) である。

それ以外の場合は、\(P_{\!D} = 2 P_{\!A}\) は、\(P_{\!A}\) でのEの接線がE自身と交わる(\(P_{\!A}\) とは異なる)交点の、y座標の符号を反転したものである。すなわち \(P_{\!D}\, (x_4,\, y_4)\) は以下で求められる。

\(x_{4}=\phi^{2}-2x_{1},\)
\(y_{4}=-\phi x_{4}-\psi.\)
この式は異なる二点の加算の場合と同じであるが、\(\phi,\, \psi\) の計算式が次のように変わる。
\(\phi=\frac{3x^{2}_{1}+a}{2y_{1}},\)
\(\psi=\frac{-x^{3}_{1}-a x_{1}+2y_{1}^2}{2y_{1}}.\)

スカラー倍算

スカラー倍算(Scalar Multiplication)は楕円曲線上におけるけ算である。楕円曲線上の点と点を掛けるのではなく、点に整数(スカラー)を掛けることに注意。

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

スカラー倍算はRSA暗号などにおけるべき乗剰余演算とリンクしており、これの高速化手法もそれから流用できるものが多い。例えば、そのひとつとして有名なBinary法では、dを2進数表記し、dの各ビット \(d_i\) が "0" の場合は2倍算のみを行い、"1" の場合は2倍算と加算を行うことにより、ナイーブな実装と同じ計算をより高速に行なっている。この計算手法では、2倍算はべき乗剰余演算における自乗算、加算は掛け算にそれぞれ対応している。

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

離散対数と離散対数問題

ある楕円曲線上の点 \(G\) から、\(2 G, 3 G, 4 G, \ldots \) を計算していくと、次々と異なる(楕円曲線上の)点が得られ、いずれは無限遠点 \(n G = O\) が得られる。(その後は、\((n+1)G = G, (n+2) G = 2GP, (n+3) G = 3 G, \ldots \) と繰り返される。)このように \(G\) からスカラー倍算によって得られる点の集合を \(\langle G \rangle = \{ G, 2 G, 3 G , \ldots, O \}\) と書くことにすると、\(\langle G \rangle\) は巡回群となる。巡回群の位数は \(n\) であり、\(\langle G \rangle\) を生成する元 \(G\) はベースポイントとも呼ばれる。

巡回群 \(\langle G \rangle\) の任意の要素(楕円曲線上の点)\(X\) に対し、\(X = aG\) を満たす \(a\) が \(\{0,1,\ldots , n-1\} \) の中に常にただ一つ存在する。このような \(a\) を \(X\) の離散対数と呼ぶ。また、\(\langle G \rangle\) から無作為に選らばれた \(X\) を与えられ、その離散対数を求めよという問題を、楕円曲線上の離散対数問題 と呼ぶ。

また、\(\langle G \rangle\) から無作為に選らばれた二つの点 \(X = aG, Y = bG\) を与えられ、\(abG\) を求めよという問題を、楕円曲線上のディフィー・ヘルマン問題 と呼ぶ。

最もポピュラーな離散対数問題は、\(p, g\) と \(y = g^x \bmod p\) から \(x\) を求めよ、という問題であり、\(g \isin Z_p^* (=Z/pZ)^{\times}\) から生成される乗法群の上で定義されている。これに対して、楕円曲線は加法群であるため、\(Y = aP\) を満たす \(a\) を離散対数と呼ぶという、奇妙なことになっている。

巡回群の位数 \(n\) が小さければ、離散対数問題やディフィー・ヘルマン問題が容易に解けてしまうため、位数が巨大な素数になるようなベースポイント(と楕円曲線)が使用される。

解読

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

「暗号技術」の用語

「情報セキュリティ」の他の分野

「セキュリティ」の他のカテゴリ

このページのWikipediaよりの記事は、ウィキペディアの「楕円曲線暗号」(改訂履歴)の記事を複製、再配布したものにあたり、このページ内の該当部分はクリエイティブ・コモンズ 表示 - 継承 3.0 非移植 ライセンスの下 に提供されています。


Pagetop