【密码学百科】椭圆曲线代数：Weierstrass 方程、点群运算与曲线选择

在公钥密码学的演进历程中，椭圆曲线密码学(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 方程与曲线形态

先看一张图，把这一节的关键关系串起来。

graph TD
    A[曲线方程] --> B[点群]
    B --> C[标量乘法]
    C --> D[同源与配对]
    D --> E[安全参数]

椭圆曲线最一般的定义基于 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 配对等双线性映射的基础，也是后续配对密码学的出发点。

ECDLP 攻击算法的工程意义

理解群结构之后，有必要审视攻击者视角——正是对 ECDLP 攻击算法的分析，决定了我们如何选择群阶和安全参数。

Pollard rho 算法是目前攻击 ECDLP 的最有效经典方法，其时间复杂度为 \(O(\sqrt{n})\)，空间复杂度仅为 \(O(1)\)。算法的核心思想是在群中构造伪随机游走，利用生日悖论(birthday paradox)寻找碰撞。对于 256 位的群阶 \(n\)，攻击者需要大约 \(2^{128}\) 次群运算。Pollard rho 的一大优势在于可并行化：采用杰出点(distinguished points)技术，\(r\) 个处理器可以获得 \(\sqrt{r}\) 倍的加速。即便动用 \(2^{40}\)（约一万亿）个处理器，每个处理器仍需执行约 \(2^{88}\) 次群运算——以每秒 \(10^9\) 次运算计算，仍需数十亿年，因此对 256 位曲线的攻击在经典计算框架下完全不可行。

Pohlig-Hellman 算法将合数阶群中的离散对数问题归约为各素因子阶子群中的离散对数问题。若群阶 \(n\) 可分解为 \(n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}\)，则 DLP 的难度由最大素因子决定。这一结果直接解释了前文提到的 \(h \cdot n\) 分解为何如此重要：如果群阶包含大量小因子，Pohlig-Hellman 算法可以将 DLP 逐一击破。工程上的结论非常明确——必须确保群阶包含一个大素因子 \(n\)，且余因子 \(h\) 足够小。NIST P-256 和 secp256k1 选择 \(h = 1\)（群阶本身为素数），从根本上杜绝了此类风险；Curve25519 的 \(h = 8\) 虽然引入了小子群，但通过余因子清除即可化解。

Baby-step Giant-step (BSGS)算法同样达到 \(O(\sqrt{n})\) 的时间复杂度，但需要 \(O(\sqrt{n})\) 的存储空间。对于 256 位群阶，这意味着需要存储约 \(2^{128}\) 个群元素——远超任何现实存储系统的容量。因此，尽管 BSGS 在理论上与 Pollard rho 等价，在实际大规模攻击中因内存限制而远不如后者实用。

总结而言，这些攻击算法的分析将安全等级锁定在 \(n/2\) 位：256 位群阶提供 128 位安全，这正是密码学参数选择的理论基石。

五、标量乘法算法

标量乘法(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%。

标量乘法的复杂度分析与侧信道防护框架

不同的标量乘法算法在运算次数、预计算开销和侧信道安全性方面各有取舍。下表给出了主要方法的定量对比（设标量为 \(l\) 位）：

从表中可以看出，Montgomery 阶梯虽然加法次数最多（每步都执行加法），但其天然的恒定时间特性使其成为对侧信道安全性要求最高的场景（如密钥交换）的首选。wNAF 和梳形法(comb method)在加法次数上有显著优势，适合固定基点的签名生成场景，但需要额外的侧信道防护措施。

侧信道防护的三层体系。 生产级实现通常同时叠加以下三种防御手段：

1. 标量盲化(scalar blinding)：将标量 \(k\) 替换为 \(k' = k + r \cdot n\)，其中 \(r\) 是随机数，\(n\) 是群阶。由于 \([k']P = [k + rn]P = [k]P\)，运算结果不变，但攻击者观测到的是被随机化的标量，无法通过功耗或电磁泄漏恢复真实的 \(k\)。
2. 基点盲化(point blinding)：预计算一个随机点 \(R\) 及其标量乘积 \(S = [k]R\)。实际计算时使用 \(P' = P + R\)，得到 \(Q' = [k]P'\)，再减去 \(S\) 得到 \([k]P = Q' - S\)。每次运算使用不同的 \(R\)，使得输入点对攻击者而言是随机的。
3. 射影坐标随机化(projective coordinate randomization)：将射影坐标 \((X : Y : Z)\) 替换为 \((\lambda^2 X : \lambda^3 Y : \lambda Z)\)，其中 \(\lambda\) 是随机非零域元素。这一变换不改变对应的仿射点，但使得中间计算值完全随机化，有效抵御差分功耗分析(Differential Power Analysis, DPA)。

这三种防御手段是可叠加的，生产级实现（如 OpenSSL、BoringSSL）通常同时使用全部三种。叠加防护的性能开销大约为未防护实现的 10% 至 30%——这一代价在绝大多数应用场景中完全可以接受，远小于因侧信道泄漏而导致密钥被恢复的灾难性后果。

六、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 的哲学是「只做一件事并做到极致」——丢弃 \(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 的纯软件性能优势更为突出）。

同源密码学简介

椭圆曲线不仅是经典公钥密码学的基石，也是后量子密码学(post-quantum cryptography)中一个独特方向的数学基础——同源密码学(isogeny-based cryptography)。

同源(isogeny)是椭圆曲线之间的一类特殊映射：从曲线 \(E_1\) 到曲线 \(E_2\) 的非常数有理映射 \(\varphi: E_1 \to E_2\)，且保持群结构，即 \(\varphi(P + Q) = \varphi(P) + \varphi(Q)\)。直观地说，同源是一种”保结构的曲线变换”——它将一条椭圆曲线上的群运算忠实地映射到另一条曲线上。同源的度(degree)反映了映射的复杂度，核(kernel)则是被映射到零元的点集。

将同构类的椭圆曲线作为顶点、固定素数度 \(\ell\) 的同源作为边，可以构造出同源图(isogeny graph)。超奇异(supersingular)椭圆曲线的 \(\ell\)-同源图具有良好的扩展图(expander graph)性质——图中任意两点之间都存在较短的路径，但找到这条路径在计算上却非常困难。这种”图中路径寻找”的困难性构成了同源密码学的安全基础。

SIDH/SIKE 是最早引起广泛关注的同源密码方案：Alice 和 Bob 各自沿超奇异同源图中不同素数度的方向行走，通过交换中间曲线信息来建立共享密钥。SIKE 曾进入 NIST 后量子密码标准化的第四轮候选。然而，2022 年 Castryck 和 Decru 发表了毁灭性的攻击——利用 SIDH 协议中公开的辅助挠点(auxiliary torsion point)信息，在经典计算机上即可在数小时内恢复私钥。这一攻击彻底打破了 SIDH/SIKE 的安全性假设。

尽管 SIDH 被攻破，同源密码学的研究并未停止。CSIDH（commutative SIDH）基于普通(ordinary)椭圆曲线而非超奇异曲线，其同源作用具有交换性质，且不需要公开辅助挠点信息，因此不受 Castryck-Decru 攻击的影响。SQIsign 则是一种基于四元数代数(quaternion algebra)与同源的数字签名方案，能够生成极其紧凑的签名——仅约 204 字节，远小于基于格的签名方案（如 Dilithium 的约 2.4 KB）。但 SQIsign 的签名速度较慢（约数秒），目前仍是活跃的优化研究方向。

同源密码学之所以值得关注，在于它是唯一保留了”椭圆曲线风味”的后量子方向——底层数学对象仍然是椭圆曲线，安全性基础从离散对数问题转换为同源计算问题。对于已经深入理解椭圆曲线代数的读者而言，同源密码学是最自然的后量子延伸。

总的来说，椭圆曲线代数为现代密码学提供了一个优雅而强大的数学框架。从 Weierstrass 方程的简洁定义，到弦切法的几何直觉，再到 Montgomery 阶梯的恒定时间保障和 Edwards 曲线的完备加法公式，每一层抽象都在安全性和效率之间寻找精妙的平衡。理解这些代数结构，不仅有助于正确使用现有的密码协议，也是深入研究零知识证明、同态加密和后量子密码学的必要前提。展望未来，随着后量子密码学的推进，基于格(lattice)和编码(code)的方案可能在某些场景中取代椭圆曲线，但在量子计算机真正具备破解 ECDLP 的能力之前，椭圆曲线仍将是公钥密码学领域中效率最高、研究最为深入的核心工具。而对于需要配对运算的高级协议——如 BLS 签名、零知识证明、基于身份的加密——椭圆曲线更是唯一可行的数学基础，其地位在可预见的未来都不会动摇。

密码学百科系列 · 第 35 篇

← 上一篇：数论进阶 | 系列目录 | 下一篇：离散对数与配对密码学 →