自分なりに楕円曲線暗号についてまとめてみた
楕円曲線とは
楕円曲線とは，$y^2=x^3+ax+b$で表される式です．
$y^2=(なんちゃら)$という形をしているのでx軸に関して対称であることがわかります．
具体的にどんな形をしているのかを見ていきます．
GeoGebraという関数グラフをかける神アプリを使って書いてみました．
https://www.geogebra.org/graphing?lang=ja
$y^2=x^3+2x+3$
$y^2=x^3-5x+5$
$y^2=x^3-5x+3$
離れ小島ができることもであるようです．
楕円曲線暗号の概要
楕円曲線$y^2 \equiv x^3+ax+b \pmod {p}$で$a,b,p$の値は事前に決めておきます．また，楕円曲線上の点Gも決めておきます．これらは全て公開されています．
ここで，秘密鍵$n$を使って$nG$を計算します．この$nG$が公開鍵です．$nG$の結果だけを見て$n$を計算するのは離散対数問題と言われる，解くのに膨大な時間を要するものになります．
「膨大な時間」というのはあまりにも長いので解読不可能と言われます．
これだけ見ると$nG$って何やねん，$(nx,ny)$と等しいのか？，とか思いますがそうではありません．あと，modとかいう異物が入っています．順を追って説明していきます．
加法
異なる点の加法
楕円曲線の世界での加法は$3+5=8$のようなものとは全く別のものです．
楕円曲線上の2点$P$,$Q$の足し算の結果は，$P$と$Q$を通る直線と楕円曲線の交点を$x$軸に関して対称移動させた点$R$です．
想像がしづらいので具体的な例をみてみます．
$y^2=x^3-2x+4，P(-2,0)，Q(0,-2)$とすると，PQを通る直線は$y=-x-2$と表されます．直線と楕円曲線の交点$S$は$(3,-5)$になります．$S$を$x$軸に関して対称移動させると点$R(3,5)$が得られます．よって，$P(-2,0)+Q(0,-2)=R(3,5)$です．
楕円曲線，と聞いてなんだか小難しそうですが図で見ると案外とっつきやすい印象です．
この例はたまたま座標が整数になっているだけで，実際は有理数になります．
問題はこれをどうプログラムに落とすか，です．一般化しなければなりません．
$y^2=x^3+ax+b，P(x_p,y_p)，Q(x_q,y_q)$のときの$P+Q=R$である$R(x_r,-y_r)$を求めます．
方針としては，PとQと通る直線の式と楕円曲線の方程式を連立して解けば座標$R(x_r,y_r)$が求まりそうです．
まず，PとQと通る直線の方程式は，傾きを
$$
\phi = \frac{y_q- y _ p } { x _ q - x _ p }
$$
とおくと
$$
y=\phi (x-x_p) + y_p，
y=\phi x - \phi x_p + y_p
$$
と表されます．わかりやすく$y=ax+b$の形にするために，
$$
\psi = - \phi x_p + y_p
$$
$$
= - \frac{ ( y _ q - y _ p ) x _ p } { x _ q - x _ p } + \frac { ( x _ q - x _ p ) y _ p } { x _ q - x _ p } = \frac{ x _ p y _ p - x _ q y _ q} { x _ q - x _ p }
$$
として
$$
y=\phi x + \psi
$$
と表します．この式を$y^2=x^3+ax+b$に代入すると，
$$
(\phi x + \psi)^2 = x^3+ax+b
$$
整理して，
$$
x^3- \phi^2 x^2 +ax- 2 \phi \psi x - \psi ^2 +b = 0
$$
となります．この三次方程式の解は$x_p,x_q,x_r$の3つです．なぜなら，$y^2=x^3+ax+b$と$y=\phi x + \psi$の交点は3つあり，その点は$P,Q,R$の3つであるからです．三次方程式の$x^3$の係数は1であるので，
$$
(x-x _ p ) ( x - x _ q ) ( x - x _ r )=0
$$
という式を変形すると上の三次方程式になることがわかります．よって，展開をして係数を比較すると
$$
\phi^2 = x _ p + x _ q + x _ r
$$
が得られます．よって，
$$
x _ r = \phi^2 - x _ p - x _ q
$$
そして，これを$y=\phi x + \psi$に代入し，
$$
y _ r = \phi x _ r + \psi
$$
と求まります．加法の一般化終了です．お疲れ様でした．($R$の座標は$(x_r,-y_r)$であることに注意)
同一点の加法(2倍)
楕円曲線上の点$P$について$P+P$の計算の結果は，楕円曲線の接線のうち$P$を通る直線と楕円曲線の交点をx軸に関して対称移動させた点$R$です．
接線の傾きを求めるには微分を使います．
$y^2=x^3+ax+b$の両辺を$x$で微分すると，
$$
2y \frac{dy}{dx} = 3x^2 + a
$$
よって
$$
\frac{dy}{dx} = \frac{3x^2 + a}{2y}
$$
つまり，$(x_p,y_p)$の接線の傾きは$x$と$y$に代入して，
$$
\phi = \frac{3 x _ p ^2 + a}{2 y _ p }
$$
異なる二点の加法のときと同様に，
$$
\psi = - \phi x_p + y_p
$$
$$
= - \frac{(3 x _ p ^2 + a) x_p }{2 y _ p } + \frac{2 y _ p ^ 2 }{ 2 y _ p } = \frac{- 3 x _ p ^3 - a x_p + 2 y _ p ^ 2 }{2 y _ p }
$$
あとは異なる二点の加法のときと同様です．
$x _ r = \phi^2 - 2 x _ p $と$y _ r = \phi x _ r + \psi$と求まります．($R$の座標は$(x_r,-y_r)$であることに注意)
これは$P+P$の結果ですが，$P+P=2P$とも表されます．
スカラー倍は，$3P=2P+P，4P=3P+P$というように求めていくことができます．
$P$のスカラー倍を計算する方法は早い方法がありますが，これについては後述します．繰り返し二乗法と呼ばれる方法になります．
有限体$\mathbb{F}_p$上の楕円曲線
なんか難しそうな記号がでてきました．これは$ \bmod p$についての話です．
有限個の要素からなる体(たい)を有限体といいます．体というのは四則演算ができる数の集合のことです．
$\mathbb{F}$は有限体を表す記号で，足についてる$p$は位数です．位数というのは体の要素の数です．
つまり，有限体$\mathbb{F}_p$というのはp個の要素のある四則演算ができる集合のことです．
(厳密には違います)(ここの詳しい話は僕自身よくわかっていません)．
例えば有理数は無限にありますがそれらをコンピュータで表そうとすると，コンピュータのメモリは有限であるので無限通りの数の表し方を用意することは不可能です．
しかし，それらは$ \bmod p$の演算を通すことで$0$以上$p$未満の整数のいずれかになります．有限通りの数の表し方は用意できるのでそれらの数を扱うことができます．
$ \bmod p$とは
さっきから$ \bmod p$という表記が登場していますが，これについて説明します．
$ \bmod p$がついている式を合同式と呼びます．$p$は自然数です．合同式についての説明を詳しくすると長くなりすぎてしまうので，簡単な説明だけして，性質の証明などは省略します．
整数に関しては割ったあまりという認識で良いです．例えば，
$$
7 \equiv 1 \pmod 3
$$
という式は，$7$を$3$で割ったあまりが$1$であることを表しています．別に，右辺は$3$で割ったあまりが$1$になる数が入っていればなんでもいいです．今回は$0$以上$p$未満の整数にすることが目的であるので右辺はそれに則ります．
$$
(-4) \equiv 2 \pmod 3
$$
マイナスでも定義ができます．$-4$を$3$で割った余りは$4 = 3 \times ( - 2 )+2 $より$2$と求めることができます．
次は分数(有理数)の場合です．
$$
\frac{1}{2} \equiv ? \pmod 3
$$
$\frac{1}{2}$は，$2$をかけると$1$になる数であるので
$$
2 \times \frac{1}{2} \equiv 1 \pmod 3
$$
が成り立ちます．この式を成り立たせる$ \frac{1}{2} $の代わりになる数を探すと$2$が見つかります．
$$
2 \times 2 \equiv 1 \pmod 3
$$
よって
$$
\frac{1}{2} \equiv 2 \pmod 3
$$
です．ちなみに$ \frac{1}{2} $は$2$をかけると$1$になるという意味で，$2^{-1}$と表すことがあります．行列でいう逆行列のように，(たまたま等しくなっているが)$ \frac{1}{2} $という意味はなく$2$の逆元という意味があります．逆元は$p$の値によって変わります．
実際に計算をしてみる
では，実際に楕円曲線上で計算してみます．
$y^2 \equiv x^3+x+6 \pmod{11}$の例で考えます．
$P(2,7)$は楕円曲線上の点です．これを2倍することを考えます．
2倍は同一点の足し算になるので，
$$
\phi = \frac{3 \times 2 ^2 +1 }{2 \times 7 } = \frac{13 }{14 }
$$
$$
\psi = \frac{- 3 \times 2 ^3 -1 \times 2 + 2 \times 7 ^ 2 }{2 \times 7 } =\frac{36}{7}
$$
有限体$\mathbb{F}_{11}$上の点にするため(0以上11未満の整数にするため)に$ \pmod{ 11}$で処理します．
$$
\frac{13 }{14 } \equiv 13 \times 14^{-1} \equiv 13 \times 4 \equiv 8 \pmod {11}
$$
$$
\frac{36}{7 } \equiv 36 \times 7^{-1} \equiv 36 \times 8 \equiv 2 \pmod {11}
$$
よって，
$$
x \equiv 8^8 - 2\times 2 \equiv 5 \pmod {11}
$$
$$
y \equiv -8 \times 5 - 2 \equiv 2 \pmod {11}
$$
以上の計算より$2P=(5,2)$だと求めることができました．
途中にでてきた逆元の求め方ですが，プログラムだと拡張ユークリッドの互除法やフェルマーの小定理を用いると高速に求めることができます．また，Python3であれば，
pow(7,-1,11)
と書くだけで，$\pmod {11}$の$7^{-1}$の値を取得することができます．この関数が標準で存在するのは驚きです．
スカラー倍を高速に計算する
$nG$から$n$を求めるのを難しくするにはnは十分に大きな数でなければなりません．しかし，$2G=G+G,3G=G+2G$...というナイーブな方法で計算していくと$O(n)$の時間がかかってしまいます．これだと，$nG$から$n$を求めようとしたときに全探索が$O(n)$の時間で終わってしまうので暗号化としての意味がありません．そこで，高速に$nG$を計算する方法を示します．
繰り返し二乗法と呼ばれる方法です．
わかりやすいようにまずは整数で考えます．例えば$13^{16} \pmod {10007}$を計算したいとします．愚直に計算すると，
$13 \times 13\equiv 169，169 \times 13 \equiv 2197， 2197 \times 13 \equiv 8547$...という具合に掛け算を15回することになります．
しかし，$(13^2)^2=13^4$であることを利用すると，
$13^2 \equiv 169，13^4= (13^2)^2 \equiv 8547，13^8=(13^4)^2 \equiv 109$...という具合に掛け算を4回行うだけで$13^{16} \pmod {10007}$を求めることができます．
そんなのたまたま指数が2の冪数だったからじゃないの，と思われるかもしれませんが，2の冪数でなくても大丈夫です．
例えば，$13^{13} \pmod {10007}$であったら$13^{12}=13^1 \times 13^4 \times 13^8$と変形すれば，先ほどの計算過程に出てきた数だけの式になります．
これは指数の数字を二進数にしたときに各位が1か0かで掛け算をするかしないかを決めるとうまくいきます．
楕円曲線の場合も同様に，$4G=2G+2G$，$8G=4G+4G$と計算できるので，例えば46Gを計算したいときは，$46$を二進数に直すと$101110_{(2)}$であることより，
$32G+8G+4G+2G$を計算すれば良いです．これで計算量は$0(log(n))$になりました．
あとがき，余談
楕円曲線暗号のしくみを整頓することができてよかったです．これでタイトルがsimpleECCみたいなCTFの問題は解けるようになったはずです．正直理解するのにかなりの時間を要したので，攻撃方法を学ぶのはまた今度にします．RSA暗号に比べてネット上の資料が少ないのも苦労した原因の一つだと思います．特に楕円曲線の加法の計算を実装したソースコードは数個しか見つかりませんでした(しかも言語がバラバラ)．Pythonに慣れていないのでソースコードを書きませんでしたが，今後載っけられたらいいなと思ってます．
(2021/2/23追記)SageMathというものを使うと楕円曲線や整式のライブラリが使えるので，普通はこちらを使用するようです．
(2021/10/12追記)
一応SageMathで$y^2 \equiv x^3+x+6 \pmod{11}$で$P(2,7)$の$2P$を求める方法を載せておきます
E=EllipticCurve(GF(p),[a,b])
で$E$が$y^2 \equiv x^3+ax+b \pmod{p}$として定義されます．
P=E([x,y])
で$E$上の$(x,y)$が点$P$として定義されます．
よって
sage: E = EllipticCurve(GF(11),[1,6]) sage: P=E([2,7]) sage: 2*P
と実行することで
(5 : 2 : 1)
と$(5,2)$が求めることができました．
