我们现在知道 NIST 椭圆曲线的种子是如何生成的：它们不是某些俏皮句子的哈希，而是用时间作为种子对 drand48 的输出，确实是在 1997–98 年。John Wood、Henry de Valence、Ava Howell、Zack Voase、Lucy Sweet、Amir Omidi、Paul Crowley、Iain McGinniss、Nicholas Carlini 和 Steve Weis 来自 Anthropic 解决了这个谜题，并在 2026 年 10 月 15 日 01:07:51 UTC 认领了我三年前公布的全额悬赏。他们选择将奖金捐赠给运营 Let’s Encrypt 的非营利组织 ISRG，奖金价值三倍增至 36,864 美元（36 Ki$）。感谢 Amir Omidi、Chris Palmer、Colm MacCárthaigh、David Adrian、David Anderson、Jeff Hodges、Matt Green、Matthew McPherrin、Paul Kehrer、Ryan Sleevi 和 Soatok 对悬赏的贡献。这帮助完善了密码学历史的一页，并增强了我们对这些关键密码原语的信心。NIST 椭圆曲线（P-192、P-224、P-256、P-384 和 P-521）在 2000 年由 NIST 在 FIPS 186-2 中发布。它们是按 ANSI X9.62 以任意种子随机生成的，通过用 SHA-1 对其进行哈希，并使用输出派生一些参数。在这个星期之前，我们根本不知道这些任意种子是如何挑选的。传说是 Dr. Jerry Solinas，于 2023 年初去世，1997 年通过对一些他后来忘记的英语句子进行哈希来生成它们。你可以在 Steve Weis 撰写的这篇文章或原始悬赏公告中阅读更多。事实证明，记忆会欺骗每个人：我们现在知道它们实际上是使用 POSIX 标准的 drand48 随机数生成器生成的。该算法简单到只需将当时的 UNIX 时间戳传递给 srand48()，然后通过 drand48 一次生成一个字节。每 20 字节的序列都作为种子尝试，遵循 ANSI X9.62，并在结果曲线无效时被拒绝。一些时间戳用于生成多个曲线，接受第一个后继续尝试种子。我在 Go 中重新实现了该算法以验证这一说法。阅读更多关于 Anthropic 的论文。除了 ANSI X9.62 之外，还有两个额外的未记录标准，一个相对明确，一个仍然让我们困惑。如果生成曲线的阶 n 的位长度大于曲线的基本域 p 的位长度，则种子将被拒绝。（该条件并不是更严格的 n < p，因为 prime239v2 的 p < n < 2²³⁹。）这使我们拥有的有效种子大约是发布数量的两倍。我们探索了很多对此最后一点的解释，没有找到合适的匹配。也许使用了相同的 RNG 来验证种子，消耗了 RNG 输出并跳过一些潜在的候选者，尽管“缺口”并不是规则的。也许算法中仅存在一个错误，每次返回错误结果的概率为 50%；这些计算在 1997 年时仍是非常尖端的技术，而现在我们可以在几分钟内用现成的软件完成。srand48(863711343) [1997-05-15 15:49:03 +0000 UTC]：接受第 36 个种子 25e5[...]：未发布接受第 1562 个种子 d09b[...]：未发布接受第 2185 个种子 e43b[...]：prime239v1接受第 2320 个种子 e8b4[...]：prime239v2接受第 2491 个种子 1256[...]：未发布接受第 2682 个种子 d2c1[...]：未发布接受第 2863 个种子 3a70[...]：未发布接受第 3048 个种子 7d73[...]：prime239v3 srand48(863966734) [1997-05-18 14:45:34 +0000 UTC]：接受第 139 个种子 3045[...]：P-192 即 prime192v1接受第 2198 个种子 692d[...]：未发布接受第 5228 个种子 c469[...]：prime192v3接受第 5405 个种子 3ad1[...]：未发布接受第 6013 个种子 31a9[...]：prime192v2 srand48(871002724) [1997-08-08 01:12:04 +0000 UTC]：接受第 1136 个种子 d09e[...]：P-521 srand48(871696354) [1997-08-16 01:52:34 +0000 UTC]：接受第 876 个种子 50c7[...]：未发布接受第 1842 个种子 c49d[...]：P-256 即 prime256v1 srand48(872952608) [1997-08-30 14:50:08 +0000 UTC]：接受第 2688 个种子 a335[...]：P-384 srand48(891607927) [1998-04-03 12:52:07 +0000 UTC]：接受第 777 个种子 d007[...]：未发布接受第 1485 个种子 18cf[...]：未发布接受第 5736 个种子 3c17[...]：未发布接受第 7026 个种子 bd71[...]：P-224 对基于 NIST 曲线的椭圆曲线密码学的安全性意味着什么？好吧，即使在这一发现之前，业内也没有什么严重的担忧。在他们 2015 年的论文《包裹在谜团中的谜团》第 3.1 节中，Koblitz 和 Menezes 提出了一个令人信服的论点，认为 NSA 不可能选择一个种子来利用一个逃脱超过 15（现在是 25）年的密码分析的弱点。然而，在该论文的后续版本中，Daniel Bernstein 和 Tanja Lange 在 2017 年向 Koblitz 和 Menezes 描述了一种技术，该技术可能利用了选择种子的 70 位自由度，以针对一个假设类的 2⁶¹ 弱素数阶曲线。（Bernstein 是一个竞争的椭圆曲线设计 Curve25519 的作者。）