クロードがECDSA曲線の起源を明かす
2026年10月16日「それは単なるタイムスタンプに過ぎない」：最も人気のある暗号学標準の一つについて、数十年にわたる謎が解明された。
私たちは、最も広く使用されている暗号学標準の一つであるECDSAに関する懸念を解消するために、暗号学コミュニティで長年にわたって議論されてきたこの問題に取り組んだ。
読者は、これを楽しい終わりの章と、長年にわたる推測の終結と受け止めるべきです。何か行動を起こすことも、変更すべき点もありません。ほとんどの研究者は既存の曲線を信じていました。楽しんでください。
ECDSAは最も広く使用されている楕円曲線暗号学標準です。2000年にNISTによって、様々なサイズとセキュリティレベルを持つ標準的な楕円曲線の集合を列挙したFIPS 186-2デジタル署名標準の一部として採用されました。素数領域やバイナリ領域上の曲線については、仕様書において「シード」パラメータが公表されており、そのハッシュ値が曲線の係数bを定義するために使用されます。これらのシードの出所については長年の疑問であり、NSAから説明や根拠なく提供されたものです。例として、NIST P-256曲線のシードはSEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90であり、その出所については何も記載されていません。
Neal KoblitzおよびAlfred Menezesは、この論争に関する優れた要約を執筆しました。「Enigmaに包まれた謎」です。この要約では、シード値に関する歴史と問題点が論じられています。この謎は、シードの起源に関するアマチュアの調査や、それを見つけることができた人への報酬へとつながりました。
最も素晴らしい話は、長年のNSA職員であるジェリー・ソリナスが、ユーモラスなパスフレーズのハッシュを使って種を作り出したということです：
「複数のハッシュ化ではなく、逆対応があったと思いますが、詳細はわかりません。メッセージは『ボブとジェリーに給与を上げる』や『ボブとジェリーの規則』といった内容でした。実際にコードを書いたのはボブ・リーダーで、彼も詳細を覚えていません。また、あまりに昔の記録も見つけることができませんでした。もし存在するとしても、間違いなく契約の箱の近くのハードドライブに保存されているのでしょう。」
ジェリー・ソリナス、2015
残念ながら、ジェリーは2023年に亡くなり、当時の他の同僚も応答してくれなかったため、これらの種がどのようにして得られたのかという疑問が残った。
クロードは種子を見つけた
アンタロニックの従業員数人が、それがユーモラスなフレーズのハッシュであるという手がかりに従って種を追いかけようとしたが、失敗した。それは間違いだった。2026年10月、アンタロニックの興味深い従業員が内部の研究モデルに、その手がかりを指ささずに、どうやってその種が生成されたのかを解明できるか尋ねた。
30分足らずで、クロードはNISTのP-192、P-224、P-256、P-384、P-521シードの起源を発見した。これらのものはどれもハッシュアルゴリズムの結果ではなく、Unixタイムスタンプで初期化されたCライブラリのlrand48乱数生成器の出力である！
使用されたアルゴリズムは、Unixタイムスタンプ(t)によって初期化されたランダム数生成器（RNG）から、一定回数の反復処理(n)ごとにバイトをサンプリングする。各反復処理で20バイトを候補シードとして抽出する。したがって、最初の20バイトは候補1、次の20バイトは候補2となり、このように続く。例えば、P-256では標準化されたシードを得るのに1842回の反復処理が必要であった。
これはどういう意味ですか
これは暗号学上の突破、新たな攻撃、またはECDSA曲線の弱点ではありません。実際、このことにより、その曲線がバックドアや意図的な弱点のない形で選ばれたと確信するようになりました。長年にわたり、人々はNISTの曲線パラメータの出所に疑問を抱いてきました。それらはどのように選ばれたかについて何も言及されずNISTに提示されたため、意図的にバックドアがあるかもしれないと疑問が生じています。これらの発見により、その可能性はさらに低くなります。 種子は非常に簡単な方法で生成されました。つまり、時計から初期化される一般的な擬似乱数生成器であり、今では誰でも再現できます。これにより、改変の余地が大幅に減り、パラメータが安全であると確信できます。
それがどのように発見されたか
噂から生まれたそのフレーズを探す努力は無駄に終わった。クロードは別のアプローチを試した。曲線を生成するソフトウェアがどのように機能しているかを予測することだ。クロードは、そのソフトウェアが1990年代のCライブラリに付属していた擬似乱数生成器（PRNG）を使用していると推測した。これらの古いPRNGは十分に弱いため、その出力は認識可能である。出力を認識することで、どのPRNGが使用されているかがわかり、おそらく初期化状態を復元することも可能になる。
クロードは、発表されたシードを一ビットずつスライドさせるスキャナーを作成し、隣接するチャンクが1990年代の生成器の連続的な出力であるかどうかをテストした。このスキャンでは、生成器と出力スライスの34通りの組み合わせが対象となった。その際、クロードはいくつかのシードの上位ビットにパターンがあることに気づいた：それらはすべて0であった。5つの32ビットワードとして記述すると、10個のシードのうち4個は、20個のワードすべてにおいて上位ビットが0である。これは、確率1/5810で偶然起こることである。これは、48ビットの状態の上位31ビットのみを返す線形連続生成器lrand48の特徴である。そのパターンは、探す方法を知っていれば目で見ることができる。状態を復元するために、クロードは最初のワードを取り、17個の隠されたビットの2¹⁷通りの値をすべて試し、次の4つのワードが正しいかを確認した。これは、議論されている4個のシードすべてでうまく機能した。
素数曲線シードは同じlrand48生成器から来たが、各出力のビット数は少ない。ClaudeはそのビットからPRNGの内部状態を復元する必要があった。結果、切り取られた線形連続生成器の状態を復元することは、教科書的な格子問題であり、Lenstra–Lenstra–Lovász (LLL)基準削減アルゴリズムによって解決されることがわかった。Claudeはシードがどの状態のビットを示す可能性があるかわからなかったため、すべてのウィンドウに対して解決器を実行した。NISTの5つの素数曲線シードとANSI X9.62標準のさらに5つは、すべて同じパターンを持っていた：lrand48() > 23。復元された48ビットの状態は、そのシードの160ビットすべてを再生成するが、これは偶然ではない。
この線形コンジュエンシャル生成器は、前後どちらでも同じように逆方向に動作するため、クラウドは各シードに対して状態を遡らせ、srand48によって初期化される形になるまで行った。低い16ビットは0x330Eに等しい。その形の内部PRNG状態は65,536ステップごとに一度現れるため、一度現れただけでは証拠にはならない。
しかし、10個の素数曲線シードについては、すべてのsrand48初期化が1997年5月から1998年4月の間の日付を表すUnixタイムスタンプでした。彼らはUnixタイムスタンプによって初期化された弱いPRNGを使用していました。4個のバイナリ曲線の初期化は1984年2月と読み取られます。タイムスタンプが2倍になると、P-224実行から2週間後の1998年4月17日に相当します。したがって、プログラムは時計を半分にした可能性があります。
当時のクロードの内面での考えは：
これは驚くべきことです：25年間の謎が解決されました。えっ、待って。懐疑的になりますが、私は何らかのシミュレーション/テスト環境にいるのでしょうか？…種子は私の記憶にある実際の値と一致します…えっ、現実で起こり得るのか？私の知識によると…報酬は未解決です。…すべての重要な部分が明らかです—20ビット、確率1e-6。つまり、実世界のことです。わあ、本当に発見です。
ええと、待って。妥当性に注意してみましょう：25年間でこのような明らかなことが発見されなかったのは怪しいのでしょうか？私の側での直接計算によって確認できます：32ビットのシードから160ビットの一致 + 小さなインデックス：偶然の一致の可能性はありません（10×160ビット）。これは真実です。
クラウドはいくつかの基本点を見つけた
しかし、まだある…各曲線には基準点Gも存在する。これは、すべてのECDSA公開鍵がGの倍数である固定点である。上で得られたシードはこのGを決定しないため、別の疑問が生じる：これらの基準点はどのように生成されたのか？
シードをチェックする中で、Claudeはいくつかのベースポイントがどこから来たかも明らかにした。1997年5月に生成された6つの曲線のベースポイント（P-192と5つのANSI X9.62例曲線prime192v2、prime192v3、prime239v1からv3）は、FreeLIPの乱数生成器や、Arjen Lenstraの長整数計算パッケージから来ている。Victor ShoupのNTLライブラリの初期バージョンも同じコードを使用していた。
このレシピは簡単です：
- 小さな整数を生成器に与えます。
- 7つの出力を捨てる。
- pで除算された26ビットの出力からx座標候補を生成する。
- xが曲線上になるまでステップ3を繰り返す。
クロードによると、P-192の生成器シードは20000、prime239v1からv3までの場合は20420、20507、20509であり、prime192v2およびv3の場合は20512、20517である。
私たちが知る限り、以前にNISTのベースポイントが説明されたことはありません。P-224、P-256、P-384、P-521のベースポイントはこの方法には当てはらず、どのように選ばれたのかを説明することができませんでした。
開かれた問い
20バイトの候補シードがすべて有効なカーブを生成できるわけではなく、潜在的に有効である可能性のあるカーブがスキップされることも観察されました。P-256については、公開されたシードは候補1842ですが、同じ実行での候補876も適切なサイズの素数順序のカーブを生成し、パラメータも公開されたカーブと同じ方法で選択されています。P-224の実行では3つのそのようなカーブが通過し、ANSI X9.62の例カーブの後ろにある2回の実行ではさらに7つが通過しました（図を参照）。 どのような基準が使用されたのか、またこれが意図しない産物であったかどうかはわかりません。
スキップされた候補者の数が少ないため、弱められた曲線が選ばれたとは考えにくい。それは、弱められた曲線が一般的で見つけやすいことを意味する。これらの曲線が、ランダム数生成器のタイムスタンプを検索することで、原則的に特定の特性を持つように選ばれた可能性もある。しかし、シードが無害に生成されたという証拠としてタイムスタンプを公開するつもりなら、そうする必要があるだけだ。 数字の中に、何回ランがあったかを示すものは何もありません。
また、回復できなかったシードもあります。5番目のバイナリシードであるB-163は、クロードが試したものには当てはまりませんし、その理由も分かりません。最後に、P-224、P-256、P-384、P-521のベースポイントがどのように生成されたのかもわかりません。NISTのバイナリ曲線についても同様です。
報酬
種子を発見するためにかかった36,864ドルは、インターネットセキュリティ研究グループに寄付されます。
私たちは何者か
この研究は、ジョン・ウッド、ヘンリー・デ・ヴァランス、アヴァ・ハウエル、ザック・ヴォーセ、ルーシー・スウィート、アミール・オミディ、ポール・クロウリー、イアイン・マクギニス、ニコラス・カーリニ、スティーブ・ワイスによってAnthropicで行われました。
謝辞
「悪いインターネットミーム」と「NSAのボージーマンであるYo La Tengo」という称号を、ユーモアを持って受け入れたジェリー・ソリナスに、死後でも認識したいと思います。また、NISTエルピッツ曲の種子プログラムを企画したフィリッポ・ヴァルソルダにも感謝します。
種子を再現するためのコード
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/).
関連コンテンツ
Claudeを使って、より効率的な量子回路を設計する
私たちはClaudeに8つの量子回路に関する平易な仕様を提供し、その設計をチェックし評価する自動評価器も用意した。Claudeはほぼ独立して作業し、最良の既発表回路を改善した。場合によっては10倍以上の改善が見られ、これにより実用的な量子コンピュータが以前予想していたよりも近づく可能性がある。
もっと読むAIモデルはデータセンターに接続せずに自己複製する能力を持つ可能性がある
私たちの実験によると、小規模なAIモデルは、Androidテレビやスマートオーブンなどの商業的なIoTデバイス上で自己複製が可能になるほど、わずか数ヶ月で到達できる可能性があります。
もっと読む蒸留攻撃に対する防御体制を強化する
違法な蒸留により、モデル開発者は適切な保護対策を設けることなく frontier AIの機能を複製することができる。ここでは、私たちが蒸留率を90％以上減少させた方法を説明する。
もっと読むFrontier Red Teamニュースレターを購読する
最新のレッドテーミングに関する研究と発見についての情報を得る。