楕円曲線とは (ダエンキョクセンとは) [単語記事]

楕円曲線(elliptic curve)とは、楕円の曲線部分のことではない。

概要

楕円曲線とは y² = x³ + ax + b で表すことができる曲線の総称である(変換してとか重根を持たないなどもう少し厳密な条件はある)。式を見れば分かるが、楕円 (px² + qy² = r) とは直接は関係がない。

楕円の周長を求める時に用いる楕円積分の逆関数を楕円関数と呼び、楕円関数の一種であるペー関数を局所で展開した時の式が楕円曲線の式に帰着できる、という私の祖父の兄の娘のいとこの叔父の孫よりも遠い関係があるといえばなくはないですが、ここまで離れてしまうと楕円よりもellipticの非数学的意味である「つぶれた円形」の方がよっぽど近いと言わざるを得ない。

用途

RSA暗号に代わる暗号化方式として楕円曲線暗号などに使われている。インターネットでよく見かけるhttps://はSSLによる暗号化が行われており、暗号化方式はRSA暗号が主流であったが、RSA暗号で暗号強度を上げようとすると鍵が非常に長くなるという問題があるため、楕円曲線暗号への移行が進められている。

楕円曲線暗号はビットコインなどのブロックチェーンにも用いられている。ちなみにビットコインで用いられている楕円曲線は y² = x³ + 7 である。

フェルマーの最終定理の証明に楕円曲線を用いた予想が使われたとか何とか。

楕円曲線の加法

例として y² = x³ - 5x + 1 について考える(上記赤線のグラフ)。

楕円曲線上の点P, Qを結ぶ直線(上記青線)と楕円曲線の交点は、直線の式を楕円曲線の式のyに代入するとxの3次方程式になることからわかるように、P, Q以外の交点Rが存在する。楕円曲線はx軸に対して対称なので、このRをx軸に対して対象移動した点R'も楕円曲線上に存在する。以上の操作を P + Q = R' という演算として表現する。

実はこの演算は結合法則 (P + Q) + S = P + (Q + S) を満たし、(直線PQがy軸に平行な時に無限遠の点という概念を持ち込む必要はあるが、)なんと数字の足し算と同じ様に扱うことができるのである(詳細な数式は他を当たるか自分で計算して下さい。というか、こういうのは自分で計算しないのであれば式で見ても文章の要約で見ても同じな気がする)。

さて、ここで P + P という演算について考える。PとQが限りなく近づく状態を想像すれば、P + P の結果は「Pにおける楕円曲線の接線」と楕円曲線の交点をx軸に対して対称移動した点ということがおわかりいただけただろうか。

これによりPを2倍するという演算が定義でき、さらにPを整数倍にすることが可能であるということがわかる。

離散対数問題

コンピューターに連続量は扱えない(浮動小数点数も整数と指数部の整数からなる)ので、コンピューターが暗号に用いることができるように、上記加法を「自然数という離散量」の有限体という範囲に落とし込む。 p で割った剰余を使う。

y² ≡ x³ + ax + b (mod p)

暗号では p には大きな素数が用いられる。

上記右辺について x は0以上 p 未満を考えればいいので有限である。 y は2乗して右辺と同じ剰余になる値ということで、やはり0以上 p 未満を考えればよく有限である。点(x, y)についても有限の範囲で考えれば良いので有限体という話である。

この点について上記楕円曲線の整数倍算を行う。接線とか交点とか求めようがないが、実際には上記のR'を求める時に行った代数的計算にあてはめる。解は整数でなく有理数になるが、除算を使って変換する方法があるので、上記有限体上の点に変換できる。

有限体の点の数は有限なので、1倍, 2倍, 3倍, …としていくうちに元の点に戻るときが来る。

「楕円曲線の離散対数問題」とは、有限体上の点Pとk倍した点kPが与えられた時に、kを求める問題である。

a, b, Pが特殊な値の組み合わせである場合を除いて、Pをk倍してkPを求める操作(繰り返し2乗法: binary exponentiation を使えばO(log n)の時間で到達できる)よりPとkPからkを求める方が難しいとされおり、kPに合致するまで1倍, 2倍, 3倍, …と試すしかないとされている。

「対数」なのに指数関数の逆関数でなくスカラー倍の逆関数なのは納得がいかないかもしれないが、もともとの離散対数問題が y ≡ g^x (mod p) においてp, g, y から x (≡ log _g y)を求める問題であるためこのように呼ばれる。