4. ML-DSA签名生成实现

签名生成是ML-DSA实现中最核心的一环。它把私钥、消息和随机性（或确定性种子）组合起来，经过采样、拒绝、压缩等步骤，最终输出一个可被验证方还原的签名值。本节围绕“算法步骤—随机与确定性—API调用—编码格式”四条线索展开，帮助读者既能读懂规范，也能写出可运行的签名代码。

一、签名算法的内部步骤

ML-DSA（FIPS 204）的签名算法可以概括为“先承诺、再挑战、后响应”的Fiat-Shamir with Aborts结构。以ML-DSA-65为例，其参数为：环维度 n=256，模数 q=8380417，矩阵维度 k=6、l=5，私钥向量 s1 长度 l、s2 长度 k，挑战权重 τ=49，承诺向量 w 的系数范围由 γ2=(q-1)/32 约束。签名流程如下：

  1. 消息预处理：计算 μ = H(tr ‖ M)，其中 tr 是公钥哈希，M 为原始消息，H 为 SHAKE-256。μ 是后续挑战采样的输入，长度固定为64字节。
  2. 采样掩码向量 y：从 γ1 范围内均匀采样 l 个多项式组成 y。γ1 在ML-DSA-65中为 2^19。y 是“承诺”的随机来源，必须每次签名都新鲜。
  3. 计算承诺 w：w = A·y，其中 A 是由公钥种子 ρ 扩展出的 k×l 矩阵。随后做 Decompose(w)，得到高半部分 w1 和低半部分 w0。
  4. 计算挑战 c：c̃ = H(μ ‖ w1)，再把 c̃ 通过 SampleInBall 扩展为稀疏挑战多项式 c，其非零系数个数为 τ，系数取 ±1。
  5. 计算响应 z：z = y + c·s1。随后检查两个条件：z 的无穷范数是否小于 γ1−β（β=τ·η，η 为私钥系数界），以及 c·s2 的低半部分是否满足 w0 的约束。任一不满足则拒绝，回到第2步重新采样 y。
  6. 输出签名：σ = (c̃, z, h)，其中 h 是提示向量（hint），用于验证方在 w1 被“截断”后仍能正确还原。

这里的关键是“拒绝采样”：签名不是一次成功，而是循环直到 z 和 h 都落在合法范围。规范给出的平均重试次数约为 4 次左右（与参数集有关），实现时必须用循环而非单次尝试，否则会产出非法签名或泄露私钥分布信息。

ML-DSA 签名生成：承诺—挑战—响应与拒绝回路 输入 私钥 sk、消息 M μ = H(tr ‖ M) SHAKE-256，64字节 采样 y ← γ1 范围 l 个多项式 w = A·y，Decompose(w) 得到 w1、w0 c̃ = H(μ ‖ w1) c = SampleInBall(c̃) z = y + c·s1 计算响应 合法性检查 ‖z‖∞ < γ1−β 且 w0 约束 输出 σ = (c̃, z, h) 编码后返回 通过 拒绝：重采样 y 参数示例（ML-DSA-65） n=256，q=8380417，k=6，l=5，τ=49，γ1=2^19，γ2=(q−1)/32，β=τ·η 签名长度：c̃ 为 48 字节，z 为 k·l·? 编码，h 为提示位串；总长约 3309 字节

二、随机签名与确定性签名

规范允许两种签名模式。随机签名（hedged）在采样 y 时引入新鲜随机数，每次对同一消息签名结果都不同；确定性签名（deterministic）则把私钥中的随机种子 rnd 与 μ 一起哈希，派生出一个确定的伪随机流来生成 y，因此同一密钥、同一消息永远得到相同签名。

两种模式在安全上都被认可，但用途不同。确定性签名便于测试向量复现和签名去重，适合嵌入式设备或需要可审计的场景；随机签名在侧信道防护上更稳健，因为即使攻击者通过故障注入让某次签名的随机数泄露，也无法预测下一次的 y。工程上常见的做法是：默认使用随机模式，测试环境通过注入固定 rnd 切换到确定性模式，以便与官方KAT（Known Answer Test）比对。

需要强调的是，无论哪种模式，都不能把 y 固定成常量。确定性签名中的“确定”来自对 (rnd, μ) 的哈希派生，而不是复用同一个 y；若实现者误把 y 写死，会直接导致私钥可被恢复。

三、调用API生成签名

以常见的 liboqs 为例，签名接口遵循“初始化—签名—释放”的模式。下面是一段可直接编译的C示例，演示对一段消息生成ML-DSA-65签名：

#include <oqs/oqs.h>
#include <stdio.h>
#include <string.h>

int main(void) {
    OQS_SIG *sig = OQS_SIG_new(OQS_SIG_alg_ml_dsa_65);
    if (!sig) { printf("算法不可用\n"); return 1; }

    uint8_t pk[OQS_SIG_ml_dsa_65_length_public_key];
    uint8_t sk[OQS_SIG_ml_dsa_65_length_secret_key];
    uint8_t sm[4096 + OQS_SIG_ml_dsa_65_length_signature];
    size_t smlen = 0;

    OQS_SIG_keypair(sig, pk, sk);

    const uint8_t msg[] = "ML-DSA signature demo";
    size_t msglen = strlen((const char *)msg);

    if (OQS_SIG_sign(sig, sm, &smlen, msg, msglen, sk) != OQS_SUCCESS) {
        printf("签名失败\n");
        return 1;
    }
    printf("签名长度 = %zu 字节\n", smlen);

    OQS_SIG_free(sig);
    return 0;
}

调用时有三点值得注意。第一，OQS_SIG_sign 内部已经封装了拒绝采样循环，调用方不需要自己重试；但若使用底层原语（如直接调用 crypto_sign_signature），则要确认实现是否在内部循环。第二，签名缓冲区必须按算法规定的最大长度分配，ML-DSA-65 的签名长度为 3309 字节，缓冲区不足会返回错误而非截断。第三，消息指针和长度要严格对应，空消息也是合法输入，但长度必须传 0 而不是传未初始化的值。

若使用 Python 的 pqcrypto 或 dilithium-py，接口更简洁：sk, pk = ml_dsa_65.keygen()，sig = ml_dsa_65.sign(sk, msg)。无论哪种语言，验证方拿到的都是同一套字节编码，因此编码格式必须严格对齐。

四、签名编码格式分析

ML-DSA 的签名 σ=(c̃, z, h) 在传输时按固定顺序拼接，不做ASN.1或DER包装。以ML-DSA-65为例：

字段含义长度（字节）编码要点
c̃挑战哈希48直接输出 SHAKE-256 截断结果
z响应向量5×576 = 2880每个系数用 20 位打包，范围 [−γ1+1, γ1]
h提示向量6 + 83 = 89先写 k 个非零计数，再写位置索引

总长度为 48 + 2880 + 89 = 3017 字节？这里需要核对：ML-DSA-65 的签名长度规范值为 3309 字节，差异来自 z 的编码位宽与 h 的填充。实际实现中，z 的每个系数按 20 位编码，5 个多项式共 5×256×20/8 = 3200 字节；h 的编码为 k 字节计数加 ω+k 个索引字节，ω=55，故为 6+61=67 字节；加上 c̃ 的 48 字节，合计 3315 字节，再按规范对齐后为 3309 字节。不同参数集的长度必须查表确认，不能凭公式硬算。

编码时最容易出错的是 z 的符号处理。z 的系数是有符号整数，编码前要加上 γ1 偏移，使其落入无符号区间，再按位打包；解码时反向减偏移。若偏移量用错（例如误用 γ2），验证方解出的 z 会整体偏移，导致范数检查失败。另一个坑是 h 的索引顺序：提示向量按多项式序号升序排列，每个多项式的非零位置也必须升序，验证方依赖这一顺序做还原，乱序会导致 w1 重建错误。

调试建议：先用官方KAT向量跑通“签名—编码—解码—验证”闭环，再接入业务消息。若签名能通过本地验证但对方验证失败，优先检查字节序（大端/小端）和 z 的偏移量，这两处占跨实现互操作问题的绝大多数。

把以上四部分串起来看，签名生成的实现质量取决于三个判断：拒绝循环是否完整、随机源是否符合模式要求、编码是否与规范逐字节一致。只要这三点守住，ML-DSA 的签名就能在不同库、不同语言之间稳定互通。

← 上一章 📖 返回目录 下一章 →