在前一篇关于有限域算术的文章中，我们讨论了有限域上的基本运算与结构。本文将在此基础上继续深入，介绍两个在现代密码学中扮演核心角色的数论主题：二次剩余(quadratic residue)理论与椭圆曲线上的配对映射(pairing)。二次剩余理论从 Euler 判别法到二次互反律，为密码学提供了判断平方根存在性与高效计算平方根的工具；而以 Weil 配对为代表的双线性映射，则开启了基于身份加密(Identity-Based Encryption, IBE)、BLS 签名、属性基加密(Attribute-Based Encryption, ABE)乃至零知识证明(zk-SNARKs)等一系列革命性密码学构造。两者看似相隔甚远，实则在椭圆曲线点的解压缩、曲线参数选取等环节紧密交织。

一、二次剩余与 Legendre 符号

1.1 基本定义

设 \(p\) 为奇素数，\(a\) 为不被 \(p\) 整除的整数。若同余方程

\[x^2 \equiv a \pmod{p}\]

有解，则称 \(a\) 是模 \(p\) 的二次剩余(quadratic residue, QR)；否则称 \(a\) 为模 \(p\) 的二次非剩余(quadratic non-residue, QNR)。在模 \(p\) 的缩系 \(\{1, 2, \ldots, p-1\}\) 中，恰好有 \((p-1)/2\) 个二次剩余与 \((p-1)/2\) 个二次非剩余。这一对称性源于映射 \(x \mapsto x^2\) 在 \(\mathbb{Z}_p^*\) 上恰好是一个二对一的同态，其像集即为全部二次剩余构成的子群。

1.2 Legendre 符号

Legendre 符号(Legendre symbol)是刻画二次剩余性的经典工具，定义如下：

\[\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{若 } p \mid a, \\ 1 & \text{若 } a \text{ 是模 } p \text{ 的二次剩余}, \\ -1 & \text{若 } a \text{ 是模 } p \text{ 的二次非剩余}. \end{cases}\]

Legendre 符号具有完全积性：\(\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\)。这一性质使得计算可以分解为对素因子的判断。

1.3 Euler 判别法

Euler 判别法(Euler’s criterion)给出了计算 Legendre 符号的核心定理：对于奇素数 \(p\) 和 \(\gcd(a, p) = 1\)，有

\[\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}.\]

证明的关键在于 \(\mathbb{Z}_p^*\) 是一个 \(p-1\) 阶循环群。设 \(g\) 为其生成元，\(a = g^k\)，则 \(a^{(p-1)/2} = g^{k(p-1)/2}\)。当 \(k\) 为偶数时此值为 \(1\)（对应二次剩余），当 \(k\) 为奇数时此值为 \(-1\)（对应二次非剩余）。Euler 判别法使我们可以通过一次模幂运算在 \(O(\log p)\) 次乘法内完成判定，这在密码学实现中极其高效。

以下是用 Python 实现 Legendre 符号计算的示例代码：

def legendre_symbol(a, p):
    """
    计算 Legendre 符号 (a/p)。
    要求 p 为奇素数。
    返回值：1（二次剩余）、-1（二次非剩余）、0（p 整除 a）。
    """
    if a % p == 0:
        return 0
    result = pow(a, (p - 1) // 2, p)
    # pow(a, exp, mod) 使用快速模幂，复杂度 O(log p)
    return result if result <= 1 else result - p

# 示例：p = 23
p = 23
qr_list = [a for a in range(1, p) if legendre_symbol(a, p) == 1]
qnr_list = [a for a in range(1, p) if legendre_symbol(a, p) == -1]
print(f"模 {p} 的二次剩余：{qr_list}")
print(f"模 {p} 的二次非剩余：{qnr_list}")
# 输出：
# 模 23 的二次剩余：[1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18]
# 模 23 的二次非剩余：[5, 7, 10, 11, 14, 15, 17, 19, 20, 21, 22]

二、Jacobi 符号与二次互反律

2.1 Jacobi 符号

当模数 \(n\) 不是素数而是奇数时，Legendre 符号不再适用。Jacobi 符号(Jacobi symbol)将其推广到任意奇数模。设 \(n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}\) 为 \(n\) 的素因数分解，则 Jacobi 符号定义为：

\[\left(\frac{a}{n}\right) = \prod_{i=1}^{k} \left(\frac{a}{p_i}\right)^{e_i}.\]

需要特别注意的是，Jacobi 符号为 \(1\) 并不意味着 \(a\) 是模 \(n\) 的二次剩余——它只是各 Legendre 符号之积为 \(1\)，可能出现偶数个 \(-1\) 相乘的情形。然而 Jacobi 符号为 \(-1\) 则一定意味着 \(a\) 不是模 \(n\) 的二次剩余。这一”单向”判定性质在素性检测(如 Solovay-Strassen 素性测试)中有重要应用。

Jacobi 符号的重要优点在于它可以在不分解 \(n\) 的前提下高效计算。利用互反律和一系列递推关系，计算 Jacobi 符号的过程类似于辗转相除法，时间复杂度为 \(O(\log^2 n)\)。

2.2 二次互反律

二次互反律(quadratic reciprocity law)是数论中最优美的定理之一，由 Gauss 首先给出完整证明，被他称为”算术的宝石”(theorema aureum)。该定理断言：设 \(p, q\) 为不同的奇素数，则

\[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}.\]

直观地说，当 \(p \equiv q \equiv 3 \pmod{4}\) 时，\(p\) 是模 \(q\) 的二次剩余与 \(q\) 是模 \(p\) 的二次剩余恰好”相反”；在其他情况下则”相同”。二次互反律配合两个补充定律——\(\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}\) 和 \(\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}\)——构成了递归计算 Jacobi 符号的理论基础。

2.3 在密码学中的应用

二次剩余理论在密码学中有多方面应用。Goldwasser-Micali 加密方案直接建立在判定二次剩余性的困难性假设之上：给定合数 \(n = pq\)（\(p, q\) 为大素数）和一个 Jacobi 符号为 \(1\) 的元素 \(a\)，判断 \(a\) 是否为模 \(n\) 的二次剩余在不知道 \(n\) 的分解时被认为是困难的。此外，Blum-Blum-Shub 伪随机数生成器的安全性也依赖于二次剩余假设。在椭圆曲线密码学中，点的压缩表示需要判断某个值是否为二次剩余并计算其平方根，这正是下一节的主题。

三、平方根模素数

3.1 问题陈述

给定奇素数 \(p\) 和二次剩余 \(a\)（即 \(\left(\frac{a}{p}\right) = 1\)），求满足 \(x^2 \equiv a \pmod{p}\) 的 \(x\)。若 \(x_0\) 是一个解，则 \(p - x_0\) 是另一个解；因此平方根成对出现。

当 \(p \equiv 3 \pmod{4}\) 时，情况极为简单：\(x = a^{(p+1)/4} \bmod p\) 即为一个平方根。验证：\(x^2 = a^{(p+1)/2} = a \cdot a^{(p-1)/2} = a \cdot 1 = a\)，其中最后一步使用了 Euler 判别法。

3.2 Tonelli-Shanks 算法

当 \(p \equiv 1 \pmod{4}\) 时，上述简单公式不再适用。Tonelli-Shanks 算法是此时最常用的方法。其基本思路如下：

1. 将 \(p - 1\) 写成 \(2^s \cdot q\) 的形式，其中 \(q\) 为奇数。
2. 找到一个二次非剩余 \(z\)，令 \(M = s\)，\(c = z^q \bmod p\)，\(t = a^q \bmod p\)，\(R = a^{(q+1)/2} \bmod p\)。
3. 进入循环：若 \(t = 1\)，返回 \(R\)；否则找到最小的 \(i\) 使得 \(t^{2^i} \equiv 1\)，然后更新 \(b = c^{2^{M-i-1}}\)，\(M = i\)，\(c = b^2\)，\(t = t \cdot b^2\)，\(R = R \cdot b\)。

算法的核心思想是逐步将 \(t\) 的阶从 \(2^s\) 降为 \(1\)，每一步都将阶减半。由于每次迭代 \(M\) 严格减小，算法至多迭代 \(s\) 次。整体复杂度为 \(O(s \cdot \log p)\) 次模乘，在实际应用中非常高效。

值得深入理解的是 Tonelli-Shanks 算法中”阶下降”的代数机制。初始时 \(t = a^q\) 是 \(\mathbb{Z}_p^*\) 中阶为 \(2^s\) 的某个幂次的元素，而 \(c = z^q\) 是一个恰好具有 \(2^{s}\) 阶的元素（因为 \(z\) 是二次非剩余）。在每一轮迭代中，算法首先通过反复平方 \(t\) 来找到它当前的精确阶 \(2^i\)，然后利用 \(c\) 的适当幂次 \(b = c^{2^{M-i-1}}\) 作为”校正因子”与 \(t\) 相乘，使得乘积 \(t' = t \cdot b^2\) 的阶严格降低到 \(2^{i-1}\) 或更低。与此同时，\(R\) 也乘以 \(b\) 以保持 \(R^2 = a \cdot t\) 的不变量。当 \(t\) 的阶最终降为 \(1\)（即 \(t = 1\)）时，不变量给出 \(R^2 = a\)，\(R\) 即为所求平方根。这一过程本质上是在 \(2\)-Sylow 子群中利用已知的满阶元素逐步”对齐”待求元素的阶。在密码学工程实现中，寻找二次非剩余 \(z\) 通常采用随机采样并用 Euler 判别法验证，期望仅需两次尝试；而整个算法的主循环在 \(p - 1\) 含有较低 \(2\) 的幂次因子时收敛极快，因此 Tonelli-Shanks 在绝大多数实际曲线参数下的运行效率与简单公式相差无几。

3.3 Cipolla 算法

Cipolla 算法提供了另一种计算模素数平方根的途径。其思路是在 \(\mathbb{F}_p\) 的二次扩域 \(\mathbb{F}_{p^2}\) 中进行计算。具体步骤如下：

1. 随机选取 \(t\)，使得 \(t^2 - a\) 是模 \(p\) 的二次非剩余。由于 \(\mathbb{F}_p^*\) 中恰好有一半元素是非剩余，期望尝试两次即可找到。
2. 在 \(\mathbb{F}_{p^2} = \mathbb{F}_p[x]/(x^2 - (t^2 - a))\) 中计算 \((t + x)^{(p+1)/2}\)。
3. 结果一定落在 \(\mathbb{F}_p\) 中（即虚部为零），其实部即为所求平方根。

Cipolla 算法在 \(s\) 较大时（即 \(p - 1\) 含有很高的 \(2\) 的幂次因子）可能比 Tonelli-Shanks 更快，因为它只需一次扩域上的模幂运算，而无需反复迭代。

3.4 椭圆曲线点解压缩

在椭圆曲线密码学(ECC)中，曲线上的点 \((x, y)\) 通常以压缩形式存储：只保存 \(x\) 坐标和 \(y\) 的一个比特（通常是最低有效位或符号位）。恢复完整坐标时需要求解 \(y^2 = x^3 + ax + b \pmod{p}\)。这正是上述平方根算法的典型应用场景。若右端值不是二次剩余，说明该 \(x\) 不对应曲线上的点。在实际实现中（如 secp256k1 曲线，其 \(p \equiv 3 \pmod{4}\)），使用简单公式即可；对于其他曲线则需调用 Tonelli-Shanks 算法。

四、双线性映射的概念

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

flowchart LR
    A[二次剩余] --> B[Jacobi 与 TS]
    B --> C[配对构造]
    C --> D[Miller 循环]
    D --> E[最终幂]

4.1 定义

双线性映射(bilinear map)是从两个群到第三个群的映射，满足在每个分量上都是线性的。更精确地说，设 \(\mathbb{G}_1\)、\(\mathbb{G}_2\)、\(\mathbb{G}_T\) 为三个阶为素数 \(r\) 的循环群，映射 \(e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T\) 称为双线性映射，若满足以下三个性质：

1. 双线性(bilinearity)：对所有 \(P \in \mathbb{G}_1\)，\(Q \in \mathbb{G}_2\)，\(a, b \in \mathbb{Z}\)，有 \(e([a]P, [b]Q) = e(P, Q)^{ab}\)。
2. 非退化性(non-degeneracy)：存在 \(P \in \mathbb{G}_1\)，\(Q \in \mathbb{G}_2\)，使得 \(e(P, Q) \neq 1_{\mathbb{G}_T}\)。
3. 可计算性(efficient computability)：存在多项式时间算法计算 \(e(P, Q)\)。

4.2 群的设定

在基于椭圆曲线的配对密码学中，\(\mathbb{G}_1\) 和 \(\mathbb{G}_2\) 通常是椭圆曲线 \(E\) 上的 \(r\)-扭转子群(torsion subgroup)，而 \(\mathbb{G}_T\) 是有限域扩张 \(\mathbb{F}_{p^k}\) 中 \(r\) 次单位根所构成的乘法群。这里的 \(k\) 称为嵌入度(embedding degree)，它是满足 \(r \mid (p^k - 1)\) 的最小正整数。嵌入度的大小直接影响配对运算的效率和安全性：\(k\) 太小则容易受到 MOV 攻击（见第九节），\(k\) 太大则配对计算过于耗时。

4.3 配对的类型

根据 \(\mathbb{G}_1\) 与 \(\mathbb{G}_2\) 的关系，配对可分为三种类型。Type 1（对称配对）中 \(\mathbb{G}_1 = \mathbb{G}_2\)，此时配对具有对称性 \(e(P, Q) = e(Q, P)\)，多出现在超奇异曲线(supersingular curve)上。Type 2 中存在一个从 \(\mathbb{G}_2\) 到 \(\mathbb{G}_1\) 的高效同态(homomorphism)但反方向不存在。Type 3 中两个方向均无已知高效同态。不同类型适用于不同的密码学方案，方案设计时需仔细选择。

笔者认为，双线性配对的出现在密码学史上开辟了一个全新的维度。在配对之前，密码学的世界本质上只有两种范式：对称密码（共享密钥）和公钥密码（密钥对）。配对给了我们第三种范式——一种能够在「指数位置进行乘法」的代数工具。这种能力听起来抽象，但它的实际意义是颠覆性的：基于身份的加密（IBE）、属性基加密（ABE）、BLS 聚合签名——这些构造在配对出现之前不仅没有实现，而且有理论论证表明它们在标准的离散对数框架下似乎不可能实现。配对打破了这一不可能性，它的角色类似于数学中虚数单位 \(i\) 的引入——扩展了可能性空间本身。然而，这里存在一种深刻的讽刺：赋予配对构造能力的那种精确的数学结构——嵌入度适中的椭圆曲线上的扭转群——同时也赋予了攻击者将 ECDLP 归约到有限域 DLP 的能力（即 MOV/FR 攻击）。构造与攻击使用的是完全相同的数学工具，这在整个密码学中都是罕见的对称性。

5.1 定义与数学背景

Weil 配对是定义在椭圆曲线 \(r\)-扭转群 \(E[r]\) 上的双线性映射 \(e_r: E[r] \times E[r] \to \mu_r\)，其中 \(\mu_r\) 是 \(r\) 次单位根群。更具体地，设 \(P, Q \in E[r]\)，即 \([r]P = [r]Q = \mathcal{O}\)（无穷远点），则 Weil 配对通过因子(divisor)和有理函数(rational function)的语言来定义。

选取满足 \(\mathrm{div}(f_P) = r(P) - r(\mathcal{O})\) 的有理函数 \(f_P\)，以及类似的 \(f_Q\)。为了避免 \(f_P\) 在 \(Q\) 处无定义（或为零），引入辅助点进行平移。Weil 配对定义为：

\[e_r(P, Q) = \frac{f_P(Q + S)}{f_P(S)} \bigg/ \frac{f_Q(P - S)}{f_Q(-S)}\]

其中 \(S\) 是适当选取的辅助点，使得所有函数值均有意义。该定义与 \(S\) 的选取无关（这是定义良好性的关键）。

5.2 Weil 配对的性质

Weil 配对具有以下重要性质：

• 双线性：\(e_r(P_1 + P_2, Q) = e_r(P_1, Q) \cdot e_r(P_2, Q)\)，对第二个分量亦然。
• 反对称：\(e_r(P, Q) = e_r(Q, P)^{-1}\)。这意味着 \(e_r(P, P) = 1\)（当 \(r\) 为奇数时），因此在 Type 1 设定中 Weil 配对是平凡的，需使用扭曲(twist)将 \(Q\) 映射到不同子群。
• 非退化：若 \(P\) 是 \(E[r]\) 的生成元，则存在 \(Q\) 使得 \(e_r(P, Q) \neq 1\)。
• Galois 等变性：对于有限域上的 Frobenius 自同态 \(\phi\)，\(e_r(\phi(P), \phi(Q)) = \phi(e_r(P, Q))\)。

5.3 Miller 算法

计算 Weil 配对的核心是求值有理函数 \(f_P\) 在给定点处的值。Miller 算法(Miller’s algorithm)采用”边计算边求值”的策略，将构造 \(f_P\) 与对其求值合二为一。算法结构类似于标量乘法中的”倍加法”(double-and-add)，将 \(r\) 的二进制展开逐位处理。

算法维护一个中间点 \(T\)（初始为 \(P\)）和一个累积函数值 \(f\)（初始为 \(1\)）。在每一步中：

1. 倍点步骤：计算过 \(T\) 的切线 \(\ell\) 和竖直线 \(v\)（经过 \([2]T\) 的 \(x\) 坐标对应的竖直线），更新 \(f \leftarrow f^2 \cdot \ell(Q) / v(Q)\)，\(T \leftarrow [2]T\)。
2. 加点步骤（若当前位为 \(1\)）：计算过 \(T\) 和 \(P\) 的割线 \(\ell'\) 和竖直线 \(v'\)，更新 \(f \leftarrow f \cdot \ell'(Q) / v'(Q)\)，\(T \leftarrow T + P\)。

循环结束后 \(f\) 即为 \(f_P(Q)\) 的值。以下是 Miller 算法的简化 Python 示意：

def miller_loop(P, Q, r, curve):
    """
    Miller 算法的简化示意。
    P, Q 为椭圆曲线上的点，r 为扭转阶，curve 提供曲线运算。
    返回 f_P(Q) 的值（用于配对计算）。
    """
    if P == curve.identity or Q == curve.identity:
        return 1

    bits = bin(r)[3:]  # r 的二进制表示，去掉最高位 '1'
    T = P
    f = 1

    for bit in bits:
        # 倍点步骤
        ell = curve.line_through(T, T)      # 过 T 的切线
        v = curve.vertical_line(curve.double(T))  # 竖直线
        f = f * f * ell.evaluate(Q) / v.evaluate(Q)
        T = curve.double(T)

        if bit == '1':
            # 加点步骤
            ell = curve.line_through(T, P)   # 过 T 和 P 的割线
            v = curve.vertical_line(curve.add(T, P))
            f = f * ell.evaluate(Q) / v.evaluate(Q)
            T = curve.add(T, P)

    return f

def weil_pairing(P, Q, r, curve):
    """
    计算 Weil 配对 e_r(P, Q)。
    """
    f_P_at_Q = miller_loop(P, Q, r, curve)
    f_Q_at_P = miller_loop(Q, P, r, curve)
    # Weil 配对 = f_P(Q) / f_Q(P)，附加符号修正 (-1)^r
    return f_P_at_Q / f_Q_at_P

上述代码为教学示意，省略了辅助点平移、域元素的精确归一化等实际工程细节。在生产环境中应使用经过审计的密码学库（如 RELIC、PBC 或 py_ecc）。

5.4 Miller 算法的实现细节与优化

上一节给出了 Miller 算法的整体框架，但在实际工程实现中，有几处关键细节直接决定了配对计算的效率。本节对线函数求值、分母消除和稀疏乘法三项核心优化逐一展开。

线函数(line function)的显式求值。 Miller 循环中每一步都需要对”线函数”在点 \(Q = (x_Q, y_Q)\) 处求值。设当前累积点为 \(T = (x_T, y_T)\)，对曲线 \(E: y^2 = x^3 + ax + b\)，两种情形的计算公式如下：

• 倍点（切线）情形：过 \(T\) 的切线斜率为 \(\lambda = (3x_T^2 + a) / (2y_T)\)，线函数为

\[\ell_{T,T}(x_Q, y_Q) = (y_Q - y_T) - \lambda \cdot (x_Q - x_T)\]

• 加点（割线）情形：过 \(T\) 和 \(P = (x_P, y_P)\) 的割线斜率为 \(\lambda = (y_P - y_T) / (x_P - x_T)\)，线函数为

\[\ell_{T,P}(x_Q, y_Q) = (y_Q - y_T) - \lambda \cdot (x_Q - x_T)\]

竖直线函数则为 \(v(x_Q, y_Q) = x_Q - x_{T'}\)，其中 \(T'\) 是倍点或加点运算的结果。以下伪代码展示了完整的 Miller 循环逻辑：

def miller_loop_detailed(P, Q, r, a):
    """
    Miller 算法的详细伪代码，显式展示线函数求值。
    P = (xP, yP)，Q = (xQ, yQ)，r 为群阶，a 为曲线参数。
    """
    T = P
    f = 1
    bits = bin(r)[3:]  # r 的二进制，跳过最高位

    for bit in bits:
        xT, yT = T
        # 倍点：计算切线斜率与线函数
        lam = (3 * xT**2 + a) * inverse(2 * yT)
        ell_val = (Q.y - yT) - lam * (Q.x - xT)
        T = point_double(T, lam)
        v_val = Q.x - T[0]   # 竖直线
        f = f * f * ell_val / v_val

        if bit == '1':
            xT, yT = T
            xP, yP = P
            # 加点：计算割线斜率与线函数
            lam = (yP - yT) * inverse(xP - xT)
            ell_val = (Q.y - yT) - lam * (Q.x - xT)
            T = point_add(T, P, lam)
            v_val = Q.x - T[0]
            f = f * ell_val / v_val

    return f

分母消除(denominator elimination)优化。 在 Tate 配对及其变体中，Miller 循环的最终结果要经过最终幂运算 \(f \mapsto f^{(p^k-1)/r}\)。当嵌入度 \(k\) 为偶数时，竖直线函数 \(v(Q) = x_Q - x_{T'}\) 的值位于 \(\mathbb{F}_p\)（即基域），而最终幂运算会将 \(\mathbb{F}_p^*\) 中的所有元素映射为 \(1\)。这意味着竖直线求值对最终结果没有任何贡献，因此可以完全跳过竖直线的计算与除法操作。这一优化消除了 Miller 循环中约一半的域除法运算，在实际实现中带来显著提速。对于 BLS12-381（\(k = 12\)，偶数），分母消除是默认启用的标准优化。

稀疏乘法(sparse multiplication)优化。 线函数 \(\ell_{T,T}(Q)\) 和 \(\ell_{T,P}(Q)\) 的求值结果是 \(\mathbb{F}_{p^k}\) 中的元素，但它们的大部分分量为零。以 BLS12-381 为例，\(\mathbb{F}_{p^{12}}\) 的元素由 \(12\) 个 \(\mathbb{F}_p\) 系数表示，而线函数求值仅产生 \(3\)——\(4\) 个非零系数。普通的 \(\mathbb{F}_{p^{12}}\) 乘法需要 \(144\) 次 \(\mathbb{F}_p\) 乘法，但将 Miller 循环中的 \(f \cdot \ell(Q)\) 替换为利用稀疏结构的专用乘法例程，可以将每步的 \(\mathbb{F}_p\) 乘法次数降低约 \(50\%\)，从 \(144\) 次减少到约 \(65\)——\(78\) 次。在高性能库（如 blst、gnark-crypto）中，这类稀疏乘法是经过手工优化的汇编级实现。

复杂度分析。 以 BLS12-381 的最优 Ate 配对为例，Miller 循环的迭代次数由参数 \(u\) 的比特长度决定。BLS12-381 的参数 \(u\) 为 \(64\) 位整数（\(u = -\mathtt{0xd201000000010000}\)），其二进制展开含 \(4\) 个非零位。因此 Miller 循环共需约 \(68\) 次倍点步骤和仅 \(1\)——\(3\) 次加点步骤（非零位触发）。每个倍点步骤的主要开销为一次稀疏 \(\mathbb{F}_{p^{12}}\) 乘法和一次 \(\mathbb{F}_{p^{12}}\) 平方，加点步骤的开销相近。总计 Miller 循环约需 \(68\) 次 \(\mathbb{F}_{p^{12}}\) 平方与 \(69\)——\(71\) 次（稀疏）\(\mathbb{F}_{p^{12}}\) 乘法。最终幂运算还需额外约 \(90\) 次 \(\mathbb{F}_{p^{12}}\) 乘法和平方。

六、Tate 配对与 Ate 配对

6.1 Tate 配对

虽然 Weil 配对在理论上优美，但在实际计算中效率并非最优——它需要执行两次 Miller 循环和一次除法。Tate 配对(Tate pairing)提供了一种更高效的替代方案。Tate 配对只需执行一次 Miller 循环，随后进行一次”最终幂”(final exponentiation)操作，将结果映射到 \(\mathbb{F}_{p^k}^*\) 中正确的等价类代表。

具体而言，Tate 配对的计算分为两步：

1. 执行 Miller 循环，得到 \(f \in \mathbb{F}_{p^k}^*\)。
2. 计算最终幂 \(f^{(p^k - 1)/r}\)，将 \(f\) 映射到 \(r\) 次单位根群 \(\mu_r\) 中。

最终幂运算消除了 Miller 循环中选取辅助点带来的不确定性，使得结果唯一。在嵌入度 \(k\) 较大时，最终幂运算本身也需要精心优化。常用技巧包括利用 \(p^k - 1\) 的因式分解——先计算”容易部分” \(f^{(p^{k/2} - 1)} \cdot f^{(p^{k/2} + 1)}\) 等——以及 Frobenius 自同态加速。

6.2 Ate 配对与最优 Ate 配对

Ate 配对(Ate pairing)进一步缩短了 Miller 循环的长度。在标准 Tate 配对中，Miller 循环的迭代次数由群阶 \(r\) 的比特长度决定。而 Ate 配对将循环长度缩短为 \(t - 1\)（其中 \(t\) 为 Frobenius 迹），通常远小于 \(r\)。

最优 Ate 配对(optimal Ate pairing)是 Vercauteren 于 2008 年提出的进一步优化。它通过组合多个短 Miller 循环，将总长度降至理论下界 \(\lceil \log_2 r / \varphi(k) \rceil\)（其中 \(\varphi\) 为 Euler 函数）。在 BN 曲线(Barreto-Naehrig curve)上，最优 Ate 配对的循环长度约为 \(\log_2 r / 4\)，相比标准 Tate 配对提速约四倍。

6.3 效率比较

综合来看，在现代配对密码学实现中，效率从低到高依次为：Weil 配对 < Tate 配对 < Ate 配对 < 最优 Ate 配对。因此在工程实践中，几乎所有高性能密码库都选择最优 Ate 配对作为核心原语。Miller 循环占据配对计算的主体时间，而最终幂运算通过精巧的代数分解可以大幅加速，通常仅占总时间的 20%——30%。

下表从输入群、输出群、效率与主要用途等维度对四种配对进行速查对比：

6.4 配对运算的实际性能基准

理论上的效率排序需要通过实际基准测试来量化。以下数据基于 BLS12-381 曲线在 x86-64 平台（Intel Skylake 微架构，单核，无超线程）上的测量结果，反映了当前主流密码库的配对计算性能：

从上表可以看出，优化的 C/汇编实现与 Python 参考实现之间存在约 \(600\) 倍的性能差距，这凸显了底层域算术优化（如 Montgomery 乘法、向量化指令、汇编级流水线调度）的重要性。

耗时分解。 在高性能库中，配对计算的耗时大致按如下比例分布：Miller 循环占总时间的约 \(60\%\)，最终幂运算占约 \(40\%\)。这一比例与第 6.3 节中提到的 \(20\%\)——\(30\%\) 存在差异，原因在于后者的估计基于较早期的实现；随着 Miller 循环中稀疏乘法等优化的深入应用，循环部分的绝对耗时持续下降，使得最终幂运算在总占比中相对上升。

与标量乘法的对比。 同一平台上，\(\mathbb{G}_1\) 上的标量乘法（即计算 \([s]P\)）在 blst 中约需 \(50\)——\(60\) 微秒，\(\mathbb{G}_2\) 上约需 \(120\)——\(150\) 微秒。因此，一次配对运算的开销大约相当于 \(10\)——\(15\) 次 \(\mathbb{G}_1\) 标量乘法，或 \(5\)——\(7\) 次 \(\mathbb{G}_2\) 标量乘法。这一比例意味着在协议设计中应尽量减少配对调用次数，将尽可能多的计算放在群运算层面完成。

聚合验证的效率分析。 尽管单次配对运算代价较高，BLS 签名的聚合验证机制使得批量场景下的摊销成本极低。对 \(n\) 个签名者分别签署不同消息的聚合签名，验证需要 \(n + 1\) 次配对计算（\(n\) 次用于将各公钥与对应消息哈希配对，\(1\) 次用于聚合签名与生成元的配对）。相比逐一独立验证 \(n\) 个签名（每个需 \(2\) 次配对，共 \(2n\) 次），聚合验证节省了近一半的配对计算。更重要的是，当所有签名者签署相同消息时（如区块链共识场景），验证可进一步简化为仅 \(2\) 次配对——先将所有公钥在 \(\mathbb{G}_1\) 中做点加法聚合，再验证 \(e(P_1, \sigma_{agg}) = e(pk_{agg}, H(m))\)。在 Ethereum 信标链中，单个 slot 可能涉及数千个验证者的签名聚合，此时 \(2\) 次配对加上数千次 \(\mathbb{G}_1\) 点加法（每次仅需微秒级别）的方案，比数千次独立配对验证快了三个数量级。

个人思考。 回顾密码学的发展史，配对的引入堪称一次「维度跃迁」。在配对出现之前，公钥密码学的工具箱本质上是「单向」的——我们能在群上做标量乘法，但无法在两个独立的群元素之间建立乘法关系。配对提供了一座从 \(\mathbb{G}_1 \times \mathbb{G}_2\) 到 \(\mathbb{G}_T\) 的「跨群桥梁」，正是这座桥梁使得 IBE、BLS 签名聚合、ABE 乃至 zk-SNARKs 成为可能——这些构造在纯离散对数框架下根本无法表达，因为它们在安全性证明中本质性地依赖于「在指数位置做乘法」的能力。我个人认为，配对之于密码学的意义，类似于复数之于代数——它并非简单地增加了一个工具，而是打开了一个全新的构造空间，让此前「不可能」的问题突然变得「显然可行」。

七、配对友好曲线

7.1 嵌入度与曲线选择

并非所有椭圆曲线都适合用于配对密码学。对于随机选取的素数域椭圆曲线，其嵌入度 \(k\)（即满足 \(r \mid (p^k - 1)\) 的最小 \(k\)）通常与 \(r\) 同阶——在 \(r\) 约 \(256\) 位时，\(k\) 接近 \(2^{256}\)，使得 \(\mathbb{F}_{p^k}\) 上的运算完全不可行。因此需要专门构造嵌入度适中的曲线，这类曲线称为配对友好曲线(pairing-friendly curve)。

理想的嵌入度需要在安全性和效率之间取得平衡。\(k\) 越小，\(\mathbb{F}_{p^k}\) 上的计算越快，但也意味着目标群 \(\mathbb{G}_T\) 的安全性越低（因为 \(\mathbb{F}_{p^k}^*\) 上的离散对数问题可以用数域筛法等亚指数算法攻击）。当前推荐的参数中，128 位安全级别通常要求 \(k \cdot \log_2 p \geq 3072\)。

7.2 BN 曲线

Barreto-Naehrig 曲线(BN curve)是一族嵌入度 \(k = 12\) 的配对友好曲线，由一个整数参数 \(u\) 参数化：

• \(p(u) = 36u^4 + 36u^3 + 24u^2 + 6u + 1\)
• \(r(u) = 36u^4 + 36u^3 + 18u^2 + 6u + 1\)
• \(t(u) = 6u^2 + 1\)

BN 曲线的 \(\rho\) 值（定义为 \(\log p / \log r\)）接近 \(1\)，意味着带宽效率极高。这类曲线长期以来是 128 位安全级别配对密码学的首选。然而，随着 Kim-Barbulescu 攻击(2016)对扩域离散对数问题的改进，BN 曲线的安全强度有所下降，目前 \(u\) 约 \(110\) 位的 BN 曲线仅提供约 \(100\)——\(110\) 位安全性。

7.3 BLS 曲线

Barreto-Lynn-Scott 曲线(BLS curve)提供了另一种选择。BLS12-381 曲线（嵌入度 \(k = 12\)，域素数约 \(381\) 位）已成为当前最广泛部署的配对友好曲线，被 Zcash、Ethereum 2.0、Filecoin 等项目采用。BLS12-381 的参数经过精心选取，在 Kim-Barbulescu 攻击模型下仍提供约 \(128\) 位安全性。

此外还有 BLS24 和 BLS48 等更高嵌入度的族，适用于更高安全级别（如 192 位或 256 位）的场景。曲线选择还需考虑扭曲(twist)的可用性——对于 \(k = 12\) 的曲线，六次扭曲(sextic twist)可以将 \(\mathbb{G}_2\) 中的点表示在更小的域上，显著节省存储和计算开销。

7.4 曲线选择准则

选择配对友好曲线时需综合考量以下因素：目标安全级别与对应的 \(k \cdot \log_2 p\) 下界；\(\rho\) 值是否接近 \(1\)（关系到公钥和签名的紧凑性）；是否存在高阶扭曲以优化 \(\mathbb{G}_2\) 表示；曲线判别式(discriminant)的大小（影响复乘法构造的难度）；以及是否有成熟的软件实现和安全分析。在工程实践中，除非有特殊需求，建议直接使用 BLS12-381 等经过社区充分审查的标准曲线。

7.5 Kim-Barbulescu 攻击的影响与参数迁移

2016 年，Kim 和 Barbulescu 提出了一种针对扩域离散对数问题的新型攻击，其核心思想是塔数域筛法(Tower Number Field Sieve, TNFS)的一个特殊变体。传统的数域筛法(NFS)在攻击 \(\mathbb{F}_{p^k}^*\) 上的 DLP 时，复杂度取决于 \(p^k\) 的总比特长度。然而 TNFS 利用了 \(p^k\) 的「塔结构」——当 \(p\) 本身具有特殊的多项式形式时（例如 BN 曲线中 \(p(u) = 36u^4 + 36u^3 + 24u^2 + 6u + 1\)），攻击者可以构造更高效的数域分裂，使得筛法的有效比特长度显著低于 \(k \cdot \log_2 p\)。

量化影响。 在 Kim-Barbulescu 攻击之前，128 位安全级别下 BN 曲线的标准参数选取 \(u \approx 2^{64}\)，对应 \(p\) 约 \(256\) 位，\(k \cdot \log_2 p \approx 3072\) 位。在传统 NFS 分析下，这一参数被认为提供 \(128\) 位安全性。然而 TNFS 的改进使得 BN256（\(p\) 为 \(256\) 位）的 \(\mathbb{G}_T\) 安全性降至约 \(100\)——\(110\) 位，不再满足 \(128\) 位的安全要求。这一发现对整个配对密码学社区产生了深远影响，因为 BN256 曾是以太坊预编译合约和众多零知识证明系统的默认曲线。

从 BN254 到 BLS12-381 的迁移。 面对 TNFS 攻击，社区迅速开展了参数迁移工作。BLS 曲线受影响较小的根本原因在于：BLS12-381 的域素数 \(p\) 约 \(381\) 位，\(k \cdot \log_2 p \approx 4572\) 位，提供了充足的安全余量；更重要的是，BLS 曲线的 \(p\) 虽然也由参数 \(u\) 生成，但其多项式结构（BLS12 的 \(p(u) = (u-1)^2(u^4-u^2+1)/3 + u\)）相比 BN 曲线的多项式具有更低的可利用度，在 TNFS 框架下的攻击增益更小。

参数搜索的核心准则。 在选取新的配对友好曲线参数时，需要满足以下条件：

1. \(\rho\) 值接近 \(1\)：\(\rho = \log p / \log r\) 衡量带宽效率，BLS12 的 \(\rho \approx 1.0\)，BLS24 的 \(\rho \approx 1.0\)，均接近理论最优。
2. 种子 \(u\) 的低 Hamming 权重：Miller 循环的加点步骤仅在 \(u\) 的非零比特位触发，因此 \(u\) 的二进制表示中非零位越少，Miller 循环越快。BLS12-381 的 \(u\) 仅有 \(4\) 个非零位，这使其 Miller 循环极为高效。
3. \(\mathbb{G}_1\) 和 \(\mathbb{G}_T\) 的安全级别同时达标：\(r\) 至少 \(256\) 位以确保 \(\mathbb{G}_1\) 上 ECDLP 的 \(128\) 位安全性；\(k \cdot \log_2 p\) 在 TNFS 模型下足以保证 \(\mathbb{G}_T\) 上 DLP 的 \(128\) 位安全性。
4. 高阶扭曲的存在性：\(k = 12\) 的曲线应具备六次扭曲以压缩 \(\mathbb{G}_2\) 元素的表示。

当前推荐参数。 基于上述分析，当前密码学社区的主流推荐如下：\(128\) 位安全级别首选 BLS12-381；\(192\) 位安全级别可选用 BLS24-509（嵌入度 \(k = 24\)，\(p\) 约 \(509\) 位）；\(256\) 位安全级别则考虑 BLS48-581 等更高嵌入度的族。需要强调的是，随着 TNFS 及其变体的持续研究，安全参数的估计可能在未来进一步修正，因此在系统设计中应预留参数升级的灵活性（如 Ethereum 的 EIP-2537 提案即以 BLS12-381 为标准，同时保留扩展空间）。

从工程实践来看，配对友好曲线的参数选择可能是整个密码学中最微妙的平衡行为。普通椭圆曲线的参数选择相对直接——选一个足够大的素数阶子群，避开几种已知的弱曲线类别即可。但配对友好曲线需要在一个多维约束空间中精确导航：嵌入度 \(k\) 太小，\(\mathbb{G}_T\) 上的 DLP 会被亚指数算法攻破；\(k\) 太大，配对计算的代价会变得不可接受；\(\rho\) 值偏离 1 太远，公钥会膨胀；判别式太大，曲线构造本身就变得困难。更令人不安的是，Kim-Barbulescu 等人对扩域 DLP 的改进攻击表明，某些参数化形式的素数（恰恰是 BN 曲线等配对友好族天然产生的那种素数）比随机素数更容易被攻击。这意味着让曲线「友好」的那些代数结构，同时也在削弱它的安全性——太多的结构既是祝福也是诅咒。BLS12-381 之所以成为事实标准，不是因为它在所有维度上都最优，而是因为它在所有维度上都「足够好」，并且经受了社区数年的密码分析审查。

八、配对在密码学中的应用

8.1 基于身份的加密

基于身份的加密(Identity-Based Encryption, IBE)由 Shamir 于 1984 年提出概念，但直到 2001 年 Boneh-Franklin 方案的出现才得到第一个实用构造。在 IBE 中，用户的公钥即为其身份字符串（如电子邮件地址），而私钥由可信的密钥生成中心(Key Generation Center, KGC)基于主密钥计算。

Boneh-Franklin IBE 的核心构造利用了双线性映射。设 \(e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T\)，主密钥为 \(s \in \mathbb{Z}_r^*\)，主公钥为 \(P_{pub} = [s]P\)（\(P\) 为 \(\mathbb{G}_1\) 的生成元），哈希函数 \(H: \{0,1\}^* \to \mathbb{G}_2\)。用户身份 \(\mathrm{ID}\) 的公钥为 \(Q_{\mathrm{ID}} = H(\mathrm{ID})\)，私钥为 \(d_{\mathrm{ID}} = [s]Q_{\mathrm{ID}}\)。加密时使用 \(e(P_{pub}, Q_{\mathrm{ID}})^t\)（\(t\) 为随机数）作为对称密钥的掩码，解密时利用 \(e([t]P, d_{\mathrm{ID}}) = e(P, Q_{\mathrm{ID}})^{st} = e(P_{pub}, Q_{\mathrm{ID}})^t\) 恢复。双线性性质正是等式成立的关键。

8.2 BLS 签名

Boneh-Lynn-Shacham 签名方案(BLS signature)是配对密码学最成功的应用之一，以其签名极短和天然支持聚合而著称。方案概要如下：

• 密钥生成：私钥 \(sk \in \mathbb{Z}_r^*\)，公钥 \(pk = [sk]P_1\)（\(P_1\) 为 \(\mathbb{G}_1\) 的生成元）。
• 签名：对消息 \(m\)，计算 \(H(m) \in \mathbb{G}_2\)，签名 \(\sigma = [sk]H(m)\)。
• 验证：检验 \(e(P_1, \sigma) = e(pk, H(m))\) 是否成立。

BLS 签名的一个突出优势是签名聚合(signature aggregation)。给定 \(n\) 个不同签名者对不同消息的签名 \(\sigma_1, \ldots, \sigma_n\)，可以将其聚合为一个签名 \(\sigma_{agg} = \sigma_1 + \cdots + \sigma_n\)。验证只需 \(n + 1\) 次配对计算（而非 \(n\) 次独立验证）。这一特性使 BLS 签名在区块链共识（如 Ethereum 的信标链使用数万个验证者的聚合签名）中具有巨大优势。

8.3 属性基加密

属性基加密(Attribute-Based Encryption, ABE)将 IBE 的思想进一步推广。在 ABE 中，密文与一组属性关联，只有持有满足特定访问策略的属性集合的用户才能解密。配对提供了实现这种细粒度访问控制所需的代数结构。例如，在密钥策略 ABE(KP-ABE)中，每个用户的私钥编码一棵访问树，密文携带属性集合，解密过程通过配对运算在访问树的叶节点处计算配对值，再通过树结构聚合重构密钥。

8.4 零知识证明

零知识简洁非交互式知识论证(zk-SNARK)是近年来最受关注的密码学原语之一，其多种经典构造（如 Groth16、PLONK 的 KZG 承诺版本）在核心步骤中使用配对。在 Groth16 方案中，证明由三个群元素组成，验证仅需三次配对计算和若干群运算，无论被证明的计算多么复杂。配对在此充当了”同态校验器”的角色——验证者通过配对等式检查证明者提供的群元素之间是否满足特定的多项式关系，而无需了解底层的秘密见证(witness)。

KZG 多项式承诺(Kate-Zaverucha-Goldberg commitment)是另一个依赖配对的重要构建模块。承诺者对多项式 \(f(x)\) 的承诺为一个群元素 \(C = [f(\tau)]G\)（其中 \(\tau\) 是可信设置中的秘密），验证某点处的求值 \(f(z) = y\) 时，利用配对检查 \(e(C - [y]G, H) = e(\pi, [(\tau - z)]H)\)，其中 \(\pi\) 是商多项式的承诺。这里配对的双线性性恰好实现了”在指数位置做除法”的效果。

九、MOV 攻击与安全参数选择

9.1 MOV 攻击原理

MOV 攻击(Menezes-Okamoto-Vanstone attack)是配对密码学安全分析中最重要的概念之一。该攻击利用 Weil 或 Tate 配对，将椭圆曲线上的离散对数问题(ECDLP)归约为有限域扩张 \(\mathbb{F}_{p^k}\) 上的离散对数问题(DLP)。

具体而言，给定 ECDLP 实例 \((P, Q = [s]P)\)，攻击者选取适当的 \(R \in E[r]\)，计算 \(\alpha = e(P, R)\) 和 \(\beta = e(Q, R) = e([s]P, R) = e(P, R)^s = \alpha^s\)。于是问题转化为在 \(\mathbb{F}_{p^k}^*\) 中求解 \(\beta = \alpha^s\) 的离散对数。

如果嵌入度 \(k\) 很小，\(\mathbb{F}_{p^k}\) 上的 DLP 可以用指标演算法(index calculus)等亚指数时间算法高效求解，从而间接破解 ECDLP。这正是为什么在选择用于标准 ECDLP 的曲线时要避免小嵌入度，而在设计配对友好曲线时则需要精确控制嵌入度的原因。

9.2 安全参数选择

在配对密码学中，安全参数的选择需要同时考虑三个群的安全性：

• \(\mathbb{G}_1\) 的安全性：取决于 ECDLP 的难度，当前 \(128\) 位安全级别要求群阶 \(r\) 至少 \(256\) 位。
• \(\mathbb{G}_2\) 的安全性：通常与 \(\mathbb{G}_1\) 相当（取决于曲线和扭曲的选取）。
• \(\mathbb{G}_T\) 的安全性：取决于 \(\mathbb{F}_{p^k}^*\) 上 DLP 的难度。当前 \(128\) 位安全级别要求 \(k \cdot \log_2 p \geq 3072\)（基于数域筛法的复杂度估计）。

以 BLS12-381 为例：\(r\) 约 \(255\) 位，\(p\) 约 \(381\) 位，\(k = 12\)，故 \(k \cdot \log_2 p \approx 4572\) 位，远超 \(3072\) 位的下界，在考虑 Kim-Barbulescu 等改进攻击后仍保持约 \(128\) 位安全性。

9.3 前沿威胁

值得注意的是，近年来对扩域离散对数问题的算法研究持续推进。Tower NFS(塔数域筛法)和 Special TNFS 等变体算法对特定形式的素数（如稀疏素数、Barreto-Naehrig 曲线的参数化素数）可能提供比一般数域筛法更强的攻击能力。因此，安全参数的选取应基于最新的密码分析结果，并预留适当的安全余量。

此外，量子计算机对配对密码学构成根本性威胁。Shor 算法可以在多项式时间内求解离散对数问题，包括椭圆曲线上的 ECDLP 和有限域上的 DLP。因此，所有基于配对的方案在后量子时代都将不再安全。后量子密码学(post-quantum cryptography)中的格基方案(lattice-based schemes)正在被研究作为替代，但目前尚无高效的后量子配对等价物。这意味着在可预见的未来，配对密码学仍将是实现 IBE、BLS 签名和 zk-SNARKs 等高级功能的唯一实用途径，但其长期安全性取决于量子计算的发展进程。

密码学百科系列 · 第 34 篇

← 上一篇：有限域算术 | 系列目录 | 下一篇：椭圆曲线代数 →