こんにちは！ @tsum_tsum です！
先日公開した「カーネルトリックは何が"トリック"なのか？？？」は想像よりも皆さんにご覧いただき、感謝とともに Qiita のコミュニティーの凄さを実感したところであります。元数学屋さんとして、好きな数学コンテンツを中心に書きつつ、皆さんに楽しく読んでいただける記事にできればと思っております。
第 2 回目は"楕円曲線"について解説していきたいと思います。実は、楕円曲線には個人的に思い入れがあったりします。ちょうど大学 4 年生頃に当時の担当教授の部屋にあった本で、「読んでみたい」と言った本が梅村浩先生の「楕円関数論: 楕円曲線の解析学」でした。
ちなみに、楕円と言ってはいますが、皆さんが想像している楕円が直接出てくるわけではありません。 紹介した著書のタイトルにある楕円関数というのは、楕円の弧長を計算するときに現れる楕円積分というものの逆関数として発見された関数のようです。このことは今回の議論に特に影響しませんので、気にしなくて読み進めていただいて構いません。
そんな思い入れのある楕円曲線なのですが、数学を離れてエンジニアになってからというもの、当然出会うはずもないと思っていました…。しかし、なんと暗号に使われているそうではありませんか！！！当時、基本情報技術者試験の勉強をしていた私は、急に数学屋の血が騒ぎ、基本情報技術者試験どころではなくなってしまいました。（勉強しろよ）
今回はそんな楕円曲線について、暗号理論に関わる部分について解説できればと思います！
はじめに
なお、注意点ではありますが、本記事は 楕円曲線を中心にして、暗号に関わる部分を抜粋して解説 していきます。 暗号そのもののアルゴリズムについては解説いたしません。 暗号そのものの解説になってしまうと、言葉の定義を厳密に理解できておらず、誤解を生む表現をする可能性が高いためです。筆者の力不足ではございますが、あらかじめご了承いただければ幸いです。
参考文献
参考記事を記載しております。ご興味のある方は是非こちらもご覧いただければ幸いです。
楕円曲線とは？
そもそも楕円曲線とは何でしょうか？楕円曲線とは下記のように表される曲線のことです。
y^2 = x^3 + ax + b.
参考文献や記事によっては、下記のように表されることもあります。
y^2 = ax^3 + bx^2 + cx + d \ (a \ne 0).
ただし、$y \rightarrow a^2y, x \rightarrow ax - \frac{1}{3}b $ とすることで、上記の式に変換することが可能ですので、$y^2 = x^3 + ax + b$ が一般的な定義です。この一般的な定義の形は Weierstrass の標準形 と言われています。（特に覚えなくても大丈夫です。）
この定義だけだと分かりにくいですので、実際にどんなグラフになるのか見てみましょう。例えば、
y^2 = x^3 -x +1, \
y^2 = x^3 -2x
を考えると、それぞれこのようなグラフになります。
コードはこちらに書いております。
import matplotlib.pyplot as plt
import numpy as np
x = np.arange(-2, 2, 0.001)
y1_pos = np.sqrt(x**3 - x + 1)
y1_neg = -np.sqrt(x**3 - x + 1)
y2_pos = np.sqrt(x**3 - 2*x)
y2_neg = -np.sqrt(x**3 - 2*x)
# グラフを作成
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 6))
# y^2 = x^3 - x + 1 のグラフ
ax1.plot(x, y1_pos, color='blue')
ax1.plot(x, y1_neg, color='blue')
ax1.set_title('y^2 = x^3 - x + 1')
ax1.set_xlabel('x')
ax1.set_ylabel('y')
# y^2 = x^3 - 2 のグラフ
ax2.plot(x, y2_pos, color='blue')
ax2.plot(x, y2_neg, color='blue')
ax2.set_title('y^2 = x^3 - 2')
ax2.set_xlabel('x')
ax2.set_ylabel('y')
plt.show()
$a, b$ の値によって、
- たんこぶのような形
- 円と放物線が別々になったような形
になったりしますね。さて、何となくの概形が分かったところで、もう少し数学的に定義してみます。
楕円曲線をもう少し深堀していく
そもそも、"グラフ"とは何でしょうか？ ノードとエッジで定義されるやつではありません。 グラフとは実は集合のことです。例えば皆さんが中学生の頃に書いた $y = x^2$ のグラフというのは、$y=x^2$ を満たす座標の集合 を書いてると考えることができます。つまり、
\{ (x, y) | \ y = x^2 \}
を座標平面上に書いてるんですね。楕円曲線も同じように考えることができます。先ほどグラフに書いた $y^2 = x^3 -x +1$ は、
\{ (x, y) | \ y^2 = x^3-x+1 \}
と考えることができます。
なお、本記事ではこの楕円曲線を $E$ と表します。またこの楕円曲線に無限遠点 $\infty$ を追加した集合を楕円曲線と呼ぶことにします。なので、$E$ は下記のように表されます。
E = \{ (x, y) \in \mathbb{R}^2 \ | \ y^2 = x^3 +ax+b \} \cup \{ \infty \}.
ちなみに $\mathbb{R}$ という記号が出てきましたが、これは実数の集合を表しています。が、今回はそんなに気にしなくても構いません。厳密に楕円曲線について理解したい場合は重要なポイントになるのですが、なくても楕円曲線の面白さは伝わるかと思い、詳しい説明は割愛します。数学ガチ勢の皆さんごめんなさい。
$(x,y)$ なんだから、$\{ \infty, \infty \}$ じゃないのか…とかちょっと鋭い人は感じるかもしれませんが、$\{ \infty \}$ で大丈夫です。本当は射影空間という空間を使って考えた方が、楕円曲線の見通しはより分かりやすくなります。
例えば、無限の記号を使わずに無限遠点を定義できます。そうしてもいいのですが、定義があまりに増えてしまうのも大変かと思い、今回は割愛いたしました。$\{ \infty \}$ は、$x$ も $y$ もどんな点よりも遠い場所 くらいに思っていただければ、本記事では特に問題ないかと思います…。
ここまでは、楕円曲線について説明していきました。では、この曲線と暗号がどのように関係しているのでしょうか？それを説明するために、まずは足し算掛け算について考えていきましょう。
今更足し算掛け算の勉強？
先ほど、「まずは足し算掛け算について考えていきましょう。」と述べましたが、急に何を言い出すのかと思われたかも知れませんね。もちろん足し算掛け算のことを思い出してもらうために振り返るということではありません。
しかし、楕円曲線を使った暗号を理解する上で、 あえて足し算掛け算について少し振り返った方が、後々の説明が理解していただきやすい かと思いました。既にお分かりの方にとっては少し退屈かもしれませんが、もう少しお付き合いください。
では、足し算掛け算について、その性質を考えてみましょう。まずは足し算に注目してみます。足し算は下記のような特徴を持っているはずです。
- 整数同士の足し算の和は整数
例）$3 + 5 = 8, \ (-2) + 1 = -1$ など - 整数の足し算は順番によらない
例）$(2 + 4) + 7 = 2 + (4 + 7)$ など - 足しても元の値と変わらない整数が存在する（$0$ の存在）
例）$4 + 0 = 4, \ 0 + (-5) = -5$ など - 足すと $0$ になる整数が存在する
例）$2 + (-2) = 0, \ (-6) + 6 = 0$ など
これだけ見ると、当たり前じゃないか？と思われるかもしれませんが、 そういう性質だけを抜き出して、面白い性質を探していくところも数学の面白いところ ですね。一方掛け算に注目すると、1～4のうち成り立たないものが存在します。
- 整数同士の掛け算の積は整数になります
例）$3 \times 5 = 15, \ (-2) \times 1 = -2$ など - 整数の掛け算は順番によらない
例）$(2 \times 4) \times 7 = 2 \times (4 \times 7)$ など - 掛けても元の値と変わらない整数が存在する（$1$ の存在）
例）$4 \times 1 = 4, \ 1 \times (-5) = -5$ など
ここまでは順調ですね。しかし、残念ながら4は成り立ちません。条件4は、ある整数に対し、掛け算の積が $1$ になる整数が存在するかどうかですが、
2 \times x = 1
となる $x$ は 存在しません ね。「いやいや！$0.5$ が存在するじゃないか！」と仰られるかもしれませんが、$0.5$ は整数ではありません ね。ちなみに、整数のところを有理数に読み替えると、掛け算でも1～4がちゃんと成り立ちます。なので、1～4が成り立つかどうかは 「集合（整数とか有理数など）」 と 「演算（掛け算や足し算）」 の2つを考慮する必要があることがお分かりいただけるかと思います。
群とは？
先ほど、「集合」と「演算」に注目することによって、整数の足し算掛け算の不思議な性質を見ていきました。これらの性質は現代では "群（Group）" という概念で説明されます。では実際に群の定義を見ていきましょう。さて、「集合」と「演算」に注目するんでしたね。集合を $G$ 、演算を $*$ とします。このとき、下記の $1$～$4$ の定義を満たす $(G,*)$ を群といいます。（$(G,*)$ を $G$ と略記することが一般的です。）
- 任意の $a, b \in G$ に対し、$a * b \in G,$
- 任意の $a, b, c \in G$ に対し、$(a * b) * c = a * (b * c),$
- 任意の $a \in G$ に対し、$e \in G$ が存在して、$a * e = e * a = a,$
- 任意の $a \in G$ に対し、$b \in G$ が存在して、$a * b = e.$
例えば、
- $G=\mathbb{Z}$ （整数の集合）, $*=+$ とすれば、$(G, +)$ は群である
- $G=\mathbb{Z}$ （整数の集合）, $*=\times$ とすれば、$(G, \times)$ は群でない（$4$ が成立しない）
- $G=\mathbb{Q}$ （有理数の集合）, $*=\times$ とすれば、$(G, \times)$ は群である
のようになります。ちなみに定義 $3$ で出てきた、$e$ ですが、これを単位元と言います。
- $(\mathbb{Z}, +)$ であれば $e=0$
- $(\mathbb{Q}, \times)$ であれば $e=1$
となるわけですね。
ここまで群について詳しく説明していきました。「集合」と「演算」の満たす性質に目を当てた面白い数学的概念だと思っていただければ嬉しいです。
さて、そもそも楕円曲線の話をしていたんですね。それにも関わらず、いきなり群の話をするとはどういうことなのか？と思われたかもしれません。いよいよその謎が解けます。なんと楕円曲線は群になるのです！ 次の章では楕円曲線が群になること、そして群になるための演算がどんなものか？について解説していきます。
楕円曲線の世界の"足し算"
楕円曲線ファンの方お待たせいたしました。ではここから、楕円曲線をただの「集合」から「群」に進化させていきましょう。楕円曲線はこんな式でしたね。
E = \{ (x, y) \in \mathbb{R}^2 \ | \ y^2 = x^3 +ax+b \} \cup \{ \infty \}.
$P, Q \in E$ とします。そして楕円曲線 $E$ の世界の"足し算"を $\oplus$ としておきます。このとき $\oplus$ を次のように定義します。
- $P, Q$ を直線で結ぶ
- 1で結んだ直線と $E$ にもう一つの交点 $R'$ ができる
- $R'$ と $x$ 軸に対称な点を $R = P \oplus Q$ とする
…。ブラウザバックはもう少しお待ちください。これだけではあまりにも分かりにくいですよね。なので下に図を表示しておきます。
まず $P \ne Q$ の場合は、この図に書かれた $R$ の座標が $P \oplus Q$ です。
$P$ と $Q$ を結ぶと、$E$ ともう一つの点で交わります。（ここでは $R'$ としてます。）$R'$ と $x$ 軸で対称な点を $R = P \oplus Q$ とするわけですね。
また、$P \oplus P := 2P$ は $P$ の接線を考えることで定義されます。
$E$ の点 $P$ における接線を考えると、もう一つの点と交わります。あとは同じように $x$ 軸で対称な点を $R = 2P = P \oplus P$ とします。
そして、交点がない場合もありますね。その場合にようやく $\infty$ の出番です。接線がない場合は $P \oplus Q = \infty$ と定義します。
最後に $P$ の接線と $E$ の交点がない場合があります。この場合は、$P \oplus P = 2P = \infty$ とします。
これにて、$\oplus$ の定義は完了です。ちなみに $P \oplus Q$ がどんな座標になるの？と思われた方もいらっしゃるかもしれませんが、こちらは補足にて説明いたします。
$\infty$ に関する定義が色々と出てきたのでまとめておきましょう。合わせて $\infty$ の"足し算"も合わせて定義しておきます。
- 直線 $PQ$ と $E$ の交点がない場合、$P \oplus Q = \infty$
- 点 $P$ の $E$ における接線と $E$ の交点がない場合、$2P = \infty$
- $\infty \oplus P = P \oplus \infty = P$
そうすると、なんと $(E, \oplus)$ は群になります！！！つまり、下記の1～4を満たすんですね！
- 任意の $P, Q \in E$ に対し、$P\oplus Q \in E,$
- 任意の $P, Q, R \in E$ に対し、$(P \oplus Q) \oplus R = P \oplus (Q \oplus R),$
- 任意の $P$ に対し、$\infty \in E$ であって $P \oplus \infty = \infty \oplus P = P,$
- 任意の $P$ に対し、$Q \in E$ が存在して、$P \oplus Q = \infty.$
この4つの中で、1と3は先に述べた通りです。また、4について述べると、$P \oplus Q = \infty$ となる点 $Q$ は $P$ と $x$ 軸で対称な点でしたね。2に関しては、少し計算が長くなってしまいますので割愛させてください。決してめんどくさいわけではない
まぁ、これが群になってるなんて…。すごい演算ですよね。どこからこんな演算が思いつくの？と思われるかもしれません。これにはもちろん理論的背景があるのですが、あまりにも難しすぎるのでここでは割愛します。難しすぎて解説できない
で、暗号の話は？
話が複雑になってきましたので、楕円曲線について一旦整理しましょう。ここまで下記のようなことを確認していきました。
- 楕円曲線の定義
- 群を構成するためには「集合」と「演算」が必要であること
- 楕円曲線に"足し算"を導入すると、楕円曲線が群になること
さて、これらの話と暗号の話がどう関わって来るのでしょうか？そのヒントは $2P=P \oplus P$ です。
これまでの内容を読んでいただいたのであれば、$2P$ を計算することができるかと思います。振り返ると、$2P$ とは、下記の手続きで得られるんでしたね。
- 点 $P$ における $E$ の接線を引く
- この接線と $E$ の交点のうち、$P$ でない方を $R’$ とおく
- $R’$ と $x$ 軸に対称な点が $2P$ である
すると、次に $3P$ を計算することもできるはずです。$3P = 2P \oplus P$ ですね。以下帰納的に、$nP = (n-1)P \oplus P$ を定義することができます。まぁ頑張って線を引いて…とすれば何とか計算できそうです。
一方、$P, Q$ が与えられて $P = nQ$ を満たす $n$ を求めなさいと言われると事情が変わってきます。何だか難しそうな感じがしてこないですか？（圧）
これを楕円曲線の離散対数問題というそうです。あらかじめ $P$ を設定しておきます。$n$ を秘密鍵、$nP$ を公開鍵にすることで、通信の安全性を担保するようです。なお、詳しい解説については参考文献を参照ください。
まとめ
今回は楕円曲線暗号に使われている楕円曲線と楕円曲線に定義される不思議な"足し算"について説明していきました！
数学の世界とエンジニアの世界って、（いる世界によっては）あまり繋がりを感じられないことが多いので、個人的には寂しいところです。しかし、こうやって色んなところに数学的な概念が利用されていることが分かると、やっぱり数学って素晴らしいなと感じますね。そして、それを数式から読み解いて理解できるのは、数学屋さんの特権な気もしています。
今回は2度目の投稿ということで、機械学習から一度離れてみましたがいかがでしたでしょうか？
今後も数学的な内容を皆さんにお伝えできればと思っておりますので、次回もまたご覧いただければと思います！！！
また次回お会いしましょう！
補足（具体的な R の座標）
$P(x_p,y_p), Q(x_q, y_q), R'(x'_r,y'_r), R(x_r, y_r) \ (x_p \ne x_q)$ とします。直線 $PQ$ の式は下記のようになります。
y = \frac{y_p - y_q}{x_p - x_q}(x -x_p)+y_p.
これを $y^2=x^3 +ax+b$ に代入すると、
\
\left(
\frac{y_p - y_q}{x_p - x_q}(x -x_p)+y_p
\right)^2
=x^3 +ax+b
ですね。さて、$x^2$ の係数に注目すると、解と係数の関係より
x_p + x_q + x'_r = \left(\frac{y_p - y_q}{x_p - x_q} \right)^2
になります。よって、
x'_r = \left(\frac{y_p - y_q}{x_p - x_q} \right)^2 - x_p - x_q
となりました。$x=x'_r$ を代入すれば、$R'$ の座標が求まります。
y'_r = \frac{y_p - y_q}{x_p - x_q}(x'_r - x_p)+y_p.
最後に $x$ 軸で対称な点を取れば完成です。
\begin{eqnarray}
x_r &=& \left(\frac{y_p - y_q}{x_p - x_q} \right)^2 - x_p - x_q, \\
y_r &=& - \frac{y_p - y_q}{x_p - x_q}(x_r - x_p)- y_p.
\end{eqnarray}
お疲れ様でした。