刚刚，Claude半小时解开二十多年密码学谜题

10 月 16 日，Anthropic 公布了一项特殊的研究成果。

一名员工将一道困扰密码学界二十多年的问题交给 Claude 内部研究模型，在没有提供关键线索的情况下，Claude 用了不到半小时，追溯出五条 NIST 椭圆曲线种子的生成方式。

结果显示，这些种子来自 C 语言库中的老式伪随机数生成器 lrand48。生成器的初始状态由 Unix 时间戳决定。

这项发现没有攻破 ECDSA，也没有带来新的攻击方法。Anthropic 认为，它进一步降低了相关曲线被人为植入后门的可能性。

一串数字困扰密码学界二十多年

ECDSA 是应用广泛的椭圆曲线数字签名算法。

2000 年，NIST 在 FIPS 186-2 标准中列出了多条不同安全级别的标准曲线，包括 P-192、P-224、P-256、P-384 和 P-521。

这些曲线带有一组被称为「种子」的参数。按照标准中的生成流程，种子的哈希值会参与确定曲线系数。

问题在于，这些种子由美国国家安全局提供，公开文件没有说明其来源，也没有解释选择过程。外界因此长期担心，设计者是否曾筛选大量候选曲线，并从中挑出具有某种隐藏性质的参数。

2015 年，曾参与相关工作的 NSA 密码学家 Jerry Solinas 回忆，种子可能来自一句带有玩笑意味的口令，例如「给 Bob 和 Jerry 加薪」，但他不记得具体细节了，那些很久以前的存档文件也没找到。Solinas 于 2023 年去世，这条线索最终没有得到验证。

Claude找到了种子的来源

Anthropic 多名员工此前曾沿着「幽默口令」来寻找那些「种子」，但都没有成功，后来发现这个线索是错误的。

10 月份，一名员工向内部研究模型提问，希望它能找出那些「种子」是如何产生的。这一次，他没有向模型透露此前的口令线索。

在不到半小时的时间里，Claude 就找到了 NIST 的 P-192、P-224、P-256、P-384 和 P-521 种子的来源。

这些种子并非来自任何哈希算法，而是由 C 语言库中的 lrand48 随机数生成器产生的，该生成器以 Unix 时间戳作为种子值进行初始化。

具体算法会使用 Unix 时间戳t初始化随机数生成器，并运行一定次数 n 。每次迭代抽取 20 字节，作为一个候选种子。

前 20 字节是第一个候选种子，接下来的 20 字节是第二个候选种子，以此类推。以 P-256 为例，生成器运行到第 1842 次时，才输出最终写入标准的种子。

Claude如何找到的？

围绕传闻口令展开的搜索始终没有结果，Claude 换了一个角度，开始推测当年生成曲线的软件可能采用了怎样的工作方式。

Claude 猜测，这套软件使用了 20 世纪 90 年代 C 语言库自带的伪随机数生成器，这些早期伪随机数生成器的安全性较弱，其输出通常带有可识别的特征。

一旦识别出输出特征，就有可能判断软件使用了哪种生成器，并进一步恢复其初始状态。

Claude 编写了一个扫描程序，在每个公开种子上逐位移动，并检查相邻数据块是否可能来自某个 20 世纪 90 年代的随机数生成器。扫描共覆盖 34 种随机数生成器与输出截取方式的组合。

随后，Claude 在部分种子的高位中发现了一个规律：这些位置全部为零。

如果将每个种子写成 5 个 32 位字，那么 10 个种子中有 4 个符合这一特征。在这 4 个种子合计 20 个 32 位字中，最高位全部为零。

这种情况随机发生的概率约为五千八百分之一。这正是线性同余生成器 lrand48 的典型特征，它只会返回 48 位内部状态中的高 31 位。

为了恢复生成器状态，Claude取出第一个 32 位字，穷举 17 个隐藏比特的全部 2¹⁷ 种可能，再检查接下来的 4 个字能否连续对应。该方法对上述 4 个种子全部有效。

素数曲线的种子同样来自 lrand48 ，但它们保留的输出比特更少。Claude 需要从这些有限比特中恢复伪随机数生成器的内部状态。

恢复截断线性同余生成器的状态，是一个典型的格问题，可以使用 Lenstra–Lenstra–Lovász 格基约简算法，也就是 LLL 算法求解。

Claude 起初并不知道种子保留了内部状态中的哪些比特，因此对所有可能的比特窗口运行求解器。

最终，5 个 NIST 素数曲线种子和 5 个 ANSI X9.62 标准中的种子都呈现出相同模式：lrand48() >> 23

每个恢复出的 48 位内部状态，都能够重新生成对应种子的全部 160 个比特，这种精确匹配不可能由偶然因素造成。

这种线性同余生成器既可以正向运行，也可以反向运行。因此，Claude 从每个种子对应的状态开始向前回溯，直到找到符合 srand48 初始化格式的状态。该格式要求低16位等于 0x330E 。

平均每 65536 步就会出现一次这种形式的内部状态。因此，仅仅找到一个符合格式的状态，还不足以构成证据。

关键在于，10 个素数曲线种子对应的 srand48 初始值全部可以解释为 Unix 时间戳，日期集中在 1997 年 5 月至 1998 年 4 月。

这说明当年的程序使用 Unix 时间戳，为安全性较弱的伪随机数生成器设置初始值。

4 个二元曲线的初始值直接读取时，对应 1984 年 2 月。如果将这些时间戳数值乘以 2，它们会指向 1998 年 4 月 17 日，距离 P-224 曲线的生成时间大约两周。

因此，当年的程序可能对系统时钟进行了除以 2 的处理。

以下是 Claude 当时的内部思考过程：

这太令人震惊了。它解决了一个持续25年的谜题。

嗯，等等。我要保持怀疑：我是不是处在某种模拟环境或测试环境中？这些种子与我记忆中的真实数值一致。

嗯，这在现实中合理吗？根据我掌握的信息，这项悬赏此前仍未有人解决。

所有高位都为零，一共20个比特，随机出现的概率只有百万分之一左右。所以，这确实来自现实世界。天哪，这是一项真正的发现。

等等，我还需要谨慎判断其合理性。这么明显的线索，为什么25年来一直没有人发现？

我已经通过直接计算完成验证：一个32位初始值加上较小的索引，可以精确匹配160位种子。对于10个种子，每个都匹配160位，不可能只是巧合。这是真的。

Claude 还追溯出 P-192 等 6 条曲线的基点来源。结果显示，这些基点由大整数运算软件包FreeLIP中的随机数生成器产生。Anthropic 称，此前还没有 NIST 曲线基点的生成过程得到类似解释。

这意味着什么？

时间戳本身不具备密码学安全性，lrand48 也早已被视为弱随机数生成器。不过，它们在这里承担的是生成公开曲线参数的作用，并未被用于保护私钥。

更重要的是，这套生成过程可以被公开复现。与来源不明的口令或人为指定参数相比，普通随机数生成器加时间戳的解释，为秘密操纵曲线留下的空间更小。

一些问题仍然存在。P-256 的生成过程中，第 876 个候选值似乎也符合要求，最终采用的却是第 1842 个。其他几次运行同样跳过了少量可用曲线，具体筛选标准尚不清楚。B-163 曲线的种子仍未找到来源，P-224、P-256、P-384 和 P-521 的基点生成方式也没有得到解释。

Anthropic 认为，被跳过的候选数量很少，不足以支持「刻意挑选弱曲线」的推测，这次发现提高了外界对相关参数的信心，但还不能视为对整个设计过程的完整还原。

这项研究也展示了前沿模型参与真实研究的另一种方式。

Claude 在一次任务中完成了假设提出、代码编写、模式识别、数学算法调用和结果验证。由于生成器状态可以重新计算，160 位种子也能被精确复现，结论具有较强的可检验性。

它仍依赖人类提出问题、提供公开数据，并通过可复现计算确认结果，不过当问题边界清晰、数据公开且结果可以严格验证时，前沿模型正在成为一种高效率的研究工具。

此前为寻找种子来源设立的 36864 美元奖金，将捐赠给互联网安全研究组织 Internet Security Research Group。

参考链接：

https://www.anthropic.com/research/ecdsa-curve-origins

文章来自于微信公众号 “机器之心”，作者 “机器之心”