記事検索

768bit合成数の素因数分解に成功、NTTらが世界記録更新


 NTTは8日、公開鍵暗号の安全性の根拠である「素因数分解問題」において、768bit(10進232桁)の合成数に対して、「一般数体篩(ふるい)法」による素因数分解に成功したと発表した。従来の記録である663bit(10進200桁)を上回り、世界記録を更新した。

 今回の記録は、NTTがスイス連邦工科大学ローザンヌ校(EPFL)、ドイツのボン大学、フランスの国立情報学自動制御研究所(INRIA)、オランダの国立情報工学・数学研究所(CWI)との共同研究によって得られたもの。素因数分解にあたって利用した「一般数体篩(ふるい)法」は、巨大な合成数に対して現時点で最も高速な解法で、今回の共同研究では多項式選択や篩(ふるい)など5つからなるステップに対して、適切なパラメータを選択することで高速に計算することに成功したという。

 NTTによれば、公開鍵暗号として現在広く用いられている「RSA暗号」は素因数分解の難しさを安全性の根拠としている。このため、素因数分解が可能なbit数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上できわめて重要だとしている。

 今回、700bitを超える素因数分解を達成したことで、NTTではRSA暗号で広く使われている1024bitの素因数分解も近い将来に達成される可能性があることを示唆していると説明。このことから、より強度が高く効率的な暗号技術を利用する必要性が高まっているとした。

 NTTでは、暗号技術全般の安全性を継続的に評価する考え。加えて、次世代暗号として、楕円曲線上の演算規則を利用した新しい公開鍵暗号方式である「楕円曲線暗号」の普及にも努める考えだ。


関連情報

(村松 健至)

2010/1/8 19:27

INTERNET Watch ホームページ
Copyright © 2016 Impress Corporation. All rights reserved.