九大、富士通研、NICTが次世代暗号の解読で世界記録を達成

九州大学、富士通研究所、情報通信研究機構（NICT）は2012年6月18日、次世代の暗号である「ペアリング暗号」について、鍵の長さが923ビット長の暗号解読に成功したと共同で発表した。このビット長は世界記録だという。発表を行った九州大学 マス・フォア・インダストリ研究所 教授の高木剛氏は「今回の成果は、（公開鍵暗号方式としてメジャーな）RSAに対する最高レベルの攻撃と同等だと思ってもらっていい」と語った。

ペアリング暗号は、公開鍵暗号方式の一つである楕円曲線暗号を発展させた暗号方式。ペアリングと呼ばれる数式を利用するのが特徴だ。ペアリング暗号を利用することで、任意のデータを公開鍵として利用できる「IDベース暗号」、データを暗号化したまま検索を行える「検索可能暗号」、アクセス制御が可能な「関数型暗号」といった最新の暗号技術を実現できる。

ペアリング暗号解読のこれまでの世界記録は、NICTと、はこだて未来大学が2009年に発表した676ビット長だったという。923ビット長の解読は、従来の解読技術では676ビット長の解読の数百倍の演算能力が必要だった。今回、新しい解析技術を用いることで、「汎用計算機21台（252コア）で148.2日」という現実的な時間で解読を達成した。これは、米Intel社のXeonプロセサ1コアに換算すると、102年分の計算量だという。

従来はデータを1次元空間で探索する「線形篩（ふるい）法」が使われていたが、これを2次元空間の探索に拡張した「格子篩法」を新たに用いることで、解読を効率化した。2次元空間に並べることで、解きやすい式に規則性があることを発見。これにより、ポイントを絞って解読を行えるようになり、数十倍の効率化を達成したという。これに加えて、「最適な初期値を選択する技術」「膨大な数値データから解を高速に計算する技術」「並列プログラミング技術」などを組み合わせて高速化を図った。

一般に、暗号の十分な安全性の目安は「その時点での世界最速のコンピュータ」と「最新の理論とプログラム」を使っても、解読に1年掛かることだという。今回の解読技術による923ビット長ペアリング暗号の解読は、スーパーコンピュータ「京」では13.6分の計算量に相当する。ここから、京の1年分の計算量に相当するのは1551ビット長であることを割り出した。3357ビット長のペアリング暗号であれば、今後、20年は安全だと見積もれるとした。

（日経エレクトロニクス　大森敏行）

[Tech-On！ 2012年6月18日掲載]