后量子密码库：Go语言中规避侧信道攻击的技术实践

原创

qife122

发布于 2026-01-03 12:15:36

960

我们如何在新的后量子Go密码学库中避免侧信道攻击

Trail of Bits密码学团队发布了我们对ML-DSA和SLH-DSA的开源纯Go实现，这是两种NIST标准化的后量子签名算法。这些实现已由我们的多位密码学家进行工程设计和审查，因此，如果您或您的组织希望将数字签名过渡到后量子支持，请尝试它们！

这篇文章将详细介绍我们为确保实现是常数时间所做的一些工作。这些技巧特别适用于ML-DSA算法，以防止像KyberSlash这样的攻击，但它们也适用于任何需要分支或除法的密码算法。

通往常数时间FIPS-204之路

SLH-DSA相对容易实现而不引入侧信道，因为它基于从哈希函数构建的伪随机函数。但ML-DSA规范包含多个整数除法，需要更仔细的考虑。

除法是名为KyberSlash的时序攻击的根本原因，该攻击影响了Kyber（后来成为FIPS-203）的早期实现。我们希望在我们的实现中完全避免这种风险。

每个ML-DSA参数集都包含几个影响算法行为的参数。其中之一称为𝛾2，即低阶舍入范围。

𝛾2始终是整数，但其值取决于参数集。对于ML-DSA-44，𝛾2等于95232。对于ML-DSA-65和ML-DSA-87，𝛾2等于261888。

ML-DSA指定了一种称为“分解”的算法，它将一个域元素转换为两个分量，使得这两个分量的组合等于原始域元素。这需要在一个步骤中除以2𝛾2，并在另一个步骤中计算对2𝛾2的余数。

无分支密码学之道

在任何密码算法中防止分支的直截了当的方法是始终执行条件的双方（真和假），然后基于条件使用常数时间的条件交换来获得正确结果。这涉及位掩码、二进制补码和异或操作。

从该函数中移除分支看起来像这样：

// 这是另一个AI生成的代码示例。
// 不安全 —— 请勿使用。
func DecomposeUnsafeBranchless(r, alpha int32) (r1, r0 int32) {
    // 确保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，否则为0
    r -= q & mask

    // 计算r1 = round(r/alpha)，平局时向零舍入
    signMask := r >> 31                           // 如果r < 0，signMask = -1，否则为0
    offset := (alpha/2) + (signMask & (-alpha/2 + 1)) // 如果r >= 0则为alpha/2，否则为-alpha/2 + 1
    r1 = (r + offset) / alpha

    // 计算r0 = r - r1*alpha
    r0 = r - r1*alpha

    // 如果r0太大，调整r1（无分支）
    adjustUp := -((r0 - alpha/2 - 1) >> 31) // 如果r0 > alpha/2则为-1，否则为0
    r1 += adjustUp & 1
    r0 -= adjustUp & alpha

    adjustDown := -((-r0 - alpha/2 - 1) >> 31) // 如果r0 < -alpha/2则为-1，否则为0
    r1 -= adjustDown & 1
    r0 += adjustDown & alpha

    return r1, r0
}

这解决了我们的条件分支问题；然而，我们还没有完成。仍然存在麻烦的除法运算符。

不分时间：无除法算法

常数时间条件交换的技巧也可以用来以常数时间实现整数除法。

func DivConstTime32(n uint32, d uint32) (uint32, uint32) {
    quotient := uint32(0)
    R := uint32(0)

    b := uint32(32)
    i := b
    for range b {
        i--
        R <<= 1

        R |= ((n >> i) & 1)

        Rprime, swap := bits.Sub32(R, d, 0)

        swap ^= 1

        Qprime := quotient
        Qprime |= (1 << i)

        mask := uint32(-swap)
        R ^= ((Rprime ^ R) & mask)
        quotient ^= ((Qprime ^ quotient) & mask)
    }
    return quotient, R
}

这按预期工作，但速度很慢，因为它需要完整的循环迭代来计算商和余数的每一位。我们可以做得更好。

一个巧妙的优化技巧：Barrett约减

由于对于给定的参数集，值𝛾2是固定的，并且除法和取模运算是针对2𝛾2执行的，我们可以使用Barrett约减和预计算值来代替除法。

Barrett约减涉及乘以一个倒数，然后执行最多两次校正减法以获得余数。商是这个计算的副产品。

// 给定(n, d)计算(n/d, n%d)
func DivBarrett(numerator, denominator uint32) (uint32, uint32) {
    var reciprocal uint64
    switch denominator {
    case 190464: // 2 * 95232
        reciprocal = 96851604889688
    case 523776: // 2 * 261888
        reciprocal = 35184372088832
    default:
        return DivConstTime32(numerator, denominator)
    }

    hi, _ := bits.Mul64(uint64(numerator), reciprocal)
    quo := uint32(hi)
    r := numerator - quo * denominator

    for i := 0; i < 2; i++ {
        newR, borrow := bits.Sub32(r, denominator, 0)
        correction := borrow ^ 1  // 如果r >= d则为1，如果r < d则为0
        mask := uint32(-correction)
        quo += mask & 1
        r ^= mask & (newR ^ r)
    }

    return quo, r
}

有了这个有用的函数，我们现在可以在没有分支或除法的情况下实现Decompose。

迈向后量子安全的未来

Go语言中后量子签名算法的可用性，是朝着即使未来开发出与密码学相关的量子计算机，互联网通信也能保持安全的未来迈出的一步。

B66Q6Ou1tAlwnlpPPdAu77+nNUwoBs1zkLmuVVwDZNmtEHD7CcWCLNSFI1wkVFRejhRsmVmhCO2uCc++7o/0FRpkMJmW41wZ/JUCPNCf4DRB3K9QUwyxWXbeH74lT0B9IPoMv/9n2cTW0wGrEb4yKGmy2mGFX4/8QYyO6dU8rVA=

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

密码学