ECDSA の起源に関する謎解明：単なるタイムスタンプから

暗号コミュニティが何十年も抱えていた ECDSA（楕円曲線デジタル署名アルゴリズム）の未解決課題に、ついに答えが出ました。今回の調査により、長年存在した「シード値の起源」についての疑問と懸念が解消されました。これら曲线にはバックドアや意図的な弱点はなく、安全性に確信を持つことができます。 多くの研究者は既にこれらの曲線に信頼を寄せていましたが、今回の発見によってその根拠がさらに強固なものになりました。

ECDSA の背景と長年の謎

ECDSA は最も広く利用されている楕円曲線暗号の標準規格であり、2000 年に NIST が FIPS 186-2 として採用しました。この規格には一連の標準楕円曲線がリストされています。

• シードパラメータ: 素数体およびバイナリ体上の曲線については、「シード」と呼ばれるパラメータが定義されていました。
• 欠乏した説明: これらのシード値は NSA から提供されたにもかかわらず、その出自や生成ロジックについての明文化された説明が存在しませんでした。
• 主な懸念: 例として NIST P-256 のシード

  C49D3608...

  ですが、それがどこから来たのか不明という状況は、長年「バックドア」や意図的な弱点が含まれているのではないかという疑念を生み出していました。

Neal Koblitz 氏や Alfred Menezes 氏が論じたように、この謎を探るためのアマチュアの調査や、報奨金付きの悬赏活動が数年来行われてきましたが、解決にいたりませんでした。Jerry Solinas 氏のユーモアあふれる仮説（昇給を願うフレーズのハッシュなど）も、同僚たちが亡くなるまで検証されることはありませんでした。

シードの真の原因：Claude の発見

Anthropic の従業員が内部の研究モデル「Claude」に問いかけたことで、この謎はついに解けました。

• 仮説の否定: 「ユーモアあふれるフレーズのハッシュ値である」という長年の仮説は誤りでした。
• 真の原因: NIST P-192, P-256, P-384 などすべてのシードは、**C ライブラリの

  lrand48

  擬似乱数生成器（RNG）**による出力です。
• 種付け元: その RNG を初期化するものこそが、Unix タイムスタンプでした！

使用されたアルゴリズムの概要

シード生成プロセスは以下の通りです。

1. 初期化: Unix タイムスタンプ ($t$) で擬似乱数生成器（RNG）を初期化。
2. サンプリング: 反復処理 ($n$) を行い、各回から 20 バイトずつ抽出します（例：P-256 では 1842 回の反復）。

発見プロセス：どのように見付けたか？

Claude はフレーズ検索ではなく、曲線生成ソフトウェアの動作予測からアプローチしました。

ステップ 1: 予察と弱点の悪用

• 1990 年代の C ライブラリに同梱されていた

  lrand48

  を使用していたと推測。
• この古い PRNG は弱いため、出力パターンを特定し内部状態（初期化値）を復元できる可能性が高い。

ステップ 2: スキャンとパターン認識

• シードのビットをずらしてテストし、34 の組み合わせをスキャン。
• 決定的な発見: 上位ビットに「すべてゼロ」のパターンが複数見られた。これは偶然ではあり得ない（確率 $1/5^{810}$）。

ステップ 3: アルゴリズムの特定

• このパターンは、48 ビットの状態のうち上位 31 ビトのみを返す線形合同式ジェネレーター（LCG）

  lrand48

  の特徴と一致。
• 状態復元:

  lrand48

  の内部状態を復元する教科書的な格子問題として LLL アルゴリズムを使用し、成功。

ステップ 4: 全曲線の検証

• 素数曲線: すべて同じパターン

  lrand48() >> 23

  を持つことが確認。
• バイナリ曲線: 初期化には

  _srand48(time / 2)

  が使用されていた可能性があり、1997-1998 年間のタイムスタンプに対応していることが判明。

思考プロセス

• 「25 年前の謎を解明した」という驚きから始まり、「現実的にはあり得るのか？」という懐疑を経て、確率的な一致が偶然ではないと判断。
• 「32 ビットのシードからの 160 ビット一致」は偶発的な一致とは不可能であるため、これが真の現実であると結論づけた。

基点（Base Point）の起源も解明

シードだけでなく、すべての ECDSA 公開鍵の基礎となる基点 $G$ の生成方法も見出されました。

• アルゴリズム: Arjen Lenstra 氏の FreeLIP や Victor Shoup 氏の NTL ライブラリに含まれる乱数生成器を使用。

  1. 小さな整数で種付けする。
  2. 出力の最初 7 つを破棄する（ウォームアップ）。
  3. 次のビットから $x$ 座標を生成し、曲線上にあるか検証を繰り返す。

• 特定されたシード値:

  • P-192

    :

    20000

  • prime239v1〜v3

    :

    20420

    ,

    20507

    ,

    20509

  • prime192v2/v3

    :

    20512

    ,

    20517

注釈: P-224、P-256、P-384、P-521 の基点についてはまだ説明がついていない残存問題です。

未解決の問題とセキュリティへの影響

今回の発見は暗号学的な破綻や新たな攻撃を示すものではありません。

• 安全性の向上: パラメータが「バックドア」ではなく、誰でも再現可能な公開アルゴリズム（時計＋疑似乱数）」によって選択されたことが確認されました。改ざんの余地が極端に減り、パラメータの安全性に確信を持てます。
• スキップされた候補: すべてのランダムな試行から有効な曲線が生成されるわけではなく、いくつかの候補がスキップされていた可能性があります。しかし、その数が小さいため、「弱体化された曲線を意図的に選択した」という可能性は低いです。

報奨金と謝辞

• 報奨金の分配: シード発見のため支払われた

  $36,864

  は、Internet Security Research Group (ISRG) に寄付されました。
• 関係者: 本調査は Anthropic の John Wood、Henry de Valence など多数のチームメンバーによって行われました。
• 追悼と感謝: Jerry Solinas 氏のユーモアなアプローチと、NIST 楕円曲線シード報奨金を主催された Filippo Valsorda 氏に深く感謝いたします。

シードを再現するためのコード

以下の Python スクリプトは、タイムスタンプから NIST P-256 のシードを正確に再生成します。

1. シード生成と検証スクリプト

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, ""                      # srand48(t) が設定する状態
    for i in range(per * n):
        x = (0x5DEECE66D * x + 0xB) % 2**48              # lrand48 の一ステップ
        if i >= per * (n - 1):
            out += "%0*X" % (width, x >> shift)
    return out

PRIME = {  # srand48(time); 20 バイトあたりの候補: 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)；5 ワードあたりの候補: 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),
}

print("=== Prime Curves ===")
for name, (when, n) in PRIME.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when), n, 20, 40, 2)}")

print("\n=== Binary Curves ===")
for name, (when, n) in BINARY.items():
    print(f"{name:10} {when} {n:5} {candidate(unix(when) // 2, n, 5, 17, 8)}")

コード実行結果の要約

1997-08-16 01:52:34

C49D3608...

1997-08-30 14:50:08

A335926A...

1998-04-03 12:52:07

BD713447...

重要: P-256 のシードは、このアルゴリズムで完全に再現可能です。これは偶然の一致ではなく、意図的な（あるいは無作為ながらも一貫した）生成プロセスである証明です。

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

FreeLIP ライブラリの乱数生成器を用いて、基点 $G$ の座標を復元するスクリプトです。

2. 基点（Base Point）生成スクリプト

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): 新しい状態の下位 26 ビット
        nonlocal state
        state = state * A % M
        return state % 2**26
    for _ in range(7):                   # まず 7 つの単一リム（limb）の抽出が行われる
        limb()
    limbs = -(-p.bit_length() // 26) + 1 # zrandomb(p): p のリム数に 1 を加え、上位リムから
    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:   # x は曲線上にあるか？
            return x, tries

print("=== Base Point Verification ===")
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}")

検証結果

すべての曲線について、計算された基点座標が NIST の公開値と完全に一致することが確認されました。

prime192v1

prime239v1

prime239v2

prime239v3

prime192v2

prime192v3

ライセンス情報

本ページに含まれるすべてのコードは、法律の許す限り CC0 1.0 ユニバーサルライセンスの下で公開されます。

• 著作権放棄: 著者は著作権および関連する権利を放棄し、パブリックドメインとして寄付しています。
• リンク先: CC0 1.0 Universal

関連コンテンツ（他の研究事例）

今回の調査と同じく、AI モデル「Claude」を応用してセキュリティや効率性を向上させた他の成果物も参照できます。

• [量子回路の効率化] Claude を用いてより効率的な量子回路を設計する
  • 8 つの量子回路に対する仕様を提供し、既存の最良の公開された circuit を改善。実用的な量子コンピュータへの到達が近づく可能性があります。
• [AI の経済への影響] AI の期待値ギャップ
  • 今後数年間で AI が経済をどのように再形作っていくかに関する調査証拠の発表。
• [雇用の変遷] Anthropic における雇用の変化
  • AI が仕事の組織化、採用、労働需要をどのように変化させるかを示す指標となる事例。