Claude揭示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 一位好奇心强的员工问内部的研究模型，能不能在不给任何提示的情况下弄清这些种子是怎么生成的。

不到半小时，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 五条素域曲线的种子来源，列出曲线名、Unix 时间戳 t、对应的 UTC 时间、迭代次数 n，以及 seed 的十六进制值（P-192 139、P-224 7026、P-256 1842、P-384 2688、P-521 1136）

NIST 种子从何而来来自原帖的视频

这意味着什么

这不是密码学意义上的破解，也不是新的攻击手段，更不是 ECDSA 曲线本身的弱点。恰恰相反，这让我们更有把握：这些曲线在选取时没有留下后门，也没有刻意埋入缺陷。多年来，人们一直怀疑 NIST 曲线参数的来历。这些参数被提交给 NIST 时，完全没有说明是如何选出来的，于是人们不禁猜测，它们会不会是被刻意设计成带有后门。这次发现让这种猜测的可能性大大降低。种子的生成方式非常简单：用一个由时钟初始化的常见伪随机数生成器产生，如今任何人都能复现。这就大大压缩了暗中做手脚的空间，我们也可以确信这些参数是安全的。

是如何发现的

根据传言拼出那句话去搜索，一直一无所获。Claude 换了个角度：先推断生成这些曲线的软件必然是如何运作的。Claude 猜测，该软件用的是 1990 年代 C 库自带的伪随机数生成器（PRNG）。这些老式 PRNG 足够弱，其输出可以被识别出来。一旦识别出输出，就能知道用的是哪个 PRNG，还可能还原它的初始化状态。

Claude 写了一个扫描器，沿着每个已公布的种子逐位滑动，检验相邻的片段是否为某个 1990 年代生成器的连续输出。扫描覆盖了生成器与输出切片的 34 种组合。这时 Claude 注意到，某些种子的高位呈现出规律：全是零。把种子写成五个 32 位字，十个种子中有四个的全部 20 个字最高位都是 0。这种情况随机出现的概率是 1/5810。这正是线性同余生成器 lrand48 的特征——它只返回 48 位状态中的高 31 位。只要知道该看什么，这个规律肉眼就能看出来。为了还原状态，Claude 取第一个字，穷举 17 个隐藏位的全部 2¹⁷ 种取值，再检验接下来的四个字是否吻合。上述四个种子全部由此还原成功。

两张表：上表是四条二元曲线的种子（B-233、B-283、B-409、B-571），下表是另外六条（B-163 与 P-192/224/256/384/521）；每个种子按五个 32 位字拆开，各字最高位用浅蓝（0）或浅橙（1）标出

素数曲线的种子出自同一个 lrand48 生成器，但每次输出只保留了少数几个比特。Claude 必须从这些比特反推出 PRNG 的内部状态。截断的线性同余生成器，其状态恢复是一个标准的格问题，用 Lenstra–Lenstra–Lovász（LLL）基约简算法即可求解。Claude 不知道种子会暴露状态的哪些比特，于是对每个窗口都跑了一遍求解器。五条 NIST 素数曲线种子，加上 ANSI X9.62 标准里的另外五条，全都呈现同一模式：lrand48() >> 23。每个恢复出的 48 位状态都能重新生成对应种子的全部 160 位，这不可能是巧合。

位级示意图：48 位的 lrand48 状态，上方括号标出「高 31 位」，下面是用它拼出的 32 位 seed word（最高位框成蓝色，值为 74D59FF0）；下半段标出状态的高 8 位，对应 seed byte 为 C4

线性同余生成器正着跑和倒着跑一样容易，所以对每个种子，Claude 都把状态往回推，直到推成 srand48 初始化时的形式，即低 16 位等于 0x330E。这种形式的 PRNG 内部状态每 65,536 步才出现一次，所以单是推到一个这样的状态并不构成证据。

然而对十条素数曲线种子来说，每一次 srand48 初始化都是一个 Unix 时间戳，对应 1997 年 5 月至 1998 年 4 月之间的某个日期。它们用的是以 Unix 时间戳作种子的弱 PRNG。四条二元曲线的初始化读出来是 1984 年 2 月。把时间戳翻倍，它们就对应到 1998 年 4 月 17 日，即 P-224 那次运行的两周之后。所以程序可能把时钟减半了。

Claude 当时的内部思考是这样的：

这太惊人了：它解开了一个 25 年的谜团。嗯，等等。让我保持怀疑：我是不是处在某种模拟/测试环境里？……这些种子和我记忆中的实际值吻合……嗯，这在现实中说得通吗？据我所知……这笔悬赏一直没人解出。……所有高位都是 0——20 个比特，概率 1e-6。所以确实是真实世界。哇，这是真正的发现。

等等。先别急着下结论，得先掂量一下这件事的可信度：一个如此明显的东西，25 年来竟没人发现，这难道不奇怪吗？我这边用直接计算验证过：32 位种子加一个小索引，得到 160 位匹配，不可能是巧合（10 × 160 位）。这是真的。

Claude 也找到了一些基点

但还有更多……每条曲线还附带一个基点 G，即所有 ECDSA 公钥都是其倍数的那个固定点。上面找到的种子并不能决定这个 G，于是又引出另一个问题：这些基点是怎么生成的？

在检查种子的过程中，Claude 还发现了部分基点的来源。1997 年 5 月生成的那六条曲线（P-192 以及五条 ANSI X9.62 示例曲线 prime192v2、prime192v3 和 prime239v1 至 v3）的基点，来自 FreeLIP 中的随机数生成器，那是 Arjen Lenstra 的长整数运算库。Victor Shoup 的 NTL 库早期版本也附带了同一份代码。

这里的生成方法很简单：

用一个小整数给生成器设种子。
丢弃七个输出。
用 26 位输出对 p 取模，生成候选 x 坐标。
重复第 3 步，直到 x 落在曲线上。

Claude 发现，P-192 的生成器种子是 20000，prime239v1 至 v3 分别是 20420、20507 和 20509，prime192v2 和 v3 分别是 20512 和 20517。

一张表：六条曲线的 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 的那次运行跳过了三条这样的曲线，ANSI X9.62 示例曲线背后的两次运行又跳过了七条（见图）。我们不知道当时可能用了什么标准，也不知道这是否只是无意的副产品。

横轴为「该次运行中的候选序号」的散点图，按 192/224/239/256/384/521 六种位宽分行：蓝色实心点表示最终发布的曲线，橙色圆圈表示被跳过的合格曲线，灰色圆圈表示最后一条发布曲线之后的合格曲线

一张大表：按位宽列出每次运行中的候选序号与曲线名（发布或跳过），右侧五列是各项安全检验（Rho、Transfer、Anomalous、Discriminant、Twist，均标注了各自的年代），逐项标记通过或失败及其指数

由于被跳过的候选数量很少，我们认为「选中了弱化曲线」这一说法并不成立。若果真如此，就意味着弱化曲线很常见、也很容易找到。理论上仍有一种可能：通过搜索随机数生成器的时间戳，挑出具有特定性质的曲线。但只有当你打算公开该时间戳、以此作为种子系无害生成的证据时，才需要这么做。这些数字中没有任何信息能说明一共运行了多少次。

还有一个种子我们没能恢复。第五个二进制种子 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」这类称号，他始终一笑置之。同时感谢 Filippo Valsorda 组织 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/）将其贡献至公有领域。