1. 引言FN-DSA原名 Falcon是一项拟议中的后量子签名标准它一直让工程师们意见两极分化一边是密码学工程师他们可能得负责实现这个庞然怪物因此对它深恶痛绝。另一边是协议工程师尤其是那些使用 UDP 的工程师他们从中看到了一线希望——也许终于不必处理数据包分片了——所以非常想采用它。在大多数情况下 Sophie Schmieg 和其他密码学工程师看法一致使用 FN-DSA 的最佳方式就是不用它。然而无论谈的是毒品还是密码学禁止都不是一种成功的做法。因此本着减少伤害的原则下面列出了所有想使用 FN-DSA 的人都必须了解的关键注意事项以便尽可能安全地使用它。2. FN-DSA 标准的现状FN-DSA 最大的问题是目前根本不存在正式标准。NIST 已于 2025 年 8 月准备好初始公开草案IPDinitial public draft但至少截至本文写作时的 2026 年 5 月该草案仍卡在 NIST 发布流程中的某个环节状态不明所以眼下它更像是一份“初始非公开草案”。由于 IPD 尚未发布在这里提出的所有观点都以第三轮候选方案 Falcon 为基础Falcon 最终将演变为 FN-DSA而真正的 IPD 完全有可能解决其中部分乃至全部问题最终标准更是如此。需要特别注意的是如果 FN-DSA 接受与 ML-KEM、ML-DSA 和 SLH-DSA 相同程度的审查从 IPD 到正式标准大约需要一年甚至可以说鉴于算法的复杂性FN-DSA 可能需要严格得多的审查。从 IPD 到正式标准之间通常会引入破坏兼容性的变更。这意味着任何希望立即使用 FN-DSA 解决所有签名尺寸问题的人都必须至少再等一年甚至数年标准才真正具备可实现性。2. 对 FN-DSA 进行预哈希预哈希是一个非常奇怪的话题。密码学界有一半人坚持认为它绝对不可或缺另一半人却从未听说过它。通常没听说过预哈希的那一半是理论密码学家而他们显然不是这篇博客文章的目标读者因此在此只会简要说明什么是预哈希。更全面的讨论可参见关于 ML-DSA 预哈希的2024年11月博客文章——HashML-DSA considered harmful。简单来说预哈希把签名生成变成了一个多方算法一方签名者持有私钥但计算资源有限另一方哈希方持有消息计算能力则不受限制。在这种场景下希望尽量减少传给签名者的数据量理想情况下只传一个哈希值。为了让这一过程对任何验证方都透明人们通常希望最终得到的签名仍然是完全符合标准的消息签名而不是先对消息额外应用一次标准未规定的哈希。经典签名算法尤其是 RSA 和 ECDSA 签名通常可以分解为哈希步骤和签名步骤。实践者看到这种分解后很自然地把它当作引入预哈希的方式由哈希方计算哈希值再由签名者基于该哈希值完成签名的其余计算。这种做法甚至发展到了这样的程度X.509 证书会随消息本身定义该消息所用的哈希函数而不是随相应公钥定义它因此严格来说X.509 证书并没有定义一个完整的签名方案。对于 RSA 和 ECDSA这种做法大体上无害但并非完全无害。尤其是 RSA 存在一种伪造攻击哈希方可以为某条消息伪造签名而签名者甚至从未见过这条消息的哈希值。不过由于签名者本来就只能看到消息的哈希值无法对消息本身做任何有意义的验证因此在预哈希的威胁模型中哈希方发起的伪造攻击并不被视为相关威胁。相比之下密钥恢复攻击则绝对相关。毕竟预哈希的目的就是把私钥放在一个比哈希方环境更难外泄的位置因此任何能让哈希方恢复密钥的攻击都将是灾难性的也会从根本上否定采用预哈希的意义。而 Falcon 恰好就存在这样一种密钥恢复攻击。要理解原因必须认识到哈希函数在签名方案中有两种不同用途一是压缩消息二是充当随机函数模型。只要哈希函数仅用于压缩预哈希就没有问题可一旦它还必须承担其他安全保证预哈希就开始失效。对于经 Fiat–Shamir 变换得到的签名方案与安全性相关的哈希函数总会埋在签名算法更深的位置因为其输入既要包含消息也要包含承诺而承诺要到算法后续阶段才能计算出来。ML-DSA 具有单独的消息压缩哈希用于计算臭名昭著的μ \muμ因此可以用它进行预哈希。ECDSA 则是一种“YOLO”签名方案它并没有清晰的安全性归约而且根本不把承诺哈希进挑战值就目前所知倒也没有因此发生什么可怕的事情。然而RSA 和 FN-DSA 一样都属于所谓的“哈希后签名”hash-and-sign方案。这类方案通常使用一个陷门函数f ff和一个哈希函数h hh正向计算f ff很容易但要计算其逆则必须拥有私钥。签名s ss是f ff定义域中的某个值并满足f ( s ) h ( m ) f(s)h(m)f(s)h(m)。要理解这个哈希为何承担着关键的安全作用只需观察去掉它之后会发生什么可以轻易找到一个存在性伪造。只要从定义域中随机选择一个s ss再计算f ( s ) f(s)f(s)即可。恭喜这样就已经为f ( s ) f(s)f(s)伪造了一份签名。但有哈希函数时这种做法就走不了多远因为还必须找到f ( s ) f(s)f(s)在h hh下的一个原像除非攻破哈希函数否则做不到这一点。关键问题来了去掉哈希函数后FN-DSA 不仅允许伪造甚至会直接开始泄露私钥。要安全地实现 FN-DSA唯一的办法是让签名者选择一个随机值将其与消息拼接后做哈希再对这个本质上随机的值计算签名。对非随机值签名会破坏整个方案。至少在第三轮算法说明中不存在安全预哈希 FN-DSA 的方法但其中有一次看起来极具诱惑力的哈希函数调用很容易让粗心的实现者误以为可以用它进行预哈希。预哈希 FN-DSA 唯一可行的选择是引入一个独立的消息压缩哈希对消息进行两次哈希。3. 关于那些浮点数FN-DSA 最常被讨论的特性大概就是规范使用了浮点数。浮点数是该算法数学结构中不可分割的一部分参见下文其中会多次提到复数域C \mathbb{C}C。FN-DSA 不可能在完全不使用浮点数的情况下实现。不过浮点运算确实可以实现为常数时间。为此只需翻开数值分析教材手工实现浮点数每个浮点数用两个整数跟踪一个表示尾数另一个表示指数。乘法非常容易做成常数时间事实上它很可能本来就是常数时间的只需要两次整数运算。加法稍微麻烦一些但也不至于无法应付。为了正确地移动两个数并使其对齐需要进行一些常数时间比较不过问题不大性能损失也相对有限。但除法简直是一场噩梦。浮点数常用的标准除法算法是一个迭代过程每一轮都要执行多次乘法与加法等结果达到足够精度后才返回。这对常数时间算法而言不可接受无论输入是什么都只能在完成相同轮数的迭代后返回于是所有情况都会退化到最坏情况性能。计算这个迭代上限本身并不难但目前几乎没有硬件、也只有极少的软件采用这种实现方式。此外它迫使每一种输入都承担最坏情况复杂度尤其在软件实现中这会让算法慢得令人胆寒。Sophie Schmieg在自己的 bad computer algebra 系统中实现 Falcon 时花了相当多时间重构原有的任意精度浮点逻辑当任意精度被任意地设为 64 位时就改用双精度浮点数。唯一的原因是这套非常数时间的软件浮点除法实现慢得令人痛苦在调试算法时Sophie Schmieg实在厌倦了等待。这会给签名端带来重要的性能影响。FN-DSA 的验证逻辑尤其快速、简单但签名要么慢得可怕要么无法做到常数时间无论哪种情况都可能让它不适合需要实时签名的应用。说到调试算法浮点逻辑还有另一个有趣的怪癖它只在误差ε \varepsilonε范围内有定义。即便是同一个 IEEE 浮点标准的不同实现也会对某些输入给出不同结果。通常这并不是什么大问题因为差异只存在于最低有效位——说到底只是舍入误差。处理浮点数的人往往不会在意如果是数值分析师他们会进行适当的误差分析否则他们只是接受结果会有细微偏差。但对密码学家来说这意味着测试向量没法完全正常工作。事实上Falcon 是Sophie Schmieg第一次、也是唯一一次不得不用统计检验来调试实现中某个格外棘手错误的算法。4. 可变的签名大小FN-DSA 的另一个有趣怪癖是其签名大小可能可变也可能不可变。这并不像乍看起来那么罕见。事实上如果观察过普通的 ML-DSA 签名很可能会注意到有效签名末尾存在数量可疑的零字节。这是因为 ML-DSA 签名本身也是可变长的只不过标准用填充把它们统一成了相同长度。对于 FN-DSA还不知道 NIST 最终会在标准中写什么但他们至少考虑过不进行这种填充。毕竟FN-DSA 的核心卖点就是尺寸小而填充签名恰恰与此背道而驰。因此请注意FN-DSA 的签名大小可能是可变的也可能不是。经典算法中已有可变长签名的先例ECDSA 签名采用 ASN.1 格式编码时长度并不固定但如果使用更优秀的 IEEE 格式则不存在这个问题。可变长签名确实容易引发问题。甚至当某个团队抱怨验证偶发失败时Sophie Schmieg几乎不用看相关产物就能断定原因是没有正确地在签名中添加或移除零字节从而使 ASN.1 签名有1 / 256 1/2561/256的概率格式错误。总的来说这种特性并非无法应对但也绝不是一种从未引发过缺陷的特性。5. FN-DSA 的数学原理最后简单谈谈 FN-DSA 的数学原理。考虑到目标读者是应用开发者而非密码学家这一节会保持简短不做太深入的展开也许会在后续文章中详述。简而言之FN-DSA 的数学结构美得惊人。它基于 NTRU而不是 LWE。这意味着不是在s ss和e ee都很短的条件下计算A s e t AsetAset而是在f ff、g gg、F FF、G GG四个元素都很短的条件下计算f G − g F q fG-gFqfG−gFq然后把公钥设为h f / g m o d q hf/g \bmod qhf/gmodq。这两个问题密切相关它们都是p pp-adic 有理重构问题在 NTRU 中尤其直观因为该公钥实际上就是一个有理数只不过被舍入到一个q qq-进数位。主要区别在于NTRU 计算的是一组完整的格基而 LWE 只计算一个短格向量。有了这组短格基就能求解最近格点问题。签名时做的正是这件事要对整数r rr签名就计算s 1 , s 2 s_1,s_2s1​,s2​使s 1 h ⋅ s 2 r s_1h\cdot s_2rs1​h⋅s2​r且s 1 , s 2 s_1,s_2s1​,s2​都很短。要把它变成签名方案只需对消息做哈希然后对所得哈希值签名。然而如果签名时真的精确求解最近向量问题就会泄露短格基的信息。因此实际使用格基寻找的是一个“足够近、但未必最近”的向量。所有棘手的计算都出现在这里也正是在这里Falcon 与数域逻辑深度交织而 ML-DSA 只是把数域逻辑当作一种方便的加速手段。为了计算这个点考察数域的复嵌入利用它们会体现在快速傅里叶变换中的事实以及当数域的整数环对理想( q ) (q)(q)取商时这些 FFT 会转化为 NTT 的事实。如开头所述为了确保安全必须保证绝不对同一条消息签名两次也绝不能让攻击者选择所签名的整数。对应的做法不是直接对消息做哈希而是把消息与一个随机整数一起做哈希。也就是说对消息签名或验证签名时需要计算或检查满足s 1 h ⋅ s 2 h ( r ∥ m ) s_1h\cdot s_2h(r \parallel m)s1​h⋅s2​h(r∥m)的s 1 , s 2 s_1,s_2s1​,s2​并将s 2 , r s_2,rs2​,r作为签名公开s 1 s_1s1​可以由这两个值重新计算出来而且还需要验证s 1 , s 2 s_1,s_2s1​,s2​都很小。以上只是对其数学原理极度简化的介绍。关于这些傅里叶变换如何工作以及它们如何帮助计算距离近、但又不会过近的格点还有许多内容可讲。后续将展开。6. FN-DSA作者Thomas Prest 2026年5月27日反馈预哈希。我的确属于“从未听说过它的另一半”。依我的理解你所描述的假想预哈希模式是把“预哈希”c cc定义为c H ( m s g , s a l t ) cH(\mathrm{msg},\mathrm{salt})cH(msg,salt)。我同意不应该这样做但还有很多其他可行的解决方案其中一种甚至已经在你的文章中有所暗示。如c H 1 ( H ( m s g ) , s a l t ) cH_1(H(\mathrm{msg}),\mathrm{salt})cH1​(H(msg),salt)看起来就能实现这样的功能目标把H ( m s g ) H(\mathrm{msg})H(msg)的计算委托给另一台设备。只要在签名时随机采样s a l t \mathrm{salt}salt这样做就是安全的。如果还想把公钥p k \mathrm{pk}pk也哈希进去那么可以使用c H 1 ( H 2 ( p k ) , H ( m s g ) , s a l t ) cH_1(H_2(\mathrm{pk}),H(\mathrm{msg}),\mathrm{salt})cH1​(H2​(pk),H(msg),salt)并预先计算和存储H 2 ( p k ) H_2(\mathrm{pk})H2​(pk)。浮点数。我完全同意它们无论从实现还是安全分析的角度看都极其烦人。这里先稍微预告一下过去大约一年里我一直在与其他研究人员合作开发 Falcon 的定点数实现。简而言之Falcon 可以使用 64 位定点整数而非 float64 实现对安全性的影响很小规范也只需做极少改动。我们有一篇证明这一点的论文Toward a Secure Fixed-Point Implementation of the Falcon Signature Scheme被 CRYPTO 接收并将在 CRYPTO 终稿截止日期6 月 8 日后不久发表。我知道严格来说这会“破坏规范兼容性”但我们已将论文告知 NIST也会在 PQC 论坛上进行说明希望双方都能看到该提案的价值从而推动它进入标准。可变的签名大小。2020 年 10 月发布的最新版规范强制要求签名具有固定长度。我知道参考实现对此更为含糊也支持可变长度但规范本身写得很清楚。我不知道 IPD 会怎样规定不过希望它会强制采用固定长度。FN-DSA 的数学原理。我同意你的看法——它太复杂了。现有文献中有一些简化 Falcon 签名流程的技术尤其是“Antrag”我曾在 2024 年推动采用“Antrag”但目前看来NIST 已决定维持 Falcon 原样。参考资料[1] Sophie Schmieg 2026年5月13日博客 So you want to deploy FN-DSA