公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新
~768ビット合成数を一般数体篩法にて完全分解に成功~NTT情報流通基盤総合研究所
NTTは、スイス連邦工科大学ローザンヌ校(以下、EPFL)、ドイツのボン大学、フランスの国立情報学自動制御研究所(以下、INRIA)、オランダの国立情報工学・数学研究所(以下、CWI)との共同研究により、わずかなビット数でも桁違いの計算量が必要となる素因数分解問題において、これまでの世界記録(663ビット、10進200桁)を大きく上回り、768ビット(10進 232桁)の合成数に対して一般数体篩法による素因数分解を達成し、世界記録を更新した。
研究の内容
今回の素因数分解は、巨大な合成数に対して現段階で最も高速な解法として知られている一般数体篩法により実現した。一般数体篩法は、多項式選択、篩(ふるい)、filtering、線形代数、平方根の5つのステップからなっている。このうち、篩と線形代数が最も計算量を要するステップである。各ステップにおいて、選択すべきパラメータが多数あり、このパラメータの選択によって計算量が大きく変化するが、その有効な選択方法については、まだ解明されていない。今回の共同研究では、このパラメータを適切に選択することにより、高速に計算することに成功した。以下、今回の分解におけるそれぞれのステップの概要を示す。
①多項式選択
今回は、2005年夏、ボン大学においてOpteron 2.2GHzをおよそ20年かけたのと同程度の計算量で探索して得られた多項式を選択。その後、2007年はじめにEPFLでさらによい多項式の探索を試みたが、Opteron 2.2GHz換算で20年かけたのと同程度の計算量を費やしても見つからなかった。
②篩(ふるい)処理
このステップは全体の計算量の大半を占めるが、比較的容易に分散計算可能であることから多数の参加組織により並列に計算を行った。今回の計算では、利用可能計算機のメモリ容量に応じいくつかのパラメータを準備。2007年夏から開始し2009年4月に終了した。篩処理は主にNTT研究所、EPFL、ボン大、INRIA、CWIの多種多様のPCやクラスタを用いた。全体ではおよそOpteron 2.2GHz換算で1500年かけたのと同程度の計算量を要した。
③filtering
EPFLにある10TBのハードディスクを備えた8コア計算機とクラスタを利用した。様々なパラメータで何度かやり直したことにより、Core2 2.66GHz換算で6カ月以下の計算量であった。
④線形代数(連立方程式の解法)
分散計算が困難なこのステップでは、今回、少数のクラスタを利用し、またそれぞれのクラスタの速度や空き時間が異なっていても効率的に計算できる手法を開発・利用した。NTT研究所及びEPFLのクラスタ、またINRIAはフランスにあるALADDIN-G5Kを効率的に用い、filteringで生成された疎行列からなる連立方程式を解いた。Opteron 2.2GHz換算でおよそ155年の計算量を要した結果、分解に利用可能な解が得られた。
⑤平方根(代数的数の平方根の計算及び最小公約数の計算)
このステップは数学的には高度な理論を用いるが、計算量はさほど要しない。EPFLに設置された計算機を用い、数時間で700ビットを大幅に超える素因数分界を達成した。
今後の展望
NTT研究所は暗号技術全般の安全性を継続的に評価していくとともに、次世代暗号として楕円曲線上の演算規則を利用した新しい公開鍵暗号方式「楕円曲線暗号」の普及にも努めていくほか、今後も、暗号理論から社会的影響まで幅広い領域におけるセキュリティ研究を推進し、ネットワーク社会の安心・安全を追求していくとしている。
NEWS(2010年2月)
NTTグループ関連
- 公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新(NTT情報流通基盤総合研究所)
- Googleマップを活用した業務用地図ソフトウエア「Geoffice」の販売を開始(NTTデータ)
- GaN系エピタキシャルウエハ製造を三菱化学に委託、量産化に対応へ(NTTアドバンステクノロジ)
- NTTコミュニケーションズと協業し、intra-martと連携したクラウド型メールサービスを提供(NTTデータ イントラマート)
- 技術プロフェッショナルによる人材育成部門「ソフト道場」を設立-実践で活躍できる人材育成を目指す(NTTソフトウェア)
- 検索するだけで環境保護活動を支援できる「緑のgoo」リニューアル(NTTレゾナント)
SIer・ベンダ
- トランスプロモ対応帳票システム「ePromo」のクラウドサービスを提供開始(CTC)
- 富士通と「SPARC Enterprise M3000」の性能を強化(サン・マイクロシステムズ)
- 仮想化を活用したシステム統合基盤における統合運用管理ソリューションで協業(日本オラクル)
- 効率的なデータ保護・回復を支援するソフトウェアを発表(日本IBM)
- システム基盤からアプリケーションまで統合する新ソリューションを開発(日本HP/マイクロソフト)
- アプリケーション・デリバリ・コントローラVIPRION搭載の最新ブレードを発表(F5ネットワークス)
- クラウド・コンピューティングを支えるITネットワーク統合パッケージ製品「Cloud Platform Suite」(NEC)
- データセンター向けに高性能、高拡張性、高可用性を兼ね備えたArista Networks社の10GbEスイッチ(東京エレクトロン デバイス)
- NGN対応テレビ会議アプリケーション「HelloMeeting」、NTT東日本の「フレッツ・ソフト配信サービス」で販売を開始(ソフトフロント)
- インテルAtomプロセッサを搭載したZabbix統合監視サーバの販売を開始(ミラクル・リナックス/ネクストコム・ジャパン)
- HDTV画質、Pアイリス制御機能を備えた最新のネットワークカメラ「P13シリーズ」を発表(アクシス)