Bitcoinでも使われている楕円曲線暗号について

楕円曲線とは

楕円曲線暗号は，楕円曲線を利用した暗号です．"楕円"とは言っても楕円の形はしておらず，下図のように横に見るとタコのような形ですね．

また，次の方程式で表されます．式の形から(x)軸対称な図形であることがわかります．

$$ y^2 = x^3 + ax + b $$

さて，楕円曲線にどのようにして暗号の機能をもたせることができるのでしょうか．それを理解するためには，群論を少しかじっている必要があります．群論と言っても，難しい事を理解する必要はありません．

楕円曲線上の点はアーベル群をなす

アーベル群

群論自体の基礎については，びりあるさんのブログ投稿「これから群論を学ぶ方のための入門講座」が詳しいです．以後，このブログの内容を前提として進めます． 群の種類のうち，アーベル群（可換群，加法群）というものがあります．これは，整数全体の集合などが，加法（足し算）に対してなす群です．

楕円曲線上の加算

楕円曲線の上での足し算は次のように定義されます．

楕円曲線上に２点P, Qがあるとき，その和は，直線PQと楕円曲線とのP, Q以外の交点とx軸に対して対称な点である．

図にすると下のような感じです．

なんだか変な定義ですが，このように定義すると，楕円曲線上の点は，演算「＋」について，アーベル群を成します．つまり，以下の４つが成り立ちます．

1. P + Q = Q + P（交換法則）

2. (P + Q) + R = P + (Q + R)（結合法則）

3. 単位元Oが存在する．この場合，単位元は無限遠の点である．

4. 任意の元に対して，逆元が存在する．この場合，Pに対する逆元はPとx軸対称の点

1.は２点を結ぶ順番は関係がないことから成り立つことはわかると思います．2.も同様です． 3.は，Pと-P（Pについてx軸対称な点）を結ぶ直線を考えます．Pと-P以外に直線が楕円曲線と交わる点は存在しませんが，それを無限に遠い場所で交わると考え，点Oとします． 4.は今述べたようにPに対する-Pを逆元と考えています． このように，「楕円曲線上の有理点はアーベル群をなす」ことが言えました．

離散対数問題

離散対数問題（discrete logarithm problem）という，公開鍵暗号の原理になっている問題があります．これを少し簡略化して説明すると，xからyを計算するのは容易だが，yからxを求めるのは非常に困難であるという数学的性質のことです． 楕円曲線上の点がなす群においても， 離散対数問題を作ることができます．それは以下のような問題です．

ある楕円曲線上の点Gから，G+G=2G，2G+G=3G,... のようにnGが計算できる．ある定数nと点Gが与えられたとき，nGを計算するのは容易だが，GとnGを与えられた時にnを求めるのは非常に困難である．

掛け算についての群ならば，その名の通り「対数」，logについての問題なのですが，今回はアーベル群（足し算についての群）なので，割り算（nG/G=n）の問題となっています． 以上のような楕円曲線上の離散対数問題は，ビットコインの秘密鍵で署名を行うときに利用されています．みなさんが意識しないうちに，楕円曲線上の演算を利用して，秘密鍵から公開鍵を生成しています．秘密鍵から公開鍵を生成するのは容易でも，公開鍵から秘密鍵を生成するにはスーパーコンピューターでも数百年，数千年とか買ってしまうので，安全です．つまり，公開鍵を知られてもビットコインを盗まれないのは，楕円曲線暗号のおかげなのです．

量子コンピュータ

量子コンピュータは，並列計算が得意なので，ECDSAでも容易に解けてしまうようになるそうです．するとビットコインが盗まれてしまい大変だと思うかもしれませんが，それにはもう対策案が提案されているようです．