椭圆曲线密码学（ECC）数学基础与曲线形式
概述
椭圆曲线密码学（Elliptic Curve Cryptography, ECC）是现代公钥密码学中最具影响力的技术之一。与 RSA 基于大整数分解、DH 基于有限域离散对数不同，ECC 的安全性建立在椭圆曲线离散对数问题（ECDLP）之上——在已知曲线上的基点 $P$ 和点 $Q = kP$ 的情况下，求解标量 $k$ 在计算上不可行。
ECC 的核心优势在于：同等安全级别下，密钥尺寸远小于 RSA。128 位安全级别仅需 256 位密钥，而 RSA 需要 3072 位。这一优势使 ECC 成为资源受限环境（移动设备、物联网、国密应用）的首选方案。
ECC 并非单一算法，而是一个庞大的理论体系。从 Weierstrass 方程到 Montgomery ladder，从 twisted Edwards 曲线到双线性对，不同的曲线形式决定了不同的性能特征和安全属性。理解这些数学基础，是正确选择和实现 ECC 算法的前提。
代数基础：从群论到有限域
群、环、域
椭圆曲线的代数结构建立在有限域（Finite Field）之上的阿贝尔群（Abelian Group）。
定义 1（群）：集合 $G$ 配备二元运算 $\cdot$，满足：
- 封闭性：$\forall a,b \in G, a \cdot b \in G$
- 结合律：$(a \cdot b) \cdot c = a \cdot (b \cdot c)$
- 单位元：$\exists e \in G, a \cdot e = a$
- 逆元：$\forall a \in G, \exists a^{-1} \in G, a \cdot a^{-1} = e$
定义 2（有限域）：元素个数有限的域，记为 $\mathbb{F}_q$，其中 $q = p^m$。密码学中最常用的是：
- 素域 $\mathbb{F}_p$：$p$ 为素数，运算为模 $p$ 加法和乘法
- 二元扩域 $\mathbb{F}_{2^m}$：用于硬件实现场景
椭圆曲线的群结构
椭圆曲线上的点，加上一个特殊的"无穷远点" $\mathcal{O}$（作为群单位元），在点加法运算下构成一个阿贝尔群。
点加法的几何定义：
给定椭圆曲线上的两点 P = (x₁, y₁) 和 Q = (x₂, y₂)：
若 P = O，则 P + Q = Q（单位元性质）
若 Q = O，则 P + Q = P
若 x₁ = x₂ 且 y₁ = -y₂，则 P + Q = O（互逆点）
否则：
计算斜率 λ：
- 若 P ≠ Q：λ = (y₂ - y₁) / (x₂ - x₁) mod p （点加）
- 若 P = Q：λ = (3x₁² + a) / (2y₁) mod p （倍点）
结果 R = (x₃, y₃)：
x₃ = λ² - x₁ - x₂ mod p
y₃ = λ(x₁ - x₃) - y₁ mod p这个几何定义直接转化为有限域上的代数运算，构成了 ECC 的基石。
三种主流曲线形式
Weierstrass 形式
一般方程：
$$y^2 = x^3 + ax + b$$
其中 $a, b \in \mathbb{F}_p$，且满足判别式 $\Delta = -16(4a^3 + 27b^2) \neq 0$（确保曲线无奇点）。
密码学中通常使用短 Weierstrass 形式，即上述标准形式。NIST P-256、SM2 等主流曲线均采用此形式。
SM2 曲线参数（GM/T 0003-2012）：
素数 p = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFF
系数 a = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF 00000000 FFFFFFFF FFFFFFFC
系数 b = 28E9FA9E 9D9F5E34 4D5A9E4B CF6509A7 F39789F5 15AB8F92 DDBCBD41 4D940E93
阶 n = FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 7203DF6B 21C6052B 53BBF409 39D54123
基点 G = (32C4AE2C 1F198119 5F990446 6A39C994 8FE30BBF F2660BE1 715A4589 334C74C7,
BC3736A2 F4F6779C 59BDCEE3 6B692153 D0A9877C C62A4740 02DF32E5 2139F0A0)SM2 使用 256 位素域，提供约 128 位安全级别。其参数选择遵循特定模式（如 $p$ 为特殊形式的素数），旨在优化模约减运算效率。
NIST P-256 曲线参数：
p = 2^256 - 2^224 + 2^192 + 2^96 - 1
a = -3
b = 0x5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604BP- 256 的 $a = -3$ 是一个刻意选择，因为此时倍点公式可以简化——分母 $2y_1$ 的计算中可以利用 $a = -3$ 的性质减少一次乘法。
Montgomery 形式
方程：
$$By^2 = x^3 + Ax^2 + x$$
Montgomery 曲线由 Peter Montgomery 于 1987 年提出，其核心优势在于Montgomery ladder——一种恒定时间的标量乘法算法。
Montgomery ladder 原理：
输入：标量 k = (k_{n-1} ... k₁k₀)₂，基点 P
初始化：R₀ = O, R₁ = P
从最高位到最低位遍历每一位 kᵢ：
若 kᵢ = 0：
R₁ = R₀ + R₁ （点加）
R₀ = 2R₀ （倍点）
若 kᵢ = 1：
R₀ = R₀ + R₁ （点加）
R₁ = 2R₁ （倍点）
返回 R₀ = kP关键特性：每一步都执行一次点加和一次倍点，操作模式与标量 $k$ 的比特值无关。这使得 Montgomery ladder 天然抵抗时序攻击（Timing Attack）和简单功耗分析（SPA）。
Curve25519 是最著名的 Montgomery 曲线（RFC 7748），由 Daniel J. Bernstein 设计：
方程：y² = x³ + 486662x² + x
素数：p = 2²⁵⁵ - 19
A = 486662
基点 x 坐标：9Curve25519 的设计哲学：
- 刚性参数（nothing-up-my-sleeve）：系数 $A = 486662$ 是满足 Montgomery 形式约束的最小整数，消除了参数被植入后门的疑虑
- 快速模约减：$p = 2^{255} - 19$ 的特殊形式使模运算无需除法
- 单坐标计算：仅使用 $x$ 坐标，$y$ 坐标通过曲线方程推导，减少数据传输
Edwards 形式与 Twisted Edwards
完整 Edwards 曲线方程：
$$x^2 + y^2 = 1 + dx^2y^2$$
Twisted Edwards 曲线方程（更一般的形式）：
$$ax^2 + y^2 = 1 + dx^2y^2$$
Edwards 曲线由 Harold Edwards 于 2007 年引入密码学，其最大优势是加法公式统一——点加和倍点使用完全相同的公式，无需区分。
Edwards 曲线的统一加法公式：
给定 P = (x₁, y₁), Q = (x₂, y₂)
x₃ = (x₁y₂ + y₁x₂) / (1 + dx₁x₂y₁y₂)
y₃ = (y₁y₂ - ax₁x₂) / (1 - dx₁x₂y₁y₂)Ed25519 是基于 twisted Edwards 曲线的签名方案（RFC 8032）：
曲线方程：-x² + y² = 1 + (-121665/121666)x²y²
素数：p = 2²⁵⁵ - 19
a = -1
d = -121665/121666 mod pEd25519 的优势：
- 统一加法：加法和倍点使用同一公式，天然抵抗侧信道
- 完备性：加法公式对所有输入点有效，不需要处理特殊情况
- 快速验证：Ed25519 签名验证比 ECDSA 快约 2 倍
三种形式的对比
| 维度 | Weierstrass | Montgomery | Twisted Edwards |
|---|---|---|---|
| 方程 | $y^2 = x^3 + ax + b$ | $By^2 = x^3 + Ax^2 + x$ | $ax^2 + y^2 = 1 + dx^2y^2$ |
| 单位元 | 无穷远点 $\mathcal{O}$ | $(0, 1)$ | $(0, 1)$ |
| 点加/倍点 | 不同公式 | 不同公式 | 统一公式 |
| 恒定时间 | 需要额外措施 | Montgomery ladder | 天然恒定时间 |
| 坐标 | $(x, y)$ | 仅 $x$（蒙哥马利阶梯） | $(x, y)$ |
| 完备性 | 否（需处理特殊情况） | 否 | 是 |
| 典型曲线 | P-256, SM2, P-384 | Curve25519 | Ed25519, Ed448 |
| 安全级别 | 128-256 bit | 128 bit | 128-224 bit |
曲线形式间的转换
在一定条件下，三种形式可以互相转换：
Montgomery → Weierstrass：
$$A_{W} = \frac{3 - A_M^2}{3B_M^2}, \quad B_W = \frac{2A_M^3 - 9A_M}{27B_M^3}$$
Twisted Edwards → Montgomery（当 $a$ 是平方元时）：
$$A_M = \frac{2(a + d)}{a - d}, \quad B_M = \frac{4}{a - d}$$
Montgomery → Twisted Edwards：
$$a = \frac{A_M + 2}{B_M}, \quad d = \frac{A_M - 2}{B_M}$$
注意：Weierstrass 形式不能直接转换为 Montgomery 或 Edwards 形式，除非满足特定条件（即 $x^3 + ax + b$ 有三个有理根）。
标量乘法与算法优化
标量乘法 $Q = kP$ 是 ECC 中最核心、最耗时的运算。给定 256 位标量 $k$ 和曲线上的点 $P$，高效计算 $kP$ 是性能的关键。
Double-and-Add 算法
最朴素的标量乘法：
k = (1 0 1 1 0 1)₂
初始化 R = O
从最高位到最低位：
R = 2R （倍点）
若当前位为 1：
R = R + P （点加）
结果：kP = 1·P + 0·2P + 1·4P + 1·8P + 0·16P + 1·32P复杂度：约 $n$ 次倍点 + $n/2$ 次点加（$n$ 为比特长度）。
NAF（非相邻形式）表示
NAF 将标量表示为 $\{0, \pm 1\}$ 的形式，使得非零位最少：
$$k = \sum_{i=0}^{l-1} k_i \cdot 2^i, \quad k_i \in \{0, \pm 1\}$$
性质：NAF 表示中，非零位不超过总位数的 $1/2$，平均密度为 $1/3$。这意味着点加次数减半。
示例：$k = 7 = (111)_2 = (100\bar{1})_{NAF}$（$\bar{1}$ 表示 $-1$）
$$7P = 2^3P - P = 8P - P$$
只需 3 次倍点 + 1 次点减，而非 3 次倍点 + 2 次点加。
GLV 方法（Gallant-Lam-Vanstone）
对于具有复乘（Complex Multiplication, CM）的曲线，GLV 方法可以将标量乘法分解为两个较小标量的并行计算：
$$kP = k_1P + k_2(\lambda P)$$
其中 $\lambda$ 是曲线的自同态（endomorphism），$k_1, k_2$ 约为原标量长度的一半。
GLV 在 SM2 上的应用：
SM2 曲线的自同态为：
$$\phi(x, y) = (\beta x, y), \quad \beta^3 \equiv 1 \pmod{p}$$
利用 GLV，标量 $k$ 可分解为 $k_1, k_2$，满足 $|k_1|, |k_2| \leq \lceil n/2 \rceil$，从而将一次完整的标量乘法分解为两次半长标量乘法并行执行，性能提升约 30-40%。
标量乘法的侧信道防护
| 攻击类型 | 原理 | 防护措施 |
|---|---|---|
| 时序攻击 | 不同标量导致不同执行时间 | 恒定时间算法（Montgomery ladder） |
| SPA | 功耗曲线泄露操作序列（点加 vs 倍点） | 统一操作模式、dummy 操作 |
| DPA | 统计分析多次功耗曲线 | 标量盲化、点盲化 |
| 故障注入 | 电压/时钟毛刺导致计算错误 | 结果验证、冗余计算 |
双线性对（Bilinear Pairing）
双线性对是 ECC 中最具革命性的数学工具，它使得基于身份的加密（IBE）、短签名、零知识证明等高级密码原语成为可能。
定义
设 $\mathbb{G}_1, \mathbb{G}_2$ 是阶为 $q$ 的加法循环群，$\mathbb{G}_T$ 是阶为 $q$ 的乘法循环群。映射 $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ 若满足以下条件，则称为双线性对：
- 双线性：$e(aP, bQ) = e(P, Q)^{ab}$，$\forall P \in \mathbb{G}_1, Q \in \mathbb{G}_2, a, b \in \mathbb{Z}_q$
- 非退化性：$e(P, Q) \neq 1$（对非单位元）
- 可计算性：存在高效算法计算 $e(P, Q)$
Weil 对与 Tate 对
Weil 对：最早的构造，定义在椭圆曲线的 $n$- torsion 群上：
$$e_n: E[n] \times E[n] \rightarrow \mu_n$$
其中 $\mu_n$ 是 $n$ 次单位根群。
Tate 对：计算效率更高的变体，定义在乘法子群上：
$$e(P, Q) = f_P(Q)^{(q^k - 1)/n}$$
其中 $f_P$ 是 Miller 函数，$k$ 是嵌入度（embedding degree）。
优化变体：
- Ate 对：缩短 Miller 循环长度
- 最优 Ate 对：进一步优化的 Miller 循环，是目前最快的对运算实现
配对友好曲线
并非所有曲线都适合构造高效的双线性对。配对友好曲线需要满足：
- 嵌入度 $k$ 足够小（使 $\mathbb{F}_{q^k}$ 中的离散对数可计算）
- 曲线阶 $n$ 足够大（保证安全性）
| 曲线 | 安全级别 | 嵌入度 $k$ | $\mathbb{G}_1$ | $\mathbb{G}_2$ | 特征 |
|---|---|---|---|---|---|
| BN256 | ~100 bit | 12 | $\mathbb{F}_{p}$ | $\mathbb{F}_{p^{12}}$ | 已过时 |
| BLS12-381 | ~128 bit | 12 | $\mathbb{F}_{p}$ | $\mathbb{F}_{p^{12}}$ | Zcash/Ethereum |
| BLS24-315 | ~128 bit | 24 | $\mathbb{F}_{p}$ | $\mathbb{F}_{p^{24}}$ | 更高安全 |
| BW6-761 | ~128 bit | 6 | $\mathbb{F}_{p}$ | $\mathbb{F}_{p^{6}}$ | 配对效率优先 |
SM2 与双线性对
SM2 曲线（素数 $p \approx 2^{256}$，阶 $n \approx 2^{256}$）的嵌入度 $k \approx 2^{255}$，意味着 $\mathbb{F}_{p^k}$ 的规模极大。因此，SM2 不适合构造高效的双线性对。
这是 SM2 与 BN/BLS 系列曲线在设计上的根本区别——SM2 专注于加密和签名场景，不支持基于对的密码学原语。
配对的应用
双线性对的密码学应用：
1. 基于身份的加密（IBE）
用户邮箱作为公钥，无需证书
安全性：e(H(ID), Ppub) = e(QID, sP)
2. BLS 短签名
签名：σ = H(m)ˣ（仅一个群元素）
验证：e(σ, P) = e(H(m), Ppub)
3. 零知识证明
简洁非交互式证明（SNARK）的核心组件
Groth16 使用配对验证多项式等式
4. 密钥协商
三方一轮密钥协商：e(aP, bQ)^{c} = e(bP, cQ)^{a} = e(cP, aQ)^{b}曲线参数选择原则
安全性要求
- 大素数阶子群：曲线阶 $n$ 必须包含大素数因子（$n \geq 2^{256}$ 用于 128 位安全）
- 嵌入度：对于非配对场景，嵌入度应足够大（$k > (\log_2 n)/8$），以抵抗 MOV 攻击
- 迹：避免迹 $t = p + 1 - n$ 过小（抵抗异常曲线攻击）
- 协因子：$h = \#E(\mathbb{F}_p)/n$ 应小（通常 $h \leq 4$）
性能优化
- 素数形式：选择特殊形式的素数（如 $p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1$）以加速模约减
- 系数选择：$a = -3$ 可优化倍点公式
- 刚性参数：参数应有透明的生成方式（如 Curve25519 的 $A = 486662$ 是最小满足条件的整数）
安全曲线设计标准
现代 ECC 曲线设计检查清单：
□ 安全级别 ≥ 128 bit
□ 素数阶子群（或协因子 ≤ 4）
□ 嵌入度足够大（非配对曲线）
□ 抵抗 MOV 攻击和 Frey-Rück 攻击
□ 抵抗异常曲线攻击（anomalous curve, #E(Fp) = p）
□ 抵抗小子群攻击
□ 常数时间实现可行
□ 参数刚性（nothing-up-my-sleeve numbers）
□ 无已知弱点和后门（截至发布时）主流曲线的设计哲学对比
NIST 曲线（P-256, P-384, P-521）
- 来源：NSA 推荐，FIPS 186-4 标准化
- 素数：广义梅森素数，优化模约减
- 争议：P-256 的种子来源不透明（"random" 曲线的种子由 NSA 生成）
- 适用：政府、金融、传统 PKI
Curve25519/Ed25519
- 来源：Daniel J. Bernstein 设计，RFC 7748/8032
- 哲学：刚性参数 + 恒定时间实现 + 侧信道防护优先
- 优势：参数透明，实现安全，速度快
- 适用：TLS 1.3、Signal、SSH、现代应用
SM2
- 来源：中国国家密码管理局，GM/T 0003-2012
- 特点：256 位素域，国密标准强制要求
- 优势：合规性，与国密生态兼容
- 注意：不适合配对场景，GLV 自同态优化是其主要性能优化手段
- 适用：中国金融、政务、关基系统
综合对比表
| 曲线 | 安全级别 | 签名速度 | 验证速度 | 密钥大小 | 签名大小 | 侧信道防护 | 参数透明度 |
|---|---|---|---|---|---|---|---|
| P-256 (ECDSA) | 128 bit | 中等 | 慢 | 64 B | 64 B | 需额外措施 | 低 |
| Ed25519 | 128 bit | 快 | 很快 | 32 B | 64 B | 内置 | 高 |
| SM2 | 128 bit | 中等 | 中等 | 64 B | 64 B | 需额外措施 | 中 |
| BLS12-381 | 128 bit | — | — | 48 B | 96 B | 内置 | 高 |
ECC 与后量子密码：迁移压力
ECC 正面临量子计算的实质性威胁。Shor 算法可以在多项式时间内求解 ECDLP，使当前所有基于 ECC 的密码方案在量子计算机面前不再安全。
时间线：
- 2025 年：NIST 完成 PQC 标准制定（ML-KEM、ML-DSA、SLH-DSA）
- 2026 年：各国加速 PQC 迁移路线图制定（加拿大 2026 年 4 月、欧盟 2026 年 12 月截止）
- 2029 年：Google、Cloudflare 等科技巨头设定的 PQC 完全迁移截止线
- 2031-2035 年：加拿大等国设定的完全采用时间
- SM2、P-256、Curve25519 等主流曲线均会被量子计算机破解
- 迁移方向：基于格的密码（CRYSTALS-Kyber/Dilithium）、基于哈希的签名（SPHINCS+）
- 国密体系也在探索基于格的 SM2 替代方案
参考来源
- RFC 7748 - Elliptic Curves for Security (Curve25519)
- RFC 8032 - EdDSA: Ed25519 and Ed448
- GM/T 0003-2012 - SM2 椭圆曲线公钥密码算法
- FIPS 186-4 - Digital Signature Standard (NIST curves)
- RFC 5639 - ECC Brainpool Standard Curves
- SafeCurves: choosing safe curves for ECC — Daniel J. Bernstein, Tanja Lange
- IETF draft - Alternative Elliptic Curve Representations
相关实践
- 如需了解 SM2 国密算法在 TLS 中的完整部署流程，请参阅《SM2 国密算法实战：从密钥生成到 TLS 完整部署》
- 如需了解国密 HTTPS 部署中的常见问题，请参阅《国密 HTTPS 踩坑实录：从开发到上线的 12 个坑》
- 如需了解 SM2 算法的数学细节，请参阅《SM2 椭圆曲线公钥密码算法》