楕円曲線暗号

楕円曲線暗号（だえんきょくせんあんごう、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年にニール・コブリッツ () と ビクター・S・ミラー () によって独立に提案された。楕円曲線暗号は、2004～2005年ごろから広く使用されるようになっている。
理論.
暗号における楕円曲線とは、ある有限体 K 上の式
を満たす全ての点 "P=(x,y)" の集合に、無限遠点と呼ばれる特別な点 "O" を加えたものである。ここで、 "x" と "y" は有限体 K の要素である。（K の標数が2または3の場合、上式では不都合が生じるため、ここでは標数は2と3以外であるとする。一般には、もう少し複雑な式と議論が必要になる。）
この集合と楕円曲線上の群演算は、無限遠点を単位元とするアーベル群となる。群演算は楕円加算と呼ばれる。群構造は、代数多様体の因子群から引き継がれる。
楕円曲線上の加算.
楕円曲線E上に位置する2点 formula_2 の加算は以下の通りである。
まず、無限遠点を formula_3 とすると、formula_4 である。すなわち、formula_3 が単位元である。
もし formula_6 ならば、formula_7 である。
それ以外の場合、formula_8 は、2点 formula_9 を通る直線とEとの（formula_10 および formula_11 と異なる）交点の、y座標の符号を反転したものである。すなわち formula_12 は以下のようになる。
ただし formula_15 は
楕円曲線上での2倍算.
楕円曲線E上の点 formula_18 に対し、これを2倍した点 formula_19 は、以下のように求められる。
formula_20 のとき、formula_21 である。また、formula_22 である。
それ以外の場合は、formula_23 は、formula_10 でのEの接線がE自身と交わる（formula_10 とは異なる）交点の、y座標の符号を反転したものである。すなわち formula_26 は以下で求められる。
この式は異なる二点の加算の場合と同じであるが、formula_15 の計算式が次のように変わる。
スカラー倍算.
スカラー倍算（Scalar Multiplication）は楕円曲線上における掛け算である。楕円曲線上の点と点を掛けるのではなく、点に整数（スカラー）を掛けることに注意。
暗号化・復号の過程において、formula_32（formula_33 は楕円曲線上の点）という演算を行う。
ナイーヴな実装としては formula_34 というように Pを formula_35 回加算（1回目は2倍算となる）するが、これでは効率が悪い。
スカラー倍算はRSA暗号などにおけるべき乗剰余演算とリンクしており、これの高速化手法もそれから流用できるものが多い。例えば、そのひとつとして有名なBinary法では、dを2進数表記し、dの各ビット formula_36 が "0" の場合は2倍算のみを行い、"1" の場合は2倍算と加算を行うことにより、ナイーブな実装と同じ計算をより高速に行なっている。この計算手法では、2倍算はべき乗剰余演算における自乗算、加算は掛け算にそれぞれ対応している。
この演算は楕円曲線暗号の根幹を成している部分であり、楕円曲線暗号を利用する際の時間の大半を占めている。ゆえに、ICカードなどハードウェア上に演算回路を実装する場合はサイドチャネル攻撃（特にSPA、DPA）のターゲットとなる箇所なので工夫が必要となる。
離散対数と離散対数問題.
ある楕円曲線上の点 formula_37 から、formula_38 を計算していくと、次々と異なる（楕円曲線上の）点が得られ、いずれは無限遠点 formula_39 が得られる（ただし楕円曲線によってはそのようなGはG=Oしか無い事もある）。（その後は、formula_40 と繰り返される。）このように formula_37 からスカラー倍算によって得られる点の集合を formula_42 と書くことにすると、formula_43 は巡回群となる。巡回群の位数は formula_44 であり、formula_43 を生成する元 formula_37 はベースポイントとも呼ばれる。
巡回群 formula_43 の任意の要素（楕円曲線上の点）formula_48 に対し、formula_49 を満たす formula_50 が formula_51 の中に常にただ一つ存在する。このような formula_50 を formula_48 の離散対数と呼ぶ。また、formula_43 から無作為に選らばれた formula_48 を与えられ、その離散対数を求めよという問題を、楕円曲線上の離散対数問題 と呼ぶ。
また、formula_43 から無作為に選ばれた二つの点 formula_57 を与えられ、formula_58 を求めよという問題を、楕円曲線上のディフィー・ヘルマン問題 と呼ぶ。
最もポピュラーな離散対数問題は、formula_59 と formula_60 から formula_61 を求めよ、という問題であり、formula_62 から生成される乗法群の上で定義されている。これに対して、楕円曲線は加法群であるため、formula_63 を満たす formula_50 を離散対数と呼ぶ。
巡回群の位数 formula_44 が小さければ、離散対数問題やディフィー・ヘルマン問題が容易に解けてしまうため、位数が巨大な素数になるようなベースポイント（と楕円曲線）が使用される。
攻撃手法.
サイドチャネル攻撃.
楕円曲線上で楕円加算 "P + Q " を行う場合、加算("P" ≠ "Q")と2倍算("P" = "Q")では演算プロセスが大きく異なる。そのため、サイドチャネル攻撃（例えば、タイミング攻撃や単純電力解析/差分電力解析）への対策（例えば など）が必要である。あるいは、を使うこともできる。この曲線は、加算と2倍算を同じ演算プロセスで実行できる特別な楕円曲線の族である。
量子コンピュータを用いた攻撃.
離散対数問題を効率的に解くことのできるショアのアルゴリズムは、楕円曲線暗号の解読にも利用できる。256ビットの法を持つ楕円曲線暗号（128ビット安全）を破るためには、2330量子ビット、1,260億トフォリゲートのリソースを持つ量子コンピュータが必要であると見積もられている。
一方、アメリカ国立標準技術研究所の勧告（NIST SP 800-57）によりこれと同等のセキュリティレベルとされる3072ビット鍵のRSA暗号を破るためには、6146量子ビット、18.6兆トフォリゲートが必要であり、いずれにせよ、これらのリソースは現在実存する量子コンピュータのリソースをはるかに超えており、このようなコンピュータの構築は10年以上先になると見られている。
同種写像暗号は、楕円曲線の同種写像を用いた暗号方式であり、量子コンピュータに対して耐性がある（耐量子）と考えられている。同種写像暗号の例としてディフィー・ヘルマン鍵共有と同様に鍵共有を行うSIDHがある。従来の楕円曲線暗号と同じ体の演算を多く使用し、必要な計算量や通信量は現在使用されている多くの公開鍵システムと同程度である。