在公钥密码学的演进历程中，椭圆曲线密码学(Elliptic Curve Cryptography, ECC)的出现堪称一次范式跃迁。1985 年，Neal Koblitz 与 Victor Miller 各自独立提出将椭圆曲线上的离散对数问题(Elliptic Curve Discrete Logarithm Problem, ECDLP)作为密码系统的安全基础，由此开启了以更短密钥获取更高安全强度的新时代。与 RSA 依赖大整数分解、经典 Diffie-Hellman 依赖有限域离散对数不同，ECDLP 至今没有亚指数级的经典算法，这意味着 256 位的椭圆曲线密钥便可提供与 3072 位 RSA 密钥相当的安全等级。如此显著的效率优势使得椭圆曲线成为 TLS 1.3、SSH、Signal 协议乃至区块链签名中不可或缺的数学基石。
本文将从定义椭圆曲线的 Weierstrass 方程入手，逐步展开点加法的几何直觉与代数公式、群结构理论、标量乘法的高效算法，再扩展到 Montgomery 曲线与 Edwards 曲线两大替代形式，最后以工程实践中的曲线选择标准收束，力求为读者构建一幅从抽象数学到工程落地的完整图景。
一、Weierstrass 方程与曲线形态
椭圆曲线最一般的定义基于 Weierstrass 方程(Weierstrass equation)。在特征不等于 2 和 3 的域上，经过变量替换可将其化简为短 Weierstrass 形式(short Weierstrass form)：
\[ y^2 = x^3 + ax + b \]
其中 \(a, b\) 是定义域 \(\mathbb{F}_p\)（素数域）或 \(\mathbb{F}_{2^m}\)（二元扩展域）中的元素。这个等式定义了一条平面三次曲线。然而，并非所有满足该形式的曲线都是椭圆曲线——我们还需要施加一个非奇异条件(non-singular condition)：判别式(discriminant)
\[ \Delta = -16(4a^3 + 27b^2) \neq 0 \]
当 \(\Delta = 0\) 时，曲线在某点出现尖点(cusp)或结点(node)，几何上不再光滑，代数上不再构成群，因此被排除在椭圆曲线的定义之外。
直观地看，当 \(a\) 和 \(b\) 取不同的值时，曲线呈现出截然不同的形态。例如，\(y^2 = x^3 - x\)（\(a = -1, b = 0\)）的图像关于 \(x\) 轴对称且包含两个分离的连通分支；而 \(y^2 = x^3 + 1\)（\(a = 0, b = 1\)）则只有一个连通分支。更一般地，当方程右侧的三次多项式拥有三个不同的实根时，曲线呈现出”卵形加无限延伸”的双分支形态；当只有一个实根时，曲线只有一个连通分支。在实数域上的这些直观形态有助于建立几何理解，但实际密码学运算发生在有限域 \(\mathbb{F}_p\) 上——此时”曲线”变成了离散的点集，不再有连续的几何图形，所有性质都由代数关系决定。
值得补充的是，一般 Weierstrass 方程(general Weierstrass equation)的完整形式为 \(y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6\)，包含五个系数。在特征大于 3 的域中，通过适当的线性变量替换可以消去 \(a_1\)、\(a_2\)、\(a_3\) 三项，得到短 Weierstrass 形式。在特征 2 的域上（如 \(\mathbb{F}_{2^m}\)），这种化简无法完成，需要保留更多项，因此二元域上的椭圆曲线运算有其独立的公式体系。不过，随着素数域曲线在标准中的主导地位日益巩固，二元域曲线在实践中的使用已逐渐减少。
在有限域 \(\mathbb{F}_p\) 上，椭圆曲线 \(E(\mathbb{F}_p)\) 的点集由满足方程 \(y^2 \equiv x^3 + ax + b \pmod{p}\) 的所有有序对 \((x, y)\) 构成，并额外包含一个特殊的无穷远点(point at infinity) \(\mathcal{O}\)。这个无穷远点在射影几何(projective geometry)中自然出现，代数上它充当群运算的单位元(identity element)——对于任意点 \(P\)，都有 \(P + \mathcal{O} = P\)。
二、点加法的几何直觉
椭圆曲线之所以能承载密码学，根本原因在于其上的点集可以配备一个加法群结构。理解这一群运算的最佳起点是几何直觉。
在实数域上，取曲线上两个不同的点 \(P\) 和 \(Q\)，过这两点作一条直线(chord)。由于三次曲线与直线最多有三个交点，这条直线必然与曲线再交于第三个点 \(R'\)。将 \(R'\) 关于 \(x\) 轴取对称点（即将 \(y\) 坐标取反），得到的点就定义为 \(P + Q\)。这一过程被称为弦切法(chord-and-tangent method)。
当 \(P = Q\) 时，即需要计算 \(P + P = 2P\)（点倍增, point doubling），直线退化为曲线在 \(P\) 点的切线(tangent)。切线与曲线的另一交点经对称后即为 \(2P\)。
几个关键的特殊情形需要注意。首先，如果 \(P\) 和 \(Q\) 具有相同的 \(x\) 坐标但 \(y\) 坐标互为相反数——即 \(Q = -P\)——则过两点的直线是一条垂直线。垂直线与三次曲线的”第三个交点”正是无穷远点 \(\mathcal{O}\)，因此 \(P + (-P) = \mathcal{O}\)，这与逆元的定义完全一致。其次，如果 \(P\) 恰好在 \(x\) 轴上（\(y_P = 0\)），则 \(P\) 的切线是垂直线，\(2P = \mathcal{O}\)，即 \(P\) 是一个二阶元素(order-2 element)。
弦切法的优美之处在于：它只用到了直线与三次曲线的交点——这些运算可以完全用有理运算（加减乘除）表达，不需要开方或超越函数。这意味着一旦曲线定义在有限域上，所有点加法运算都可以精确地在该域内完成，不会产生舍入误差或域外溢出。
从代数几何的角度看，这一加法运算之所以能构成群，根源在于椭圆曲线是亏格为 1(genus 1)的代数曲线且附带一个有理基点。亏格为 0 的曲线（如圆锥曲线）不具备非平凡的群结构，而亏格大于等于 2 的曲线虽然有更丰富的算术性质，但其雅各比簇(Jacobian variety)的群运算远比椭圆曲线复杂。椭圆曲线恰好处于一个”甜蜜点”——群结构既足够丰富以支撑密码学，又足够简洁以实现高效运算。
三、点加法的代数公式
将上述几何操作翻译为代数公式，是实现椭圆曲线运算的基础。设 \(P = (x_1, y_1)\)，\(Q = (x_2, y_2)\)，均为曲线 \(y^2 = x^3 + ax + b\) 上的点。
点加法（\(P \neq Q\), \(x_1 \neq x_2\)）：
计算斜率 \(\lambda = \dfrac{y_2 - y_1}{x_2 - x_1}\)，然后：
\[ x_3 = \lambda^2 - x_1 - x_2, \quad y_3 = \lambda(x_1 - x_3) - y_1 \]
结果 \(P + Q = (x_3, y_3)\)。
点倍增（\(P = Q\), \(y_1 \neq 0\)）：
切线斜率 \(\lambda = \dfrac{3x_1^2 + a}{2y_1}\)，然后同样使用上述 \(x_3, y_3\) 公式。
这些公式看似简单，但直接在仿射坐标(affine coordinates)中实现存在一个严重的性能瓶颈：每次加法或倍增都需要一次模逆运算(modular inversion)——即计算分母的模逆。模逆的代价远高于模乘（通常高 20 到 100 倍），在大量连续运算中会成为显著的性能瓶颈。
解决方案是采用射影坐标(projective coordinates)。最常用的是雅各比坐标(Jacobian coordinates)：用三元组 \((X : Y : Z)\) 表示仿射点 \((X/Z^2, Y/Z^3)\)，无穷远点对应 \((1 : 1 : 0)\)。在此坐标系中，点倍增只需模乘和模平方，无需模逆，完整的倍增公式约需 1 次平方、3 次乘法和若干加减法。混合加法(mixed addition)——即一个雅各比点与一个仿射点相加——也有优化公式，只需约 8 次模乘。在标量乘法结束后，才需要一次模逆将结果转换回仿射坐标。
以下是在小素数域上实现点加法和标量乘法的 Python 代码：
def point_add(P, Q, a, p):
"""椭圆曲线点加法（仿射坐标），曲线 y^2 = x^3 + ax + b over F_p"""
if P is None:
return Q
if Q is None:
return P
x1, y1 = P
x2, y2 = Q
if x1 == x2 and (y1 + y2) % p == 0:
return None # P + (-P) = O
if P == Q:
# 点倍增
lam = (3 * x1 * x1 + a) * pow(2 * y1, -1, p) % p
else:
# 点加法
lam = (y2 - y1) * pow(x2 - x1, -1, p) % p
x3 = (lam * lam - x1 - x2) % p
y3 = (lam * (x1 - x3) - y1) % p
return (x3, y3)
def scalar_mult(k, P, a, p):
"""标量乘法：double-and-add 算法，计算 k * P"""
result = None # 无穷远点
addend = P
while k > 0:
if k & 1:
result = point_add(result, addend, a, p)
addend = point_add(addend, addend, a, p)
k >>= 1
return result
# 示例：曲线 y^2 = x^3 + 2x + 3 over F_97
a, b, p = 2, 3, 97
# 基点 G = (3, 6)，可验证 6^2 mod 97 = 36, 3^3+2*3+3 = 36
G = (3, 6)
assert (G[1] ** 2) % p == (G[0] ** 3 + a * G[0] + b) % p
# 计算 2G, 3G, ...
for k in range(1, 6):
kG = scalar_mult(k, G, a, p)
print(f"{k}G = {kG}")运行这段代码，可以观察到标量乘法的结果在曲线上的点之间”跳跃”，没有明显的规律可循——这正是 ECDLP 难度的直觉来源。给定 \(P\) 和 \([k]P\)，在不知道 \(k\) 的情况下恢复 \(k\)，目前已知的最佳经典算法是 Pollard rho 方法，其时间复杂度为 \(O(\sqrt{n})\)，与群阶 \(n\) 的平方根成正比。对于 256 位的群阶，这意味着攻击者需要大约 \(2^{128}\) 次群运算——在经典计算机上完全不可行。
四、椭圆曲线群的结构
椭圆曲线 \(E(\mathbb{F}_p)\) 上的全部有理点（包括无穷远点）在上述加法运算下构成一个阿贝尔群(Abelian group)。理解这个群的结构对于密码学参数选择至关重要。
Hasse 定理(Hasse’s theorem) 给出了群阶(group order) \(\#E(\mathbb{F}_p)\) 的范围：
\[ p + 1 - 2\sqrt{p} \leq \#E(\mathbb{F}_p) \leq p + 1 + 2\sqrt{p} \]
即 \(\#E(\mathbb{F}_p) = p + 1 - t\)，其中 \(|t| \leq 2\sqrt{p}\)，\(t\) 称为 Frobenius 迹(trace of Frobenius)。这意味着曲线上的点数大致等于 \(p\)，偏差不超过 \(2\sqrt{p}\)。对于 256 位的素数 \(p\)，群阶约为 \(2^{256}\)，偏差量级为 \(2^{128}\)，在密码学意义上群阶与 \(p\) 几乎等大。
根据有限阿贝尔群的基本定理，\(E(\mathbb{F}_p)\) 同构于 \(\mathbb{Z}/n_1\mathbb{Z} \times \mathbb{Z}/n_2\mathbb{Z}\)，其中 \(n_2 | n_1\)，\(n_1 n_2 = \#E(\mathbb{F}_p)\)。在密码学应用中，我们希望群结构尽可能接近循环群(cyclic group)——即 \(n_2 = 1\)，此时群完全由一个生成元(generator) \(G\) 生成。
群阶 \(\#E(\mathbb{F}_p)\) 通常可以分解为 \(\#E(\mathbb{F}_p) = h \cdot n\)，其中 \(n\) 是一个大素数（即基点 \(G\) 的阶），\(h\) 称为余因子(cofactor)。理想情况下 \(h = 1\)，此时群阶本身就是素数，群中的每一个非零点都是生成元。NIST P-256 和 Brainpool 曲线追求 \(h = 1\)，而 Curve25519 的 \(h = 8\)，Ed448 的 \(h = 4\)。余因子不为 1 时，存在小子群攻击(small subgroup attack)的风险：攻击者可以发送位于小子群中的点，使得共享密钥只有 \(h\) 种可能。防御方法是在协议中对接收到的点进行余因子清除(cofactor clearing)——即计算 \([h]P\)，将结果限制在素数阶子群中。
挠子群(torsion subgroup)的概念在理论层面同样重要。\(n\)-挠子群 \(E[n]\) 是满足 \([n]P = \mathcal{O}\) 的所有点的集合。在代数闭包上，\(E[n] \cong \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}\)（当 \(\gcd(n, p) = 1\) 时），这一结构是 Weil 配对与 Tate 配对等双线性映射的基础，也是后续配对密码学的出发点。
五、标量乘法算法
标量乘法(scalar multiplication)——给定标量 \(k\) 与点 \(P\)，计算 \([k]P = \underbrace{P + P + \cdots + P}_{k}\)——是椭圆曲线密码学中最核心的运算。密钥生成、签名、Diffie-Hellman 密钥交换本质上都是一次标量乘法。因此，标量乘法的效率直接决定了整个密码系统的性能。
倍加法(double-and-add)是最基本的算法，其思想与模幂运算中的平方乘法(square-and-multiply)完全类似。将 \(k\) 的二进制表示为 \(k = \sum_{i=0}^{l-1} k_i 2^i\)，从最高位到最低位扫描，每步执行一次倍增，遇到 \(k_i = 1\) 时再额外执行一次加法。对于 \(l\) 位的标量，总共需要 \(l\) 次倍增和平均 \(l/2\) 次加法。
然而，朴素的倍加法存在严重的侧信道(side-channel)安全隐患：加法和倍增在时间、功耗等物理特征上可能不同，攻击者可以通过简单功耗分析(Simple Power Analysis, SPA)逐比特恢复标量 \(k\)。
Montgomery 阶梯(Montgomery ladder)是一种天然恒定时间(constant-time)的标量乘法算法。它维护两个点 \(R_0\) 和 \(R_1\)，满足 \(R_1 - R_0 = P\) 的不变量。每一步根据 \(k\) 的当前比特，要么更新 \((R_0, R_1) \leftarrow (2R_0, R_0 + R_1)\)，要么更新 \((R_0, R_1) \leftarrow (R_0 + R_1, 2R_1)\)。关键在于：无论比特值是 0 还是 1，每步都执行恰好一次倍增和一次加法，运算序列相同，仅操作数不同。结合条件交换(conditional swap)操作的恒定时间实现，Montgomery 阶梯天然抵抗 SPA 攻击。
窗口化非相邻形式(windowed Non-Adjacent Form, wNAF)通过对标量进行重编码来减少加法次数。NAF 是一种带符号的二进制表示，保证没有两个相邻的非零位，从而使非零位密度降至约 \(1/3\)。窗口化版本进一步扩大预计算表，将密度降至约 \(1/(w+1)\)，其中 \(w\) 是窗口宽度。代价是需要预计算 \(2^{w-1}\) 个点——这在固定基点(fixed-base)场景下可以离线完成，适用于签名生成。
GLV 分解(Gallant-Lambert-Vanstone endomorphism)利用曲线的自同态(endomorphism)将标量乘法分解为两个半长度的标量乘法，再用 Shamir 技巧(Shamir’s trick)并行计算。例如，secp256k1 曲线上存在高效的自同态 \(\phi: (x, y) \mapsto (\beta x, y)\)，其中 \(\beta\) 是 \(\mathbb{F}_p\) 中的一个立方根。通过将 \(k\) 分解为 \(k = k_1 + k_2 \lambda\)（\(\lambda\) 是 \(\phi\) 在群上的特征值），可以计算 \([k]P = [k_1]P + [k_2]\phi(P)\)，每个半长标量只需约 128 位的多标量乘法。这一技术使得 secp256k1 上的标量乘法比没有自同态的曲线快约 30% 至 50%。
六、Montgomery 曲线与 x-only 算术
Montgomery 曲线(Montgomery curve)由 Peter Montgomery 于 1987 年提出，其方程形式为：
\[ By^2 = x^3 + Ax^2 + x \]
其中 \(B(A^2 - 4) \neq 0\)。与短 Weierstrass 形式相比，Montgomery 形式有一个独特的优势：差分加法(differential addition)——即已知 \(P - Q\) 的情况下计算 \(P + Q\)——可以完全避免 \(y\) 坐标，仅使用 \(x\) 坐标（更准确地说，使用射影坐标 \((X : Z)\)）。这被称为 x-only 算术(x-only arithmetic)。
差分加法的核心公式如下。设 \(P = (X_P : Z_P)\)，\(Q = (X_Q : Z_Q)\)，\(P - Q = (X_{P-Q} : Z_{P-Q})\)，则：
\[ X_{P+Q} = Z_{P-Q} \cdot [(X_P - Z_P)(X_Q + Z_Q) + (X_P + Z_P)(X_Q - Z_Q)]^2 \]
\[ Z_{P+Q} = X_{P-Q} \cdot [(X_P - Z_P)(X_Q + Z_Q) - (X_P + Z_P)(X_Q - Z_Q)]^2 \]
而倍增公式仅需 \(P\) 本身的坐标和曲线常数 \((A + 2)/4\)。
Montgomery 阶梯与 Montgomery 曲线堪称天作之合。在阶梯算法中，\(R_1 - R_0 = P\) 的不变量恰好提供了差分加法所需的已知差值。因此，整个标量乘法过程中每步只需要 5 次模乘和 4 次模平方（加上若干加减法），不需要任何模逆。
Curve25519 是 Daniel J. Bernstein 于 2006 年设计的 Montgomery 曲线，定义为：
\[ y^2 = x^3 + 486662x^2 + x \quad \text{over } \mathbb{F}_{2^{255} - 19} \]
其设计体现了多项精巧的工程考量。首先，素数 \(p = 2^{255} - 19\) 是一个伪梅森素数(pseudo-Mersenne prime)，使得模约简可以用少量移位和加法完成，极大提升了运算速度。其次，\(A = 486662\) 是满足安全要求的最小正偶数值，体现了参数选择的严格性(rigidity)——攻击者无法声称设计者隐藏了后门。最后，Curve25519 的群阶为 \(8 \cdot n\)，其中 \(n\) 是一个大素数，余因子 \(h = 8\) 的选择使得曲线上所有点的 \(x\) 坐标恰好覆盖 \(\mathbb{F}_p\) 中约一半的元素，简化了密钥生成——随机 32 字节直接作为标量即可，无需验证点是否在曲线上。
Curve25519 上的 Diffie-Hellman 协议被称为 X25519，其输入和输出均为 32 字节的 \(x\) 坐标值。由于 x-only 算术天然忽略 \(y\) 坐标的符号，协议不受点压缩或符号约定的影响，接口极其简洁。
从工程实践来看，Curve25519 的设计堪称密码工程学的教科书范例。Bernstein 在这条曲线中做的每一个选择都不是为了数学上的美观，而是为了消除实现者犯错的可能性。素数 \(p = 2^{255} - 19\) 的形状使得模约简只需几条移位和加法指令——不是因为这是「最安全」的素数，而是因为它让常数时间实现变得简单到几乎不可能出错。余因子 \(h = 8\) 的选择使得随机 32 字节可以直接用作私钥，无需验证是否在子群内——这消除了一整类因错误验证而导致的小子群攻击。最精妙的是密钥钳位（clamping）：将私钥的最低 3 位清零（确保是 8 的倍数以清除余因子）、最高位置 1（确保标量乘法的循环次数恒定）——这两个看似简单的位操作，一举解决了小子群攻击和时序侧信道两个独立的安全问题。笔者认为，Curve25519 的真正创新不在于它的数学（Montgomery 曲线早在 1987 年就存在），而在于它证明了一条曲线可以被设计得「几乎不可能被误用」——这对密码工程的理念产生了深远影响。
七、Edwards 与扭曲 Edwards 曲线
2007 年，Harold Edwards 提出了一种新的椭圆曲线形式，后经 Bernstein 和 Lange 推广为扭曲 Edwards 形式(twisted Edwards form)：
\[ ax^2 + y^2 = 1 + dx^2y^2 \]
其中 \(a \neq d\)，\(a, d \in \mathbb{F}_p\)。当 \(a = 1\) 时即为标准 Edwards 形式。
Edwards 曲线最引人注目的特性是其加法公式的完备性(completeness)。加法公式如下：
\[ (x_1, y_1) + (x_2, y_2) = \left(\frac{x_1 y_2 + y_1 x_2}{1 + d x_1 x_2 y_1 y_2},\; \frac{y_1 y_2 - a x_1 x_2}{1 - d x_1 x_2 y_1 y_2}\right) \]
当 \(d\) 在 \(\mathbb{F}_p\) 中不是二次剩余(quadratic residue)时，分母 \(1 + dx_1 x_2 y_1 y_2\) 和 \(1 - dx_1 x_2 y_1 y_2\) 对于曲线上的所有点对都不为零。这意味着同一个公式适用于所有情况——包括 \(P + Q\)、\(P + P\)、\(P + \mathcal{O}\)、\(P + (-P)\)——无需任何条件分支。没有条件分支意味着实现天然抵抗侧信道攻击，同时大幅简化了代码验证的复杂度。
在性能方面，使用扩展坐标(extended coordinates) \((X : Y : T : Z)\)（其中 \(T = XY/Z\)），统一加法需要 8 次模乘；倍增需要 4 次模平方加 1 次模乘。这些数字与短 Weierstrass 形式下的雅各比坐标运算相当，但由于无需条件分支，实际流水线效率更高。
Ed25519 是基于扭曲 Edwards 曲线的签名方案(EdDSA 的一个实例)，其底层曲线为：
\[ -x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2 \quad \text{over } \mathbb{F}_{2^{255} - 19} \]
这条曲线双有理等价(birational equivalence)于 Curve25519——两者定义在相同的素数域上，描述的是”同一条”椭圆曲线的不同坐标表示。Ed25519 用于签名（如 SSH 密钥、Signal 协议），而 X25519 用于密钥交换，两者可以共享参数甚至密钥（经过适当的域分离）。
Ed448 则基于 Goldilocks 素数 \(p = 2^{448} - 2^{224} - 1\) 上的 Edwards 曲线，提供约 224 位的安全强度，适用于需要更高安全余量的场景。其完整名称为 Edwards448-Goldilocks，余因子 \(h = 4\)。
7.1 三种曲线形式并排对照
下表将 Weierstrass、Montgomery 与 Edwards 三种曲线形式从方程、运算特性到工程适用性进行全面对比：
| 维度 | 短 Weierstrass | Montgomery | 扭曲 Edwards |
|---|---|---|---|
| 方程 | \(y^2 = x^3 + ax + b\) | \(By^2 = x^3 + Ax^2 + x\) | \(ax^2 + y^2 = 1 + dx^2y^2\) |
| 加法公式复杂度 | 混合坐标下约 11-16M（视坐标系） | x-only 阶梯：5M + 4S + 1D 每步 | 扩展坐标：8M（统一公式） |
| 加法公式完备？ | 否（需区分 \(P+Q\)、\(2P\)、\(P+\mathcal{O}\)、\(P+(-P)\)） | 否（但 x-only 阶梯天然统一） | 是（当 \(d\) 非二次剩余时单一公式覆盖所有情形） |
| 侧信道安全？ | 需额外工程措施（条件分支多） | Montgomery 阶梯天然恒定时间 | 完备公式天然恒定时间 |
| 主要用途 | 通用：NIST 标准曲线、secp256k1（比特币）、配对友好曲线 | Diffie-Hellman 密钥交换（X25519、X448） | 数字签名（Ed25519、Ed448） |
| 代表曲线 | NIST P-256、secp256k1、BLS12-381 | Curve25519、Curve448 | Ed25519、Ed448 |
个人思考。 三种曲线形式的选择，表面上是数学公式的差异，本质上却反映了截然不同的设计哲学。Weierstrass 追求的是「最大公约数」式的通用性——几乎所有椭圆曲线都能写成这种形式，标准化文档和硬件加速也围绕它构建，代价是实现者必须自行处理大量边界情况。Montgomery 的哲学是「只做一件事并做到极致」——丢弃 \(y\) 坐标后，密钥交换所需的全部运算压缩进一条无分支的阶梯循环中，这是一种为特定协议量身定制的极简主义。Edwards 则代表了「安全优先」的理念——完备加法公式从数学层面消除了实现缺陷的可能性，将侧信道防护从工程问题降格为数学定理。我个人的经验是：当你不确定该选哪种形式时，先问自己「我最害怕的实现错误是什么」——这个问题的答案往往直接指向正确的选择。
八、曲线选择标准
选择一条安全、高效的椭圆曲线远非随机取值那样简单。密码学社区在经历了围绕 NIST 曲线的信任危机后，逐步形成了一套系统化的曲线选择标准。Daniel J. Bernstein 和 Tanja Lange 发起的 SafeCurves 项目将这些标准整理为一份可操作的检查清单。
安全强度(security level)：曲线的素数阶子群 \(n\) 应满足 \(\log_2 n \geq 2s\)，其中 \(s\) 是目标安全位数。对于 128 位安全，\(n\) 至少 256 位。
抗已知攻击：曲线必须避免以下弱点——(1) MOV 攻击：嵌入度(embedding degree)不能太小，即 \(p^k \bmod n \neq 1\) 对于所有小 \(k\)（通常要求 \(k > (n-1)/100\)）；(2) 异常曲线攻击(anomalous curve attack)：\(\#E(\mathbb{F}_p) \neq p\)，即 Frobenius 迹 \(t \neq 1\)；(3) 低余因子相关的小子群攻击。
扭曲安全(twist security)：曲线的二次扭曲(quadratic twist) \(E'\) 的群阶 \(\#E'(\mathbb{F}_p) = p + 1 + t\) 也应具有大的素因子。这一要求至关重要，因为在 x-only 协议中，如果一方发送了不在 \(E\) 上的 \(x\) 坐标值，它可能在扭曲曲线 \(E'\) 上有效。如果 \(E'\) 的群阶只有小因子，攻击者可以通过这类无效点(invalid point)恢复私钥——这就是无效曲线攻击(invalid curve attack)的一种变体。Curve25519 的扭曲阶为 \(4 \cdot n'\)，\(n'\) 为大素数，因而具备强扭曲安全性。
参数刚性(rigidity)：曲线参数的选择过程应公开且可验证，不留”后门余地”。NIST P-256 的种子(seed)来源未被完全解释，引发了社区对”nothing-up-my-sleeve”性质的质疑。相比之下，Curve25519 的 \(A = 486662\) 是满足所有安全条件的最小值，选择过程完全透明。Brainpool 曲线使用 SHA-1 哈希生成参数，虽然过程确定，但对哈希输入的选择仍有一定的灵活度，刚性不如 Curve25519。
余因子考量(cofactor concerns)：\(h = 1\) 的曲线在协议设计上最为简单——无需余因子清除，Diffie-Hellman 输出天然在素数阶子群中。但 \(h > 1\) 的曲线（如 Curve25519 的 \(h = 8\)）在性能和参数刚性方面有优势。为调和这一矛盾，Mike Hamburg 提出了 Decaf 编码(Decaf encoding)，后来 Ristretto 编码将其推广到余因子为 8 的曲线：通过在点的编码层面消除余因子，向上层协议呈现一个素数阶群的接口，兼顾安全性与效率。
恒定时间可实现性(constant-time implementability)：曲线形式应便于编写没有秘密相关分支(secret-dependent branch)和秘密相关内存访问(secret-dependent memory access)的代码。Edwards 曲线的完备加法公式和 Montgomery 曲线的阶梯算法在此方面具有结构性优势。
一个值得深思的现象是，「可验证生成」的曲线参数（即 nothing-up-my-sleeve numbers）对安全性的贡献远小于对信任的贡献——但在密码学的社会契约中，信任往往比数学安全性更重要。从纯数学角度看，NIST P-256 和 Curve25519 的安全性论证同样坚实——没有任何已知攻击能利用 P-256 种子的「不透明性」。但从社会工程角度看，当 Snowden 文件揭示 NSA 曾试图在 Dual_EC_DRBG 中植入后门后，整个密码学社区对 NSA 参与设计的任何标准都产生了合理的怀疑。Curve25519 的参数选择过程——\(A = 486662\) 是满足所有安全约束的最小正偶数——具有一种数学上的必然性，不给设计者留下任何「选择空间」。这种刚性之所以重要，不是因为它让曲线更安全（在数学意义上没有区别），而是因为它让使用者无需信任设计者的动机。在后 Snowden 时代，这种「零信任参数选择」已经成为新密码标准的隐性门槛。
九、实际曲线对比
下面对比密码学实践中最常见的几条曲线，从安全性、性能和生态支持三个维度进行分析。
NIST P-256(secp256r1)：短 Weierstrass 形式，\(h = 1\)，256 位安全。优点是获得 NIST 标准背书，硬件加速广泛（Intel AES-NI 同代的 AVX 指令集、ARM Crypto Extension），在 TLS 生态中占有率最高。缺点是参数来源不够透明（种子由 NSA 提供），短 Weierstrass 形式需要条件分支，恒定时间实现难度较高。OpenSSL 等主流库已投入大量工程努力解决这一问题，但历史上曾出现多次时序攻击(timing attack)漏洞。
Curve25519/Ed25519：Montgomery/扭曲 Edwards 形式，\(h = 8\)，约 128 位安全。优点是参数选择完全刚性、恒定时间实现简单、软件性能极优（在没有硬件加速的平台上通常是最快的曲线）。缺点是余因子 \(h = 8\) 需要在协议层面小心处理，不过 Ristretto 编码已基本消除了这一负担。目前被 Signal、WireGuard、SSH(Ed25519)、TLS 1.3 等广泛采用。
secp256k1：短 Weierstrass 形式，\(h = 1\)，256 位安全。这条曲线因比特币而闻名。其参数 \(a = 0\)、\(b = 7\) 选择极为简洁，并且 \(\mathbb{F}_p\) 上存在高效的自同态映射，使得 GLV 分解可以将标量乘法加速约 40%。然而，\(a = 0\) 使得某些特殊攻击(如某些故障注入攻击)需要额外防护。
BLS12-381：这是一条配对友好(pairing-friendly)曲线，嵌入度 \(k = 12\)，设计用于双线性配对。其安全强度约为 128 位。BLS12-381 是零知识证明系统(如 Groth16、PLONK)和 BLS 签名聚合的核心曲线，在以太坊 2.0 的共识机制中扮演关键角色。由于配对运算本身代价高昂，BLS12-381 的标量乘法速度远慢于 Curve25519，但在需要配对功能的场景下不可替代。
从性能角度做一个粗略对比：在现代 x86-64 处理器上，X25519 密钥交换约需 15 万个时钟周期，ECDH-P256（无硬件加速）约需 30 万至 50 万个时钟周期，而 BLS12-381 上的配对运算则需要数百万个时钟周期。当 CPU 支持专用指令（如 Intel 的 IFMA 乘法指令）时，P-256 可大幅缩小与 Curve25519 的差距。
选择曲线时，工程师需要在以下因素间权衡：标准合规性（政府和金融领域通常要求 NIST 曲线）、生态系统支持（TLS 库的实现质量和互操作性）、参数信任度（是否相信参数选择过程没有后门）、特殊功能需求（是否需要配对、是否需要 GLV 加速）、以及目标平台的硬件能力（嵌入式设备可能没有 NIST P-256 的硬件加速，此时 Curve25519 的纯软件性能优势更为突出）。
总的来说，椭圆曲线代数为现代密码学提供了一个优雅而强大的数学框架。从 Weierstrass 方程的简洁定义，到弦切法的几何直觉，再到 Montgomery 阶梯的恒定时间保障和 Edwards 曲线的完备加法公式，每一层抽象都在安全性和效率之间寻找精妙的平衡。理解这些代数结构，不仅有助于正确使用现有的密码协议，也是深入研究零知识证明、同态加密和后量子密码学的必要前提。展望未来，随着后量子密码学的推进，基于格(lattice)和编码(code)的方案可能在某些场景中取代椭圆曲线，但在量子计算机真正具备破解 ECDLP 的能力之前，椭圆曲线仍将是公钥密码学领域中效率最高、研究最为深入的核心工具。而对于需要配对运算的高级协议——如 BLS 签名、零知识证明、基于身份的加密——椭圆曲线更是唯一可行的数学基础，其地位在可预见的未来都不会动摇。
密码学百科系列 · 第 35 篇
← 上一篇：数论进阶 | 系列目录 | 下一篇：离散对数与配对密码学 →