ML-DSA（FIPS 204）的完整实现

《应用后量子密码学》本章的全部代码：共 2 段，其中 1 段可在此运行。编辑任意单元格，然后点击运行。

书中的代码片段在一章之内层层相依，但 Sage Cell 内核每次只运行一个单元格，运行后不保留任何状态，因此每个单元格都会用 apqc_book 重放此前的代码。这一调用是在书中原有代码之外唯一添加的内容。

代码 1：SageMath 实验

核心的抵消关系很容易在缩小版中验证。使用小参数，采样一个密钥，构造一个加了掩码的响应，并在发布任何签名之前就确认验证恒等式成立。

代码 2：完整的 SageMath 实现

上面的抵消检查只是一个片段。配套文件 sage/fips204_mldsa.sage 则是整个标准：FIPS 204 中全部四十九个编号算法，每个都实现为独立的函数并注明其算法编号，覆盖 ML-DSA-44、65 和 87。其中包括本章当作黑盒处理的部分——ExpandA、ExpandS、 ExpandMask、SampleInBall、Power2Round、 Decompose、MakeHint、UseHint——以及位打包、提示编码、预哈希变体 HashML-DSA 和 Montgomery 约简。

与 FIPS 203 一样，代数运算由 Sage 承载。不过这里标准细心地区分了环 R_q 与系数范围受限的整系数多项式环 R，代码也同样如此：模 q 约简的量（秘密 s₁,s₂、掩码 y、响应 z）位于 Sage 商环 R_q = 𝔽₈₃₈₀₄₁₇[X]/(X²⁵⁶+1) 中，而 t₁、 w₁、r₀ 以及提示 h 则保持为整数列表。 NTT 域 T_q 是直积 (ℤ_q)²⁵⁶，因此 MultiplyNTT（算法 45）实际上就是逐坐标乘积。

于是，书中的算法的拒绝循环读起来几乎与标准中的写法完全一致：

无法单独运行：这是从配套文件中引用的 Sign_internal 方法体——它引用了 self 并带有 return，因此只能作为方法运行。

kappa = 0
while True:
    y  = self.ExpandMask(rhopp, kappa)
    yh = [NTT(Rq(p)) for p in y]
    w  = [NTTInverse(a) for a in MatrixVectorNTT(Ah, yh)]
    w1 = HighBitsVec(w, self.gamma2)

    ctilde = H(mu + self.w1Encode(w1), self.lam // 4)
    c      = self.SampleInBall(ctilde)
    ch     = NTT(Rq(c))

    cs1  = [NTTInverse(MultiplyNTT(ch, a)) for a in s1h]
    cs2  = [NTTInverse(MultiplyNTT(ch, a)) for a in s2h]
    z    = [Rq(y[i]) + cs1[i] for i in range(self.ell)]
    wcs2 = [w[i] - cs2[i] for i in range(self.k)]
    r0   = LowBitsVec(wcs2, self.gamma2)

    kappa += self.ell
    if inf_norm_vec(z) >= self.gamma1 - self.beta:      # unsafe: retry
        continue
    if inf_norm_ints(r0) >= self.gamma2 - self.beta:
        continue

    ct0 = [NTTInverse(MultiplyNTT(ch, a)) for a in t0h]
    h   = MakeHintVec([-p for p in ct0],
                      [wcs2[i] + ct0[i] for i in range(self.k)],
                      self.gamma2)
    if inf_norm_vec(ct0) >= self.gamma2:
        continue
    if sum(sum(p) for p in h) > self.omega:
        continue

    return self.sigEncode(ctilde, [centered(zi) for zi in z], h)