4. SM2 签名算法：生成、验证与性能瓶颈

SM2 签名算法，说白了就是给数据盖个「电子印章」。你发出去的消息，别人能确认是你发的，而且内容没被篡改。这个流程看起来简单，但里面的计算量可不小。我刚开始接触 SM2 时，觉得不就是个椭圆曲线签名嘛，跟 ECDSA 差不多。后来真上手优化才发现，坑多着呢。

这一章，咱们把签名生成、签名验证掰开揉碎了讲，再聊聊性能瓶颈到底在哪。

4.1 签名生成流程

签名生成，是私钥持有者做的事。流程分三步：预处理、核心计算、输出签名。我习惯把每一步的输入输出都理清楚，不然调优时容易乱。

核心公式：签名 (r, s) 满足 r = (e + x₁) mod n，s = ((1 + dA)⁻¹ · (k - r · dA)) mod n

其中 e 是消息摘要，dA 是私钥，k 是随机数，n 是基点阶。

4.1.1 预处理阶段

预处理主要做两件事：计算消息摘要 e，以及生成随机数 k。这里有个细节——SM2 的摘要计算不是直接对消息原文做哈希，而是先拼接 ZA（用户标识、椭圆曲线参数等）和消息 M，再算 SM3。

// 伪代码：预处理
ZA = SM3(ENTL || IDA || a || b || xG || yG || xA || yA)
e = SM3(ZA || M)
k = random(1, n-1)  // 必须真随机

嗯，这里要注意。随机数 k 的质量直接决定签名安全性。我在项目中遇到过因为随机数生成器熵不足，导致签名私钥被恢复的案例。那真是血的教训——后来我们强制要求使用硬件随机数，或者至少用 NIST SP 800-90A 标准的 DRBG。

4.1.2 核心计算阶段

核心计算分四步，每一步都有优化空间：

  1. 计算椭圆曲线点 (x₁, y₁) = [k]G —— 这是最耗时的操作，标量乘法。
  2. 计算 r = (e + x₁) mod n —— 如果 r = 0 或 r + k = n，要重新生成 k。
  3. 计算 s = ((1 + dA)⁻¹ · (k - r · dA)) mod n —— 模逆运算。
  4. 输出签名 (r, s) —— 注意 r 和 s 都是 256 位整数。

我的优化习惯：标量乘法 [k]G 可以用预计算表加速。如果签名频繁，提前算好 16 个或 32 个点的组合，能省 40% 以上的时间。不过代价是多占几百 KB 内存，看场景取舍。

4.2 签名验证流程

签名验证是公钥持有者做的事。流程比生成稍微复杂一点，因为涉及两次标量乘法。你想想看，验证方没有私钥，只能通过公钥和签名来确认。

4.2.1 验证前置检查

验证前，先检查签名 (r, s) 是否在有效范围内。这个步骤很多人会忽略，但它是安全防线的一部分。

// 验证前置检查
if (r < 1 || r > n-1) return false;
if (s < 1 || s > n-1) return false;

我曾经见过一个实现，没做这个检查，结果攻击者传了个 r=0 的签名，直接绕过了验证。嗯，从那以后我再也不敢省这一步了。

4.2.2 核心验证计算

验证的核心是计算两个点：t = (r + s) mod n，然后算椭圆曲线点 (x₁', y₁') = [s]G + [t]PA。最后检查 x₁' + e 是否等于 r。

  1. 计算 t = (r + s) mod n —— 如果 t = 0，验证失败。
  2. 计算椭圆曲线点 [s]G + [t]PA —— 这是最耗时的操作，双标量乘法。
  3. 计算 R = (e + x₁') mod n —— 比较 R 是否等于 r。

关键区别：签名生成只用一次标量乘法 [k]G，而签名验证需要两次标量乘法 [s]G 和 [t]PA。所以验证通常比生成慢 1.5 到 2 倍。

4.3 性能瓶颈分析

性能瓶颈，说白了就是「时间花在哪了」。我做过一次完整的 profiling，结果让我很惊讶——90% 以上的时间都花在椭圆曲线标量乘法上。剩下的 10% 是模运算和哈希。

4.3.1 标量乘法：最大的瓶颈

标量乘法 [k]G 的实现方式，直接决定签名速度。常见的实现方法有：

方法 点加次数 倍点次数 适用场景
二进制展开法 ≈ 128 256 内存受限
NAF (非相邻形式) ≈ 85 256 通用场景
窗口法 (w=4) ≈ 64 256 预计算可用
固定基点预计算 ≈ 32 256 签名频繁

我个人习惯在签名场景用固定基点预计算，因为 G 是固定的，可以提前算好 2⁴ 或 2⁵ 个点的组合。验证场景则用窗口法，因为 PA 每次不同，没法预计算。

4.3.2 模逆运算：隐藏的坑

签名生成里有个 (1 + dA)⁻¹ 的模逆运算。模逆比模乘慢一个数量级。我见过有人用扩展欧几里得算法，也有人用费马小定理（因为 n 是素数）。

避坑指南：我曾经在 ARM Cortex-M4 上实现 SM2，发现模逆占了 15% 的时间。后来改用 Montgomery 模逆 + 预计算 (1+dA)⁻¹ 的方法，把模逆次数从每次签名一次降为零——因为私钥不变，这个值可以提前算好存起来。

4.3.3 模乘与模约减

SM2 的素数 p 和 n 都是 256 位。模乘如果用通用 Montgomery 模乘，性能还行。但如果你用 x86 的 MULX/ADX 指令，或者 ARM 的 SM3 指令加速，那又是另一回事了。

我测试过，纯 C 实现的 Montgomery 模乘，一次大约 200 个周期。用 MULX + ADX 优化后，能压到 80 个周期以内。嗯，这个差距在大量签名时就很明显了。

4.3.4 哈希计算：被低估的开销

SM3 哈希虽然比标量乘法快得多，但在签名验证里要算两次（一次 ZA，一次 e）。如果消息很长，SM3 的开销也会上升。我记得有个项目，消息平均 10KB，SM3 占了总时间的 8%。虽然不多，但优化时也不能放过。

4.4 签名与验证的完整流程对比

我把两个流程画成了一张图，方便你对比差异。红色节点是性能热点，绿色节点是安全关键点。

SM2 签名生成与验证流程对比 签名生成（私钥持有者） ① 计算 ZA = SM3(ENTL||IDA||a||b||xG||yG||xA||yA) ② 计算 e = SM3(ZA || M) ③ 生成随机数 k，计算 [k]G ④ 计算 r = (e + x₁) mod n ⑤ 计算 s = ((1+dA)⁻¹ · (k - r·dA)) mod n ⑥ 输出签名 (r, s) 签名验证（公钥持有者） ① 检查 r, s ∈ [1, n-1] ② 计算 e = SM3(ZA || M) ③ 计算 t = (r + s) mod n ④ 计算 [s]G + [t]PA → (x₁', y₁') ⑤ 计算 R = (e + x₁') mod n ⑥ 验证 R == r 公钥 性能热点分布 标量乘法 [k]G / [s]G / [t]PA 占 85-90% 总时间 | 模逆运算占 5-10% | SM3 哈希占 3-8%

4.5 性能瓶颈总结

说了这么多，我帮你把核心瓶颈列出来：

  • 标量乘法：签名生成 1 次，签名验证 2 次。这是最大的优化目标。
  • 模逆运算：签名生成 1 次。可以通过预计算消除。
  • 模乘运算：标量乘法内部大量调用。用 Montgomery 模乘 + 指令集优化。
  • SM3 哈希：如果消息长，优化 SM3 的压缩函数也能省时间。
  • 随机数生成：虽然不占 CPU，但质量影响安全。别用 rand()。

我的建议：做性能优化前，先做 profiling。别凭感觉猜瓶颈。我见过有人花两周优化 SM3，结果标量乘法才是大头。用 perf 或类似工具跑一下，数据说话。

← 上一章 📖 返回目录 下一章 →