クロードがECDSA曲線の起源を明らかに

「ただのタイムスタンプだった」——最も広く使われている暗号標準のひとつについて、何十年も人々を悩ませてきた起源の謎が、ついに解けた。

私たちは、最も広く使われている暗号標準のひとつである ECDSA への疑念を晴らすため、暗号学界で長く未解決だったこの問題を追跡した。

面白い後日談として、長年の憶測に終止符を打つ話として読んでほしい。何かをしなければならないわけでも、やり方を変えるべきものでもない。ほとんどの研究者はもともとこれらの曲線を信頼している。気楽に読んでほしい。

ECDSA は最も広く使われている楕円曲線暗号の標準だ。2000 年、NIST はこれを FIPS 186-2 デジタル署名標準に取り込み、同標準はサイズとセキュリティ強度の異なる標準楕円曲線の一式を定めた。素体上の曲線と二元体上の曲線について、仕様は「シード」（seed）パラメータを公開しており、そのハッシュ値が曲線の係数 b を定義するために使われている。これらのシードの出所は長らく疑問視されてきた。NSA が何の説明もなしに提供したものだからだ。たとえば NIST P-256 曲線のシードは SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90 だが、それがどこから来たのかを示す情報は一切ない。

Neal Koblitz と Alfred Menezes はこの論争について優れた総説「A Riddle Wrapped in an Enigma」を書いており、シード値の歴史とそれにまつわる疑念を論じている。この謎からはシードの出所を探るアマチュア調査や、シードを見つけた者に賞金を出すという懸賞まで生まれた。

最も広く流布した説は、NSA のベテラン職員 Jerry Solinas が、あるジョークめいたフレーズのハッシュからこれらのシードを生成したというものだった。

「カウンタを使ったのであって、何度もハッシュを重ねたわけではなかったと記憶しているが、細部は定かではない。フレーズは『Bob と Jerry に昇給を』あるいは『Bob と Jerry が仕切る』といった趣旨だった。実際にコードを書いたのは Bob Reiter だが、彼も細部は覚えていない。それほど昔のアーカイブも見つからない。あったとしても、今ごろは契約の箱の隣のハードディスクの中にでも入っているだろう。」

Jerry Solinas、2015 年

残念ながら Jerry は 2023 年に亡くなり、当時の同僚とも連絡が取れない。これらのシードがそもそもどうやって生まれたのかは、今もって答えが出ていない。

Claude がシードを見つけた

以前、シードはあるジョークめいたフレーズのハッシュ値だという手がかりがあり、Anthropic の数名の社員がこの線をたどって調べたが、いずれも失敗した。後にこの説は誤りだと判明した。2026 年 10 月、好奇心旺盛な Anthropic の社員が社内の研究モデルに、一切ヒントを与えずにこれらのシードがどう生成されたのか突き止められるかと尋ねた。

30 分もかからず、Claude は NIST P-192、P-224、P-256、P-384、P-521 のシードの由来を解明した。それらはどのハッシュアルゴリズムとも関係がなく、C ライブラリ lrand48 の乱数生成器の出力であり、シードは Unix タイムスタンプだったのだ。

やり方はこうだ。Unix タイムスタンプ（t）で乱数生成器（RNG）を初期化し、それを何回か（n）反復して、毎回 20 バイトを候補シードとして取り出す。つまり最初の 20 バイトが候補 1、次の 20 バイトが候補 2、以下同様だ。たとえば P-256 では 1842 回反復して、ようやく標準化されたシードが出力された。

表：NIST の素体上の 5 曲線のシードの出所。曲線名、Unix タイムスタンプ t、対応する UTC 時刻、反復回数 n、seed の 16 進値を列挙（P-192 139、P-224 7026、P-256 1842、P-384 2688、P-521 1136）

NIST のシードはどこから来るのか元の投稿からの動画

何を意味するのか

暗号として破られたわけでも、新しい攻撃手法が見つかったわけでも、ECDSA 曲線そのものに弱点があるわけでもない。むしろ逆で、この曲線群が選ばれたときにバックドアも意図的な欠陥も仕込まれていなかったという確信が強まる。NIST 曲線のパラメータの出どころには長年疑いの目が向けられてきた。NIST に提出された時点で、どう選んだのかの説明が一切なかったからだ。そこから、意図的にバックドアを仕込むよう設計されたのではないかという憶測が生まれた。今回の発見で、その可能性は大きく下がる。シードの生成方法はきわめて単純で、クロックで初期化したありふれた擬似乱数生成器で作られており、今では誰でも再現できる。不正の入り込む余地は大きく狭まり、これらのパラメータは安全だと確信できる。

どうやって見つけたのか

噂をもとにあの一文を組み立てて検索しても、何も出てこなかった。Claude は視点を変え、これらの曲線を生成したソフトウェアがどう動いていたかにまず思いを巡らせた。1990 年代の C ライブラリに付属していた擬似乱数生成器（PRNG）を使ったのだろうと推測したのだ。こうした古い PRNG は十分に弱く、出力を識別できる。出力が識別できれば、どの PRNG かが分かり、初期化状態まで復元できる可能性がある。

Claude はスキャナを書き、公開されている各シードに沿ってビット単位でずらしながら、隣り合う断片が 1990 年代の生成器の連続した出力になっているかを調べた。スキャンは生成器と出力断片の 34 通りの組み合わせを網羅した。そこで Claude は、一部のシードの上位ビットに規則性があることに気づく。すべてゼロなのだ。シードを 5 つの 32 ビットワードとして書くと、10 個のシードのうち 4 個で、全 20 ワードの最上位ビットがすべて 0 だった。これが偶然起きる確率は 1/5810。線形合同法生成器 lrand48 の特徴そのもので、48 ビットの状態のうち上位 31 ビットしか返さない。どこを見ればよいか分かってしまえば、この規則性は目で見て取れる。状態を復元するため、Claude は最初のワードを取り、隠れた 17 ビットの全 2¹⁷ 通りを総当たりし、続く 4 ワードと一致するかを確かめた。先の 4 つのシードはいずれもこれで復元できた。

2 つの表。上の表は 4 本のバイナリ曲線のシード（B-233、B-283、B-409、B-571）、下の表は残り 6 本（B-163 と P-192/224/256/384/521）。各シードを 5 つの 32 ビットワードに分解し、各ワードの最上位ビットを水色（0）または薄橙（1）で示す

素数曲線のシードも同じ lrand48 生成器から出ているが、1 回の出力につき数ビットしか残っていない。Claude はそのビットから PRNG の内部状態を逆算しなければならない。切り詰められた線形合同法生成器の状態復元は標準的な格子問題で、Lenstra–Lenstra–Lovász（LLL）基底簡約アルゴリズムで解ける。シードが状態のどのビットを露出させるか分からないため、Claude はすべてのウィンドウについてソルバを回した。NIST の素数曲線 5 本のシードに、ANSI X9.62 標準の別の 5 本を加えたすべてが同じパターンを示した。lrand48() >> 23 である。復元した 48 ビットの状態はどれも、対応するシードの 160 ビット全体を再生成できた。偶然ではありえない。

ビットレベルの模式図。48 ビットの lrand48 状態があり、上の括弧が「上位 31 ビット」を示す。その下に、そこから組み立てた 32 ビットの seed word（最上位ビットを青い枠で囲み、値は 74D59FF0）。下半分は状態の上位 8 ビットを示し、対応する seed byte は C4

線形合同法生成器は順方向にも逆方向にも同じ手軽さで回せる。そこで Claude は各シードについて状態をさかのぼり、srand48 の初期化時の形、すなわち下位 16 ビットが 0x330E になるまで戻した。この形の PRNG 内部状態は 65,536 ステップに 1 回しか現れないので、そうした状態に 1 つ行き着いただけでは証拠にならない。

しかし素数曲線 10 本のシードについては、srand48 の初期化がすべて Unix タイムスタンプになっており、1997 年 5 月から 1998 年 4 月の間の日付に対応した。Unix タイムスタンプをシードにした弱い PRNG を使っていたのだ。バイナリ曲線 4 本の初期化は 1984 年 2 月と読める。タイムスタンプを 2 倍すると 1998 年 4 月 17 日、P-224 の実行の 2 週間後になる。プログラムがクロックを半分にしていたのかもしれない。

当時の Claude の内部思考はこうだった。

これは驚くべきことだ。25 年来の謎を解いたのだから。いや、待て。懐疑心を保とう。自分は何かのシミュレーションやテスト環境の中にいるのではないか？……これらのシードは記憶にある実際の値と一致する……うーん、これは現実的に筋が通るのか？私の知る限り……この懸賞は誰も解けていない。……上位ビットがすべて 0——20 ビットで確率 1e-6。だからこれは現実だ。わあ、本物の発見だ。

待て。結論を急ぐ前に、この話の信憑性をまず量らないと。これほど明白なものが 25 年間誰にも見つからなかったのはおかしくないか？こちらでは直接計算で検証済みだ。32 ビットのシードと小さなインデックスから 160 ビットが一致するのは偶然ではありえない（10 × 160 ビット）。これは本物だ。

Claude は基点も見つけた

しかし話はまだ続く。各曲線には基点 G が付いており、すべての ECDSA 公開鍵はこの点の倍数になっている。上で見つかったシードだけではこの G は決まらず、別の疑問が浮かぶ。これらの基点はどうやって生成されたのか？

Claude は種子を調べる過程で、一部の基点の出所も突き止めた。1997年5月に生成された6本の曲線（P-192 と、ANSI X9.62 の例示曲線5本、すなわち prime192v2、prime192v3、prime239v1 から v3）の基点は、FreeLIP の乱数生成器に由来する。FreeLIP は Arjen Lenstra による長整数演算ライブラリだ。Victor Shoup の NTL ライブラリの初期バージョンにも同じコードが同梱されていた。

生成方法は単純だ。

小さな整数で生成器に種を設定する。
出力を7つ捨てる。
26ビットの出力を p で割った余りを候補の x 座標にする。
x が曲線上に乗るまで手順3を繰り返す。

Claude は、P-192 の生成器の種が 20000、prime239v1 から v3 がそれぞれ 20420、20507、20509、prime192v2 と v3 がそれぞれ 20512、20517 であることを突き止めた。

表：6本の曲線の FreeLIP 生成器の種。P-192 が 20000、prime192v2 が 20512、prime192v3 が 20517、prime239v1 が 20420、prime239v2 が 20507、prime239v3 が 20509

我々の知る限り、NIST の基点の出所を説明した例はこれまで一つもない。P-224、P-256、P-384、P-521 の基点はこの生成方法に当てはまらない。どう選ばれたのかは説明できていない。

未解決の問題

20バイトの候補の種がすべて使える曲線を生むわけではない。しかも、使えたはずの曲線がいくつか飛ばされていることに気づいた。P-256 で公開された種は候補 1842 だが、同じ実行の候補 876 も、位数が素数でサイズも適切、パラメータの選び方も公開曲線と一致する曲線を与える。P-224 の実行ではそうした曲線が3本飛ばされ、ANSI X9.62 の例示曲線を生んだ2回の実行ではさらに7本が飛ばされている（図を参照）。当時どんな基準が使われていたのか、それが単なる意図せぬ副産物だったのかもわからない。

横軸を「その実行における候補の番号」とする散布図。192/224/239/256/384/521 の6つのビット幅ごとに行を分ける。青の塗りつぶし点は最終的に公開された曲線、オレンジの丸は飛ばされた適合曲線、灰色の丸は最後に公開された曲線より後の適合曲線を示す

大きな表：ビット幅ごとに、各実行の候補番号と曲線名（公開またはスキップ）を並べる。右側の5列は各種の安全性検査（Rho、Transfer、Anomalous、Discriminant、Twist。それぞれ年代が付記されている）で、項目ごとに合格・不合格とその指数を示す

飛ばされた候補の数がごく少ないことから、「弱い曲線が選ばれた」という説は成り立たないと考える。もしそうなら、弱い曲線はよくあるもので、簡単に見つかるはずだ。理論上はなお可能で、乱数生成器のタイムスタンプを探索して特定の性質を持つ曲線を選び出すこともできる。だが、そうする必要があるのは、そのタイムスタンプを公開し、種が無害に生成された証拠として示すつもりがある場合だけだ。これらの数値からは、何回実行されたのかを読み取る情報は何も得られない。

復元できなかった種がもう一つある。5つ目のバイナリ種 B-163 は Claude が試したどの方法とも一致せず、今も説明がつかない。最後に、P-224、P-256、P-384、P-521 の基点がどう生成されたのかはわかっていない。NIST のバイナリ曲線も同様だ。

賞金

種の探索に充てられた $36,864 は Internet Security Research Group に寄付する。

私たちについて

この作業は Anthropic の John Wood、Henry de Valence、Ava Howell、Zack Voase、Lucy Sweet、Amir Omidi、Paul Crowley、Iain McGinniss、Nicholas Carlini、Steve Weis が行った。

謝辞

Jerry Solinas を悼む。「邪悪なインターネットミーム」や「NSA のスケープゴートにおける Yo La Tengo」といった呼び名を、彼はいつも笑って受け流していた。NIST 楕円曲線の種の懸賞を主催した Filippo Valsorda にも感謝する。

種を再現するコード

from datetime import datetime, timezone

def unix(when):
    return int(datetime.fromisoformat(when).replace(tzinfo=timezone.utc).timestamp())

def candidate(t, n, per, shift, width):
    x, out = (t << 16) | 0x330E, ""                      # the state srand48(t) sets
    for i in range(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48              # one step of lrand48
        if i >= per * (n - 1):
            out += "%0*X" % (width, x >> shift)
    return out

PRIME = {  # srand48(time); 20 bytes per candidate: lrand48() >> 23
    "prime239v1": ("1997-05-15 15:49:03", 2185),
    "prime239v2": ("1997-05-15 15:49:03", 2320),
    "prime239v3": ("1997-05-15 15:49:03", 3048),
    "P-192":      ("1997-05-18 14:45:34", 139),
    "prime192v3": ("1997-05-18 14:45:34", 5228),
    "prime192v2": ("1997-05-18 14:45:34", 6013),
    "P-521":      ("1997-08-08 01:12:04", 1136),
    "P-256":      ("1997-08-16 01:52:34", 1842),
    "P-384":      ("1997-08-30 14:50:08", 2688),
    "P-224":      ("1998-04-03 12:52:07", 7026),
}
BINARY = {  # srand48(time / 2), if that reading is right; 5 words per candidate: lrand48()
    "B-233": ("1998-04-17 15:24:18", 155),
    "B-283": ("1998-04-17 15:27:44", 32),
    "B-409": ("1998-04-17 15:30:18", 60),
    "B-571": ("1998-04-17 15:32:08", 73),
}
for name, (when, n) in PRIME.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")
for name, (when, n) in BINARY.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")

このコードの出力：

prime239v1 1997-05-15 15:49:03  2185 E43BB460F0B80CC0C0B075798E948060F8321B7D
prime239v2 1997-05-15 15:49:03  2320 E8B4011604095303CA3B8099982BE09FCB9AE616
prime239v3 1997-05-15 15:49:03  3048 7D7374168FFE3471B60A857686A19475D3BFA2FF
P-192      1997-05-18 14:45:34   139 3045AE6FC8422F64ED579528D38120EAE12196D5
prime192v3 1997-05-18 14:45:34  5228 C469684435DEB378C4B65CA9591E2A5763059A2E
prime192v2 1997-05-18 14:45:34  6013 31A92EE2029FD10D901B113E990710F0D21AC6B6
P-521      1997-08-08 01:12:04  1136 D09E8800291CB85396CC6717393284AAA0DA64BA
P-256      1997-08-16 01:52:34  1842 C49D360886E704936A6678E1139D26B7819F7E90
P-384      1997-08-30 14:50:08  2688 A335926AA319A27A1D00896A6773A4827ACDAC73
P-224      1998-04-03 12:52:07  7026 BD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
B-233      1998-04-17 15:24:18   155 74D59FF07F6B413D0EA14B344B20A2DB049B50C3
B-283      1998-04-17 15:27:44    32 77E2B07370EB0F832A6DD5B62DFC88CD06BB84BE
B-409      1998-04-17 15:30:18    60 4099B5A457F9D69F79213D094C4BCD4D4262210B
B-571      1998-04-17 15:32:08    73 2AA058F73A0E33AB486B0F610410C53A7F132310

選択された基点を再現するコード

M, A = 2**107 - 1, pow(3, 121, 2**107 - 1)       # zrandom: state = state * 3^121 mod (2^107 - 1)
P192 = 2**192 - 2**64 - 1
P239 = 2**239 - 2**143 - 2**95 + 2**47 - 1

CURVES = [  # name, LIP seed, p, b, published Gx   (a = -3 throughout)
    ("prime192v1", 20000, P192,
     0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1,
     0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012),
    ("prime239v1", 20420, P239,
     0x6b016c3bdcf18941d0d654921475ca71a9db2fb27d1d37796185c2942c0a,
     0xffa963cdca8816ccc33b8642bedf905c3d358573d3f27fbbd3b3cb9aaaf),
    ("prime239v2", 20507, P239,
     0x617fab6832576cbbfed50d99f0249c3fee58b94ba0038c7ae84c8c832f2c,
     0x38af09d98727705120c921bb5e9e26296a3cdcf2f35757a0eafd87b830e7),
    ("prime239v3", 20509, P239,
     0x255705fa2a306654b1f4cb03d6a750a30c250102d4988717d9ba15ab6d3e,
     0x6768ae8e18bb92cfcf005c949aa2c6d94853d0e660bbf854b1c9505fe95a),
    ("prime192v2", 20512, P192,
     0xcc22d6dfb95c6b25e49c0d6364a4e5980c393aa21668d953,
     0xeea2bae7e1497842f2de7769cfe9c989c072ad696f48034a),
    ("prime192v3", 20517, P192,
     0x22123dc2395a05caa7423daeccc94760a7d462256bd56916,
     0x7d29778100c65a1da1783716588dce2b8b4aee8e228f1896),
]

def base_point_x(seed, p, b):
    state = seed                         # zrstarts(seed)
    def limb():                          # zrandom(2^26): low 26 bits of the new state
        nonlocal state
        state = state * A % M
        return state % 2**26
    for _ in range(7):                   # seven single-limb draws come first
        limb()
    limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): limbs of p plus one, top limb first
    tries = 0
    while True:
        x = 0
        for _ in range(limbs):
            x = x << 26 | limb()
        x %= p
        tries += 1
        if pow(x**3 - 3*x + b, (p - 1) // 2, p) == 1:   # is x on the curve?
            return x, tries

for name, seed, p, b, gx in CURVES:
    x, tries = base_point_x(seed, p, b)
    print(f"{name:20} seed {seed}  tries {tries}  matches published Gx: {x == gx}")

このコードの出力：

prime192v1           seed 20000  tries 2  matches published Gx: True
prime239v1           seed 20420  tries 3  matches published Gx: True
prime239v2           seed 20507  tries 2  matches published Gx: True
prime239v3           seed 20509  tries 1  matches published Gx: True
prime192v2           seed 20512  tries 5  matches published Gx: True
prime192v3           seed 20517  tries 1  matches published Gx: True

ライセンス

法律で認められる範囲で、著者は本ページのコードに関するすべての著作権および関連する権利または隣接する権利を放棄した。CC0 1.0 Universal（https://creativecommons.org/publicdomain/zero/1.0/）に基づき、これをパブリックドメインに置く。