配对密码学：双线性对的数学原理、构造与应用
概述
配对密码学（Pairing-Based Cryptography）的核心工具是双线性对（Bilinear Pairing）：一种定义在椭圆曲线群之间的特殊映射，能够将两个群中的元素"相乘"到第三个群中，同时保持代数结构。
这一概念的密码学应用始于 2001 年。Dan Boneh 和 Matthew Franklin 提出了首个可证明安全的身份基加密（Identity-Based Encryption, IBE）方案，解决了传统 PKI 中证书管理的根本性难题——在 IBE 中，用户的公钥就是其身份标识（如邮箱地址），无需数字证书。同年，Boneh、Lynn 和 Shacham 提出了 BLS 短签名方案，将签名长度压缩到单个群元素。
此后，配对密码学催生了一系列突破：
- 三方一轮密钥协商（Joux, 2000）：三方只需一轮通信即可建立共享密钥
- 基于属性的加密（ABE）：密文与访问策略绑定，细粒度访问控制
- 聚合签名：多个签名可聚合成一个固定大小的签名
- 零知识证明：zk-SNARK 的核心组件之一
- 国密 SM9：中国自主设计的标识密码算法标准
数学基础
椭圆曲线群与有限域
设 $\mathbb{F}_q$ 为 $q = p^n$ 元的有限域（$p$ 为素数），椭圆曲线 $E$ 在 $\mathbb{F}_q$ 上的 Weierstrass 方程为：
$$E : y^2 = x^3 + ax + b, \quad a, b \in \mathbb{F}_q, \quad 4a^3 + 27b^2 \neq 0$$
椭圆曲线上的点加法构成一个有限阿贝尔群 $E(\mathbb{F}_q)$。设 $r$ 为素数且 $r \mid \#E(\mathbb{F}_q)$，则 $E[r]$ 表示 $r$-挠子群（torsion subgroup），即所有阶整除 $r$ 的点构成的子群：
$$E[r] = \{ P \in E(\mathbb{F}_{q^k}) \mid [r]P = \mathcal{O} \}$$
其中 $k$ 为嵌入度（embedding degree），是满足 $r \mid q^k - 1$ 的最小正整数。嵌入度是配对密码学中最关键的参数之一。
除子理论与 Weil 对
配对密码学的数学根基来自代数几何中的除子（Divisor）理论。
除子是曲线上点的形式线性组合。对于椭圆曲线 $E$ 上的函数 $f$，其除子 $\text{div}(f)$ 记录了 $f$ 的零点与极点及其重数：
$$\text{div}(f) = \sum_{P \in E} n_P [P] - \sum_{P \in E} n_P [\mathcal{O}]$$
其中 $n_P$ 为 $f$ 在点 $P$ 处的零点/极点重数。
Weil 对的定义如下：
设 $r$ 为与 $\text{char}(\mathbb{F}_q)$ 互素的整数，$P, Q \in E[r]$。选取函数 $f_P, f_Q$ 使得：
$$\text{div}(f_P) = r[P] - r[\mathcal{O}], \quad \text{div}(f_Q) = r[Q] - r[\mathcal{O}]$$
则 Weil 对定义为：
$$e_r(P, Q) = \frac{f_P(Q + S)}{f_P(S)} \cdot \frac{f_Q(-T)}{f_Q(P - T)}$$
其中 $S, T$ 为适当的辅助点。最终取值在 $\mathbb{F}_{q^k}^*$ 的 $r$ 次单位根子群 $\mu_r$ 中。
双线性对的正式定义
一个双线性对（bilinear pairing）是一个映射 $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$，其中 $\mathbb{G}_1$、$\mathbb{G}_2$、$\mathbb{G}_T$ 均为阶为 $r$ 的循环群，满足以下性质：
1. 双线性（Bilinearity）
$$\forall P, P' \in \mathbb{G}_1, \forall Q, Q' \in \mathbb{G}_2:$$ $$e(P + P', Q) = e(P, Q) \cdot e(P', Q)$$ $$e(P, Q + Q') = e(P, Q) \cdot e(P, Q')$$
这是配对最核心的性质——将群运算转化为域乘法。
2. 非退化（Non-degeneracy）
$$\exists P \in \mathbb{G}_1, Q \in \mathbb{G}_2: e(P, Q) \neq 1$$
即配对不是平凡的常值映射。
3. 可计算（Computability）
存在高效算法计算 $e(P, Q)$。
┌─────────────────────────────────────────────────────┐
│ 双线性对的代数结构 │
│ │
│ G₁ × G₂ ──── e ────→ G_T │
│ (加法群) (加法群) (乘法群) │
│ │
│ P₁ + P₂ │ e(P₁+P₂, Q) │
│ ─────────┼─── e ──→ = e(P₁,Q) · e(P₂,Q) │
│ │ │
│ Q₁ + Q₂ │ e(P, Q₁+Q₂) │
│ ─────────┼─── e ──→ = e(P,Q₁) · e(P,Q₂) │
│ │ │
│ 核心：群运算 → 域乘法 │
└─────────────────────────────────────────────────────┘配对的类型与计算优化
Weil 对
Weil 对是最经典、最直接的配对构造。其计算基于 Miller 算法，通过迭代计算有理函数的值来得到配对结果。
Miller 算法的核心思想：
对于 $P \in E[r]$，构造函数 $f_{r,P}$ 使得 $\text{div}(f_{r,P}) = r[P] - r[\mathcal{O}]$。利用"倍点-加点"的二进制展开，通过重复的切线/弦操作累积函数值。
Miller 算法伪代码（Weil 对）:
function MillerLoop(P, r):
f ← 1
V ← P
for i from ⌊log₂(r)⌋ - 1 down to 0:
// 倍步（doubling step）
g ← 切线方程 at V（过 V 的切线）
f ← f² · g(V + V) / g(辅助点)
V ← [2]V
if rᵢ = 1:
// 加法步（addition step）
g ← 弦方程 through V, P
f ← f · g(V + P) / g(辅助点)
V ← V + P
return fWeil 对的主要缺点是计算效率较低——Miller 循环的长度约为 $\log_2(r)$，且每次迭代涉及有限域上的复杂运算。
Tate 对
Tate 对是 Weil 对的重要优化版本。关键区别在于：
- 最终幂运算（Final Exponentiation）：Tate 对的值在 $\mathbb{F}_{q^k}^*/(\mathbb{F}_{q^k}^*)^r$ 的商群中，而非直接在 $\mu_r$ 中。通过最终幂运算将结果映射到 $\mu_r$ 的唯一代表元。
- Miller 循环更短：Tate 对的 Miller 循环只需约 $\log_2(r)/2$ 步（利用 Frobenius 自同态加速）。
$$e_{\text{Tate}}(P, Q) = f_{r,P}(Q)^{(q^k - 1)/r}$$
其中 $f_{r,P}$ 的除子为 $r[P] - r[\mathcal{O}]$，最终幂运算将值投影到 $\mu_r$。
Ate 对与 R-ate 对
Ate 对进一步利用 Frobenius 自同态 $\pi_q: (x, y) \mapsto (x^q, y^q)$ 来缩短 Miller 循环。
设 $t$ 为 Frobenius 迹（满足 $\#E(\mathbb{F}_q) = q + 1 - t$），Ate 对将 Miller 循环的基从 $r$ 替换为 $t - 1$（通常 $|t - 1| \ll r$），从而大幅减少迭代次数。
R-ate 对是 Ate 对的推广，使用最优化的线性组合 $a\pi_q + b$ 来进一步缩短循环长度。国密 SM9 标准中使用的就是 R-ate 对。
配对类型计算效率对比（概念示意）:
┌──────────────┬────────────────┬──────────────────┬──────────────┐
│ 配对类型 │ Miller循环长度 │ 最终幂运算 │ 典型应用场景 │
├──────────────┼────────────────┼──────────────────┼──────────────┤
│ Weil 对 │ log₂(r) │ 不需要 │ 理论分析 │
│ Tate 对 │ log₂(r)/2 │ 需要 │ 早期方案 │
│ Ate 对 │ log₂(t)/φ(k) │ 需要 │ 高效实现 │
│ R-ate 对 │ 最优线性组合 │ 需要 │ SM9 国密 │
└──────────────┴────────────────┴──────────────────┴──────────────┘
注: φ(k) 为欧拉函数，k 为嵌入度配对友好椭圆曲线
并非所有椭圆曲线都适合构造配对。配对密码学需要满足两个关键条件：
- 存在大素数阶子群：曲线上有素数 $r$ 阶子群
- 低嵌入度：嵌入度 $k$ 不能太大（否则 $\mathbb{F}_{q^k}$ 上的运算不可行）
参数选择的安全约束
配对友好曲线的参数 $(q, r, t, k)$ 必须同时满足：
- $r \mid \#E(\mathbb{F}_q)$（存在 $r$ 阶子群）
- $r \mid q^k - 1$（嵌入度条件）
- $r \nmid q^i - 1$ 对所有 $1 \leq i < k$（最小嵌入度）
- $r$ 足够大以抵抗离散对数攻击（通常 $\geq 256$ 位）
- $\rho = \log(q)/\log(r) \approx 1$（计算效率与安全性的平衡）
主流配对友好曲线
┌─────────────────┬──────────┬──────────┬────────┬──────────┬──────────────┐
│ 曲线名称 │ 安全等级 │ 嵌入度 k │ ρ 值 │ 基域大小 │ 主要应用 │
├─────────────────┼──────────┼──────────┼────────┼──────────┼──────────────┤
│ BN254 │ ~100 bit │ 12 │ 1.0 │ 254 bit │ 早期 Zcash │
│ BLS12-381 │ ~128 bit │ 12 │ 1.0 │ 381 bit │ Ethereum 2.0 │
│ BLS12-377 │ ~128 bit │ 12 │ 1.0 │ 377 bit │ Zcash │
│ BLS24-315 │ ~128 bit │ 24 │ 1.0 │ 315 bit │ 高安全场景 │
│ KSS16 │ ~128 bit │ 16 │ 1.25 │ ~256 bit │ 研究用途 │
│ SM9 曲线 │ ~128 bit │ 12 │ 1.0 │ 256 bit │ 国密 SM9 │
└─────────────────┴──────────┴──────────┴────────┴──────────┴──────────────┘安全强度的演变：
配对友好曲线的安全强度并非静态。随着数域筛法（NFS）等攻击算法的进步，低嵌入度曲线的安全边界在持续收窄：
- BN254（2016 年广泛使用）：最初被认为提供 ~128 bit 安全，目前评估已降至 ~100 bit，不再推荐用于新系统
- BLS12-381（2019 年设计）：目前提供 ~128 bit 安全，被 Ethereum 2.0 采用
- BLS24 系列：更高嵌入度，提供更高安全余量
国密 SM9 曲线参数
GM/T 0044 系列标准定义的 SM9 标识密码算法使用特定的配对友好曲线：
- 基域：256 位素数域 $\mathbb{F}_p$，其中 p =
0xB640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D - 曲线方程：$y^2 = x^3 + b$（简化 Weierstrass 形式，$a = -3$ 的优化变体），其中 b =
0x0000000000000000000000000000000000000000000000000000000000000005 - 嵌入度：$k = 12$
- 子群阶：$r$ 为 256 位素数 =
0xB640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25 - 配对类型：R-ate 对
0x786279616C6C20736D3920637572766520706172616D657465727320722D323536（ASCII 编码 "sm9 curve parameters r-256"）生成，无可信设置后门风险。注意：上述参数为 SM9 签名算法（GM/T 0044.1）的公开参数。实际 SM9 标准还定义了加密和密钥交换的曲线参数，略有不同。详细参数请查阅 GM/T 0044.1-2016。
核心协议与应用
身份基加密（IBE）
传统 PKI 中，Alice 要加密消息给 Bob，需要先获取 Bob 的数字证书，验证其公钥。IBE 彻底简化了这个过程——Bob 的公钥就是他的身份标识（如 bob@example.com）。
Boneh-Franklin IBE 方案：
┌──────────────────────────────────────────────────────────────┐
│ IBE 系统架构 │
│ │
│ KGC（密钥生成中心） │
│ ┌─────────────────────┐ │
│ │ 主密钥 s ∈ Z_r │ │
│ │ 公钥 P_pub = [s]P │ │
│ └─────────┬───────────┘ │
│ │ 派生私钥 │
│ │ d_ID = [s]H₁(ID) │
│ ▼ │
│ ┌─────────────────────┐ │
│ │ 用户（身份 ID） │ │
│ │ 私钥 d_ID │ │
│ └─────────────────────┘ │
│ │
│ 加密（Alice → Bob，身份 "bob@example.com"）： │
│ 1. Q_ID = H₁("bob@example.com") │
│ 2. 选随机 r ∈ Z_r │
│ 3. C = ([r]P, M ⊕ H₂(e(Q_ID, P_pub)^r)) │
│ │
│ 解密（Bob）： │
│ M = C₂ ⊕ H₂(e(d_ID, C₁)) │
│ 正确性: e(d_ID, C₁) = e([s]H₁(ID), [r]P) │
│ = e(H₁(ID), P_pub)^r ← 双线性！ │
└──────────────────────────────────────────────────────────────┘为什么 IBE 有意义？
- 消除证书：不需要证书颁发、验证、吊销
- 离线公钥：任何人都可以用身份标识加密，无需在线获取公钥
- 天然过期：身份标识可包含时间戳（如
bob@example.com|2026Q2），实现密钥天然过期
BLS 短签名
Boneh-Lynn-Shacham（BLS）签名方案利用配对将签名长度压缩到单个群元素。
方案流程：
- 密钥生成：私钥 $x \in \mathbb{Z}_r$，公钥 $X = [x]P_2 \in \mathbb{G}_2$
- 签名：$\sigma = [x]H(m) \in \mathbb{G}_1$（$H$ 将消息映射到 $\mathbb{G}_1$）
- 验证：$e(\sigma, P_2) = e(H(m), X)$
- 签名极短：仅一个 $\mathbb{G}_1$ 元素（如 BLS12-381 上仅 48 字节）
- 签名聚合：$n$ 个签名可聚合成一个
- 密钥聚合：多个公钥可聚合成一个
三方一轮密钥协商（Joux 协议）
Diffie-Hellman 协议允许两方在两轮通信内建立共享密钥。Joux 在 2000 年证明，利用配对可以实现三方一轮密钥协商：
设 $P$ 为 $\mathbb{G}_1$ 的生成元，三方分别持有私钥 $a, b, c \in \mathbb{Z}_r$，公开 $[a]P, [b]P, [c]P$。
共享密钥： $$K = e([b]P, [c]P)^a = e([a]P, [c]P)^b = e([a]P, [b]P)^c = e(P, P)^{abc}$$
三方只需广播自己的公钥，即可独立计算出相同的共享密钥。
安全性基础
核心困难问题
配对密码学的安全性建立在以下计算困难问题上：
┌─────────────────────────────────────────────────────────────────┐
│ 安全性层次结构 │
│ │
│ CDH（计算 Diffie-Hellman） │
│ "已知 P, [a]P, [b]P，计算 [ab]P" │
│ │ │
│ ├── BDH（双线性 CDH） │
│ │ "已知 P, [a]P, [b]P, [c]P，计算 e(P,P)^{abc}" │
│ │ ← IBE 安全性的基础 │
│ │ │
│ ├── DBDH（判定性 BDH） │
│ │ "区分 e(P,P)^{abc} 与随机值" │
│ │ ← 加密方案安全性的基础 │
│ │ │
│ └── BDDH（双线性 DDH） │
│ "给定 P, [a]P, [b]P, [c]P, T， │
│ 判定 T = e(P,P)^{abc}" │
│ │
│ 层次关系: CDH ≥ BDH ≥ DBDH ≥ BDDH │
│ （左侧问题可解则右侧问题也可解） │
└─────────────────────────────────────────────────────────────────┘安全强度的动态评估
配对密码学的安全评估需要同时考虑两个层面的攻击：
- $\mathbb{G}_1/\mathbb{G}_2$ 上的离散对数：Pollard's rho 算法，复杂度 $O(\sqrt{r})$
- $\mathbb{G}_T$ 上的离散对数：数域筛法（NFS），复杂度为 $L_{q^k}[1/3, c]$
配对密码学与国密 SM9
SM9 的配对构造
国密 SM9 标识密码算法（GM/T 0044 系列）是中国自主设计的基于配对的标识密码标准，包含三个子算法：
| 子算法 | 标准编号 | 核心配对等式 | |
|---|---|---|---|
| 数字签名 | GM/T 0044.2 | $e(P_1, \sigma) = e(P_{\text{pub}}, H(M \ | w) \cdot g^{-1})$ |
| 密钥交换 | GM/T 0044.3 | $K = e([d_A]Q_B, P_2)^{e_0} \cdot e(P_{\text{pub}}, P_2)^{r_A r_B}$ | |
| 加密 | GM/T 0044.4 | $C_2 = M \oplus H_2(g^r)$，其中 $g = e(Q_{\text{ID}}, P_{\text{pub}})$ |
SM9 与国外方案的对比
┌──────────────────┬──────────────────┬──────────────────┬──────────────────┐
│ 特性 │ SM9 (国密) │ BF-IBE (国际) │ BLS 签名 │
├──────────────────┼──────────────────┼──────────────────┼──────────────────┤
│ 算法类型 │ 标识密码 │ 标识加密 │ 短签名 │
│ 配对类型 │ R-ate │ Weil/Tate │ Ate/最优 Ate │
│ 曲线 │ 256 bit 定制 │ BN/BLS12 系列 │ BLS12-381 │
│ 安全强度 │ ~128 bit │ ~128 bit │ ~128 bit │
│ 签名长度 │ ~128 字节 │ N/A │ ~48 字节 │
│ 密钥托管 │ 有（KGC） │ 有（KGC） │ 无 │
│ 标准化 │ GM/T 0044 │ 无正式标准 │ IETF/BLS 标准 │
└──────────────────┴──────────────────┴──────────────────┴──────────────────┘配对计算的工程实现
快速上手：用 SageMath 计算配对
以下代码演示如何在 SageMath 中计算 BN254 曲线上的 Weil 对。SageMath 是开源数学软件，内置了配对计算支持。
# SageMath 代码（在 https://sagecell.sagemath.org/ 在线运行）
# BN254 曲线参数
p = 0x2523648240000001BA344D80000000086121000000000013A70000000000013
F = GF(p)
a = F(0)
b = F(2)
E = EllipticCurve(F, [a, b])
# 曲线阶和子群阶
n = E.order() # 曲线阶
r = 0x2523648240000001BA344D8000000007FF9F80000000010A1000000000000D # 子群阶
# 找到生成元点
G = E.gens()[0]
# 配对计算示例（ Weil 对）
# 注意：SageMath 内置的 pairing() 函数需要指定扩域
F2 = GF(p^12) # 扩域 F_p^12
E2 = E.change_ring(F2)
P = E2(G)
Q = E2(G) * 12345 # 另一个点
# 计算 Weil 对
# e(P, Q) 的值在 F_p^12 的 r 次单位根中
# SageMath 中: e = P.weil_pairing(Q, r)
e = P.weil_pairing(Q, r)
print(f"Weil 对 e(P, Q) = {e}")
print(f"e(P, Q)^r = {e^r}") # 应该等于 1
# 验证双线性性质
Q2 = E2(G) * 67890
e2 = P.weil_pairing(Q + Q2, r)
e3 = P.weil_pairing(Q, r) * P.weil_pairing(Q2, r)
print(f"双线性验证: e(P, Q+Q2) == e(P,Q)*e(P,Q2) ? {e2 == e3}")注意：SageMath 需要安装后才能运行。本地安装 sage 或使用在线 SageMathCell。BN254 的安全强度已降至 ~100 bit，此处仅用于教学演示。生产环境请使用 BLS12-381 或 SM9 曲线。
Miller 算法的优化
实际工程中，配对计算的优化涉及多个层面：
- Miller 循环优化：
- 最终幂运算优化：
- 有限域运算优化：
主流实现库
| 库 | 语言 | 特点 |
|---|---|---|
| PBC (Pairing-Based Cryptography) | C | 学术原型，功能全面 |
| RELIC | C | 嵌入式优化，支持多种曲线 |
| mcl | C++ | BLS12-381 优化，Ethereum 生态 |
| blst | C/Rust | BLS12-381，Ethereum 2.0 官方 |
| GMSSL | C | 国密 SM2/SM3/SM4/SM9 全支持 |
| Apache Milagro | C/Rust | 企业级 MPC 和配对库 |
后量子时代的配对密码学
量子威胁
Shor 算法对配对密码学的威胁是双重的：
- 椭圆曲线离散对数：$\mathbb{G}_1$ 和 $\mathbb{G}_2$ 上的离散对数可被量子计算机多项式时间求解
- 有限域离散对数：$\mathbb{G}_T$ 上的离散对数同样受量子威胁
演进方向
- 基于格的配对替代方案：
- 基于同源的配对：
- 混合方案：
┌─────────────────────────────────────────────────────────────┐
│ 配对密码学的时间线 │
│ │
│ 2000 Joux: 三方一轮密钥协商 │
│ 2001 Boneh-Franklin IBE / BLS 签名 │
│ 2003 配对密码学会议 (Pairing-Based Cryptography) 首次召开 │
│ 2005 Barreto-Naehrig (BN) 曲线提出 │
│ 2008 Zcash 使用 BN 曲线 │
│ 2012 BN 曲线安全强度开始受质疑 │
│ 2016 国密 SM9 标准发布（GM/T 0044 系列） │
│ 2017 BLS12-381 曲线设计 │
│ 2019 Ethereum 2.0 采用 BLS12-381 │
│ 2022 SIDH/SIKE 被完全破解 │
│ 2024 NIST PQC 首批标准发布（2024 年 8 月，FIPS 203/204/205） │
│ 2025 行业开始 PQC 迁移规划 │
│ 2026 PQC 进入执行阶段：Cloudflare/Google 加速迁移路线 │
│ SM9 标识密码在政务、金融领域持续推广 │
│ IETF ACME dns-persist-01 强化 CAA 账户绑定 │
│ │
│ ← 配对密码学的黄金时代 (2001-2025) → │
│ ← 后量子迁移的过渡期 (2025-2035) → │
└─────────────────────────────────────────────────────────────┘总结
配对密码学是密码学中少有的从纯数学理论快速走向工程应用的典范。双线性对将椭圆曲线群上的离散对数问题"降维"到有限域上的离散对数问题，同时赋予了密码协议前所未有的表达能力——身份基加密、短签名、聚合签名、三方密钥协商等方案在传统公钥密码框架下是不可能实现的。
然而，配对密码学也面临严峻挑战：安全强度的持续收窄要求曲线参数不断升级，而量子计算的威胁则意味着整个框架需要在 2035 年前完成迁移。理解配对密码学的数学原理，不仅是掌握现有系统的基础，更是评估后量子迁移路径的关键。
参考来源
- Boneh, D., & Franklin, M. (2001). Identity-Based Encryption from the Weil Pairing. *SIAM Journal on Computing*, 32(3), 586–615.
- Boneh, D., Lynn, B., & Shacham, H. (2001). Short Signatures from the Weil Pairing. *ASIACRYPT 2001*, LNCS 2248, 514–532.
- Joux, A. (2000). A One Round Protocol for Tripartite Diffie-Hellman. *ANTS-IV*, LNCS 1838, 385–394.
- Barreto, P. S. L. M., & Naehrig, M. (2005). Pairing-Friendly Elliptic Curves of Prime Order. *SAC 2005*, LNCS 3897, 319–331.
- Galbraith, S. D., Paterson, K. G., & Smart, N. P. (2008). Pairings for Cryptographers. *Discrete Applied Mathematics*, 156(16), 3113–3121.
- IETF. (2023). Pairing-Friendly Curves. RFC draft-irtf-cfrg-pairing-friendly-curves-11.
- 国家密码管理局. GM/T 0044 系列: 标识密码算法 (2016年3月发布).
- Scott, M. (2019). A Note on the Calculation of Pairing in BN Curves. *IETF CFRG*.
- NCC Group. (2023). Estimating the Bit Security of Pairing-Friendly Curves.
相关实践
- 如需了解 SM9 标识密码算法的完整实现细节，请参阅《SM9 标识密码算法原理详解》
- 如需了解 BLS 签名在区块链中的工程应用，请参阅《Schnorr 签名算法原理：数学基础、协议设计与门限签名》
- 如需了解后量子密码学的整体图景，请参阅《后量子密码学：从量子威胁到 NIST 标准化的新密码体系》