さて

これはmyjlabアドベントカレンダー第22日目の記事です。

私の担当回は1回目が（1か月前に）NRI Secure Netwars 2019に参加してきましたでオンサイトCTF初参加したよ,という感想記で,2回目がCpawCTFからやさしい問題を抜き出してみる回で初心者向けCTF記事でした。

といった感じで,CTFの話ばかりしていたのでたまにはIoTの話でもするかと思ったのですが,やっぱり鉄は熱いうちに食うべきなのでCTF関連で。今回は楕円曲線暗号で知られる楕円曲線および楕円曲線における離散対数性について考えてみたいと思います。

目標は,この記事を読んだ方が他の楕円曲線/楕円曲線暗号に関する文献や記事について読み始められるレベルに到達することとします。

できる限り暗号/数学について知らない人にも理解できるよう,高校数学レベルで読み解けるやさしい表現を心がけます。

簡単な理解のためのものであり,表現が厳密でない場合があります。

足し算ってなんだろうね。

楕円曲線 is なに

まず聞きなれない単語である楕円曲線について調べてみると,

y^2 = x^3 + ax + b

などの形で表される曲線のことで,非特異である（尖点を持ったり,自分自身と交叉したりしない）もの

といった記述が出てきました。

なるほどわからんがわかった。

見た目はこんな感じのものや

こんな感じのも。

楕円曲線上の2点を足す

はじめに,楕円曲線上での加法,つまり足し算について考えます。（普段使う数字の足し算とは大きく異なるものですが,加法の性質を持つため加法と呼ばれます）

ここでは楕円曲線をEとします。

E上のある2点A,Bをとったとき（すなわちA+Bを計算するとき）,その2点を通る直線がEと交わるもう一つの点C'をx軸に対し対称に移動した点Cをその加算結果とする,というルールがあります。

マジで何言ってるのかわからないので図示します。

下図は上の式においてa=3,b=4を代入したもの,すなわち

y^2 = x^3 + 3x + 4

をグラフにしたものです。（私のmatplotlib熟練度が低すぎてあまりにも酷いものになったのでコードは後日追記します）

図を見ながらもう一度確認すると,

E上のある2点A（図の黒い点）,B（マゼンタの点）をとったとき（すなわちA+Bを計算するとき）,その2点を通る直線がEと交わるもう一つの点C（青い点）をx軸に対し対称に移動した点C'（緑の点）をその加算結果とします。

つまり実際の流れとしては,黒い点とマゼンタの点を通る直線の方程式を求めて,その直線が楕円曲線と交わる点を求めて,得られた点のy座標に-1をかけてあげれば緑の点が求められそうですね。

同時に,定義および図から順序に関わりなく同じ結果が得られることがわかります(可換性がある)。

ふ,ふむう

とりあえずこれが何の役に立つのかはわからないがなんとなくわかった気がする,ぐらいで大丈夫です。

で,この不思議な足し算はわかったので,こいつをどのようにして暗号に使うのかというところまで行きます。

一つの点を足してみる

先ほどの足し算では異なる2点A,Bについて足すことを考えましたが,今度は同じ点同士を足し合わせることを考えます。

同じように楕円曲線上にある点を選び,その点を通る直線を引いて,楕円曲線と交わる点を反転させて……という処理を行えば良いのですが,選ぶ点が1つになるので,この場合は選んだ点を通る直線の代わりに接線を用いて考えます。(ここで上で示した楕円曲線の定義である非特異であるということが生きてきます。)

足し算の延長としての掛け算

ところで,我々が普段使う数字では数xと数xを足し合わせたとき,その結果を2xと表すことができますね。これと同様に楕円曲線上の加算においても同じ点Xを足し合わせた結果を2Xと表すことができます。

つまり

X+X=2X,X+X+X=3X,……

あるいは

X+X=2X,2X+X=3X,……

といったようにnXが計算でき,実質的に掛け算を行うことができると言えます。

無限遠点と巡回群

このパートは大変重い上,様々な証明を省略しているので読み飛ばしていただいても構いません。

最初の図をもう一度見ます。

足し算ができるようになったので,ちょっと考えてみたいのが,青い点と緑色の点を足すとどうなるかということです。

2点を通る直線が楕円曲線と交わる点について考えればいいから……あれ？

点,なくね？

いや,ないわけではないのですが,このグラフ上には示せないというのが比較的厳密な言い方でしょうか。とりあえず今は見えないですが,この点を無限遠点といい,Oで表されます。

あまり厳密な表現ではありませんが,楕円曲線における足し算ではこのOは普段の足し算での０と同様に扱います。

これについて詳しく説明を試みようとするとなかなかに大変なのでここでは割愛しますが,感覚的に理解を試みるのであれば,

青い点を点Rとしたとき,緑色の点はx軸に対し対称であるため,-Rと表記してみます。

この表記において,両者を足し合わせることは普段の足し算における

A+(-A)=0

と同様なものであると考えられ,

R+(-R)=O

となります。

また,証明は省きますが同じく

O + R ＝ R

が成り立ちます。

先ほどの一つの点を足し続けた足し算の結果をまとめると以下のようになります

X,2X,3X,4X,……,O

（色々省略しましたが）先ほど示した通り,Oに対し足し算を行うと

O + R = R

のように,足したものがそのまま帰ってきます。

つまり,

X,2X,3X,4X,……,O,X,2X,3X,……O

といった風に,XにXを足し続けると,Oを経由してぐるぐる循環すると考えられます。これを巡回群といいます。

また,OはXを足し続けた先に出てくると見ても良いですが,逆に言えば

{0,X,2X,3X,4X,……,O}

と考えることができますね。このように考えるとこの加法群（楕円曲線上）においてOが単位元であることがわかります。

これまで示したものをまとめると

グラフ・定義より

1. 可換であること（交換法則）

   R+(-R)=O
   

   より

2. 逆元が存在すること

   X+X=2X,X+X+X=3X,……
   

   X+X=2X,2X+X=3X,……
   

   より

3. 有限個の加算について,その順番を入れ替えても結果が変わらないこと（結合法則）

   O + R ＝ R
   

   より

4. 単位元が存在すること

以上4点が示されたので,これらに対し加法の性質を持つということがわかります。

これにより,なぜグラフ上で行ったり来たりする操作のことを「足し算」「加算」と呼んだか,ということがわかったかなと思います。感覚的に「足し算」とは大きく異なる処理ばかりでしたが,足し算の性質を持つという不思議な体験ができました。

楕円曲線の離散対数性

現実にこの計算を利用して暗号化する際には,楕円曲線上の群を考えるのではなく,有限体上での楕円曲線について考えますが,これについては割愛します。気になった方は調べてみてください。

ある点Aに対し,1A,2A,3A,……XA,……といった計算をすることが比較的容易である（上に示した計算を続けるだけ）のに対し,XAからXを導出するのは難しいという性質を用います。

実際にビットコインではSecp256k1という名前のついた楕円曲線を用いた暗号化がされています。

おわりに

これまでのアドベントカレンダーとはかなり毛色が異なる記事になりましたがいかがでしたでしょうか。誤りなどありましたらご指摘いただけると非常に助かります。

もうかれこれn年来の親友であるR氏にはこの記事を書く上で多くの助言をいただきました,本当にありがとう。

ちょうど１週間前のJupyterじゃなくてJupyterLabを勧めるN個の理由を読んでJupyter Labを使い始めたのですがタブ増えないのマジでサイコーですね。

あと前日の【foliumで可視化】近年ファミマ増えすぎな気がするがめっちゃよかったのでサイコーです。

参考

暗号技術入門第3版/結城浩
楕円曲線暗号の超簡単な理論の紹介