10月18日、pbxscience.comが「Claude Cracks a 25-Year-Old Cryptographic Mystery Behind NIST Curve Seeds in Under 30 Minutes」と題した記事を公開した。この記事では、AnthropicのAIモデルClaudeがNIST楕円曲線の「シード」の起源という25年来の暗号学的謎を30分以内に解明した事例について詳しく紹介されている。
NISTカーブのシードとは何か
ECDSA（楕円曲線デジタル署名アルゴリズム）は、TLSやSSHなど現代の暗号通信基盤で広く使われている署名方式だ。2000年にNISTがFIPS 186-2として標準化したP-192、P-224、P-256、P-384、P-521の5曲線には、それぞれ「シード」と呼ばれるパラメータが付随している。このシードのハッシュ値が曲線の係数を決定する仕組みだ。
問題は、これらのシードがNSA（米国家安全保障局）から提供されたものであり、その生成方法が公文書に一切記録されていなかったことだ。「NSAが意図的に弱い曲線を選んだのではないか」という疑念は、暗号コミュニティで20年以上くすぶり続けた。2015年には、当時の関係者であるNSA暗号研究者のJerry Solinasが「"give Bob and Jerry a raise"のような冗談めかしたフレーズが元になったかもしれない」と証言したが、記録は見つからず、Solinasは2023年に死去した。
Claudeが30分以内に解明したプロセス
Anthropicの社員が過去にこの「冗談フレーズ」の手がかりを元に調査したが成果は得られなかった。10月、ある社員が今度はそのフレーズへの言及なしに、内部研究モデルへシンプルに「シードはどう生成されたか」と問いかけた。Claudeは30分以内に全5曲線のシードの起源を特定した。
答えはシンプルかつ予想外のものだった。シードの生成には暗号学的ハッシュ関数ではなく、CライブラリのPRNG（疑似乱数生成器）であるlrand48にUnixタイムスタンプでシードを与えたものだった。手順は次のとおりだ。
- タイムスタンプ
tでsrand48(t)を初期化する - 20バイトずつ候補シードを生成し続ける
- 曲線生成条件を満たした候補を採用する
P-256の場合、1,842番目の候補が最終的に採用された。
Claudeがこの結論に至ったプロセスも読みどころだ。フレーズ探索が行き詰まると、Claudeは「1990年代のC言語ソフトウェアがどう動作するか」という観点から推論を転換した。各シードを5つの32ビットワードとして解釈すると、10シードのうち4シードで上位ビットがゼロになるパターンを発見した。この現象がランダムに起きる確率は約1/5,800で、これはlrand48が内部の48ビット状態の上位31ビットのみを返すことに起因する典型的なパターンだ。
素数体曲線（P-192等）のシードは出力ビットが少なく、内部状態の直接回復が難しい。そこでClaudeはLLL格子基底簡約アルゴリズム（Lenstra–Lenstra–Lovász）を適用した。これは切り捨てられた線形合同法の状態回復に使われる古典的な手法だ。ビットウィンドウの全パターンを試した結果、5つのNIST素数体曲線と5つのANSI X9.62シードすべてがlrand48() >> 23という同一パターンに従っていることが判明した。
「バックドア疑惑」への影響
回復された48ビット状態から160ビットのシードを完全に再現できたという事実は、偶然では説明がつかない。さらに決定的な証拠として、10の素数体曲線シードに対応するsrand48の初期値がすべて1997年5月〜1998年4月の間のUnixタイムスタンプとして解釈できる。プログラムはシステムクロックで弱い乱数生成器を初期化していたわけだ。
lrand48は暗号用途には不適切な古い生成器だが、ここでは秘密鍵ではなく公開パラメータの生成にのみ使われている。タイムスタンプベースの手順は誰でも再現可能であり、「出所不明のフレーズ」や「手動選定」よりも秘密の操作が介入する余地は少ない。元記事によれば、この発見は「意図的に弱い曲線が選ばれた説を支持する根拠にはならない」と評価されており、むしろNISTカーブへの信頼性を高める結果だとされている。
残る未解決事項
今回の解明は完全ではない。以下の点は依然として不明のままだ。
- P-256では1,842番目の候補が採用されたが、876番目の候補もすでに条件を満たしていたとされる。元記事はこの点を未解決事項として列挙しているが、なぜ条件適合の順番どおりに採用されなかったのかについての詳細な分析は示されていない
- B-163曲線のシードの特定
- P-224、P-256、P-384、P-521の基点（ベースポイント）の生成方法
なお、P-192を含む6曲線の基点については、大整数演算パッケージFreeLIPの乱数生成器で生成されたことをClaudeが突き止めており、これも初めて説明された成果だという。
AIによる研究支援の一例として
今回のタスクでClaudeが実行したことは、仮説の立案、コード生成、パターン認識、数学的アルゴリズムの適用、結果の検証という一連の作業を単一セッションで完遂したことだ。
人間の研究者が25年間解けなかった問題をClaudeが30分で解明した背景には、いくつかの構造的な要因が考えられる。まず、過去の調査は「冗談フレーズ」という証言に引きずられ、探索空間が誤った方向に絞られていた。Claudeはその先入観なしに問いに向き合い、1990年代のC言語実装という全く別の角度から推論を組み立てた。次に、LLL格子基底簡約のような数学的手法の適用と、上位ビットのゼロパターン検出のような統計的観察を一つのセッション内で組み合わせられる点も、人間が分業で進める研究とは異なる強みだ。問題の境界が明確で、データが公開されており、答えが再現可能な計算で検証できる——こうした条件が揃ったとき、現在のフロンティアモデルは高い効率で機能することを示す事例と言えるだろう。
※編集部の考察：ただし、この種の「先入観のなさ」と「広い探索能力」が有効に働くのは、検証基盤が整った問題に限られる点には留意が必要だ。
シード起源の発見に対して設けられていた36,864ドルの懸賞金は、Internet Security Research Groupに寄付される予定だ。
詳細はClaude Cracks a 25-Year-Old Cryptographic Mystery Behind NIST Curve Seeds in Under 30 Minutesを参照していただきたい。
