第3章 椭圆曲线点运算：仿射坐标与Jacobian坐标、点加与倍点运算、标量乘法基础

椭圆曲线上的点运算，说白了就是SM2算法的「发动机」。你想想看，签名、验签、加密、解密，底层全在跑点加、倍点和标量乘法。如果这几块跑不快，上层再怎么优化都是白搭。

我个人习惯，在讲具体优化之前，先把坐标系统讲透。因为很多性能瓶颈，根源就在坐标选择上。

3.1 仿射坐标：最直观，但最慢

仿射坐标就是我们数学课上学的 (x, y) 表示法。SM2 的椭圆曲线方程是：

y² = x³ + ax + b   (mod p)

在仿射坐标下，点加和倍点运算需要计算模逆元。模逆元有多慢？我做过实测，一次模逆运算大约相当于 80-100 次模乘运算。这意味着什么？

• 点加：需要 1 次模逆 + 2 次模乘 + 1 次模平方
• 倍点：需要 1 次模逆 + 2 次模乘 + 2 次模平方

3.2 Jacobian 坐标：用空间换时间

Jacobian 坐标用 (X, Y, Z) 三个分量表示一个点，其中 Z ≠ 0。仿射坐标和 Jacobian 坐标的转换关系是：

x = X / Z²
y = Y / Z³

为什么要引入 Z 坐标？说白了，就是为了避免模逆运算。在 Jacobian 坐标下，点加和倍点运算只需要模乘和模平方，不需要模逆。只有在最终输出结果时，才需要做一次模逆把结果转回仿射坐标。

我建议你记住这个对比表：

注：I = 模逆，M = 模乘，S = 模平方。混合点加指一个 Jacobian 点加一个仿射点。

你看，虽然 Jacobian 坐标下模乘次数多了，但省掉了昂贵的模逆运算。整体性能反而提升明显。

3.3 点加与倍点运算的实现要点

先看 Jacobian 坐标下的点加公式。假设 P = (X₁, Y₁, Z₁)，Q = (X₂, Y₂, Z₂)，且 P ≠ ±Q：

λ₁ = X₁ × Z₂²
λ₂ = X₂ × Z₁²
λ₃ = λ₁ − λ₂
λ₄ = Y₁ × Z₂³
λ₅ = Y₂ × Z₁³
λ₆ = λ₄ − λ₅

X₃ = λ₆² − λ₃³ − 2 × λ₁ × λ₃²
Y₃ = λ₆ × (λ₁ × λ₃² − X₃) − λ₄ × λ₃³
Z₃ = λ₃ × Z₁ × Z₂

嗯，公式看着有点吓人。但实际编码时，我习惯用临时变量把中间结果存起来，避免重复计算。比如 Z₂² 和 Z₂³ 只需要算一次。

倍点公式相对简单一些。当 P = (X₁, Y₁, Z₁)，且 P ≠ −P：

λ₁ = 3 × X₁² + a × Z₁⁴
λ₂ = 4 × X₁ × Y₁²
λ₃ = 8 × Y₁⁴

X₃ = λ₁² − 2 × λ₂
Y₃ = λ₁ × (λ₂ − X₃) − λ₃
Z₃ = 2 × Y₁ × Z₁

3.4 标量乘法基础

标量乘法就是计算 k × P，其中 k 是一个大整数（256 位），P 是椭圆曲线上的点。这是 SM2 中最核心、最耗时的运算。

最基础的实现是二进制展开法（也叫 double-and-add）：

输入：标量 k = (k_{n-1} ... k₁ k₀)₂，点 P
输出：Q = k × P

Q = O（无穷远点）
for i from n-1 down to 0:
    Q = double(Q)
    if k_i == 1:
        Q = add(Q, P)
return Q

这个算法平均需要 256 次倍点和 128 次点加。但实际项目中，我从来不用这个「裸」版本。为什么？因为它存在两个问题：

1. 性能不够好：每次循环都要判断 k_i 是否为 1，分支预测失败会拖慢流水线。
2. 存在侧信道风险：执行时间与 k 的汉明重量相关，攻击者可以通过时序分析推断 k。

我曾经在调试一个安全模块时，发现标量乘法的执行时间波动达到 15%。后来一查，就是二进制展开法导致的时序泄漏。

3.5 知识体系总览

下面这张图把本章的核心脉络串起来了：

3.6 实践建议

基于我多年的调优经验，给你几条实在的建议：

• 优先使用 Jacobian 坐标：除非你明确知道模逆运算已经优化到极致（比如用蒙哥马利模逆），否则别在仿射坐标下做大量点运算。
• 混合点加是宝藏：在标量乘法中，预计算的点可以存为仿射坐标（Z=1），这样每次点加就变成混合点加，从 12M+4S 降到 8M+3S。
• 复用中间结果：点加和倍点公式中有大量重复计算，比如 Z²、Z³、Y² 等。用临时变量缓存，别重复算。
• 考虑侧信道防护：如果做安全产品，别用二进制展开法。Montgomery 阶梯或带伪操作的实现更安全。