NIST曲线种子破解：关于ECDSA起源的5个误区

二十五年来，NIST ECDSA曲线种子几乎就是应用密码学里最接近“未破悬案”的存在。五个看似随机的160位数值由NSA交给NIST，却没有任何解释，而它们却支撑着从TLS连接到比特币交易的一切签名。本周这桩案子终于结了，答案几乎让人尴尬：这些种子是C标准库的lrand48()生成器输出的，种子来自1997和1998年的Unix时间戳。就这么简单。没有什么秘密口令的哈希，也没有高深机制，就是srand48(time(NULL))，每门安全课程都告诉你千万别用的写法。

这一发现来自Anthropic的一个研究模型。一位好奇的员工把问题丢给它，模型从已公布的常量中识别出了九十年代线性同余生成器的统计特征，然后把状态倒推，直到对上日历日期。我在密码系统审计上花了不少年头，清楚这件事的分量。不是因为这些曲线被破解了（它们并没有），而是因为它推翻了业内几条我们一直深信不疑的东西。下面我们一个一个来看这些误区。

误区一：来历不明的常量就意味着隐藏后门

这种怀疑并非无中生有。2000年NIST发布FIPS 186-2曲线时，每条曲线都附带一个种子，其哈希值决定曲线系数b。NIST称这些种子保证了曲线“可验证地随机”，却说不清、或者不愿说清种子本身是怎么生成的。Koblitz和Menezes为此写了一整篇论文，标题毫不客气，叫《包裹在谜团中的谜题》（A Riddle Wrapped in an Enigma）。社区里最有价值的线索来自NSA的Jerry Solinas，他在2015年回忆说，输入是一句幽默短语的哈希，大意是“给Bob和Jerry加薪”。他在2023年去世，细节始终没能还原。

对于爱琢磨阴谋的人（包括我自己有时候）来说，真相有点扫兴：来历不明通常意味着没有文档，而不是存心作恶。实际的生成过程是一个开发者跑了一个小型C程序，让默认的伪随机数生成器用墙上时钟自行播种，然后取第一个能生成可用曲线的候选。P-256公布的种子，来自1997年8月16日凌晨1:52开始的一次运行中的第1842号候选。这不像是某个机构在植入数论陷阱的做法，更像是一个工程师凌晨一点跑循环，直到输出一个有效结果。

我在事故复盘里见过太多次这种模式了。一个神秘的配置值、一个没有记录的魔法常量、一个没人说得清的部署步骤，最后复盘发现，那只是某个疲惫工程师当时觉得合理的捷径，从没写下来过。NSA在这件事上的真正过错并不是在曲线里埋后门，而是把密码学常量发给了全世界，却没附上一份README。

误区二：生成方法能证明选择过程是诚实的

接下来是矫枉过正。这一周很多评论把“不过是时间戳”当作彻底洗白的证据。并非如此，研究者们自己也很谨慎地强调这一点。知道候选是怎么生成的，并不能告诉你最终曲线是怎么挑出来的，而这个挑选过程持续了好几个月，从1997年5月到1998年4月。

证据是双向的。在P-256的那次运行中，第876号候选同样生成了一条阶数为素数、规模合适、并采用相同参数约定的曲线，但它被跳过了。最终公布的是第1842号。P-224的那次运行跳过了三条可行的曲线，ANSI X9.62的几次运行又跳过了另外七条。我们能看到的只是运行记录中可追溯的候选，被丢弃候选的完整历史我们并不知道。如果有人想要一条带有某种罕见特性的曲线，原则上完全可以在时间戳里搜索，直到找到为止，然后对时间戳只字不提。“做了但不说”从来都是一个选项。

我的看法是：在关注弱曲线研究多年之后，我认为后门假说虽然受到重创，但并未在形式上彻底死亡。被跳过的候选数量很少，如果靠挑选就能得到曲线，那意味着弱曲线很常见、很容易找到，而二十年的公开密码分析表明事实并非如此。目前还没有人公布过能把这些曲线和随机曲线区分开的区分器。但“目前没有已知弱点”和“可证明没有弱点”是两回事，诚实的立场只能是前者。这恰好是规范与实现之间的鸿沟在标准层面的体现：规范说的是“可验证地随机”，实现的结果却是“时钟显示什么就是什么”。

这些种子是一个研究生式的做法生成的：一个现成的伪随机数生成器加上系统时钟。丑闻从来不在数学本身，而在于缺失的文档。

误区三：老旧的弱伪随机数生成器只用一次就无害

每个写过srand(time(NULL))的工程师都该读到这里坐直了。这件事情之所以隐藏了二十五年，正是因为lrand48()的一个设计特性：它会泄露自身结构。这个生成器只返回48位状态中的高31位，因此它的输出字的最高位总是零。把输出写成32位字之后，十个二进制曲线种子中有四个在连续二十个字中最高位全为零，在均匀分布下，这种事件的概率约为五万八千分之一。这个特征对任何肯留意的人来说都肉眼可见。

从这里开始，攻击简单得令人尴尬。要恢复二进制曲线的状态，你只需取第一个输出字，暴力枚举隐藏的2^17个低位，再检查接下来的四个字是否符合规律。这只需要几毫秒的计算。对于素数曲线，种子每次输出保留的位数更少，因此恢复状态需要经典的截断线性同余生成器攻击：把它建模为格问题，然后用LLL基约化来求解。字面意义上的教科书内容。一旦拿到状态，线性同余生成器倒着运行和正着运行一样容易，于是你把它倒推，直到出现srand48初始化的形式（低位等于0x330E），然后读出它当初播种用的时间戳。

# The whole mystery, reproduced
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, ""   # state set by srand48(t)
for i in range(per * n):
x = (0x5DEECE66D * x + 0xB) % 2**48   # one lrand48 step
if i >= per * (n - 1):
out += "%0*X" % (width, x >> shift)
return out
# P-256: run started 1997-08-16 01:52:34 UTC, candidate 1842
print(candidate(unix("1997-08-16 01:52:34"), 1842, 20, 40, 2))
# -> C49D360886E704936A6678E1139D26B7819F7E90  (the published NIST seed)

这个教训不只适用于标准化组织。任何你输出的“看起来随机”的值，比如会话令牌、请求ID、盐值、文件名，都带着生成它的生成器的指纹。如果那个生成器是线性同余引擎或梅森旋转算法，少量输出就足以重建内部状态，你之前和之后生成的所有值都会变得可预测。二十五年前的一次使用，被伪装成噪声的文件，就这样被完全逆推了。每当我审查代码中用非密码学随机数生成器生成攻击者可以观察到的内容时，我从现在开始都会引用这个真实案例。

误区四：“无需解释的数字”从来都不是真正的保护

“无需解释”（nothing-up-my-sleeve）的思路是：从明显无害的东西推导常量，比如圆周率的数字，目的是限制设计者的自由度。如果我能证明我的常量来自一个公开、严格固定的流程，我就没有空间夹带后门。NIST的种子在程序上没能通过这项测试：流程是保密的，因此自由度的界限也就不得而知。但这一事件真正暴露的是：即便这种检验生效，它也比我们之前以为的要弱。

想想“从时间戳可验证地随机”到底能给你什么。对于一个合理的时间窗口，时间戳大约只有31位熵。任何人（包括原作者本人）都可以遍历数百万个时间戳，生成数百万条候选曲线，然后只公布他想要的那一条，连同看起来无害的种子一起。如果带有秘密弱点的曲线出现率是百万分之一，那么时间戳遍历一个下午就能找到一条。种子证明了数字从哪里来，却几乎没有说明为什么选中了这一个。对于“口令哈希”方案同样如此，这也是为什么关于Solinas那句笑话短语的传言，从来都谈不上让人完全放心。

现代更稳妥的做法是严格构造曲线：在搜索开始之前固定选择规则，并选取满足公开安全标准清单的最小系数。Curve25519背后的理念正是如此，Dan Bernstein关于刚性的论证也重塑了业界评估曲线的方式。抵御恶意常量的真正保护从来不是某个漂亮的推导故事，而是尽量缩小搜索空间、提前公布筛选标准，并让足够多的独立专家审视数学，使隐藏的性质无处藏身。审计常量，就意味着审计筛选它们的过程。这也是为什么这里那些尚未解答的问题（被跳过的候选、P-256等曲线中无法解释的基点，以及仍未查明来源的B-163种子）应当被明确记录在案，而不该被庆祝的喧嚣淹没。

误区五：LLM只会复述，做不了原创密码分析

这是最扎心的一条，因为我自己也曾相信过它的某个版本。这个未解问题悬而未决了四分之一个世纪，公开悬赏高达36,864美元，还吸引了不少资深业余爱好者的关注。Anthropic内部的几位研究人员也曾亲自追查过，顺着“某个搞笑短语的哈希”这条线索，最后无功而返。随后，一个内部研究模型在没有拿到传言的情况下，用不到半小时换了一个角度：它不再去猜哈希的输入，而是问哪种软件会生成这些种子，假设是九十年代C标准库的伪随机数生成器，然后写了一个扫描器，在每个种子上滑动测试34种生成器与输出切片的组合，发现最高位为零的规律，对截断后的输出运行格攻击，并把状态一路倒推到日历日期。

注意这套工作流程的性质。这不是记忆检索，因为没有任何训练文档包含这个答案，答案原本就不存在于任何地方。这是假设生成加工具使用加验证，正是密码分析工作的实际形态。模型甚至在运行中途检查了自己的合理性：这是不是模拟的测试环境？一个如此明显的东西真的会躺了25年无人发现吗？160位的匹配来自32位种子，能排除巧合吗？这种自我怀疑正是我对人类分析师的期待，坦白说，有些人类分析师反而会跳过这一步。我们在本站已经检验过关于这些模型实际工作方式的种种误解，而这是一个干净的数据点：LLM现在已经能够针对真实世界的制品执行多步取证推理，而不只是在基准测试上表现。

从业者提出的合理反驳集中在来源问题上。模型并没有发明LCG状态恢复或LLL算法，它站在数十年已发表的密码分析成果之上，这些成果有的署名，有的无名，而它也无法告诉你是哪些论文塑造了它的思路。这一点让我的在意程度比某些人低一些。扫描器、验证代码和复现脚本都是公开的；团队中的人类负责提出问题并验证结果。诚实地看待这种分工：机器提供了不知疲倦的假设搜索，人类提供了判断力和问责。那笔36,864美元的悬赏被交给了Internet Security Research Group，这是一种体面的收尾方式。

这对安全审计意味着什么

那么，这件事对一线工程师意味着什么？从现在起，我在审计中的做法会有几点具体转变。第一，把协议或代码库中的每个魔法常量都当作法医证据，而不是自然事实。先问它可能是哪种生成器产生的，检查结构性指纹（有偏的高位、与LCG相关的连续字、符合时间戳的状态恢复），然后再接受“它是随机的”这一说法。如今实现这些检测的工具已经触手可及。

第二，如果你要公布常量，就公布生成器。包括源代码、确切输入和确切环境。没有可复现流程支撑的“可验证地随机”，换来的只是二十五年的怀疑，以及你遗产上的一笔悬赏。第三，继续使用P-256。这一发现提升的是对这些曲线的信心，而不是降低它，而椭圆曲线真正的威胁模型是量子硬件，而不是1997年某台工作站的时钟。但也要坦诚地读懂那些未解问题：无法解释的基点和被跳过的候选是悬而未决的线头，成熟的安全工作意味着把它们保留在账本上。

最深刻的启示关乎机构记忆。Jerry Solinas记得一个关于加薪的笑话，结果证明记错了。用他自己的话说，相关档案可能就躺在约柜附近的某块硬盘里。我们今天之所以能知道真相，只是因为输出本身保留了足够的结构，才得以“招供”。你的系统此时此刻正在写下它们自己的供词，写在你发布的每一个ID、每一个令牌、每一个常量里。确保它们招出来的，是你为之自豪的东西。