你想要部署 FN-DSA

# 所以你想部署FN-DSA 来源：https://keymaterial.net/2026/05/13/so-you-want-to-deploy-fn-dsa/ FN-DSA（原名Falcon）是一项拟议的后量子签名标准，它持续让工程师们两极分化。一方面是密码学工程师，他们被要求实现这个潜在的怪物，对此深恶痛绝。另一方面是协议工程师，尤其是在处理UDP时，他们看到了一线希望——或许不必应对数据包分片，因此非常想用它。 大多数情况下，我同意我的密码学工程师同行们的观点：使用FN-DSA的最佳方式就是不用。然而，无论是毒品还是密码学，禁绝主义都是失败的方法。因此，本着降低危害的原则，以下是为任何想使用FN-DSA的人准备的关键注意事项，以便他们能尽可能安全地使用。 ## 标准状态 FN-DSA最大的问题是标准目前尚不存在。NIST已于2025年8月准备了初始公开草案（ipd），但这份草案——至少在我撰写本文的2026年5月——仍卡在NIST的发布流程中，状态不明。因此当前它更像是初始私人草案。 ipd未发布意味着我在此提出的所有观点都基于最终将演变为FN-DSA的、名为Falcon的第三轮候选方案，而且这些观点中的部分或全部很可能会在实际的ipd中得到解决。或者是在实际的标准中得到解决。重要的是，从ipd到标准大约需要一年时间，如果采用与ML-KEM/ML-DSA/SLH-DSA相同的审查力度，那么可以说，由于FN-DSA算法的复杂性，它可能还需要更多的审查。ipd和最终标准之间通常会引入重大变更，这意味着任何希望直接使用FN-DSA解决所有尺寸问题的人都必须等待至少一年，甚至可能数年，直到标准真正准备好可以实施。 ## FN-DSA的预哈希 预哈希是一个非常奇怪的话题。一半密码学界坚持认为它绝对必要，而另一半则从未听说过它。通常，从未听说过的那一半是理论密码学家，他们根本不是这篇博文的目标读者，所以我会简短解释什么是预哈希。更详细的讨论可以在我的博文《对ML-DSA进行预哈希的危害》（https://keymaterial.net/2024/11/05/hashml-dsa-considered-harmful/）中找到。 简而言之，预哈希将签名生成变成了一个多方算法：一方（签名者）持有私钥，但计算资源有限；另一方（哈希者）持有消息，且计算能力不受限。在此场景下，我们希望限制传输给签名者的数据量，理想情况下仅传输一个哈希。为了使此过程对所有验证方透明，人们通常希望生成的签名是完全符合标准的标准签名，并且没有对消息应用标准未提及的额外哈希。 经典签名算法（特别是RSA和ECDSA签名）通常分解为哈希步骤和签名步骤。从业者看到这种分解，便自然地将预哈希引入其中：哈希者计算哈希，签名者再基于该哈希计算签名的其余部分。这甚至延伸到了X.509证书——它为给定的消息定义了要使用的哈希函数（与该消息本身关联，而非对应的公钥），使得X.509证书在技术意义上不再是一个完全定义的签名方案。 对于RSA和ECDSA，这大多是无害的，但并非完全无害。特别是RSA存在一种伪造攻击：哈希者可以伪造一条签名者从未见过其哈希的消息的签名。然而，由于签名者一开始只能看到消息的哈希，它实际上无法对消息本身进行任何有意义的验证，因此哈希者的伪造攻击在预哈希威胁模型中被认为无关紧要。但密钥恢复攻击则完全不同。毕竟，预哈希的目的是让私钥处于某种比在哈希者手中更难泄露的环境中，因此任何允许哈希者恢复密钥的攻击都是灾难性的，完全违背了使用预哈希的初衷。 而事实证明，Falcon恰好就有一种这样的密钥恢复攻击。要理解原因，需要认识到哈希函数在签名方案中有两个不同的用途：消息压缩和随机函数模型。当哈希函数仅用于压缩时，预哈希工作良好；但一旦它还需要提供其他安全保证，就会开始失效。 对于Fiat-Shamir变换签名方案，安全相关的哈希函数总是深埋在签名算法内部，因为哈希需要同时包含消息和承诺，而承诺只在算法后期才会计算。ML-DSA有一个单独的消息压缩哈希（用于计算那个臭名昭著的μ（https://keymaterial.net/2024/11/05/hashml-dsa-considered-harmful/）），可用于预哈希。ECDSA则是一种YOLO签名方案，没有明确的安全规约，只是不将承诺哈希进挑战中，而据我们所知，并没有发生什么可怕的事情。 然而，RSA和FN-DSA一样，被称为“哈希然后签名”方案。哈希然后签名方案通常的工作原理是：有一个陷门函数f，它在单向容易计算，但求逆需要私钥；以及一个哈希函数h。签名s是f定义域中的一个值，满足f(s) = h(m)。我们可以看出，这个哈希具有关键的安全作用——如果没有它，我们可以轻易找到存在性伪造：只需从定义域中随机选取一个s，计算f(s)。恭喜，你已经伪造了针对f(s)的签名。但有了哈希函数，这就行不通了，因为我们还需要找到f(s)在h下的原像，而如果不破解哈希函数，我们无法做到。 关键点来了：FN-DSA不仅在没有哈希函数时允许伪造，它还会直接泄露其私钥。安全实现FN-DSA的唯一方法是让签名者选取一个随机值，将其与消息连接，哈希，然后再对这个本质上是随机的值进行签名。对非随机值进行签名会破坏方案。 至少在三轮算法描述中，**没有安全地对FN-DSA进行预哈希的方法**，但有一个非常诱人的哈希函数调用，会引诱粗心的实现者这样做。预哈希FN-DSA唯一可行的选择是引入一个单独的消息压缩哈希，并对消息进行双重哈希。 ## 关于那些浮点数 可能讨论最频繁的FN-DSA特性是规范中使用了浮点数。浮点数内置于算法的数学中（见下文，其中会大量提及\mathbb{C}，复数）。没有浮点数就不可能实现FN-DSA。 但是，可以在常数时间内实现浮点运算。为此，我们只需要翻开数值分析教科书，手动实现浮点数——每个浮点数跟踪两个整数，一个尾数，一个指数。乘法很容易实现常数时间，实际上它可能已经是常数时间的，只需两个整数运算。加法稍微棘手，但也不是世界末日。你需要一些常数时间比较来正确对齐两个数，但这不算大问题，只会带来相对较小的性能损失。然而，除法是一场噩梦。标准的浮点除法算法是一个迭代过程，每次迭代使用多次乘法和加法，并在结果足够精确时返回。 对于常数时间算法，这行不通，我们只能在任何情况下都迭代相同步数才能返回，从而将所有情况都变成最坏情况性能。我们不难计算出这个迭代上限，但目前没有任何现有硬件，只有非常有限的软件采用这种方式实现。除此之外，这迫使我们所有情况都是最坏情况复杂度，尤其是在软件实现中，这会让事情慢得可怕。 当我在我的破电脑代数https://github.com/sophieschmieg/abca/blob/master/src/main/java/cryptography/Falcon.java）系统中实现Falcon时，很大一部分时间都花在重构我现有的任意精度浮点逻辑上——当任意精度被设置为64位时，切换到使用double，原因仅仅是因为我非常数时间的浮点除法软件实现实在太慢，以至于在调试算法时我厌倦了等待。 这对签名者的性能有重要影响。虽然FN-DSA的验证逻辑特别快且简单，但签名要么极其缓慢，要么不是常数时间，每种情况都可能使你的应用无法进行实时签名。 说到调试算法，浮点逻辑另一个有趣的怪癖是它只定义到epsilon精度。同一IEEE浮点标准的不同实现在某些输入上会产生不同的结果。通常这不太重要，因为差异只在最低有效位，毕竟它们是舍入误差，所以使用浮点数的人通常不关心这个问题——数值分析师会进行适当的误差计算，其他人则只是接受细微的错误。但对于密码学家来说，这意味着测试向量不太管用。事实上，Falcon是我第一次也是唯一一次需要使用统计测试来调试实现中特别棘手的错误。 ## 可变签名大小 FN-DSA的另一个有趣怪癖是签名大小可能可变，也可能不变。这并不像乍看起来那么不寻常，事实上，如果你看过一般的ML-DSA签名，你很可能注意到有效签名末尾有可疑数量的零字节。这是因为ML-DSA签名也是可变大小的，标准只是将它们填充为相同大小。 对于FN-DSA，我们尚不知道NIST将在标准中写什么，但他们至少考虑过不这么做（https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Dpr3tnTlKy0/m/CZneBCe6AQAJ）。毕竟，FN-DSA的全部意义在于体积小，而填充签名与此背道而驰。所以请注意，签名大小可能可变，也可能不变。 ## FN-DSA的数学 最后，简单聊聊FN-DSA的数学。鉴于目标受众是应用开发者而非密码学家，我将简短介绍，不深入探讨，也许我会在后续文章中展开。但简而言之：FN-DSA的数学非常优美。它基于NTRU而不是LWE，这意味着我们计算的不是 As + e = t（其中s和e短小），而是计算 fG - gF = q（所有四个元素短小），然后将公钥设为 h = f/g mod q。这两个问题密切相关（它们都是p-adic有理重构问题，在NTRU中尤其明显，因为我们的公钥就是一个有理数，舍入到一个q-adic数字），主要区别在于NTRU计算完整的格基，而LWE只计算一个短格向量。 有了这个短格基，我们现在可以解决最近格向量问题。为了签名，我们正是这样做的：我们签名一个整数r，通过计算满足 s_1 + h·s_2 = r 且 s_1, s_2 短小的 s_1, s_2。为了将其变成签名方案，你只需哈希你的消息并签名得到的哈希。 然而，如果在签名时真的解决了最近向量问题，我们会泄露关于短基的信息，所以我们实际做的是使用我们的基来找到一个“足够接近，但不一定最近”的向量。这就是所有复杂计算的地方，也是Falcon与数域逻辑深度交织的地方——ML-DSA只是将其用作方便加速的工具。为了计算这个点，我们查看数域的复数嵌入，利用这些嵌入反映在快速傅里叶变换（FFT）中的事实，并且这些FFT在数域阶模掉(q)时会转化为数论变换（NTT）。 为了安全，如第一段所述，我们需要确保永远不签名相同的消息两次，并且永远不让攻击者选择我们签名的整数。我们通过不是直接哈希消息，而是将消息与一个随机整数一起哈希来实现这一点。也就是说，我们签名（和验证）一条消息时，通过计算（或检查）满足 s_1 + h·s_2 = h(r || m) 的 s_1, s_2，并将 s_2, r 作为签名发布（s_1 可以从这两个值重新计算，我们需要验证它们都很小）。 这就是非常简略的数学运作方式。关于这些傅里叶变换如何工作以及如何帮助计算接近但不至于太接近的格点，还有很多可以说的。但如果我要讲解那一部分数学，就需要专门写一篇博文，这样我仍然可以把这一篇标记为可理解的密码学。