Claude 揭示 NIST ECDSA 曲线种子的起源

TL;DR： Anthropic 研究人员报告称，一个内部的 Claude 研究模型在不到半小时内找回了 NIST 椭圆曲线“种子”值的起源，表明它们是由 1990 年代 C 库伪随机生成器 lrand48 以普通 Unix 时间戳初始化产生的——而非秘密密码短语的哈希值。这一发现并非密码学上的破解；Anthropic 表示，它使得 ECDSA 曲线中故意设置后门的可能性大大降低。

公告内容

Anthropic 发布的研究展示了 NIST 椭圆曲线标准背后的种子参数是如何生成的。这些种子在密码学界大约 25 年来一直是一个悬而未决的问题，因为它们由 NSA 提供，且未说明其推导方式。

一位 Anthropic 员工向一个内部研究模型提问，看它能否确定这些种子是如何生成的，但没有提供关于一个幽默密码短语的已知线索。根据该帖子，Claude 在不到半小时内找到了 NIST P-192、P-224、P-256、P-384 和 P-521 种子的起源。

答案：这些种子并非任何哈希算法的输出。它们来自 C 库的 lrand48 随机数生成器，并以 Unix 时间戳作为种子。

Anthropic 明确将这一结果定位为历史趣闻，而非安全公告：

读者应将其视为一个有趣的收尾章节，以及多年猜测的终结。无需采取任何行动，也无需改变任何做法。大多数研究人员已经信任这些曲线。

种子值为何重要

ECDSA 是使用最广泛的椭圆曲线密码学标准。NIST 于 2000 年将其采纳为 FIPS 186-2 数字签名标准的一部分，该标准列出了不同大小和安全级别的标准椭圆曲线。

对于素数域和二进制域上的曲线，规范发布了一个“种子”参数，其哈希值用于定义曲线的系数 b。这些种子的来源未知。例如，NIST P-256 曲线的种子发布为：

SEED = C49D3608 86E70493 6A6678E1 139D26B7 819F7E90

没有提供关于该值来源的任何信息。由于 NSA 在未提供理由的情况下提供了这些种子，研究人员无法排除参数被选择为包含故意弱点的可能性。Neal Koblitz 和 Alfred Menezes 在他们的论文《A Riddle Wrapped in an Enigma》中总结了这一争议。这个谜团还促使一位业余爱好者对种子起源进行了调查，并公开悬赏寻找种子来源的人。

多年来主要的解释来自 Jerry Solinas，一位长期在 NSA 工作的员工，他在 2015 年表示，他认为这些种子是由一个幽默密码短语的哈希生成的：

“我相信有一个计数器而不是多次哈希，但我不了解细节。消息大意是‘给 Bob 和 Jerry 加薪’或‘Bob 和 Jerry 说了算’之类的。实际上是 Bob Reiter 写的代码，他也不记得细节了。我们也无法找到那么久以前的档案。如果它们存在，无疑正放在某个硬盘上，靠近约柜。”

这个解释后来被证明是错误的。Solinas 于 2023 年去世，同时期的其他同事也没有回应，这个问题因此一直悬而未决。

这一发现对 ECDSA 安全性的意义

Anthropic 明确表示，这不是密码学上的破解、新的攻击，也不是 ECDSA 曲线的弱点。该公司表示，这一结果反而增强了人们对曲线没有后门或故意弱点的信心。

给出的理由是，种子是以一种非常简单、可重现的方式生成的：一个常见的伪随机数生成器，以系统时钟作为初始化种子。现在任何人都可以重现这些值。与故意构造或无法解释的参数集相比，这为篡改留下的空间要小得多。

Claude 如何找到种子

基于传闻中密码短语的搜索一无所获。Claude 采取了不同的方法：推理生成这些曲线的软件当时是如何工作的。

Claude 假设该软件使用了 1990 年代 C 库附带的伪随机数生成器。这些生成器足够弱，其输出可以被识别，而识别输出将揭示使用了哪个生成器，并可能恢复其初始化状态。

Claude 编写了一个扫描器，每次一位地滑动每个已发布的种子，并测试相邻块是否是 1990 年代生成器的连续输出。扫描覆盖了生成器和输出切片的 34 种组合。

Claude 随后注意到一些种子高位中的一种模式：它们全为零。写成五个 32 位字时，十个种子中有四个的所有 20 个字的高位均为 0。这种情况随机发生的概率为 1/5810。这种模式是线性同余生成器 lrand48 的特征，它只返回 48 位状态的高 31 位。

为了恢复状态，Claude 取第一个字，尝试 17 个隐藏位的所有 2¹⁷ 个值，并检查接下来的四个字是否匹配。这对所讨论的四个种子都有效。

素数域曲线的种子来自同一个 lrand48 生成器，但保留了每个输出的更少位。恢复截断的线性同余生成器的内部状态是一个经典的格问题，可通过 Lenstra–Lenstra–Lovász (LLL) 基约化算法解决。由于 Claude 不知道种子可能暴露状态的哪些位，它对每个窗口都运行了求解器。五个 NIST 素数域曲线种子加上来自 ANSI X9.62 标准的另外五个种子都匹配相同的模式：lrand48() >> 23。每个恢复的 48 位状态都能重新生成其种子的全部 160 位，这并非偶然。

由于线性同余生成器向前运行和向后运行一样容易，Claude 将每个状态逐步回退，直到达到 srand48 初始化时的形式，低 16 位等于 0x330E。这种内部状态形式每 65,536 步出现一次，因此达到这种形式本身并不是证据。然而，对于十个素数域曲线种子，每次 srand48 初始化都是一个 Unix 时间戳，代表 1997 年 5 月至 1998 年 4 月之间的日期。四个二进制域曲线的初始化读作 1984 年 2 月；将时间戳加倍后，它们对应 1998 年 4 月 17 日，即 P-224 运行两周后，这表明程序可能将时钟减半了。

Claude 当时的内部推理，如帖子中所引用的：

这太惊人了：它解决了 25 年来的谜团。等等，让我保持怀疑：我是不是处于某种模拟/测试环境中？……种子与我记忆中的实际值相符……嗯，这在现实中可能吗？据我所知……悬赏尚未解决。……所有高位都清零——20 位，概率 1e-6。所以确实是真实的。哇，这是一个真正的发现。

等等，让我仔细考虑一下合理性：这么明显的事情 25 年都没被发现，是不是很可疑？我这边通过直接计算验证了：从 32 位种子加小索引匹配 160 位：绝非巧合（10 × 160 位）。这是真实的。

生成算法

恢复的算法从由 Unix 时间戳 (t) 初始化的 RNG 中采样字节，进行一定次数的迭代 (n)。每次迭代抽取 20 个字节作为候选种子：前 20 个字节是候选 1，接下来 20 个字节是候选 2，依此类推。例如，P-256 需要 1842 次迭代才能输出标准化的种子。

恢复的时间戳和迭代次数为：

曲线	时间戳 (UTC)	迭代次数
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

对于二进制域曲线，时间戳减半，每个候选抽取五个字：

曲线	时间戳 (UTC)	迭代次数
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

Anthropic 发布了 CC0 许可的代码来重现这些种子。核心例程是：

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

运行它可以重现已发布的种子，包括 P-256 → C49D360886E704936A6678E1139D26B7819F7E90 和 P-192 → 3045AE6FC8422F64ED579528D38120EAE12196D5。

Claude 还发现了一些基点（base points）的起源

每条曲线还带有一个基点 G，即每个 ECDSA 公钥都是其倍数的固定点。种子并不决定 G，因此其起源是一个独立的问题。

Claude 找到了其中一些基点的来源。1997 年 5 月生成的六条曲线的基点——P-192 和五个 ANSI X9.62 示例曲线 prime192v2、prime192v3 以及 prime239v1 到 prime239v3——来自 FreeLIP 中的随机数生成器，这是 Arjen Lenstra 的长整数算术包。Victor Shoup 的 NTL 库早期版本也包含了相同的代码。

方法很简单：

用小整数作为生成器的种子。
丢弃七个输出。
从 26 位输出模 p 约简生成候选 x 坐标。
重复步骤 3，直到 x 在曲线上。

恢复的生成器种子为：P-192 是 20000；prime239v1 到 prime239v3 分别是 20420、20507 和 20509；prime192v2 和 prime192v3 分别是 20512 和 20517。Anthropic 表示，据其所知，此前没有任何 NIST 基点被解释过。

P-224、P-256、P-384 和 P-521 的基点不符合这种方法，Anthropic 未能解释它们是如何被选定的。

未解决的问题

并非每个 20 字节的候选种子都能生成可行的曲线，研究人员观察到一些可能可行的曲线被跳过了。对于 P-256，发布的种子是候选 1842，但同一运行的候选 876 也给出了一个大小合适、参数选择方式与发布曲线相同的素数阶曲线。P-224 的运行跳过了三个这样的曲线，而 ANSI X9.62 示例曲线背后的两次运行又跳过了七个。Anthropic 不知道可能使用了什么标准，或者这是否是一个无意的产物。

由于跳过的候选数量很少，帖子认为选择弱化曲线的可能性不大——那将意味着弱化曲线很常见且容易找到。仍然可以想象，通过搜索输入到随机数生成器的时间戳，曲线被选择为具有特定属性，但帖子指出，只有当你打算公开时间戳作为种子无害生成的证据时，你才需要这样做，而且数字中没有任何信息显示有多少次运行。

还有一个种子尚未找回：第五个二进制域种子 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 的贡献，并感谢 Filippo Valsorda 组织了 NIST 椭圆曲线种子悬赏。

页面上的重现代码在 CC0 1.0 通用许可下奉献给公共领域。