楕円曲線暗号

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

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

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

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

歴史[編集]

暗号理論に楕円曲線を利用しようというアイディアは、1985年にニール・コブリッツ (Neal Koblitz（英語版）)^[1] とビクター・S・ミラー (Victor S .Miller（英語版）)^[2] によって独立に提案された。楕円曲線暗号は、2004～2005年ごろから広く使用されるようになっている。

理論[編集]

暗号における楕円曲線とは、ある有限体 K 上の式

y^{2}=x^{3}+ax+b\,

を満たす全ての点 P=(x,y) の集合に、無限遠点と呼ばれる特別な点 O を加えたものである。ここで、 x と y は有限体 K の要素である。（K の標数が2または3の場合、上式では不都合が生じるため、ここでは標数は2と3以外であるとする。一般には、もう少し複雑な式と議論が必要になる。）

この集合と楕円曲線上の群演算は、無限遠点を単位元とするアーベル群となる。群演算は楕円加算と呼ばれる。群構造は、代数多様体の因子群から引き継がれる。

楕円曲線上の加算[編集]

楕円曲線E上に位置する2点 $P_{\!A}\,(x_{1},\,y_{1}),\,P_{\!B}\,(x_{2},\,y_{2})$ の加算は以下の通りである。

まず、無限遠点を $O$ とすると、 $P_{\!A}+O=O+P_{\!A}=P_{\!A}$ である。すなわち、 $O$ が単位元である。

もし $x_{1}=x_{2},y_{1}=-y_{2}$ ならば、 $P_{\!A}+P_{\!B}=O$ である。

それ以外の場合、 $P_{\!C}=P_{\!A}+P_{\!B}$ は、2点 $P_{\!A},\,P_{\!B}$ を通る直線とEとの（ $P_{\!A}$ および $P_{\!B}$ と異なる）交点の、y座標の符号を反転したものである。すなわち $P_{\!C}\,(x_{3},\,y_{3})$ は以下のようになる。

x_{3}=\phi ^{2}-x_{1}-x_{2},

y_{3}=-\phi x_{3}-\psi .

ただし $\phi ,\,\psi$ は

\phi ={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}},

\psi ={\frac {y_{1}x_{2}-y_{2}x_{1}}{x_{2}-x_{1}}}.

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

楕円曲線E上の点 $P_{\!A}\,(x_{1},\,y_{1})$ に対し、これを2倍した点 $2P_{\!A}=P_{\!A}+P_{\!A}$ は、以下のように求められる。

$y_{1}=0$ のとき、 $2P_{\!A}=O$ である。また、 $2O=O+O=O$ である。

それ以外の場合は、 $P_{\!D}=2P_{\!A}$ は、 $P_{\!A}$ でのEの接線がE自身と交わる（ $P_{\!A}$ とは異なる）交点の、y座標の符号を反転したものである。すなわち $P_{\!D}\,(x_{4},\,y_{4})$ は以下で求められる。

x_{4}=\phi ^{2}-2x_{1},

y_{4}=-\phi x_{4}-\psi .

この式は異なる二点の加算の場合と同じであるが、 $\phi ,\,\psi$ の計算式が次のように変わる。

\phi ={\frac {3x_{1}^{2}+a}{2y_{1}}},

\psi ={\frac {-3x_{1}^{3}-ax_{1}+2y_{1}^{2}}{2y_{1}}}.

スカラー倍算[編集]

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

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

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

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

離散対数と離散対数問題[編集]

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

巡回群 $\langle G\rangle$ の任意の要素（楕円曲線上の点） $X$ に対し、 $X=aG$ を満たす $a$ が $\{0,1,\ldots ,n-1\}$ の中に常にただ一つ存在する。このような $a$ を $X$ の離散対数と呼ぶ。また、 $\langle G\rangle$ から無作為に選らばれた $X$ を与えられ、その離散対数を求めよという問題を、楕円曲線上の離散対数問題 と呼ぶ。

また、 $\langle G\rangle$ から無作為に選ばれた二つの点 $X=aG,Y=bG$ を与えられ、 $abG$ を求めよという問題を、楕円曲線上のディフィー・ヘルマン問題 と呼ぶ。

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

巡回群の位数 $n$ が小さければ、離散対数問題やディフィー・ヘルマン問題が容易に解けてしまうため、位数が巨大な素数になるようなベースポイント（と楕円曲線）が使用される。

攻撃手法[編集]

サイドチャネル攻撃[編集]

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

量子コンピュータを用いた攻撃[編集]

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

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

解読[編集]

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.
^ 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.
^ 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.
^ “Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system”. 2020年1月2日閲覧。
^ ^a ^b Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". arXiv:1706.06752 [quant-ph]。
^ De Feo, Luca; Jao, David; Plut, Jerome (2014). “Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies”. Journal of Math. Cryptology: 209–247.

参考文献[編集]

Blake, Seroussi & Smart 著、Elliptic Curves in Cryptography, CAMBRIDGE UNIVERSITY PRESS, 1999