1. 引言
Trail of Bits 的加密团队近期发布了其开源纯 Go 实现的 ML-DSA (FIPS-204) 和 SLH-DSA (FIPS-205) 两个 NIST 标准化的后量子签名算法。这些实现已经经过了多个密码学家的工程设计和审查。
- https://github.com/trailofbits/ml-dsa（FIPS-204）（Go）
- https://github.com/trailofbits/go-slh-dsa（FIPS-205）（Go）
本文将详细介绍在 ML-DSA (FIPS-204) 和 SLH-DSA (FIPS-205) 代码实现中所做的一些工作，确保其是常量时间的。特别是，这些技巧适用于 ML-DSA (FIPS-204) 算法，防止诸如 KyberSlash 等攻击，但它们也适用于任何需要分支或除法的加密算法。
2. 实现常量时间 FIPS-204 的道路
SLH-DSA (FIPS-205) 相对容易实现，并且不会引入侧信道攻击，因为它是基于从哈希函数构建的伪随机函数，但 ML-DSA (FIPS-204) 规范包含了几个整数除法操作，这就需要更小心的处理。
除法是早期 Kyber 实现中发生 KyberSlash 时间攻击的根本原因，后来该算法变成了 ML-KEM (FIPS-203)。在此希望在实现中完全避免这种风险。
每个 ML-DSA 参数集（ML-DSA-44、ML-DSA-65 和 ML-DSA-87）都包括几个影响算法行为的其他参数。其中一个是叫做γ 2 γ_2γ2的低阶四舍五入范围。
γ 2 γ_2γ2总是一个整数，但它的值取决于参数集。
- 对于 ML-DSA-44，γ 2 γ_2γ2等于 95232；
- 对于 ML-DSA-65 和 ML-DSA-87，γ 2 γ_2γ2等于 261888。
ML-DSA 指定了一个名为Decompose的算法，将一个域元素转换为两个组件（r 1 r_1r1,r 0 r_0r0），使得( r 1 ⋅ 2 γ 2 ) + r 0 (r_1 \cdot 2γ_2) + r_0(r1⋅2γ2)+r0等于原始域元素。这需要在一步中除以2 γ 2 2γ_22γ2，并在另一步中计算2 γ 2 2γ_22γ2的余数。
若要求 AI 来实现 Decompose 算法，将得到如下代码：
// 此代码样本由 Claude AI 生成。// 不安全 - 请勿使用。// 这里 `alpha` 等于 `2 * γ2`，`r` 是域元素：funcDecomposeUnsafe(r,alphaint32)(r1,r0int32){// 确保 r 在范围 [0, q-1] 内r=r%qifr<0{r+=q}// 将 r 中心化到 0（映射到范围 [-(q-1)/2, (q-1)/2]）ifr>(q-1)/2{r=r-q}// 计算 r1 = round(r/alpha)，其中 round 是四舍五入，// 其中相等时向零取整ifr>=0{r1=(r+alpha/2)/alpha}else{r1=(r-alpha/2+1)/alpha}// 计算 r0 = r - r1*alphar0=r-r1*alpha// 如果 r0 太大，调整 r1ifr0>alpha/2{r1++r0-=alpha}elseifr0<-alpha/2{r1--r0+=alpha}returnr1,r0}然而，这违反了密码学工程的最佳实践：
- 1）该代码明显使用了除法和取模运算符。
- 2）包含了多个基于域元素派生值的分支操作。
3. Zen与无分支密码学艺术
防止密码学算法中出现分支的直接方法是始终执行条件语句的两侧（真和假），然后基于条件使用常量时间的条件交换来获得正确的结果。这涉及到位掩码、二补码和异或（XOR）操作。
将该函数中的分支去除后，代码看起来像这样：
// 这是另一个 AI 生成的代码示例。// 不安全 - 请勿使用。funcDecomposeUnsafeBranchless(r,alphaint32)(r1,r0int32){// 确保 r 在范围 [0, q-1] 内r=r%q r+=q&(r>>31)// 如果 r < 0，则加上 q（使用算术右移）// 将 r 中心化到 0（映射到范围 [-(q-1)/2, (q-1)/2]）mask:=-((r-(q-1)/2-1)>>31)// 如果 r > (q-1)/2，则 mask = -1，否则为 0r-=q&mask// 计算 r1 = round(r/alpha)，其中四舍五入时向零取整// 对于 r >= 0：r1 = (r + alpha/2) / alpha// 对于 r < 0：r1 = (r - alpha/2 + 1) / alphasignMask:=r>>31// 如果 r < 0，则 signMask = -1，否则为 0offset:=(alpha/2)+(signMask&(-alpha/2+1))// r >= 0 时为 alpha/2，否则为 -alpha/2 + 1r1=(r+offset)/alpha// 计算 r0 = r - r1*alphar0=r-r1*alpha// 如果 r0 太大，调整 r1（无分支）// 如果 r0 > alpha/2：r1++，r0 -= alpha// 如果 r0 < -alpha/2：r1--，r0 += alpha// 检查 r0 > alpha/2adjustUp:=-((r0-alpha/2-1)>>31)// 如果 r0 > alpha/2，则为 -1，否则为 0r1+=adjustUp&1r0-=adjustUp&alpha// 检查 r0 < -alpha/2adjustDown:=-((-r0-alpha/2-1)>>31)// 如果 r0 < -alpha/2，则为 -1，否则为 0r1-=adjustDown&1r0+=adjustDown&alphareturnr1,r0}这解决了条件分支问题；然而，还没有完成。仍然存在麻烦的除法运算符。
4. 无除法：无除法算法（Undivided by time: Division-free algorithms）
前面提到的常量时间条件交换技巧也可以用来 在常量时间内实现整数除法。
funcDivConstTime32(nuint32,duint32)(uint32,uint32){quotient:=uint32(0)R:=uint32(0)// 处理的是32位整数，因此迭代32次b:=uint32(32)i:=bforrangeb{i--R<<=1// R(0) := N(i)R|=((n>>i)&1)// Sub32()中的交换操作看起来像这样：// 如果余数 > d，交换 == 0// 如果余数 == d，交换 == 0// 如果余数 < d，交换 == 1Rprime,swap:=bits.Sub32(R,d,0)// 对Sub32的逻辑取反来进行条件交换swap^=1/* 期望： 如果 R > D，则交换 = 1 如果 R == D，则交换 = 1 如果 R < D，则交换 = 0 */// Qprime := Q// Qprime(i) := 1Qprime:=quotient Qprime|=(1<<i)// 条件交换：mask:=uint32(-swap)R^=((Rprime^R)&mask)quotient^=((Qprime^quotient)&mask)}returnquotient,R}这个代码按预期工作，但它比较慢，因为它需要完整的循环迭代来计算商和余数的每一位。可以做得更好。
5. 一个精妙的优化技巧：Barrett约简
由于对于给定的参数集，值γ 2 γ_2γ2是固定的，并且除法和取模操作是针对2 γ 2 2γ_22γ2进行的，可以使用Barrett约简，并通过预计算的值来代替除法。
Barrett约简涉及乘以倒数（在本情况下是2 64 / 2 γ 2 2^{64}/2γ_2264/2γ2），然后执行最多两次修正减法来得到余数。商是该计算的副产物。
// 计算 (n/d, n%d)，给定 (n, d)funcDivBarrett(numerator,denominatoruint32)(uint32,uint32){// 由于 d 总是 2 * γ2，可以预计算 (2^64 / d) 并使用它varreciprocaluint64switchdenominator{case190464:// 2 * 95232reciprocal=96851604889688case523776:// 2 * 261888reciprocal=35184372088832default:// 回退到慢速除法returnDivConstTime32(numerator,denominator)}// Barrett约简hi,_:=bits.Mul64(uint64(numerator),reciprocal)quo:=uint32(hi)r:=numerator-quo*denominator// 使用 bits.Sub32 进行两步修正（常数时间）fori:=0;i<2;i++{newR,borrow:=bits.Sub32(r,denominator,0)correction:=borrow^1// 如果 r >= d，则修正 = 1；如果 r < d，则修正 = 0mask:=uint32(-correction)quo+=mask&1r^=mask&(newR^r)// 使用 XOR 的条件交换}returnquo,r}通过这个有用的函数，现在可以[无分支、无除法地实现Decompose](https://github.com/trailofbits/ml-dsa/blob/9fd8970f6bbad89baa5ddc0a45832bc8bcd5caf1/internal/field/field.go#L114-L160)。
6. 朝着后量子安全的未来迈进
Go中提供后量子签名算法是朝着未来迈出的一步，未来即使出现与密码学相关的量子计算机，互联网通信仍然能够保持安全。
参考资料
[1] Trail of Bits团队2025年11月博客 How we avoided side-channels in our new post-quantum Go cryptography libraries
)
