Aggressive Style 5

Aggressive Style 5

昨今はコミケ関係を中心に書いています。同人やニコニコ動画方面で活躍される方の相互リンクをお待ちしています。

PS3はやはりすごい!?楕円曲線の計算をもこなすその姿

暗号学者ヨッパ・W・ボス (Joppe W. Bos)、マルセロ・E・カイハラ (Marcelo E. Kaihara)、トルステン・クラインユング (Thorsten Kleinjung)、アリエン・K・レンストラ(Arjen K. Lenstra)、ピーター・L・モンゴメリ (Peter L. Montgomery) の発表によると、112 ビットの楕円曲線上の離散対数問題の解を求めることに成功、新記録を出したという (スイス連邦工科大学、暗号アルゴリズム研究室の発表記事、本家 /. 記事より) 。

前回の記録は 109 ビット暗号の解読で 2002 年 10 月にさかのぼる。今回のプロジェクトはスイス連邦工科大学ローザンヌ校 (EPFL)にある200 台を越える PS3 を利用して計算が行われた (前回、MD5 衝突攻撃による偽 SSL 証明書の作成に使われたものと同じ設定) 。PS3 上では、今回の問題を解くための計算量は 56 ビット DES のキーサーチを 14 回行うのに相当するものだ。(スラッシュドットより)

PS3を使って数学の楕円曲線に関する計算を行った人がいるとか。ここでまず引用にある楕円曲線の離散対数問題について説明したい。

楕円曲線

楕円曲線とはxy平面上において,y^2=x^3+ax+bを満たす曲線の事を言う。例えばy^2=x^3-4xという曲線をfunction viewを使って描画してみると左のようになる。


y^2=x^3-4xの式


ここで楕円曲線y>0のときは、y=\sqrt{x^3-4x}y<0のときは、y=-\sqrt{x^3-4x}という式になる。つまりx軸に対して対称な曲線となり、今回はこの性質を用いる。

楕円曲線の加算



ここでもう一つ必要な話を。楕円曲線の加算とは以下のような操作を言う。

  1. 直線Ay=mx+nを、楕円曲線Cと交点を持つように引く。
  2. AとCの交点を2つみつける。さらにみつけたものをP(x_1,y_1),Q(x_2,y_2)とする。
  3. P,QからRのx座標を求める。求める際にはCのyに、直線のyを代入し解と係数の関係よりRのx座標を求めることができる。
  4. Rのx軸に対して対称な点を取り、それをP+Qとする。この時x軸対称であるためP+Qは必ずC上に存在する。

楕円曲線の加算と離散対数問題

ここでP=QのときRは、Pに関する接線が楕円曲線と再び交わる点となり,R=P+P=2Pと表現できる。さらにR=P+P+P=2P+P=3Pこのように、どういう規則で点が動くのかが分かりづらい様子となる。



今回は複数回加算を行って3Pを得た。逆に楕円曲線上の点P,Qと整数iが与えられ,Q=iPとなるi。つまりPからQに至るまで何回加算を行ったかを調べる問題を離散対数問題という。

一般にa,b,P,Qの各座標値には整数を用いて計算される。今回の実験ではa = 4'451'685'225'093'714'772'084'598'273'548'424 ,b = 2'061'118'396'808'653'202'902'996'166'388'514というとてつもない整数で実験。P、Qも(188281465057972534892223778713752,3419875491033170827167861896082688)、
(1415926535897932384626433832795028, 3846759606494706724286139623885544)というバベルの塔もできるような気の遠い数字。PからQに至るまで312521636014772477161767351856699回加算を行えば良いという結論が出されたらしい。



ちなみにPS3を200台の様子。こいつらを連結することに依り、2009.1〜2009.7の6ヶ月間で仕上げたらしい。どのような方法で解を見つけたのか。一回一回しらみつぶしで探すにしても、どういった方法で200台に分散処理をしたのかは分からないので、追って調べてみようと思う。

ちなみにこの楕円曲線。「nを3以上の自然数とする。この時x^n+y^n=z^nを満たす自然数の組(x,y,z)は存在しない」というフェルマーの最終定理の証明にも用いられているらしい。このように整数を扱った問題は本当に奥深い事が思い知らされる。

参考文献