第二章 椭圆曲线密码学基础：有限域、椭圆曲线方程、点加法、点倍运算

做SM2性能优化，绕不开椭圆曲线。说白了这个东西就是SM2的数学地基。你如果不理解有限域、点加、点倍，后面看倍点算法、窗口加速、坐标系的优化都会一头雾水。我刚开始接触国密时也栽过跟头，满眼都是公式，后来一点点捋清楚了。

2.1 有限域：密码学里的“沙盒”

有限域，说白了就是元素个数有限的集合，里面可以做加减乘除（除法就是乘逆元）。密码学里最常用的两种：

• 素数域 GF(p) —— p 是大素数，元素是 0 到 p-1 的整数，运算结果 mod p。
  我记得 SM2 国家推荐标准里用的就是素数域，素数 p 是 256 位的。
• 特征 2 域 GF(2^m) —— 二进制域，硬件友好，但 SM2 没用它。

为什么要有有限域？因为实数域上的椭圆曲线是光滑连续的，密码学没法用。只有把坐标限制在一个有限集合里，才能形成离散的、难解的问题。
我在一次性能调优项目中，发现域求逆占了总运算时间的 40%。嗯，这里要记牢：域求逆是优化重灾区。

2.2 椭圆曲线方程：SM2 的数学外壳

SM2 使用的椭圆曲线是 Weierstrass 标准型，在 GF(p) 上：

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

其中判别式 Δ = 4a³ + 27b² ≠ 0 (mod p)，确保曲线没有奇异点。

参数	SM2 推荐值（16进制）	说明
p	0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF	素数域模数
a	0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC	曲线参数 a = p - 3
b	0x28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93	曲线参数 b
G (基点)	Gx, Gy (具体略)	生成元，阶为素数 n
n	0xFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123	基点的阶（素数）

2.3 点加法：不是简单的加，是弦切

椭圆曲线上的“加法”不是坐标相加，而是几何规则——过两个点的直线与曲线交于第三点，然后做关于 x 轴的对称。

设 P = (x₁, y₁)，Q = (x₂, y₂)，P ≠ -Q，则 P + Q = (x₃, y₃) 计算公式如下：

λ = (y₂ - y₁) * (x₂ - x₁)⁻¹  mod p   （如果 P ≠ Q）
x₃ = λ² - x₁ - x₂  mod p
y₃ = λ * (x₁ - x₃) - y₁  mod p

这里的关键是模逆运算。我过去在项目里用扩展欧几里得算法做逆，后来发现费马小定理 a^(p-2) mod p 在大素数域上更易向量化。不过那是后话了。

2.4 点倍运算：自己加自己

点加的特例：P = Q 时，几何意义是过 P 点的切线。公式变为：

λ = (3x₁² + a) * (2y₁)⁻¹  mod p
x₃ = λ² - 2x₁  mod p
y₃ = λ * (x₁ - x₃) - y₁  mod p

点倍是标量乘的核心。你想想看：要计算 kP，最朴素的做法是重复点倍+点加，这个流程就叫“双倍加算法”。我记得 SM2 签名和加密里都会出现形如 k·G 或 d·Q 的运算，性能瓶颈就在这里。

2.5 知识体系梳理

下面这张图把本章的核心概念串起来。

2.6 本章要点速查

概念	关键点	对性能的影响
有限域	GF(p)，256位素数；GF(2^m)不用于SM2	模运算是所有计算的基础，域求逆最耗时
椭圆曲线方程	Weierstrass标准型，Δ ≠ 0	参数 a = p-3 可减少一次乘法
点加法	弦略：λ = (Δy)·(Δx)⁻¹	每次需要一次模逆，推荐投影坐标系推迟除法
点倍运算	切略：λ = (3x²+a)·(2y)⁻¹	同样需要模逆，且乘方运算较多
标量乘	点加 + 点倍组合（双倍加算法）	SM2性能瓶颈，优化空间最大