Cognitionは9月9日、同社の研究者Eric Lu氏が自社のコーディングエージェント「Devin」を使い、RSA因数分解チャレンジにおいて現時点で公開されている最大記録となるRSA-260の分解に成功したと発表した。従来の記録RSA-250は2020年2月に樹立されて以来、6年半にわたり破られていなかった。
RSA-260は260桁の10進数で、130桁の素数2つに分解される。使われたアルゴリズム自体は目新しいものではなく、1990年代から大きな整数の分解における標準手法である一般数体篩法(GNFS)がそのまま使われている。変化があったのは実装層だ。一連の処理がCPUクラスタからGPUへと移された。
4900GPU日の内訳
Cognitionが示した内訳は、多項式選択に643GPU日、格子篩に3813GPU日、線形方程式の求解に467GPU日。篩の工程だけで全体の4分の3以上の計算資源を消費しており、GNFSに典型的な傾向と一致する。
鍵となる成果物は、CUDAで書き直された「glas」というGPU格子篩エンジンだ。改造版CADO-NFSと、GPU向けに最適化されたブロックWiedemannアルゴリズムを組み合わせている。Cognitionによれば、この実装によって篩処理の単位コストは約1桁引き下げられたという。
CADO-NFSは、2020年にフランスのチームがRSA-250を分解した際に使ったオープンソースソフトウェアと同一だ。コードベースは同じで、ハードウェアの土台だけが変わった。その6年間の差が、この2組の数字に表れている。
Devinがここで担ったのはエンジニアリング作業であり、数学的な発見ではない。コードの最適化、パラメータ調整、クラスタ管理などだ。Cognitionは公表文の中でこれを「計算数論とGPU性能エンジニアリングの境界にある課題を解決できる、十分に優秀なソフトウェアエンジニア」と表現している。
人間の関与についても数字が公開されている。233セッション、指示に用いた語数は8万2702語。1セッションあたり平均300語強で、コードレビューのコメント1件分に近い分量だ。無人運転だったわけではなく、1人の人間が、連続稼働できるツールを操りながら、かつてはチームが数カ月がかりで調整していたエンジニアリング作業を3週間に圧縮した形だ。
外挿するとどうなるか
Cognitionは2つの外挿値も示しており、いずれも現在のGPU価格に基づく概算と明記されている。RSA-1024の難易度はRSA-260の約78倍で、コストは約3000万ドル。RSA-2048の難易度は9.12兆倍で、コストは3.77×10の16乗ドルとされている。
最初の数字は注目に値する。3000万ドルという規模は、国家機関はもちろん大企業でも支払える水準だ。RSA-1024は標準規格ではすでに非推奨とされているが、組み込み機器、旧版ファームウェアの署名、保守されていない一部の証明書チェーンにはこの鍵長がまだ残っている。この2つの数字の間にある約10億倍の差こそが、2048ビットが今なお安全とされている理由のすべてだ。
記録の歴史を振り返ると、1999年のRSA-155分解は約8000MIPS年、2009年末のRSA-768は2.2GHzのOpteronコア1つ換算で約2000年、2020年のRSA-250は2700コア年、そして今回は13.5GPU年となっている。最初の3回の進歩は主にムーアの法則とアルゴリズムの調整によるもので、ペースはおおむね10年に1段階だった。今回の飛躍では、ハードウェア世代交代と「誰がCUDAコードを書くのか」という問題が重なり合っている。
まだ分かっていないこと
論文やコードを完全に公開するのか、glasをオープンソース化するのかについて、Cognitionの発表では触れられていない。独立した第三者による再現もまだ行われていない。RSA-250の際は複数のチームが篩のパラメータを相互検証したが、今回の結果は現時点で一者のデータしかない。
分解結果そのものの検証は容易だ。2つの素数を掛け合わせればよい。検証が難しいのはコストの内訳の方だ。4900GPU日に使われたのはどのGPUモデルで、単価はいくらで、失敗した試行分はカウントされているのか——発表文はこれらを項目ごとに分解していない。40万ドルという数字がセキュリティ評価にとってどんな意味を持つかは、これらの詳細次第だ。
参考資料：Cognition公式テックブログ、caramba.loria.frのRSA-250分解発表、CocoLoop。GPU日とコア年の数値は各発表の原文表記のまま引用しており、統一換算は行っていない。