楕円曲線暗号をプログラムしたらこうなった

楕円曲線暗号をプログラムしたらこうなった


楕円曲線暗号についてまとめたいと思います。

この特定の暗号方式を指しているわけではなく、楕円曲線を使用した公開鍵暗号、署名、鍵交換の総称になるようです。

有名どころだとSSLの鍵交換や、ビットコインの楕円曲線を使用したデジタル署名に使われています。

RSAはだいたい鍵の長さが1024とか2048ですが、この楕円曲線暗号250程度の鍵長でRSAと同等の強度を持つと言われています。

今回は、楕円曲線暗号がどういうものでどのような動きをするのかを自分なりにまとめます。
そしてそれをいつか何かに役立てることをここに誓います。


楕円曲線暗号の演算


楕円曲線暗号は楕円曲線の演算を有限体上で行います。
有限体はpという素数があるとして0,1,2,3….p-1からなる整数の集合に演算を定義したものです。
有限体の詳しい説明はここでは省きます。

それを踏まえて以下のような公式があるとします。
y② = x③ + ax + b mod(223) 有限体上の楕円曲線
これは y② と x③ + ax + b をそれぞれ223で割ったあまりが等しいということを表しています。

この公式を使って楕円曲線上の点Gに対して2G(2*Gということです)、3G、4G…と演算を繰り返していくと多くの点が現れます。
例えば点Gをx = 47, y = 71, a = 0, b = 7だとします。
この点対して1Gから10Gまで計算すると以下のような結果になります。


点Gをを二倍(2G)するとx=36 y=111になりました。
数学的背景はさておき、具体的にどのような計算をしているのかプログラムを書いて高みの見物してみましょう。

実装


まず有限体の演算をしてくれるクラスを作成します。
言語は見た感じscalaですね。


有限体をある程度理解していれば特に難しいことはないかと思います。


そして楕円曲線上の演算をしてくれるクラスです。


先ほど例に挙げた演算はこのクラスの+メソッドが行っています。
以下のようにして計算できます。


これを実行すると先ほどと同じ結果が表示されるかと思います。

楕円曲線暗号の離散対数問題


この問題はなにを表しているかというと、
数xと点GがあるとしてこのふたつからxGを得ることは簡単だが、
xGから数xを求めることが難しいということです。

任意の点Gに2G,3G,4G…と繰り返し演算をすることで点が現れます。
先程もかきましたが、点Gをを二倍(2G)するとx=36 y=111になります。
これは数が小さいため数xを求めることはそれほど難しくはありませんが、
さらに巨大な数を使用した場合数xを求めることはとても難しくなります。

これが楕円曲線暗号の安全性の根拠だそうです。


ちなみにProgramming Bitcoin: Learn How to Program Bitcoin from Scratchを参考にしました。
この書籍はゼロからbitcoinを作ることをテーマにしています。
使用されている言語はPythonですが、ただ書き写すだけではつまらないかなと思ったので、Scalaで実装しました。

コメントする