楕円曲線

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

概要

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

楕円の周長を求める時に用いる楕円積分の逆関数を楕円関数と呼び、楕円関数の一種であるペー関数を局所で展開した時の式が楕円曲線の式に帰着できる、という私の祖父の兄の娘のいとこの叔父の孫よりも遠い関係があるといえばなくはないです。

用途

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

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

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

楕円曲線の加法

P

Q

R

R'

例として 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 には大きな素数(ex: ビットコインでは2²⁵⁶に近い値)が用いられる。

上記右辺について 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 k)の時間で到達できる)よりPとkPからkを求める方が難しいとされており、√p回くらいの計算を要する方法しかないとされている。(ex: ビットコインでは2¹²⁸くらいの回数)

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

シュノア署名

(雑にどんな感じのアルゴリズムかを説明するために、実際のシュノア署名とは細かい箇所が結構違うので注意すること。)

離散対数問題の困難性を実際に署名アルゴリズムとして実現するための方法には何通りかある。ここではシュノア署名について取り上げ、概要を説明する。

あらかじめ以下のパラメータを決めておく。

• 有限体上の楕円曲線E。
• Eの上のある点B。
• ハッシュ関数H。

公開鍵の生成は以下の通り。

1. xをランダムに選ぶ。A = xBとし、xを秘密鍵、Aを公開鍵とする。

署名プロセスは以下の通り。メッセージMがあり、これに対して秘密鍵xの所有者が署名を付けるとする。

1. kをランダムな整数とする。R = kBとする。
2. RとMから作られたハッシュ値をV = H(R || M)とする。(R || MはRとMを連接したデータを表す。)
3. S = k + Vxとする。
4. (R, S)を署名とする。

署名の検証プロセスは以下の通り。なお検証する側は、公開鍵Aはあらかじめ知っておくものとする。

1. (R, S)からSBとR + VAを計算する。なおVは先ほどと同じくV = H(R || M)である。
2. 両者が等しければ署名が正しいことを信用する。

Sが実際に署名プロセスによって作られていれば、SB = (k + Vx)B = kB + VxB = R + VAとなるはずである。

この方式を応用したEd25519という方式では、パラメータは以下の通り。

• 楕円曲線E: Curve25519(を変形したもの)。 y² ≡ x³ + 486662x² + x (mod 2²⁵⁵ - 19)
• H: SHA-512
• B: x座標が9である点(2個あるが、y座標が奇数である方。)

なお、この方式だと(R, S)からVを復元する方法はないことに注意。よく署名プロセスを「メッセージハッシュを暗号化」と誤って説明している文章を見かけるが、少なくともこの方式ではその説明は正しくない。

関連項目

• ≡

関連動画

関連項目

• RSA暗号 / 暗号 / SSL(TLS)
• ブロックチェーン / ビットコイン
• フェルマーの最終定理 / 数学
• 楕円積分 / 楕円関数
• 数学関連用語の一覧

参考

• 楕円曲線暗号アルゴリズムを理解する

補足

楕円曲線にはy = 0の時のxの実数解が3つの場合は上記のように円形と曲線で構成されるが、xの実数解が1つの場合は下記の例のように1本の曲線になる。

y² = x³ + 7