楕円曲線暗号

楕円曲線暗号（だえんきょくせんあんごう、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(後述)で規定されている ${\displaystyle \mathbb {R} ^{2}}$ 上の ${\displaystyle y^{2}=x^{3}+7}$ のグラフ。

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

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

楕円曲線上の加法

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

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

もし ${\displaystyle x_{1}=x_{2},y_{1}=-y_{2}}$ ならば、${\displaystyle P_{1}+P_{2}=O}$ である。このとき ${\displaystyle P_{2}}$ を ${\displaystyle -P_{1}}$ と書き、 ${\displaystyle P_{1}}$ の逆元と呼ぶことにする。

それ以外の場合、${\displaystyle P_{1}+P_{2}}$ は、2点 ${\displaystyle P_{1},\,P_{2}}$ を通る直線と ${\displaystyle E}$ との（${\displaystyle P_{1}}$ および ${\displaystyle P_{2}}$ と異なる）交点の、y座標の符号を反転したものである。つまり ${\displaystyle P_{3}\,(x_{3},y_{3})=P_{1}+P_{2}}$ と置けば、次のように計算される。 $${\displaystyle x_{3}=\phi ^{2}-x_{1}-x_{2},}$$ $${\displaystyle y_{3}=-\phi x_{3}-\psi .}$$ ただし ${\displaystyle \phi ,\,\psi }$ は $${\displaystyle \phi ={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}},}$$ $${\displaystyle \psi ={\frac {y_{1}x_{2}-y_{2}x_{1}}{x_{2}-x_{1}}}.}$$

上の方法で定義された2項演算は加法として必要な次の性質を備えている。

• 零元 ${\displaystyle O}$ の存在
• 各元${\displaystyle P_{1}}$に対する逆元${\displaystyle -P_{1}}$の存在
• 可換性： ${\displaystyle P_{1}+P_{2}=P_{2}+P_{1}}$ (定義式の対称性から明らか)
• 結合性： ${\displaystyle (P_{1}+P_{2})+P_{3}=P_{1}+(P_{2}+P_{3})}$ (煩雑であるが定義式を丁寧に解けば証明できる)

楕円曲線上での2倍算

楕円曲線${\displaystyle E}$上の点 ${\displaystyle P_{1}\,(x_{1},\,y_{1})}$ に対し、さらに${\displaystyle P_{1}}$ を加算する場合、つまり ${\displaystyle P_{1}+P_{1}=2P_{1}}$ を求める場合、上記の方法は使えない。

この場合、まず ${\displaystyle y_{1}=0}$ のときは、${\displaystyle 2P_{1}=O}$ である。また、${\displaystyle 2O=O+O=O}$ である。

それ以外の場合は、${\displaystyle 2P_{1}}$ は、${\displaystyle P_{1}}$ での ${\displaystyle E}$ の接線が ${\displaystyle E}$ 自身と交わる（${\displaystyle P_{1}}$ とは異なる）交点の、${\displaystyle y}$座標の符号を反転したものである。すなわち ${\displaystyle P_{4}\,(x_{4},\,y_{4})=2P_{1}}$ と置けば、次のように計算される。 $${\displaystyle x_{4}=\phi ^{2}-2x_{1},}$$ $${\displaystyle y_{4}=-\phi x_{4}-\psi .}$$ この式は異なる二点の加算の場合と同じであるが、${\displaystyle \phi ,\,\psi }$ の計算式が次のように変わる。 $${\displaystyle \phi ={\frac {3x_{1}^{2}+\alpha }{2y_{1}}},}$$ $${\displaystyle \psi ={\frac {-3x_{1}^{3}-\alpha x_{1}+2y_{1}^{2}}{2y_{1}}}.}$$

スカラー倍算

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

${\displaystyle E}$上のある点 ${\displaystyle P_{1}}$を始点として、これに順次 ${\displaystyle P_{1}}$ 自身を ${\displaystyle n-1}$ 回加算して得られる点を ${\displaystyle nP_{1}}$で表すことにする。この操作は ${\displaystyle O}$ に ${\displaystyle P_{1}}$ を ${\displaystyle n}$ 回加算することと同じである。${\displaystyle O}$ に ${\displaystyle -P_{1}}$ を ${\displaystyle n}$ 回加算すれば${\displaystyle -nP_{1}}$が得られる。 このようにして、${\displaystyle E}$上の点と整数の掛け算が定義できる。この操作をスカラー倍算（Scalar Multiplication）と呼ぶことにする。

${\displaystyle P_{1}}$を始点として、加法により生成される点列(つまり全ての整数についての${\displaystyle P_{1}}$のスカラー倍算の集合)は、${\displaystyle E}$ 上の巡回群を作っている(これを ${\displaystyle \langle P_{1}\rangle }$と表すことにする)。

楕円曲線上の有理点

楕円曲線のパラメーター ${\displaystyle \alpha ,\,\beta }$ が有理数の場合、2つの有理点(${\displaystyle x,y}$ が共に有理数の点)を加算して得られる点はやはり有理点である。つまり、${\displaystyle E}$ 上の全ての有理点の集合＋無限遠点 ${\displaystyle O}$ を ${\displaystyle E(\mathbb {Q} )}$ と表すと、${\displaystyle E(\mathbb {Q} )}$ は加法について ${\displaystyle E}$ の部分加群を成している。また、${\displaystyle E(\mathbb {Q} )}$ 上のある有理点を始点として加法により生成される ${\displaystyle E(\mathbb {Q} )}$ 上の点列は、${\displaystyle E(\mathbb {Q} )}$ 上の全ての点が成す加群の部分加群(巡回群)を成している。さらに始点が整点(${\displaystyle x,y}$ が共に整数の点)でない場合、この巡回群の位数は無限大である(Nagell-Lutzの定理^[5])。

また、${\displaystyle E(\mathbb {Q} )}$ 全体が成す加群は、有限個の始点が生成する巡回群の直和になることが知られている(モーデルの定理)。

素数 p による還元

楕円曲線暗号で扱う楕円曲線とは、${\displaystyle E(\mathbb {Q} )}$ をある素数 ${\displaystyle p}$ で還元した有限体 ${\displaystyle \mathbf {F} _{p}}$ 上の離散的楕円曲線であり、これを ${\displaystyle E(\mathbf {F} _{p})}$ と表すことにする(無限遠点 ${\displaystyle O}$ も含む。誤解の恐れがないので無限遠点は ${\displaystyle E}$ または ${\displaystyle E(\mathbb {Q} )}$ のものと同じ記号を使うことにする。)。ここで素数 ${\displaystyle p}$ による還元とは、${\displaystyle E(\mathbb {Q} )}$ に、次の ${\displaystyle \mathbb {Q} ^{2}}$ から ${\displaystyle {\mathbf {F} _{p}}^{2}}$ への写像 ${\displaystyle {\tilde {f}}_{p}}$ を作用させることであるとする^[6]。

まず、有理数体 ${\displaystyle \mathbb {Q} }$ から有限体 ${\displaystyle \mathbf {F} _{p}}$ 上への写像 ${\displaystyle f_{p}}$ を、次のように定義する。 有理数を ${\displaystyle u/v}$ (uは整数、vは自然数)と表した場合、 $${\displaystyle f_{p}(u/v)=(u{\bmod {\,}}p)(v{\bmod {\,}}p)^{-1}{\bmod {\,}}p}$$ ただし、${\displaystyle (v{\bmod {\,}}p)^{-1}}$ は ${\displaystyle \mathbf {F} _{p}}$ の元 ${\displaystyle v{\bmod {\,}}p}$ の ${\displaystyle \mathbf {F} _{p}}$ における逆元とする。

${\displaystyle f_{p}}$ は有理数体 ${\displaystyle \mathbb {Q} }$ から 有限体 ${\displaystyle \mathbf {F} _{p}}$ への体準同型写像であり、 ${\displaystyle \mathbb {Q} }$ 上の加法、乗法、逆元は ${\displaystyle \mathbf {F} _{p}}$ 上の加法、乗法、逆元に写される。例えば ${\displaystyle \mathbb {Q} }$ における除算は、${\displaystyle \mathbf {F} _{p}}$ では逆元を乗ずる操作に写される。

${\displaystyle {\tilde {f}}_{p}}$ を次のように定義する。

• ${\displaystyle {\tilde {f}}_{p}(O)=O}$
• ${\displaystyle {\tilde {f}}_{p}(x,y)=(f_{p}(x),f_{p}(y))}$

${\displaystyle {\tilde {f}}_{p}}$ は ${\displaystyle f_{p}}$ の性質から、${\displaystyle E(\mathbb {Q} )}$ 上の接弦法による加法を ${\displaystyle E(\mathbf {F} _{p})}$ 上の加法に矛盾なく写す。つまり${\displaystyle {\tilde {f}}_{p}}$ は楕円曲線上の加法に関する準同型写像を成している。

離散的楕円曲線の例： 有限体 F₆₁ 上の楕円曲線 y² = x³ − x

${\displaystyle \mathbb {Q} }$ 上で定義された楕円曲線 ${\displaystyle E(\mathbb {Q} ):y^{2}=x^{3}+\alpha x+\beta }$ (${\displaystyle \alpha ,\beta }$ は有理数) を素数 ${\displaystyle p}$ で還元した離散的楕円曲線 ${\displaystyle E(\mathbf {F} _{p})}$ は ${\displaystyle \mathbf {F} _{p}}$ 上では次の式で定義される。

${\displaystyle E(\mathbb {\mathbf {F} _{p}} ):y^{2}=x^{3}+ax+b\,\,({\bmod {\,}}p)}$

ただし、${\displaystyle x,y}$ は ${\displaystyle \mathbf {F} _{p}}$ の元であり、${\displaystyle a=f_{p}(\alpha ),\,b=f_{p}(\beta )}$ とする。このようにして定義された離散的楕円曲線は、グラフにすれば最早曲線ではなく、離散した点の集まりにしか見えない(ただし分布は直線 ${\displaystyle y=0}$ に対して対称である)。

上述の${\displaystyle E}$における接弦法の加法の計算式は、${\displaystyle E(\mathbb {\mathbf {F} _{p}} )}$では${\displaystyle x_{2}-x_{1}}$ または ${\displaystyle 2y_{1}}$ による除法が、 ${\displaystyle \mathbf {F} _{p}}$ における逆元 ${\displaystyle (x_{2}-x_{1})^{-1}}$ または ${\displaystyle (2y_{1})^{-1}}$ による乗法に置き換えられ、全体としては次のように書き換えられる。

${\displaystyle P_{1}\,(x_{1},y_{1}),\,P_{2}\,(x_{2},y_{2})}$ を${\displaystyle E(\mathbb {\mathbf {F} _{p}} )}$上の任意の2点とする。${\displaystyle x_{1}=x_{2},y_{1}=-y_{2}}$ の場合、${\displaystyle P_{1}+P_{2}=O}$。

それ以外の場合、${\displaystyle P_{3}\,(x_{3},y_{3})=P_{1}+P_{2}}$ と置けば、 $${\displaystyle x_{3}=\phi ^{2}-x_{1}-x_{2}\,({\bmod {\,}}p)}$$ $${\displaystyle y_{3}=-\phi x_{3}-\psi \,({\bmod {\,}}p)}$$

ただし ${\displaystyle \phi ,\,\psi }$ は ${\displaystyle P_{1}\neq P_{2}}$ の場合、 $${\displaystyle \phi =(y_{2}-y_{1})(x_{2}-x_{1})^{-1}\,({\bmod {\,}}p)}$$ $${\displaystyle \psi =(y_{1}x_{2}-y_{2}x_{1})(x_{2}-x_{1})^{-1}\,({\bmod {\,}}p)}$$

${\displaystyle P_{1}=P_{2}}$ の場合、 $${\displaystyle \phi =(3x_{1}^{2}+a)(2y_{1})^{-1}\,({\bmod {\,}}p)}$$ $${\displaystyle \psi =(-3x_{1}^{3}-ax_{1}+2y_{1}^{2})(2y_{1})^{-1}\,({\bmod {\,}}p)}$$

上記の式で、${\displaystyle \mathbf {F} _{p}}$ の任意の元 ${\displaystyle v}$ の ${\displaystyle \mathbf {F} _{p}}$ における逆元 ${\displaystyle v^{-1}}$ は、フェルマーの小定理から ${\displaystyle v^{p-1}\equiv 1\,({\bmod {\,}}p)}$ であるから、${\displaystyle v^{-1}=(v^{p-2}\,{\bmod {\,}}p)}$ によって計算できる。

なお、前述のように、${\displaystyle \mathbb {Q} }$ 上においては、始点が整点でない巡回加群の位数は無限大であるが、楕円曲線 ${\displaystyle E(\mathbb {Q} )}$ の ${\displaystyle {\tilde {f}}_{p}}$ による像である ${\displaystyle \mathbf {F} _{p}}$ 上の楕円曲線 ${\displaystyle E(\mathbf {F} _{p})}$ は有限集合であり、当然位数も有限となる。

補足：上記の方法を拡張して、有限体 ${\displaystyle \mathbf {F} _{p}}$ の ${\displaystyle m}$次拡大体 ${\displaystyle \mathbf {F} _{p^{m}}}$ 上での楕円曲線 ${\displaystyle E(\mathbf {F} _{p^{m}})}$ を用いる暗号法も考案されており、実用的な仕様も公開されているが、話が煩雑になるので立ち入らないことにする。

ベースポイントと巡回群の位数

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

${\displaystyle E(\mathbf {F} _{p})}$ 上の全ての点の個数を ${\displaystyle \sharp E(\mathbf {F} _{p})}$ とすれば、これは高々 ${\displaystyle 2p+1}$ 個(無限遠点 ${\displaystyle O}$ を含む)であり、位数 ${\displaystyle n}$ はこれより小さくなるが^[7]、楕円曲線のパラメーター ${\displaystyle a,b,p}$に依存し、実際の値はSchoofのアルゴリズムまたはその改良版などを用いて計算しないと分からない( ${\displaystyle \sharp E(\mathbf {F} _{p})}$ の値の範囲については、ハッセの定理という手掛かりがある)。${\displaystyle n}$ が素数の場合、巡回群 ${\displaystyle \langle G\rangle }$ の全ての元は ${\displaystyle \langle G\rangle }$ の生成元であり、それらの位数は全て ${\displaystyle n}$ になる。

${\displaystyle h={\frac {1}{n}}\sharp E(\mathbf {F} _{p})}$ で定義される値 ${\displaystyle h}$ はコファクターと呼ばれるが、この値は 1 に近いことが望ましい。 ${\displaystyle a,b,p,G}$ の取り方によっては、${\displaystyle h=1}$ とすることが可能である(後述の secp256k1 では ${\displaystyle h=1}$ である)。${\displaystyle h=1}$ の場合、${\displaystyle E(\mathbf {F} _{p})}$ 上の点は、ほぼ全て ${\displaystyle \langle G\rangle }$ の元であるので、ベースポイントを見つけることは容易になる。モーデルの定理が示唆するように ${\displaystyle h=1}$ 以外の場合も可能であり、${\displaystyle h=2}$ となる実用的楕円曲線の仕様もある。

楕円曲線暗号においては、巡回群の位数 ${\displaystyle n}$ が小さければ、次に説明する離散対数問題やディフィー・ヘルマン問題が比較的容易に解けてしまうため、セキュリティ強度(後述)を強くするためには、${\displaystyle n}$ がなるべく大きな素数となるように、パラメーター ${\displaystyle a,b,p,G}$ を決定する必要がある。これは、多数のパラメーターの候補について、Schoofのアルゴリズムまたはその改良版などを用いて実際に ${\displaystyle n}$ を計算するという試行錯誤により行われる^[8]。

楕円曲線のパラメーターの一例として、ビットコインで使われている楕円曲線暗号である secp256k1 のものを示す^[9]。

${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1}$
${\displaystyle \,}$ = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
${\displaystyle E:\,y^{2}=x^{3}+7}$
${\displaystyle G=(G_{x},G_{y})}$
${\displaystyle G_{x}}$ = 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
${\displaystyle G_{y}}$ = 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
${\displaystyle n}$ = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
${\displaystyle h}$ = 1

離散対数と離散対数問題

巡回群 ${\displaystyle \langle G\rangle }$ の任意の要素（楕円曲線上の点）${\displaystyle Q}$ に対し、${\displaystyle Q=dG}$ を満たす ${\displaystyle d}$ が ${\displaystyle \{0,1,\ldots ,n-1\}}$ の中に常にただ一つ存在する。このような ${\displaystyle d}$ を ${\displaystyle Q}$ の離散対数と呼ぶ。また、${\displaystyle \langle G\rangle }$ から無作為に選ばれた ${\displaystyle Q}$ を与えられ、その離散対数を求めよという問題を、楕円曲線上の離散対数問題 と呼ぶ^{[注 1]}。${\displaystyle d}$ と ${\displaystyle Q}$ の対応は1対1であり、${\displaystyle d}$ から ${\displaystyle Q}$ を計算することは比較的容易だが、${\displaystyle Q}$ から ${\displaystyle d}$ を計算することは実質的に不可能である。つまり ${\displaystyle d}$ と ${\displaystyle Q}$ の対応は一方向性関数になっている。この性質を利用して、${\displaystyle d}$ を秘密鍵とし、${\displaystyle Q}$ を公開鍵としたデジタル署名アルゴリズムが実用化されている(楕円曲線DSA (ECDSA))。

これの応用問題として、2者 A、B がそれぞれ秘密鍵 ${\displaystyle d_{A},\,d_{B}}$ を保持し、これから生成された公開鍵 ${\displaystyle Q_{A},\,Q_{B}}$ (${\displaystyle Q_{A}=d_{A}G,Q_{B}=d_{B}G}$) をそれぞれ公開しており、A、B は互いに相手の秘密鍵の値は知らない場合を考える。A は、公開されている ${\displaystyle Q_{B}}$ に自分が保持している ${\displaystyle d_{A}}$ をスカラー倍すれば ${\displaystyle Q_{AB}=d_{A}d_{B}G}$ の値を得られるし、B は同様に、${\displaystyle Q_{A}}$ に ${\displaystyle d_{B}}$ をスカラー倍すれば ${\displaystyle Q_{AB}=d_{A}d_{B}G}$ の値を得られる。では ${\displaystyle d_{A},\,d_{B}}$ の両方の値を知らない第三者 C は ${\displaystyle Q_{A}}$ および ${\displaystyle Q_{B}}$ の値のみから ${\displaystyle Q_{AB}=d_{A}d_{B}G}$ の値を得る方法はあるかというのが 楕円曲線上のディフィー・ヘルマン問題 と呼ばれる問題である。現在のところ解法としては、${\displaystyle Q_{A}=d_{A}G}$ または ${\displaystyle Q_{B}=d_{B}G}$ についての離散対数問題を解く以外の方法は知られておらず、この問題を一方向性関数として使用することが可能である。つまり ${\displaystyle Q_{AB}=d_{A}d_{B}G}$ を A、B のみが知る共通鍵として使用可能である(ディフィー・ヘルマン鍵共有)。

スカラー倍算の効率化

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

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

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

安全性と攻撃手法

離散対数問題のセキュリティ強度

セキュリティ強度（英語版）(セキュリティ・レベル)は暗号の破られにくさを表す1つの指標(単位はビット)であり、セキュリティ強度が ${\displaystyle l}$ (ビット)であるとは、攻撃者が暗号から鍵(あるいは平文)を解読するために必要な単位操作の回数が ${\displaystyle 2^{l}}$ 回程度であることを表している^[10] 。例えば 共通鍵暗号である AES-128 (鍵長 128 ビット) は、攻撃者が必要な単位操作の回数が ${\displaystyle 2^{128}}$ 回になるように設計されている(つまり、全ての鍵について総当たり攻撃(Brute-force attack)を行わないと解読できないように設計されている。この場合はセキュリティ強度＝鍵長となる)。一方、RSA暗号の場合、これと同等のセキュリティ強度を得るには約 3072 ビットの鍵長が必要になる(つまり何らかの冗長性を利用して、攻撃者は必要な単位操作の回数を節約することが可能なことを意味している)^[11]。

離散対数問題は、残念ながら総当たり攻撃によらなくても解読できることが分かっている。例えば、ポラード・ロー離散対数アルゴリズムを用いて離散対数を計算するのに必要な単位操作回数(この場合は楕円加算回数)はおよそ ${\displaystyle {\sqrt {n\pi /4}}}$ 回である^[12]。従って、離散対数問題(およびそれと同等なディフィー・ヘルマン問題)のセキュリティ強度 ${\displaystyle l}$ は、鍵長を ${\displaystyle m=\log _{2}n}$ とした場合、${\displaystyle l=\log _{2}{\sqrt {n\pi /4}}={\frac {1}{2}}(\log _{2}n+\log _{2}(\pi /4))}$ であるから、概略 ${\displaystyle l={\frac {1}{2}}\log _{2}n={\frac {m}{2}}}$ となる。つまり鍵長 256 ビットの楕円曲線暗号(secp256k1 など) は、鍵長 128 ビットのAESと同程度のセキュリティ強度を有するということになる。この ${\displaystyle l={\frac {m}{2}}}$ という離散対数問題のセキュリティ強度の特性は、ワイエルシュトラスの標準形ではないエドワーズ曲線などの楕円曲線(Curve448、Curve25519など)を用いた場合も同様である。

アメリカ国立標準技術研究所(NIST)は、セキュリティ強度が 112 ビットの暗号は、2030年まで社会的な用途で使用を許容されるが、2031年以降はセキュリティ強度が 128 ビット以上の暗号のみが許容可能であると勧告している^[13]。

サイドチャネル攻撃

楕円曲線上で楕円加算 P + Q を行う場合、加算(P ≠ Q)と2倍算(P = Q)では演算プロセスが大きく異なる。そのため、サイドチャネル攻撃（例えば、タイミング攻撃や単純電力解析/差分電力解析）への対策（例えば ^[14] など）が必要である。あるいは、ツイステッドエドワーズ曲線（英語版）を使うこともできる。この曲線は、加算と2倍算を同じ演算プロセスで実行できる特別な楕円曲線の族である。^[15]

量子コンピュータを用いた攻撃

離散対数問題を効率的に解くことのできるショアのアルゴリズムは、楕円曲線暗号の解読にも利用できる。256ビットの法を持つ楕円曲線暗号（128ビット安全）を破るためには、2330量子ビット、1,260億トフォリゲートのリソースを持つ量子コンピュータが必要であると見積もられている。^[16] 一方、アメリカ国立標準技術研究所の勧告（NIST SP 800-57）によりこれと同等のセキュリティレベルとされる3072ビット鍵のRSA暗号を破るためには、6146量子ビット、18.6兆トフォリゲートが必要であり^[16]、量子コンピュータにとっては、RSA暗号に比べ楕円曲線暗号は攻撃しやすいといえる。^{[独自研究?]}いずれにせよ、これらのリソースは現在実存する量子コンピュータのリソースをはるかに超えており、このようなコンピュータの構築は10年以上先になると見られている^[要出典]。

同種写像暗号は、楕円曲線の同種写像を用いた暗号方式であり、量子コンピュータに対して耐性がある（耐量子）と考えられている。同種写像暗号の例としてディフィー・ヘルマン鍵共有と同様に鍵共有を行うSIDHがある。従来の楕円曲線暗号と同じ体の演算を多く使用し、必要な計算量や通信量は現在使用されている多くの公開鍵システムと同程度である。 ^[17]

注釈

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

解読

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

脚注

1. Koblitz, N. (1987). “Elliptic curve cryptosystems”. Mathematics of Computation 48 (177): 203?209. doi:10.2307/2007884. JSTOR 2007884.
2. 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.
3. 足立恒雄『フェルマーの大定理 [第3版]』日本評論社、1996年5月、164-167頁。ISBN 4-535-78231-8。
4. J.Song『プログラミング・ビットコイン ゼロからビットコインをプログラムする方法』中川卓俊、住田和則、中村昭雄 監訳 星野靖子 訳、オライリー・ジャパン (オーム社)、2020年10月、36-40頁。ISBN 978-4-87311-902-1。
5. J.H.シルヴァーマン、J.テイト『楕円曲線論入門』足立恒雄ほか 訳、丸善出版、2012年7月、61頁。ISBN 978-4-621-06571-6。
6. コブリッツ 1997, pp. 246, 272.
7. コブリッツ 1997, p. 246.
8. コブリッツ 1997, pp. 253–261.
9. S.Chandrashekar & N.Ramani (27 January 2010). SEC 2：Recommended Elliptic Curve Domain Parameters (Version 2.0) (PDF) (Report). Standards for Efficient Cryptography Group (SECG). p. 13. 2024年5月30日閲覧。
10. Barker, Elaine (May 2020). Recommendation for Key Management, Part 1: General (PDF) (Report). NIST. p. 17. CiteSeerX 10.1.1.106.307. doi:10.6028/nist.sp.800-57pt1r5。
11. Barker, Elaine (May 2020). Recommendation for Key Management, Part 1: General (PDF) (Report). NIST. p. 55. CiteSeerX 10.1.1.106.307. doi:10.6028/nist.sp.800-57pt1r5。
12. Daniel J. Bernstein; Tanja Lange; Peter Schwabe (1 January 2011). On the correct use of the negation map in the Pollard rho method (Technical report). IACR Cryptology ePrint Archive. 2011/003. 2016年11月14日閲覧。
13. Barker, Elaine (May 2020). Recommendation for Key Management, Part 1: General (PDF) (Report). NIST. p. 59. CiteSeerX 10.1.1.106.307. doi:10.6028/nist.sp.800-57pt1r5。
14. Hedabou, M.; Pinel, P.; Beneteau, L. (2004). “A comb method to render ECC resistant against Side Channel Attacks”. IACR ePrint Report. http://eprint.iacr.org/2004/342.
15. “Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system”. 2020年1月2日閲覧。
16. Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". arXiv:1706.06752 [quant-ph]。
17. De Feo, Luca; Jao, David; Plut, Jerome (2014). “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies”. Journal of Math. Cryptology: 209–247. https://www.degruyter.com/view/j/jmc.2014.8.issue-3/jmc-2012-0015/jmc-2012-0015.xml.

参考文献

• N.コブリッツ『数論アルゴリズムと楕円暗号理論入門』櫻井幸一 訳、シュプリンガー・フェアラーク東京、1997年8月。ISBN 4-431-70727-1。
• Blake; Seroussi; Smart (1999). Elliptic Curves in Cryptography. CAMBRIDGE UNIVERSITY PRESS

関連項目

• 暗号理論
• 楕円曲線暗号の特許
• 楕円曲線ディフィー・ヘルマン鍵共有
• 楕円曲線DSA