NTTなどが素因数分解問題で世界記録更新

cryptography

NTTらの研究チームががRSA暗号に使われている素因数分解問題で世界記録更新を出したようです。

NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号解読に一歩近づくか:ニュース - CNET Japan

これまでの世界記録を大きく上回る700ビットを超える素因数分解が可能になったが、これは将来的にRSA暗号で使われている1024ビットの素因数分解も達成できる可能性があることを示唆するものと注目される。その延長線上として、RSA暗号より強度が高く、より効率的な暗号技術を利用する必要性も高まるだろうと、NTTは見ている。

普段使われている1024ビットにだいぶ近づいてきましたね。NTTのプレスリリース「公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新」によると、解を求めるためのステップごとの計算量が書いてあるので、これを抜粋すると下記のような感じになります。

（1）多項式選択 → Opteron 2.2GHz換算で20年
（2）篩（ふるい）処理 → Opteron 2.2GHz換算で1500年
（3）filtering → Core2 2.66GHz換算で6カ月以下
（4）線形代数（連立方程式の解法） → Opteron 2.2GHz換算でおよそ155年
（5）平方根（代数的数の平方根の計算及び最小公約数の計算） → 数時間

これを見る限り、計算量的にはまだ１つのCPUで1700年弱くらいはかかるようなので、どこかの国に狙われたりしない限りは、すぐに現在の1024ビットRSAが危ないということはなさそうですね。