30年間、空白だった場所

画像: eprint.iacr.org より
ECDSA の NIST 曲線は、現代の公開鍵暗号のど真ん中にある。P-256 は特に使われ方が広く、Web の証明書まわりでも頻出だ。その一方で、曲線パラメータの一部には seed が付いていて、そこから曲線係数を導く仕組みになっていた。問題は、その seed がどう作られたのか誰もはっきり説明できなかったことだ。

画像: www.anthropic.com より

たとえば P-256 の seed は C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 という 160 ビットの値として公開されている。見た目はただの16進数列だが、背景にはずっと不穏な空白があった。NSA が持ち込んだが、選び方は説明されていない。だから長年、「意図的に弱い曲線を入れたのではないか」という疑いが消えなかった。暗号の世界では、こういう空白はそれだけで疑念を育てる。

この疑問に対して、これまでの有力な説は「英語の一文を SHA-1 でハッシュしたものではないか」だった。実際、Jerry Solinas がそんな趣旨のことを話したという証言も出ていた。たとえば「Jerry deserves a raise」や「Bob and Jerry rule」のような、ちょっとした洒落をハッシュにしたのではないか、という話だ。Bounty まで用意され、パスフレーズ当てのような探索が始まった。

みんなが追っていた“ハッシュ説”

ただ、この説は妙に手触りがいいぶん、逆に怪しかった。もし本当に英語の文なら、カウンタの有無、句読点、改行、大小文字まで候補が無数にある。P-256 のような seed 1 個を狙うだけでも、当時の記憶違いに引きずられる余地が大きすぎる。Stephen A. Weis の整理でも、Jerry Solinas は seed を提供した本人としてはかなり確からしいが、肝心の生成法は本人の記憶からも消えていた可能性が高かった。

そこで 2023 年、秘密の文を総当たりする代わりに、別方向の賞金付き探索が始まる。焦点は「何を入力したか」ではなく、「どういうソフトで seed が出たのか」だった。これが重要だった。曲線の seed は、いきなり神秘的な文字列として現れたわけではないかもしれない。1990年代の C ライブラリが持つ疑似乱数生成器の出力なら、むしろ機械的な痕跡が残るはずだ。

この時点で狙いはかなり絞られていた。もし 1990年代の典型的な PRNG なら、今見れば出力の癖がある。出力の一部が切り詰められていたり、上位ビットに偏りが出たりする。つまり、seed の並びを「人間の文」として読むのではなく、「古い乱数生成器の断片」として読むわけだ。

乱数っぽさには、癖が出る

Anthropic の報告で面白いのは、Claude が最初から正解を知っていたのではなく、古い PRNG の“出力らしさ”を探る形で進んだ点だ。公開された seed の断片を 1 ビットずつずらしながら、1990年代のジェネレータの連続出力として整合するかを試したという。34 通りの組み合わせを確認し、そこで奇妙な規則性が見えた。

その一つが、binary 曲線用の 4 本の seed に含まれる 32 ビット語、計 20 個のすべてで最上位ビットが 0 だったことだ。これが偶然で起きる確率は 1/5,810 とされている。暗号の値としては小さい話に見えるが、こういう偏りは「ハッシュされた文」ではなく「疑似乱数生成器の出力」を疑うには十分だった。さらに、これは 48 ビット状態から上位 31 ビットだけを返す lrand48 の癖と一致する。つまり、seed が雑に作られたのではなく、ある種の古い乱数生成器の丸見えの跡かもしれない、ということになる。

ここから先の入り口も、英語の一文を探すのとはだいぶ違う。binary 曲線の seed なら、最初の 32 ビット語について隠れている 17 ビットを全部試し、次の語が続くかを見ればよい。P-256 を含む prime 曲線の seed は 1 出力あたり上位 8 ビットしか使っていないので、総当たりではなく別の道具が要る。それでも最終的には、P-256 は時刻で初期化した 1 回の実行の中で作られた 1,842 番目の曲線候補だった、という形で再現されたとされる。しかも他の曲線でも似たパターンが出た。単発の偶然ではなく、複数の seed に同じ癖が出たわけだ。

ここで疑問が変わる

もし seed が lrand48 の出力なら、次に気になるのは「いつ、何で初期化されたのか」になる。ここが本丸だ。srand48 の初期状態は低 16 ビットが 0x330E になる形をとるが、それだけなら 65,536 回に 1 回はたまたま一致しうる。だから“それっぽい”だけでは弱い。しかし、十個の prime-curve seed についてたどると、初期化時刻が 1997 年 5 月から 1998 年 4 月にきれいに収まった、というのが Anthropic の報告だ。binary-curve 側は 1984 年 2 月に対応し、二倍にすると 1998 年 4 月 17 日に合うものもあったという。

このへんで、話は単なる昔話ではなくなる。P-256 の seed が「何か面白い文章のハッシュ」ではなく、「Unix 時刻で初期化した古い PRNG の出力」だったとしたら、長年の疑いの形そのものが変わるからだ。しかもその時点で、seed の起源を理解するために必要なのは、ハッシュの元文探しではなく、1990年代の C ライブラリの挙動、出力の切り詰め、ビットの偏り、そして初期化時刻の復元になる。

ただし、ここから先はまだ話が終わっていない。seed の正体が見えたとしても、曲線にはもう一つ別の“固定点”がある。ベースポイント G だ。seed とは別に、これがどう作られたかも同じくらい気になる。Anthropic の報告では、P-192 と ANSI X9.62 のいくつかの曲線について、FreeLIP 由来の乱数生成器を使った生成元まで追えたとされる一方、P-224、P-256、P-384、P-521 のベースポイントは説明しきれていない。

seed が lrand48() の出力なら、何回まわして、どの時刻から始めれば P-256 の値に届くのか。その「1,842 番目」という数字が何を意味するのか。上位ビットの偏りと時刻復元が、どこまで確実で、どこから推測なのか。そこを見ないと、この発見の重みはまだ半分しか見えていない。

👉 続き（核心はここから）は PaPoo で読めます: https://papoo.work/doc/cc2a84257f7091ea