楕円曲線暗号のソースを表示

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

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

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

一部の楕円曲線には、DLPを解く多項式時間アルゴリズムが見つかっているため、注意が必要である<ref name="立教大学数学雑誌-1998">{{cite journal |first1=T. |last1=Satoh |first2=K. |last2=Araki |url=https://rikkyo.repo.nii.ac.jp/record/9910/files/AA00610867_47-01_06.pdf |title=Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves |journal=Commentarii Mathematici Universitatis Sancti Pauli (立教大学数学雑誌) |volume=47 |year=1998 }}</ref>。

== 歴史 ==
暗号理論に楕円曲線を利用しようというアイディアは、1985年にニール・コブリッツ<ref>{{cite journal |first=N. |last=Koblitz |title=Elliptic curve cryptosystems |journal=Mathematics of Computation |volume=48 |issue=177 |year=1987 |pages=203?209 |doi= 10.2307/2007884|jstor=2007884 }}</ref> と ビクター・S・ミラー<ref>{{cite journal |first=V. |last=Miller |title=Use of elliptic curves in cryptography |journal=CRYPTO |volume=85 |year=1985 |issue= |pages=417?426 |doi=10.1007/3-540-39799-X_31 |series=Lecture Notes in Computer Science |isbn=978-3-540-16463-0 }}</ref> によって独立に提案された。楕円曲線暗号は、2004～2005年ごろから広く使用されるようになっている。

== 理論 ==
[[File:Secp256k1.png|thumb|[[楕円曲線]]の例： secp256k1(後述)で規定されている <math>\mathbb{R}^2</math> 上の <math>y^2 = x^3 + 7</math> のグラフ。]]
実平面 <math>\mathbb{R}^2</math> 上の点を <math>P(x,y)</math> で表した場合、<math>\mathbb{R}^2</math> 上で定義される楕円曲線 <math>E: y^2 = x^3 + \alpha x + \beta</math> (ワイエルシュトラスの標準形)では、<math>E</math> 上の点に接弦法(またはバシェ(Bachet)の方法)<ref name="足立-1996">{{Cite Book
| 和書
| author = 足立恒雄
| title = フェルマーの大定理 [第3版]
| publisher = 日本評論社
| date = 1996-05
| isbn = 4-535-78231-8
| pages = 164-167
}}</ref>
と呼ばれる加法的な2項演算により加群の構造を与えることができる(零元は通常は無限遠点(0,∞)と定義される。これを <math>O</math> で表す)。

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

=== 楕円曲線上の加法 ===
楕円曲線<math>E</math> 上の異なる2点を <math>P_1\, (x_1,\, y_1),\, P_2\, (x_2,\, y_2)</math>とする場合、その接弦法の加法を <math>P_1 + P_2</math> で表すことにすると、これは以下の式で計算される<ref name="Song-2020">{{Cite Book
| 和書
| author = J.Song
| others = 中川卓俊、住田和則、中村昭雄 監訳 星野靖子 訳
| title = プログラミング・ビットコイン ゼロからビットコインをプログラムする方法
| publisher = オライリー・ジャパン (オーム社)
| date = 2020-10
| isbn = 978-4-87311-902-1
| pages = 36-40
}}</ref>。

まず、<math>P_1 + O = O + P_1 = P_1</math> である。すなわち、無限遠点 <math>O</math> が零元であると定義する。

もし <math> x_1 = x_2, y_1 = - y_2 </math> ならば、<math>P_1 + P_2 = O </math> であると定義する。このとき <math>P_2</math> を <math>-P_1</math> と書き、 <math>P_1</math> の逆元と呼ぶことにする。

<math>O + O = O</math> であるから、<math>O</math> の逆元は <math>O</math> 自身である。これは通常の加群の零元の条件を満たしている。

それ以外の場合、<math>P_1 + P_2</math> は、2点 <math>P_1,\,P_2</math> を通る直線と <math>E</math> との（<math>P_1</math> および <math>P_2</math> と異なる）交点の、y座標の符号を反転したものであると定義する。つまり <math>P_3\,(x_3,y_3) = P_1 + P_2</math> と置けば、次のように計算される。
<math display="block">x_{3}=\phi^{2}-x_{1}-x_{2},</math>
<math display="block">y_{3}=-\phi x_{3}-\psi.</math>
ただし <math>\phi,\, \psi</math> は
<math display="block">\phi=\frac{y_{2}-y_{1}}{x_{2}-x_{1}},</math>
<math display="block">\psi=\frac{y_{1}x_{2}-y_{2}x_{1}}{x_{2}-x_{1}}.</math>

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

*零元 <math>O</math> の存在
*各元<math>P_1</math>に対する逆元<math>-P_1</math>の存在
*可換性： <math>P_1 + P_2 = P_2 + P_1</math> (定義式の対称性から明らか)
*結合性： <math>(P_1 + P_2) + P_3 = P_1 + (P_2 + P_3)</math> (煩雑であるが定義式を丁寧に解けば証明できる)

=== 楕円曲線上での2倍算 ===
楕円曲線<math>E</math>上の点 <math>P_1\, (x_1,\,y_1)</math> に対し、さらに<math>P_1</math> を加算する場合、つまり <math>P_1 + P_1 = 2 P_1</math> を求める場合、上記の方法は使えない。

この場合、まず <math>y_1 = 0</math> のときは、<math>2P_1 = O</math> である。また、<math>2O = O+O = O</math> である。

それ以外の場合は、<math>2 P_1</math> は、<math>P_1</math> での <math>E</math> の接線が <math>E</math> 自身と交わる（<math>P_1</math> とは異なる）交点の、<math>y</math>座標の符号を反転したものである。すなわち <math>P_4\, (x_4,\, y_4) = 2 P_1</math> と置けば、次のように計算される。
<math display="block">x_4 = \phi^2 - 2x_1,</math>
<math display="block">y_4 = -\phi x_4-\psi.</math>
この式は異なる二点の加算の場合と同じであるが、<math>\phi,\, \psi</math> の計算式が次のように変わる。
<math display="block">\phi=\frac{3x^2_1+ \alpha}{2y_1},</math>
<math display="block">\psi=\frac{-3x^{3}_{1}- \alpha x_{1}+2y_{1}^2}{2y_{1}}.</math>

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

<math>E</math>上のある点 <math>P_1</math>を始点として、これに順次 <math>P_1</math> 自身を <math>n-1</math> 回加算して得られる点を <math>nP_1</math>で表すことにする。この操作は <math>O</math> に <math>P_1</math> を <math>n</math> 回加算することと同じである。<math>O</math> に <math>-P_1</math> を <math>n</math> 回加算すれば<math>-nP_1</math>が得られる。
このようにして、<math>E</math>上の点と整数の[[掛け算]]が定義できる。この操作をスカラー倍算（Scalar Multiplication）と呼ぶことにする。

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

=== 楕円曲線上の有理点 ===
楕円曲線のパラメーター <math>\alpha,\, \beta</math> が有理数の場合、2つの有理点(<math>x,y</math> が共に有理数の点)を加算して得られる点はやはり有理点である。つまり、<math>E</math> 上の全ての有理点の集合＋無限遠点 <math>O</math> を <math>E(\mathbb{Q})</math> と表すと、<math>E(\mathbb{Q})</math> は加法について <math>E</math> の部分加群を成している。また、<math>E(\mathbb{Q})</math> 上のある有理点を始点として加法により生成される <math>E(\mathbb{Q})</math> 上の点列は、<math>E(\mathbb{Q})</math> 上の全ての点が成す加群の部分加群(巡回群)を成している。さらに始点が整点(<math>x,y</math> が共に整数の点)でない場合、この巡回群の位数は無限大である([[:en:Nagell-Lutz theorem|Nagell-Lutzの定理]]{{Sfn|シルヴァーマン,テイト|2012|p=61}})。

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

=== 素数 ''p'' による還元 ===
楕円曲線暗号で扱う楕円曲線とは、ある素数 p について、以下で説明する楕円曲線 <math>E(\mathbb{Z}_p)</math> を p で還元した有限体 <math>\mathbf{F}_p</math> 上の離散的楕円曲線であり、これを <math>E(\mathbf{F}_p)</math> と表すことにする(無限遠点 <math>O</math> も含む。誤解の恐れがないので無限遠点は <math>E</math> または <math>E(\mathbb{Q})</math> のものと同じ記号を使うことにする。)。以下、順を追って説明する。

==== 有理数体 <math>\mathbb{Q}</math> の部分環 <math>\mathbb{Z}_p</math> の還元 ====
0以外の全ての有理数は、2つの整数 u、v (u、vは互いに素な整数であり、v > 0)の分数 u/v の形で表すことができる。この形式を正規化された分数と呼ぶことにする(分数 0/1 を 0 の正規化された分数と見なすことにする)。正規化された分数 u/v の 分母 v が p を因数として含まない場合、u/v を p進整数 (または p-整数)と呼ぶ{{Sfn|シルヴァーマン,テイト|2012|p=325}}。全てのp進整数の集合を <math>\mathbb{Z}_p</math> とすれば、これは 有理数体 <math>\mathbb{Q}</math> の部分[[環 (数学)|環]]を成しており、p進整数環と呼ばれる{{Sfn|青木|2019|p=41}}。 p進整数環 <math>\mathbb{Z}_p</math> から有限体 <math>\mathbf{F}_p</math> 上への写像 <math>f_p</math> を、次のように定義する。
<math display="block">f_p(u/v) = (u \bmod \,p)(v \bmod \,p)^{-1}  \bmod \,p</math>
ただし、<math>(v \bmod \,p)^{-1}</math> は <math>\mathbf{F}_p</math> の元 <math>v \bmod\,p</math> の <math>\mathbf{F}_p</math> における逆元とする。

<math>f_p</math> は環 <math>\mathbb{Z}_p</math> から 有限体 <math>\mathbf{F}_p</math> への環準同型写像であり、 <math>\mathbb{Z}_p</math> 上の加法、乗法、逆元は <math>\mathbf{F}_p</math> 上の加法、乗法、逆元に写される。特に <math>\mathbb{Z}_p</math> における除算は、<math>\mathbf{F}_p</math> では逆元を乗ずる操作に写される。<math>f_p</math> の像が体であるから、その[[核 (代数学)|核]]は環 <math>\mathbb{Z}_p</math> の[[極大イデアル]]であり、これは[[単項イデアル]] <math>p\mathbb{Z}_p</math> に一致する。

==== 楕円曲線 <math>E(\mathbb{Z}_p)</math> の還元 ====
有理数体<math>\mathbb{Q}</math> 上の楕円曲線 <math>E(\mathbb{Q})</math> を <math>\mathbb{Z}_p</math> 上に制限したものを <math>E(\mathbb{Z}_p)</math> と表すことにする(無限遠点 <math>O</math> は含むものとにする)。

<math>E(\mathbb{Z}_p)</math> の素数 p による還元とは、<math>E(\mathbb{Z}_p)</math> に、次に定義する <math>{\mathbb{Z}_p}^2</math> から <math>{\mathbf{F}_p}^2</math> への写像 <math>\tilde{f}_p</math> を作用させることであるとする{{Sfn|コブリッツ|1997|pp=246,272}}{{R|group="注"|注1}}。

* <math>\tilde{f}_p(O) = O</math>
* <math>\tilde{f}_p(x,y) = (f_p(x),f_p(y))</math>

<math>\tilde{f}_p</math> は <math>f_p</math> の性質から、<math>E(\mathbb{Z}_p)</math> 上の接弦法による加法を <math>E(\mathbf{F}_p)</math> 上の加法に矛盾なく写す。つまり<math>\tilde{f}_p</math> は楕円曲線上の加法に関する準同型写像を成している。

[[File:Elliptic curve on Z61.svg|thumb|right|360px|離散的楕円曲線の例： 有限体 {{math|'''F'''{{msub|61}}}} 上の楕円曲線 {{math|1=''y''{{exp|2}} = ''x''{{exp|3}} &minus; ''x''}}]]

<math>\mathbb{Z}_p</math> 上で定義された楕円曲線 <math>E(\mathbb{Z}_p): y^2 = x^3 + \alpha x + \beta</math> (<math>\alpha, \beta</math> はp進整数) を素数 <math>p</math> で還元した離散的楕円曲線 <math>E(\mathbf{F}_p)</math> は <math>\mathbf{F}_p</math> 上では次の式で定義される。
:<math>E(\mathbb{\mathbf{F}_p}): y^2 = x^3 + ax + b \,\,(\bmod \,p)</math>
ただし、<math>x,y</math> は <math>\mathbf{F}_p</math> の元であり、<math>a = f_p(\alpha),\, b = f_p(\beta)</math>  とする。このようにして定義された離散的楕円曲線は、グラフにすれば最早曲線ではなく、離散した点の集まりにしか見えない(ただし分布は直線 <math>y=0</math> に対して対称である)。

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

<math>P_1\,(x_1,y_1),\,P_2\,(x_2,y_2)</math> を<math>E(\mathbb{\mathbf{F}_p})</math>上の任意の2点とする。

<math> x_1 = x_2, y_1 = - y_2 </math> の場合、<math>P_1 + P_2 = O</math>。

それ以外の場合、<math>P_3\,(x_3,y_3) = P_1 + P_2</math> と置けば、
<math display="block">x_{3}=\phi^{2}-x_{1}-x_{2} \,(\bmod \,p)</math>
<math display="block">y_{3}=-\phi x_{3}-\psi \,(\bmod \,p)</math>

ただし <math>\phi,\, \psi</math> は <math>P_1 \ne P_2</math> の場合、
<math display="block">\phi=(y_{2}-y_{1})(x_{2}-x_{1})^{-1} \,(\bmod \,p)</math>
<math display="block">\psi=(y_{1}x_{2}-y_{2}x_{1})(x_{2}-x_{1})^{-1} \,(\bmod \,p)</math>

<math>P_1= P_2</math> の場合、
<math display="block">\phi=(3x^2_1+ a)(2y_1)^{-1} \,(\bmod \,p)</math>
<math display="block">\psi=(-3x^{3}_{1}- a x_{1}+2y_{1}^2)(2y_{1})^{-1} \,(\bmod \,p)</math>

上記の式で、<math>\mathbf{F}_p</math> の 0 以外の任意の元 <math>v</math> の <math>\mathbf{F}_p</math> における逆元 <math>v^{-1}</math> は、[[フェルマーの小定理]]から <math>v^{p-1} \equiv 1\,(\bmod \,p)</math> であるから、<math>v^{-1} = v^{p-2} \,\bmod \,p</math> によって計算できる。

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

{{R|group="注"|注2}}

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

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

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

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

楕円曲線のパラメーターの一例として、[[ビットコイン]]で使われている楕円曲線暗号である secp256k1 のものを示す<ref name="SECG-2010-01">{{cite report
| authors = S.Chandrashekar & N.Ramani
| url = https://www.secg.org/sec1-v2.pdf
| title = SEC 2：Recommended Elliptic Curve Domain Parameters (Version 2.0)
| publisher = Standards for Efficient Cryptography Group (SECG)
| page = 13
| date = 2010-01-27
| accessdate = 2024-05-30
}}</ref>。 

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

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

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

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

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

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

== 安全性と攻撃手法 ==
=== 離散対数問題のセキュリティ強度 ===
{{仮リンク|セキュリティ強度|en|Security level}}(セキュリティ・レベル)は暗号の破られにくさを表す1つの指標(単位はビット)であり、セキュリティ強度が <math> l</math> (ビット)であるとは、攻撃者が暗号から鍵(あるいは平文)を解読するために必要な単位操作の回数が <math> 2^l</math> 回程度であることを表している<ref>{{Cite report|last=Barker|first=Elaine|others=NIST|title=Recommendation for Key Management, Part 1: General|url=https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf|date=May 2020|page=17|doi=10.6028/nist.sp.800-57pt1r5|citeseerx=10.1.1.106.307}}</ref>
。例えば [[共通鍵暗号]]である [[AES]]-128 (鍵長 128 ビット) は、攻撃者が必要な単位操作の回数が <math> 2^{128}</math> 回になるように設計されている(つまり、全ての鍵について[[総当たり攻撃]](Brute-force attack)を行わないと解読できないように設計されている。この場合はセキュリティ強度＝鍵長となる)。一方、[[RSA暗号]]の場合、これと同等のセキュリティ強度を得るには約 3072 ビットの鍵長が必要になる(つまり何らかの冗長性を利用して、攻撃者は必要な単位操作の回数を節約することが可能なことを意味している)<ref>{{Cite report|last=Barker|first=Elaine|others=NIST|title=Recommendation for Key Management, Part 1: General|url=https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf|date=May 2020|page=55|doi=10.6028/nist.sp.800-57pt1r5|citeseerx=10.1.1.106.307}}</ref>。

離散対数問題(DLP)は、残念ながら総当たり攻撃によらなくても解読できることが分かっている。例えば、[[ポラード・ロー離散対数アルゴリズム]]を用いて離散対数を計算するのに必要な単位操作回数(この場合は楕円加算回数)はおよそ <math>\sqrt{n\pi/4}</math> 回である<ref>{{cite techreport |author=Daniel J. Bernstein |author2=Tanja Lange |author3=Peter Schwabe|title=On the correct use of the negation map in the Pollard rho method|publisher=IACR Cryptology ePrint Archive|number=2011/003|date=2011-01-01|url=https://eprint.iacr.org/2011/003|access-date=2016-11-14}}</ref>。従って、離散対数問題(およびそれと同等なディフィー・ヘルマン問題)のセキュリティ強度 <math> l</math> は、鍵長を <math> m = \log _2 n</math> とした場合、<math>l = \log _2 {\sqrt{n\pi/4}} = \frac{1}{2}(\log _2 n + \log _2 (\pi/4))</math> であるから、概略 <math> l = \frac{1}{2} \log _2 n = \frac{m}{2} </math> となる。つまり鍵長 256 ビットの楕円曲線暗号(secp256k1 など) は、鍵長 128 ビットのAESと同程度のセキュリティ強度を有するということになる。この <math> l = \frac{m}{2} </math> という離散対数問題のセキュリティ強度の特性は、ワイエルシュトラスの標準形ではないエドワーズ曲線などの楕円曲線([[Curve448]]、[[Curve25519]]など)を用いた場合も同様である。

また、前述のように、一部の「anomalous な楕円曲線」と呼ばれる <math>\mathbf{F}_p</math> 上の離散的楕円曲線では、離散対数問題を解く多項式時間アルゴリズムが見つかっているため、これはセキュリティ上の脅威となり得る。anomalous な楕円曲線とは、ある素数 p について <math>\sharp E(\mathbf{F}_p) = p</math> を満たす、かなり特殊な楕円曲線であり、この上の離散対数問題を <math>(\log_2 p)^3</math> 回程度の単位操作回数で解くアルゴリズムが提案されている<ref name="立教大学数学雑誌-1998"/>。

[[アメリカ国立標準技術研究所]](NIST)は、セキュリティ強度が 112 ビットの暗号は、2030年まで社会的な用途で使用を許容されるが、2031年以降はセキュリティ強度が 128 ビット以上の暗号のみが許容可能であると勧告している<ref>{{Cite report|last=Barker|first=Elaine|others=NIST|title=Recommendation for Key Management, Part 1: General|url=https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf|date=May 2020|page=59|doi=10.6028/nist.sp.800-57pt1r5|citeseerx=10.1.1.106.307}}</ref>。

=== サイドチャネル攻撃 ===
楕円曲線上で楕円加算 ''P + Q '' を行う場合、加算(''P'' ≠ ''Q'')と2倍算(''P'' = ''Q'')では演算プロセスが大きく異なる。そのため、[[サイドチャネル攻撃]]（例えば、タイミング攻撃や[[単純電力解析]]/[[差分電力解析]]）への対策（例えば <ref>{{cite journal |first=M. |last=Hedabou |first2=P. |last2=Pinel |first3=L. |last3=Beneteau |url=http://eprint.iacr.org/2004/342 |title=A comb method to render ECC resistant against Side Channel Attacks |journal=IACR ePrint Report |year=2004 }}</ref> など）が必要である。あるいは、{{仮リンク|ツイステッドエドワーズ曲線|en|Twisted Edwards curve}}を使うこともできる。この曲線は、加算と2倍算を同じ演算プロセスで実行できる特別な楕円曲線の族である。<ref>{{cite web | url=http://blog.cr.yp.to/20140323-ecdsa.html | title=Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system |accessdate = 2020-01-02 }}</ref>

<!-- Another concern for ECC-systems is the danger of [[Differential fault analysis|fault attacks]], especially when running on [[smart card]]s.<ref>See, for example, {{Cite book |title=Differential Fault Attacks on Elliptic Curve Cryptosystems |first=Ingrid |last=Biehl |first2=Bernd |last2=Meyer |first3=Volker |last3=Müller |journal=Advances in Cryptology&nbsp;– CRYPTO 2000 |series=[[Lecture Notes in Computer Science]] |volume=1880 |year=2000 |pages=131–146 |doi=10.1007/3-540-44598-6_8 |isbn=978-3-540-67907-3 |url=http://www.iacr.org/archive/crypto2000/18800131/18800131.pdf }}</ref>
-->
=== 量子コンピュータを用いた攻撃 ===
[[離散対数]]問題を効率的に解くことのできる[[量子コンピュータ#ショアのアルゴリズム|ショアのアルゴリズム]]は、楕円曲線暗号の解読にも利用できる。256ビットの法を持つ楕円曲線暗号（128ビット安全）を破るためには、2330量子ビット、1,260億[[トフォリゲート]]のリソースを持つ量子コンピュータが必要であると見積もられている。<ref name=":0">{{Cite arxiv |eprint=1706.06752 |last1=Roetteler |first1=Martin |title=Quantum resource estimates for computing elliptic curve discrete logarithms |last2=Naehrig |first2=Michael |last3=Svore |first3=Krysta M. |last4=Lauter |first4=Kristin |class=quant-ph |year=2017 }}</ref>
一方、[[アメリカ国立標準技術研究所]]の勧告（NIST SP 800-57）によりこれと同等のセキュリティレベルとされる3072ビット鍵の[[RSA暗号]]を破るためには、6146量子ビット、18.6兆[[トフォリゲート]]が必要であり<ref name=":0" />、{{独自研究範囲|量子コンピュータにとっては、RSA暗号に比べ楕円曲線暗号は攻撃しやすいといえる。|date=2021年1月}}いずれにせよ、これらのリソースは現在実存する量子コンピュータのリソースをはるかに超えており、このようなコンピュータの構築は10年以上先になると見られている{{要出典|date=2021年1月}}。

同種写像暗号は、楕円曲線の[[楕円曲線#同種|同種写像]]を用いた暗号方式であり、量子コンピュータに対して耐性がある（耐量子）と考えられている。同種写像暗号の例として[[ディフィー・ヘルマン鍵共有]]と同様に鍵共有を行う[[超特異同種写像ディフィー・ヘルマン|SIDH]]がある。従来の楕円曲線暗号と同じ体の演算を多く使用し、必要な計算量や通信量は現在使用されている多くの公開鍵システムと同程度である。
<ref>{{cite journal|last = De Feo|first = Luca|last2 = Jao|first2 = David|last3 = Plut|first3 = Jerome|title=Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies|url=https://www.degruyter.com/view/j/jmc.2014.8.issue-3/jmc-2012-0015/jmc-2012-0015.xml|journal = Journal of Math. Cryptology|vol=8|pages = 209–247|year=2014}}</ref>
<!--
2015年8月に、[[NSA]]は、遠くない将来に[[量子コンピュータ]]を用いた攻撃に対しても安全な暗号体系へ移行することを発表した。『残念ながら、量子コンピューティングの研究が着実に進んでいるのに反して、楕円曲線暗号の使用が高まっており、暗号戦略の再評価が必要である。（"Unfortunately, the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing, necessitating a re-evaluation of our cryptographic strategy."）』<ref name="nsaquantum">{{cite web|url=https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml|title=Information Assurance|website=www.nsa.gov|archive-url=https://web.archive.org/web/20150815072948/https://www.nsa.gov/ia/programs/suiteb_cryptography/index.shtml|archive-date=2015-08-15|url-status=dead}}</ref><ref name=":0" />
-->

== 注釈 ==
{{Reflist|group="注"|refs=
{{Refnest|name="注1"|group="注"|[[射影平面]]の考えを採り入れれば、有理数 u/v の分母 v が p を因数として含む場合も含めて論じることができるが{{Sfn|シルヴァーマン,テイト|2012|p=325}}、<math>E(\mathbf{F}_p)</math> 上の加法を論じる上では、そこまで必要ないので割愛する。
}}
{{Refnest|name="注2"|group="注"|上記の方法を拡張して、有限体 <math>\mathbf{F}_p</math> の <math>m</math>次拡大体 <math>\mathbf{F}_{p^m} </math> 上での楕円曲線 <math>E(\mathbf{F}_{p^m})</math> を用いる暗号法も考案されており、実用的な仕様も公開されているが、話が煩雑になるので立ち入らないことにする。
}}
{{Refnest|name="注3"|group="注"|最もポピュラーな離散対数問題は、<math>p, g</math> と <math>y = g^x \bmod p</math> から <math>x</math> を求めよ、という問題であり、<math>g \isin Z_p^* (=Z/pZ)^{\times}</math> から生成される乗法群の上で定義されている。これに対して、楕円曲線は加法群であるため、<math>Q = dG</math> を満たす <math>d</math> を離散'''対数'''と呼ぶ。
}}
}}

== 解読 ==
* [[2004年]][[4月10日]]: ECC2 109[[ビット]]の解読に成功 ([http://www.certicom.com/index.php?action=res,ecc_solution certicom])。
* [[2009年]][[7月8日]]: ECC 112[[ビット]]の解読に成功（[[ソニー|SONY]]・[[PlayStation 3|PS3]]使用）[http://lacal.epfl.ch/page81774.html]

==脚注==
{{Reflist}}

== 参考文献 ==
* {{Cite Book
| 和書
| author = N.コブリッツ
| others = 櫻井幸一 訳
| title = 数論アルゴリズムと楕円暗号理論入門
| publisher = シュプリンガー・フェアラーク東京
| date = 1997-08
| isbn = 4-431-70727-1
| ref = {{SfnRef|コブリッツ|1997}}
}}
*{{Cite Book
| 和書
| author = J.H.シルヴァーマン
| author2 = J.テイト
| others = 足立恒雄ほか 訳
| title = 楕円曲線論入門
| publisher = 丸善出版
| date = 2012-07
| isbn = 978-4-621-06571-6
| ref = {{SfnRef|シルヴァーマン,テイト|2012}}
}}
*{{Cite Book
| 和書
| author = 青木 美穂
| title = p進ゼータ関数
| publisher = 日本評論社
| date = 2019-02
| isbn = 978-4-535-60354-7
| ref = {{SfnRef|青木|2019}}
}}
* {{Cite book
| last = Blake
| last2 = Seroussi
| last3 = Smart
| title = Elliptic Curves in Cryptography
| publisher = CAMBRIDGE UNIVERSITY PRESS
| year = 1999
| ref = harv
}}

== 関連文献 ==
（拡充予定）
; 和書
* 有田正剛、境隆一、只木孝太郎、趙晋輝、松尾和人：「暗号理論と楕円曲線」、森北出版、ISBN 978-4-627-84751-4 (2008年9月5日).
* 宮地充子：「代数学から学ぶ暗号理論：整数論の基礎から楕円曲線暗号の実装まで」、日本評論社、ISBN 978-4-535-78679-0 (2012年3月10日).

== 関連項目 ==
* [[暗号理論]]
* [[楕円曲線暗号の特許]]
* [[楕円曲線ディフィー・ヘルマン鍵共有]]
* [[楕円曲線DSA]]

{{DEFAULTSORT:たえんきよくせんあんこう}}
[[Category:暗号]]
[[Category:暗号技術]]
[[Category:数学に関する記事]]
[[Category:有限体]]
[[Category:楕円曲線暗号]]