gmp_powm_sec 简介

(Updated: )
其他技术文章

我在 PHP 8.6 这个版本里总共新增了 4 个函数（截至本文发出）

  • locale_get_display_keyword
  • locale_get_display_keyword_value
  • gmp_powm_sec
  • gmp_prevprime

其中，我认为最值得被大家知道的，是 gmp_powm_sec。这篇文字将介绍 gmp_powm_sec 的用途，以及我为什么在新版本里推荐你使用它。

这个版本之前，全世界的 PHPer 计算高精度的幂运算都是依靠 gmp_powm。然而，这个 API 具有严重的密码学安全问题。

因此，对于需要考虑安全性的幂运算，请考虑升级到 PHP 8.6 并使用我的新函数 gmp_powm_sec。

函数介绍

gmp_powm_sec 的函数签名：

1
function gmp_powm_sec(GMP|int|string $num, GMP|int|string $exponent, GMP|int|string $modulus): GMP {}

其用处是可以密码学安全地求 ($num ** $exponent) MOD $modulus。当指数 $exponent 是私密敏感数据时，你就应该使用 gmp_powm_sec

gmp_powm 为什么不安全

简单的例子：RSA 加密算法里的解密过程，我们需要对私钥 d 运算。c = (m ** d) MOD n

1
2
3
4
5
6
7
<?php
$n = gmp_init('0x00d0a3f8...');
$d = gmp_init('0x59a3e2f...');
$ciphertext = gmp_init('0x8f2a1b...');
# $plaintext = gmp_powm($ciphertext, $d, $n); 非常危险
$plaintext = gmp_powm_sec($ciphertext, $d, $n); # 安全
?>

PHP 以前的 pow 函数 gmp_powm 是 GNU MP 的 internal API mpz_powm 的直接封装。而 gmp_powm_sec 则是 mpz_powm_sec

二进制指数法

我想问大家一个问题：b 的 e 次方模 N，其中 e 是一个大整数（RSA 情况下通常是 65537）。我们就假设 b 是 2 吧（虽然肯定比这个大）那也是 2 的 65537 次方。那要算 65537 次乘法。那这样的时间复杂度要算到到人类灭绝？

所以数学家发明了”平方-乘”算法（Square-and-Multiply），也叫二进制指数法。即：从最高位开始，每读入一个比特位，先把当前结果平方，如果这个比特位是 1，再额外乘一个 b。

现在，假设我们要计算 b 的 13 次方。13 的二进制是 1101：

第 1 位是 1，平方后还是 1；乘以 b 变成 b；结果就是 b
第 2 位是 1，用上面的结果平方后是 b ** 2 ；乘以 b 变成 b ** 3；结果就是 b ** 3
第 3 位是 0，用上面的结果平方后是 b ** 6 ；不乘以 b；结果就是 b ** 6
第 4 位是 1，用上面的结果平方后是 b ** 12 ；乘以 b 变成 b ** 13；结果就是 b ** 13

是不是特别神奇好玩？所以，我们利用二进制指数法就可以很快算出幂运算。这个算法被广泛用于各种你能想到的加密算法里。

问题来了，假设现在是一个解密场景。攻击者可以输入无限次密文给服务端解密。假如服务端解密的时候是这样的：

1
2
3
4
5
<?php
$n = gmp_init('0x00d0a3f8...');
$d = gmp_init('0x59a3e2f...');
$ciphertext = gmp_init('0x8f2a1b...'); # 攻击者可以任意控制的密文
$plaintext = gmp_powm($ciphertext, $d, $n); # 解密出明文

这样，是安全的吗？显然，不是。为什么？

注意到，对比特位为 1 的运算，我们是平方再乘，对比特位位 0 的运算，我们只平方。也就是说：

位是 1：做 2 次大数运算（平方 + 乘法）
位是 0：只做 1 次大数运算（平方）

还想不到？

假如我说，攻击者可以测量单次解密的时间呢？

计时攻击

RSA 解密是计算：c 的 d 次方取模 n。其中 c 是密文，d 是私钥。普通版 gmp_powm 在计算时，逐位扫描私钥 d 的二进制：

如果 d 的这一位是 1 → 做 “平方 + 乘法”（耗时 2 个单位）
如果 d 的这一位是 0 → 做 “平方”（耗时 1 个单位）

攻击者只需测量每一次解密操作的时间，就能画出这样的波形：

1
2
时间:  长    长    短    长    长    短    短    长 ...
位:    1     1     0     1     1     0     0     1 ...

私钥 d 的二进制就这样被完整读出来了！

偶数模数攻击

gmp_powm 是通用函数，设计目标是支持任意整数模数（包括偶数）。源码 powm.c 中花了大量代码处理模数中的因子 2：

1
2
3
4
5
6
7
while (UNLIKELY (mp[0] == 0)) { mp++; ncnt++; }  // 移除低零位
cnt = 0;
if (mp[0] % 2 == 0) {
    count_trailing_zeros (cnt, mp[0]);   // 计算 2 的幂次
    mpn_rshift (newmp, mp, nodd, cnt);   // 右移，相当于除以 2^cnt
    // ... 调用 mpn_powlo 和 mpn_binvert 处理偶数部分
}

这样的处理是耗时的。虽然 RSA 的模数 n 是大奇数（两个大素数相乘一定是奇数），正常情况下不会触发偶数模数分支。但是，假如攻击者可以利用 gmp 的特性构造中间值欺骗 gmp_powm 呢？

gmp_powm 不是只在顶层用 m 做一次模运算，它在内部会把问题拆解成多个子问题，每个子问题可能有自己的模数。

具体来说，当 gmp_powm 在处理某些特殊形式的底数 c 和指数 e 时，内部会调用其他子函数（如 mpn_powlo），这些子函数可能会：

  • 从 b 或中间结果中提取低位的 2 的幂因子，构造出一个临时模数。
  • 这个临时模数是偶数（因为包含了因子 2）。
  • 然后 gmp_powm 递归或跳转去处理这个临时偶数模数。

Bingo! 举个例子：

假设我们正在计算 (c ** d) MOD n （d 是私钥，c是攻击者可以控制的待解密的密文）

在普通版 mpz_powm 中，如果底数 c 是偶数，且指数 d 是奇数，GMP 会提取底数 c 中所有的因子 2：

1
2
3
4
5
if (bp[0] % 2 == 0) {
    // 计算 b 中因子 2 的个数 bcnt
    bcnt = (0x1213 >> ((bp[0] & 7) << 1)) & 0x3;
    // 如果 bcnt * d >= t，则整个结果在模 n 下为 0
}

在这段逻辑中，GMP 需要处理”2 的幂次”这个因子，而这个处理过程会构造一个临时模数 2 ** k 作为子问题的模数。

冷知识：2 ** k 一定是偶数（我去，不早说）

对于任意选择的 c，bcnt 的值是确定的。当 bcnt * d >= t 时，整个解密的过程时间会大幅度降低。也就是说对私钥 d 的每一位，我们都可以利用这点去做布尔测信道泄露。利用好这个特性，我们可以在 O(logd) 的时间复杂度下推出完整的私钥 d。

负指数攻击

当指数为负数时，普通版会调用 mpz_invert 求逆。这又是一个耗时工作。与上述同理可以导致泄露。

gmp_powm_sec 为什么安全

参数校验

由文档，sec版本有：

  • 指数必然 > 0
  • 模必然是奇数

否则报错。从这一点上限制了很多密码学攻击的出现（如负指数攻击）。

废除偶指数逻辑

1
2
if (UNLIKELY ((n == 0) || (mp[0] % 2 == 0)))
    DIVIDE_BY_ZERO;  // 直接报错！

安全版没有任何的偶数处理逻辑。

常数时间

其实，这些攻击主要的原因是时间。作为密码学攻击的常客，时间始终站在攻击者一边作为一个常见的攻击向量。sec 版本里我们对 0 和 1 的操作用同样的时间即可。

指数位是 1 → 平方 + 乘法（真实乘法）
指数位是 0 → 平方 + 乘法（条件赋值替代实际乘法）

这样我们通过故意提升指数位是 0 的时间，使 1 和 0 在时间上得到统一。攻击者就无法通过时间来泄露密钥了。

总结

所有对密码学安全有需求的 pow 操作必须考虑升级到 PHP 8.6 并切换到 sec 版本。