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

　NTTなどが海外の研究グループと共同で、公開鍵暗号の仕組みといえる大規模な素因数分解で世界記録を更新したという。解かれては困るRSA暗号などの解読に繋がることをあえて実行することに、どういう意義があるのだろうか。

NTTなど、公開鍵暗号の素因数分解問題で768ビット整数の分解に成功(ITpro)
NTTなど、「素因数分解問題」で世界記録更新--公開鍵暗号解読に一歩近づくか(CNET Japan)
公開鍵暗号の安全性の根拠である「素因数分解問題」で世界記録を更新（NTT)

　これまでの世界記録は663ビット、10進200ケタだったが、新しい世界記録は768ビット、10進232ケタまで更新されたという。素因数分解といえば、素朴なアルゴリズムとしては「エラトステネスのふるい」である。小さい数から素数を判定していき、その倍数を大きな数から消していくというやり方である。今回の新記録達成のアルゴリズムも、基本的にはそれを高度に発展させたものといえそうである。

　問題はそのプログラムの実行環境だろう。すなわち従来、単一プロセッサの環境を前提としてきたものが、現在ではディアルコアや並列プログラミングの環境が当たり前のようになってきたことである。「πの桁の計算」であればスーパーコンピュータの性能評価のように利用された時代もあったが、現在では「事業仕分け」ではないが、そうしたことが問題ではない。いかにネット環境で実行可能になるかどうかである。一昔前に（今でもやっているかもしれないが）話題になった「グリッドコンピューティング」で実行可能かどうかが問題になりそうである。ネットに繋がったPCの遊休のCPUを利用して大規模計算を実行してしまうというものである。NTTにもいくつかそうしたプロジェクトのテーマがあって、一般からも参加（遊休のCPUを提供するという意味で）を募っていたと思う。

　当時は、グリッドといっても自分の知らないうちにバックグラウンドで何かの計算が実行されているのは、何だかウイルスのようだ、と冗談半分に思っていたのだが、まさに現在はそれが現実化しつつある。それがボットネットである。一部の評価では大規模なボットネットの計算能力はスーパーコンピュータを凌駕するとまでいわれる。

　さてそうした中で、素因数分解の記録に挑むことは「実現しました。メデタシ、メデタシ」ではなくて、むしろ現在のRSA暗号の限界を評価することにあるという。現在の標準は1024ビットだが、それがどの程度、いつ頃まで安全と見倣されるかの評価である。そういえば暗号の2010年問題などというものもあった。すなわち素因数分解の記録としては「最高の結果」だが、RSA暗号の解読としてみれば「最悪の場合の評価」ということになる。それが1024ビットに対して768ビットに迫ったということである。もし同程度のアルゴリズムを持つ人間が最大規模のボットネットを利用してRSA暗号の解読を実行したとしたら、と想定するのが最悪のシナリオなのだろう。