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

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

EC-DLPを解く準指数関数時間アルゴリズムがまだ見つかっていないため、それが見つかるまでの間は、RSA暗号などと比べて、同レベルの安全性をより短い鍵で実現でき、処理速度も速いことをメリットとして、ポストRSA暗号として注目されている。ただしP=NPが成立した場合、EC-DLPを多項式時間で解くアルゴリズムが存在するということになり、ECCの安全性は崩壊する（公開鍵暗号自体が崩壊）。また、送信者が暗号化時に適当な乱数（公開鍵とは違うモノ）を使うので鍵が同じでも平文と暗号文の関係が1対1でない点にも注意（ElGamal暗号でも同様）。

一部の楕円曲線には、DLPを解く多項式時間アルゴリズムが見つかっているため、注意が必要である。
歴史[ソースを編集]

暗号理論に楕円曲線を利用しようというアイディアは、1985年にニール・コブリッツ[1] と ビクター・S・ミラー[2] によって独立に提案された。楕円曲線暗号は、2004?2005年ごろから広く使用されるようになっている。
理論[ソースを編集]楕円曲線の例： secp256k1(後述)で規定されている R 2 {\displaystyle \mathbb {R} ^{2}} 上の y 2 = x 3 + 7 {\displaystyle y^{2}=x^{3}+7} のグラフ。

実平面 R 2 {\displaystyle \mathbb {R} ^{2}} 上の点を P ( x , y ) {\displaystyle P(x,y)} で表した場合、 R 2 {\displaystyle \mathbb {R} ^{2}} 上で定義される楕円曲線 E : y 2 = x 3 + a x + b {\displaystyle E:y^{2}=x^{3}+ax+b} (ワイエルシュトラスの標準形)では、 E {\displaystyle E} 上の点に接弦法(またはバシェ(Bachet)の方法)[3]と呼ばれる加法的な2項演算により加群の構造を与えることができる(零元は通常は無限遠点と定義される。これを O {\displaystyle O} で表す)。

楕円曲線暗号で扱う楕円曲線とは、 E {\displaystyle E} 上の有理点を、ある素数 p {\displaystyle p} で還元した有限体 F p {\displaystyle \mathbf {F} _{p}} 上の離散的楕円曲線であり、還元によって上記の加群の構造は E ( F p ) {\displaystyle E(\mathbf {F} _{p})} 上の加群構造に写される。
楕円曲線上の加法[ソースを編集]

楕円曲線 E {\displaystyle E} 上の異なる2点を P 1 ( x 1 , y 1 ) , P 2 ( x 2 , y 2 ) {\displaystyle P_{1}\,(x_{1},\,y_{1}),\,P_{2}\,(x_{2},\,y_{2})} とする場合、その接弦法の加法を P 1 + P 2 {\displaystyle P_{1}+P_{2}} で表すことにすると、 P 3 ( x 3 , y 3 ) = P 1 + P 2 {\displaystyle P_{3}\,(x_{3},y_{3})=P_{1}+P_{2}} は次の式で計算される[4]。

まず、 P 1 + O = O + P 1 = P 1 {\displaystyle P_{1}+O=O+P_{1}=P_{1}} である。すなわち、無限遠点 O {\displaystyle O} が零元である。

もし x 1 = x 2 , y 1 = − y 2 {\displaystyle x_{1}=x_{2},y_{1}=-y_{2}} ならば、 P 1 + P 2 = O {\displaystyle P_{1}+P_{2}=O} である。