平方–求模算法侧信道攻击

平方–求模算法

平方–求模算法（通常叫做 “平方–乘算法”）是密码学里高效计算大数模幂的核心技巧

它的目的很简单，要算出：

1
a ^ b (mod n)

其中 a，b，n 都很大（比如 RSA 中的指数 b 有几千比特）

直接连乘 b 次再做模运算是不可行的，平方–求模算法能把计算量降到与 b 的比特长度成正比

原理

只用两条指数律：

  • 乘积分解：a ^ (x + y) = a ^ x + a ^ y

  • 平方倍增：a ^ 2x = (a ^ x) ^ 2

把指数 b 用二进制表示，就能把模幂拆成一系列 “平方” 和 “有条件乘” 的操作

步骤

算法步骤：从左向右，即从高位到低位

问题：计算 3 ^ 13 (mod 7)

把 13 写成二进制：1101（从左往右就是 1→1→0→1）

规则很简单，从结果 1 开始，逐位处理，每位先平方，遇到 1 再乘底数。每次算完都对 7 取模

当前位 当前结果 (开始) 平方后 遇到 1 再乘 3 最终这步结果
1 1 1×1=1 1×3=3 3
1 3 3×3=9 → 2 2×3=6 → 6 6
0 6 6×6=36 → 1 (不乘) 1
1 1 1×1=1 1×3=3 3

最后结果就是 3

核心就两句话：

  • 每步必做：结果自己乘自己（平方），模掉 n

  • 该位是 1 就多做：再乘上底数 a，模掉 n

侧信道攻击

这个算法的安全弱点在于它包含一个条件操作：

  • 密钥位为 0：只做平方

  • 密钥位为 1：做平方，然后做乘法

在物理设备（如智能卡、嵌入式芯片）上执行时，平方和乘法的计算量、执行时间、功耗波形通常不同。攻击者若能测量这些物理量，就能直接读出私钥位

原理

假设攻击者可以测量设备在执行模幂时的功耗曲线（或精确的执行时间）

  • 观察到只有一次高功耗脉冲/操作 → 只做了平方 → 该位是 0

  • 观察到一次高功耗，紧接着另一次不同的功耗形态 → 做了平方又做了乘法 → 该位是 1

功耗曲线直接描绘出了算法的执行轨迹，将私钥 d 的每一个比特都可视化了出来

蒙哥马利幂阶梯

防御方法核心思想是消除条件分支，让算法的运算模式与密钥无关。最著名的方法是蒙哥马利幂阶梯

1
2
3
4
5
6
7
8
9
R0 = 1, R1 = m
对 i 从 k-1 下到 0：
    如果 d_i == 0：
        R1 = R0 * R1 mod N
        R0 = R0^2 mod N
    否则 (d_i == 1)：
        R0 = R0 * R1 mod N
        R1 = R1^2 mod N
返回 R0

注意这里无论密钥位是 0 还是 1，每一轮都执行一次乘法和一次平方

这样功耗轨迹上每轮的操作特征完全一致，攻击者无法区分密钥位