明日から"知ったか"できる！？　速習！　楕円曲線！！

この記事はポート株式会社 サービス開発部 Advent Calendar 2024の11日目の記事です。

ポート株式会社で新卒２年目のinit-ikuyaです。大学では物理学を学んで、系の対称性の記述に群を用いたりしてきました。（群論はあまり得意ではなかったですが。。。笑）

本記事は、そんな僕が弊社のアルゴリズム勉強会中に見かけた楕円曲線というものについて書いてみたものです！

以下間違いなどありましたら指摘いただけますと幸いです

（以降、アドカレの記事として書く都合上、ですます調で書きます。数学をですます調で書くとムズムズしますが笑）

楕円曲線とは

まずは下の式と図を見てください
以下を満たすような点$(x,y)$の集合を考えます

$$y^2=x^3+ax+b\tag{1}$$

これを$xy$平面にプロットしてみると以下のような図を描きます

「全く楕円の形をしてねぇじゃねぇか！」と突っ込みたくなりますが、そもそも楕円曲線というネーミングは「楕円の孤の長さを計算する時に出てくる曲線」というニュアンスらしいので、お門違いです！

$a,b$の定数によっては離小島のような部分ができたり、逆に"おでき"のような部分さえなくなってしまうことがわかりますね

ともあれ、$(1)$式は楕円曲線の標準形と呼ばれるものになっています。本記事では簡単のため標準形のみを扱います！

楕円加算

で、なんとびっくり、この楕円曲線（に無限遠点を加えたもの）上の2点

$$P(x_1,y_1),Q(x_2,y_2)$$

には、以下のようなやや複雑な和を定義できます

1. 直線PQが$y$軸に並行でない場合$(x_1\neq x_2)$
   直線PQと楕円曲線が交わる点を$R$とすると、これを$x$軸に関して対称移動した点$R'$について
   
   $$P+Q\equiv R' \tag{2}$$
2. 直線PQが$y$軸に並行である場合$(x_1=x_2)$
   直線PQが$y$軸に並行であるとき、この直線は楕円曲線上の他の点と交差しないように見えるが、ここで無限遠点$O$を使う。無限遠点とは、イメージ的に$(x,y)=(0,\infty)$のことだと思っておけば良さそうです
   
   $$P+Q\equiv O\tag{3}$$
3. PとQが等しい場合
   $P(=Q)$を接点とする接線が楕円曲線と交差する点を$R$とすると、これを$x$軸に関して対称移動した点$R'$について
   
   $$P+Q\equiv R'\tag{4}$$
4. PとQのいずれかが無限遠点である場合
   （単に無限遠点は加法単位元であると割り切って考えてもいいですが）上記の①や③と同様に考えるなら「直線POが楕円曲線と交差する点はもう１つある。ここを$R$として、例の如く$x$軸に関して対称移動すると......当然$P$に戻ってくる」と考えても良いでしょう

$$P+O\equiv P\tag{5}$$

以下は少し別の画像で、筆者が描いたものでは無いですが、雰囲気をよく表していると思うので掲載します

このように定義される加算を"楕円加算"と言います

幾何学的に比較的わかりやすく定義されているんですが、誰がどうやってこんな和を思いついたんだ、と愕然としてしまいますね。。。

ちなみに、これは可換群になっています！ というのも、「直線を引いて、楕円曲線との残りの交点を探して、$x$軸に関して対称移動して......」という操作からわかるように可換性がある他、以下のように群としての性質を満たしているためです

• 結合法則が成り立つ（らしい）→（というのもこれの証明は難しい）
• 単位元がある → 無限遠点がこれにあたる
• 逆元 → $x$軸に対して折り返した点がこれにあたる

スカラー倍

ちなみに、和が定義できたのでここから自然にスカラー倍も定義できます。当然以下のように定義されます

$$kP\equiv P+\underbrace{\cdots\cdots}_{k-2個} +P\tag{6}$$

有限体上の楕円曲線

例えば暗号への応用、という文脈においては離散対数の計算困難性を用いたいので、巡回群が導入されます。（この辺の説明はWikipediaの離散対数 暗号への応用 項が分かりやすいです）
特に楕円曲線暗号の文脈では剰余を導入することで有限体を獲得し、これを達成します

巡回群？？　有限体？？　知らんがな、という方も次の例を見てください！

例

以下を満たす$(x,y)$を考えます

$$y^2=x^3+x+2\mod11\tag{7}$$

ただし、先ほどまでと違って$`11`$を法とし、自然数$x,y<11$に限ります。これによって先ほどまでは連続的な値をとれた$x,y$も、$(7)$式を満たすようなものは有限個に限られ、

$$\begin{aligned} (x,y)&=(1,2),(1,9),(2,1),(2,10),(4,2),(4,9),(5,0), \\ &(6,2),(6,9),(7,0),(8,4),(8,7),(9,5),(9,6),(10,0) \end{aligned}\tag{8}$$

となります

今、例えば$P=(1,2)$を基準点としてスカラー倍を考えると

$$\begin{aligned} 2P&=P+P=(10,0) \\ 3P&=2P+P=(1,9) \\ 4P&=3P+P=O \end{aligned}\tag{9}$$

となります

というのも、楕円加算は先述の通り幾何学的に行うことができるので加法の計算規則を導出するのは難しくなく、それは以下のようになるためです

1. $x_1=x_2$かつ$y_1+y_2=0\mod p$の場合、$P+Q=O$
2. それ以外の場合は
   
   $$P+Q=(\lambda^2-x_1-x_2,\lambda(x_1-x_3)-y_1)\tag{10}$$
   
   ただし、$x_3$は直線PQと楕円曲線のもう１つの交点の$x$座標
   • $P\neq Q$の場合、
     $$\lambda=\frac{y_2-y_1}{x_2-x_1}\mod p\tag{11}$$
   • $P=Q$の場合、
     $$\lambda=\frac{3x_1^2+a}{2y_1}\mod p\tag{12}$$

これにより、$(9)$式は簡単に確かめられますが、$3P=2P+P$だけ、ここで確かめておくきましょう

まず$\lambda=\frac{2-0}{1-10}=\frac{２}{-9}\mod 11$となりますが、そもそも$1/9\mod11$について考えると

$$\begin{aligned} 1/9&\equiv x\mod 11\\ &\Leftrightarrow\quad 1=9x\mod 11\\ &\Leftrightarrow\quad 9x+11y=1 \quad(y\in\mathbb{Z}) \end{aligned}$$

ここでユークリッドの互除法などを用いると$(x,y)=(5,-4)$が見つかるので

$$1/9=x=5\mod 11\tag{13}$$

これを用いると、$\lambda=\frac{2}{-9}=-2\times5=-10=1\mod 11$
よって$(10)$より

$$\begin{aligned} 3P&=(1^2-10-1,1(10-x_3)-0)\\ &=(-10,10-x_3)\\ &=(1,10-x_3)\quad(\because \mod 11)\\ &=(1,9)\quad(\because x_3は3Pのx座標と等しい) \end{aligned}\tag{14}$$

以上のように$(9)$式が確かめられます

今回は$(1,2)$を基準点にしたが、$(8)$式中の他の点を基準にしても同様の計算でスカラー倍が巡回することが確かめられますね！

楕円離散対数問題

そもそも、有限体上の楕円曲線が暗号に使われるのは楕円離散対数問題の困難性のためです。これは、「楕円曲線E上の点$P$と$Q$が与えられたとき、$Q=nP$を満たす整数$n$を求める」という問題を解くことが非常に困難なことによります

加法群であるために対数らしさを感じませんが、歴史的には乗法群の中で「$Q=P^n$となるような$n$を求める」という類の問題を離散対数問題と呼んできたらしく、それとのアナロジーから、対数っぽくはないけれども楕円離散"対数"問題、という名前で呼ばれているようです

まとめ

本記事を読んで以下3点を皆様に"知ったか"していただければと思います！

• 楕円曲線上に加法群が定義できる
• 有限体上に限ると巡回群になる
• 加法巡回群が楕円離散対数問題と呼ばれ、暗号の文脈で利用されている

今回は実際に暗号としてどのように利用されているかについては触れられなかったのですが、機会があればそういった記事も書いてみようと思います

ここまでご覧いただきありがとうございました

参考

• 暗号技術のすべて（IPUSIRON）
• ブロックチェーン技術概論 理論と実践