PR
写真1●今回解読した768ビット整数と素因数分解した素数
写真1●今回解読した768ビット整数と素因数分解した素数
[画像のクリックで拡大表示]
写真2●公開鍵暗号の安全性予測と今回の結果
写真2●公開鍵暗号の安全性予測と今回の結果
[画像のクリックで拡大表示]

 NTT情報流通プラットフォーム研究所は2010年1月8日、RSA暗号に代表される公開鍵暗号で安全性の根拠となる「素因数分解問題」において、欧州の研究機関と共同で768ビット整数(10進数表示では232桁)の素因数分解に成功したと発表した(写真1)。今回の成果は、鍵長768ビットの公開鍵暗号がどのくらいの計算能力と時間をかければ解読できるのかという安全性の指標を数量的に示したことにある。

 分解に成功したのはNTTのほか、スイス連邦工科大学ローザンヌ校(EPFL)、ドイツのボン大学、フランスの国立情報学自動制御研究所(INRIA)、オランダの国立情報工学・数学研究所(CWI)。今回の分解法は一般数体篩(ふるい)法と呼ぶもので、どのような整数の素因数分解にでも適用できる方式である。

 分解に要した計算資源は1700コア・年としている。デュアルコアのCPUを搭載したコンピュータなら、850台程度あれば約1年で分解できる計算になる。実際にはNTT情報流通プラットフォーム研究所など5研究機関は2007年から分解を始め、PCクラスターなど300台程度のコンピュータを用いて、約3年かかったという。

 現在、公開鍵暗号としては鍵長1024ビットのRSA暗号がよく使われているが、安全性の面から2048ビットへの移行が推奨されている。コンピュータの計算能力が向上するにつれ、暗号解読の攻撃技術が進化するため、暗号の安全性が低下するからだ。その目安として「この鍵長ならいつごろまで安全」といった専門家の予測曲線が知られている。今回の768ビット整数の素因数分解の成功は、こうした予測を裏付けるものになっている(写真2)。「現在、鍵長1024ビットの(RSA暗号のような)素因数分解型暗号を利用している場合には、現時点で危ないというわけではないので、次のシステムの更新タイミングでより安全な暗号に移行していただくのが適切」(NTT情報流通プラットフォーム研究所)という。より安全な暗号としては、2048ビット以上の素因数分解型暗号や224ビット以上の楕円曲線暗号を推奨している。

[NTTの発表資料]