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

　NTTは1月8日、グループのNTT情報流通プラットフォーム研究所（NTT研究所）が海外の研究機関と共同で、公開鍵暗号の安全性の根拠となる「素因数分解問題」で世界記録を更新したことを発表した。

　これまでの世界記録は663ビット、10進200ケタだが、新しい世界記録は768ビット、10進232ケタで100ビット以上上回っている。独ボン大学、仏の国立情報学自動制御研究所（INRIA）、オランダの国立情報工学・数学研究所（CWI）と共同で研究した。

　素因数分解問題は、その難解さから現在公開鍵暗号として普及している「RSA暗号」の安全性の根拠になる。素因数分解可能なビット数の検証は、RSA暗号の安全性や強度の有効性をより精密に予測する上で極めて重要とされている。

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

　NTT研究所は、暗号技術全般の安全性を継続的に評価していくとともに、次世代暗号として、楕円曲線上の演算規則を利用した「楕円曲線暗号」の普及に務めていくとしている。

　素因数分解問題は、合成数を素数の積に分解するというもの。小さな合成数に対しては、短時間で素因数分解できるが、大きな数の場合、現実的な時間内に計算できることは困難といわれている。

　RSA暗号に使われるような、大きな2つの素数の積から構成される合成数の素因数分解法は「数体篩（ふるい）法」が用いられる。現在、RSA暗号に使われる合成数には「一般数体篩法」と呼ばれるやり方が高速とされている。今回の世界記録更新にも、この一般数体篩法を活用している。

　一般数体篩法は、「多項式選択」「篩」「filtering」「線形代数」「平方根」――という5つのステップから構成される。このうちの篩と線形代数が最も計算量を要するステップとされる。各ステップで選択すべきパラメータが多数存在し、パラメータの選択で計算量が大きく変化するが、有効な選択方法はあまり解明されていないという。今回の共同研究では、このパラメータを適切に選択することで、高速に計算することに成功したとしている。