Claude半小时破解二十多年密码学谜题

10 月 16 日，Anthropic 公布了一项特殊研究成果。一名员工将困扰密码学界二十多年的问题交给 Claude 内部研究模型，在未提供关键线索的情况下，Claude 用不到半小时追溯出五条 NIST 椭圆曲线种子的生成方式。结果显示，这些种子来自 C 语言库中的老式伪随机数生成器 lrand48，其初始状态由 Unix 时间戳决定。这项发现没有攻破 ECDSA，也没有带来新的攻击方法，但进一步降低了相关曲线被人为植入后门的可能性。

ECDSA 是应用广泛的椭圆曲线数字签名算法。2000 年，NIST 在 FIPS 186-2 标准中列出 P-192、P-224、P-256、P-384 和 P-521 等多条标准曲线。这些曲线带有一组被称为“种子”的参数，种子的哈希值参与确定曲线系数。问题在于，种子由美国国家安全局提供，公开文件未说明来源和选择过程，外界长期担心设计者是否筛选大量候选曲线并挑出具有隐藏性质的参数。2015 年，曾参与相关工作的 NSA 密码学家 Jerry Solinas 回忆，种子可能来自一句玩笑口令，例如“给 Bob 和 Jerry 加薪”，但他不记得细节，存档文件也未找到。Solinas 于 2023 年去世，该线索未获验证。

Anthropic 多名员工此前曾沿“幽默口令”寻找种子，均未成功。10 月，一名员工向内部研究模型提问，希望找出种子如何产生，且未透露此前的口令线索。不到半小时，Claude 就找到了五条 NIST 曲线种子的来源。这些种子并非来自哈希算法，而是由 lrand48 随机数生成器产生，该生成器以 Unix 时间戳为种子值初始化。具体算法使用 Unix 时间戳 t 初始化随机数生成器，并运行一定次数 n，每次迭代抽取 20 字节作为候选种子。以 P-256 为例，生成器运行到第 1842 次时才输出最终写入标准的种子。

Claude 换角度推测当年生成曲线的软件工作方式，猜测其使用 20 世纪 90 年代 C 语言库自带的弱伪随机数生成器。Claude 编写扫描程序，在每个公开种子上逐位移动，检查相邻数据块是否可能来自某个 20 世纪 90 年代随机数生成器，共覆盖 34 种随机数生成器与输出截取方式的组合。随后，Claude 在部分种子高位中发现规律：这些位置全部为零。若将每个种子写成 5 个 32 位字，10 个种子中有 4 个符合该特征，合计 20 个 32 位字最高位全部为零，随机发生概率约为五千八百分之一。这正是线性同余生成器 lrand48 的典型特征，它只返回 48 位内部状态中的高 31 位。为恢复生成器状态，Claude 取出第一个 32 位字，穷举 17 个隐藏比特的全部 2¹⁷ 种可能，再检查接下来的 4 个字能否连续对应，该方法对上述 4 个种子全部有效。

素数曲线的种子同样来自 lrand48，但保留的输出比特更少。Claude 需从有限比特中恢复伪随机数生成器内部状态。恢复截断线性同余生成器状态是典型格问题，可用 Lenstra–Lenstra–Lovász 格基约简算法求解。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 还追溯出 P-192 等 6 条曲线的基点来源，结果显示这些基点由大整数运算软件包 FreeLIP 中的随机数生成器产生。Anthropic 称，此前还没有 NIST 曲线基点的生成过程得到类似解释。

时间戳本身不具备密码学安全性，lrand48 也早已被视为弱随机数生成器，但它们在这里承担的是生成公开曲线参数的作用，并未用于保护私钥。更重要的是，这套生成过程可以被公开复现。与来源不明的口令或人为指定参数相比，普通随机数生成器加时间戳的解释为秘密操纵曲线留下的空间更小。不过