楕円曲線暗号

楕円曲線暗号の最新ニュースをまとめて検索！

楕円曲線暗号（だえんきょくせんあんごう,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上に位置する2点P_A,P_Bの加算は以下の通りである。但しP_Aの座標:(x_A,y_A) P_Bの座標: (x_B,y_B)とする。
P_C=P_A+P_Bの加算において点P_Cは2点P_A,P_Bを貫通する直線とP_A,P_Bでない，Eとの交点の座標について、x座標で反転したもの(すなわち、y座標の正負反転したもの)である。

[編集] 楕円曲線上での2倍算

楕円曲線E上に位置する点P_Aの2倍算は以下の通りである。
P_B=2P_Aの2倍算において点P_Bは、P_AでのEとの接線と、P_AでないEとの交点の座標について、x座標で反転したもの(すなわち、y座標の正負反転したもの)である。

[編集] Scalar Multiplication

Scalar Multiplicationは楕円曲線上における掛け算である。暗号化・復号の過程において、Q=dP(P,Qは楕円曲線上の点)という演算を行う。ナイーヴな方法ではQ=((P+P)+P)+...とPを(d-1)回加算(1回目は2倍算となる)するが、これでは効率が悪い。Scalar Multiplicationは丁度RSA暗号におけるModular Multiplication(冪剰余算)とリンクしており、dを2進数表記した場合においてdの一部分(d_iとする)が"0"の場合は2倍算のみを行い、"1"の場合は2倍算+加算を行えばよい。2倍算はModular Multiplicationにおける自乗算、加算は掛け算にそれぞれ対応している。この演算は楕円曲線暗号の根幹を成している部分である。

[編集] 解読

2009年7月8日 :ECC 112ビットの解読に成功（PS3使用） [1]

2004年4月10日 :ECC2 109ビットの解読に成功 certicom

[編集] 関連項目

• 暗号理論

この項目「楕円曲線暗号」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（P:数学／PJ:数学）