同源密码与 SIKE 之死：一台笔记本一小时破解 NIST 候选算法

全文分三层：

1. 通俗理解：在曲线的迷宫里走路
2. 实际用处：SIKE 的兴衰时间线，以及同源密码的现状（CSIDH、SQIsign）
3. 数学原理：同源是什么、Vélu 公式、SIDH 的结构、为什么泄露的额外信息是致命的，附 $\mathbb{F}_{13}$ 上的手算例子

第一层：通俗理解

1.1 曲线的迷宫

在椭圆曲线里，我们在一条曲线上"走 $k$ 步"。同源密码换了一个舞台：

• 每个"房间"是一整条椭圆曲线；
• 两个房间之间有门，门就是同源（一种把一条曲线上的点映射到另一条曲线上、且保持加法的映射）；
• 所有房间和门构成一个巨大的迷宫（同源图），房间数大约是 $p/12$，$p$ 有几百位。

难题：给你起点房间和终点房间，问中间的路怎么走。

1.2 像 Diffie–Hellman 一样交换密钥

SIDH（超奇异同源 Diffie–Hellman）的思路和Diffie–Hellman与离散对数很像：

1. Alice 和 Bob 从同一个公共房间出发，各自秘密地走一条路；
2. 各自公布终点房间；
3. 再从对方的终点出发，按自己的秘密路线"再走一遍"；
4. 两人到达同一个房间（严格说是同构的曲线），这就是共享密钥。

问题在第 3 步：为了让对方能"按自己的路线再走一遍"，SIDH 必须额外公开一些辅助点（自己路线把某些点送到了哪里）。正是这些辅助点，最终葬送了整个方案。

1.3 为什么曾经被看好

• 密钥最短：在所有后量子方案里，SIKE 的公钥只有约 330 字节，而 Kyber 约 800 字节，经典 McEliece 甚至要几百 KB；
• 数学优雅：延续了椭圆曲线的技术栈；
• 十年无人攻破。

第二层：实际用处

2.1 SIKE 的兴衰

攻击的核心工具是 Ernst Kani 1997 年关于"把两条椭圆曲线粘成一个阿贝尔曲面"的定理。一个代数几何的老结果，在 25 年后突然变成了一把钥匙。

2.2 教训

• 安全性的证据只是"没人攻破"：SIDH 研究了十年，看起来非常稳，但它依赖的是一个特殊的问题（多给了辅助点），而不是那个被广泛研究的"纯"同源问题。
• 混合部署救了场：Cloudflare 和 Google 的试验都是"经典 ECDH + SIKE"混合，所以即使 SIKE 被攻破，连接仍有经典算法兜底。这正是后量子密码里强调混合方案的原因。
• 密码多样性：NIST 在格方案之外仍保留基于哈希、基于编码的方案，就是为了防止"一个数学结构崩溃导致全军覆没"。

2.3 同源密码还活着吗

活着。攻击只针对 SIDH 那种"公开辅助点"的设计：

第三层：数学原理

3.1 同源是什么

椭圆曲线 $E_1$ 到 $E_2$ 的同源是一个非常数的映射 $\phi: E_1 \to E_2$，满足：

• 由有理函数给出：$\phi(x, y) = \big(r_1(x, y),\ r_2(x, y)\big)$；
• 把无穷远点送到无穷远点。

可以证明这样的映射自动是群同态：$\phi(P + Q) = \phi(P) + \phi(Q)$。它的核 $\ker\phi$ 是 $E_1$ 的一个有限子群。

Vélu 公式：反过来，给定 $E_1$ 的任意有限子群 $G$，都存在一个以 $G$ 为核的同源，并且有显式公式算出目标曲线 $E_2$，记作 $E_1 / G$。这和抽象代数里"给定正规子群 $N$，有商群 $G/N$ 和自然同态 $G \to G/N$"完全类似。

Tate 定理：在 $\mathbb{F}_q$ 上，$E_1$ 和 $E_2$ 之间存在同源，当且仅当它们的点数相同。

3.2 手算例子：一个 2-同源

对形如 $E: y^2 = x^3 + ax^2 + bx$ 的曲线，点 $(0, 0)$ 的阶是 $2$。以子群 $\{O, (0, 0)\}$ 为核的同源有一个简洁公式：

$$E' : y^2 = x^3 - 2a\,x^2 + (a^2 - 4b)\,x,\qquad \phi(x, y) = \left(\frac{y^2}{x^2},\ \frac{y\,(b - x^2)}{x^2}\right).$$

3.3 SIDH 的结构（简化）

• 取素数 $p = 2^{e_A} 3^{e_B} - 1$，在 $\mathbb{F}_{p^2}$ 上取一条超奇异椭圆曲线 $E_0$。
• Alice 的秘密是 $E_0$ 的一个 $2^{e_A}$ 阶循环子群 $\langle A \rangle$，她算出 $E_A = E_0 / \langle A \rangle$，相当于在 2-同源图上走了 $e_A$ 步。Bob 同理在 3-同源图上走。
• 为了让对方能在 $E_A$ 上"复刻"自己的子群，Alice 还要公开 Bob 那组基点 $P_B, Q_B$ 在她的同源 $\phi_A$ 下的像 $\phi_A(P_B), \phi_A(Q_B)$。
• 最终两人得到 $E_0 / \langle A, B \rangle$，取它的 $j$-不变量作为共享密钥。

3.4 为什么辅助点是致命的

公开 $\phi_A(P_B), \phi_A(Q_B)$，等于告诉攻击者秘密同源 $\phi_A$ 在一整个 $3^{e_B}$-挠子群上的取值。

Castryck–Decru 的关键洞察：利用 Kani 定理，可以把 $\phi_A$ 和另一个已知同源"拼"成两条曲线乘积 $E \times E'$ 上的一个高维同源。只有当猜测正确时，这个高维同源的目标才会"分裂"成两条椭圆曲线的乘积，而检查是否分裂很容易。于是攻击者可以一步一步猜出 Alice 的秘密路径，每步只需要试很少几种可能。

后来 Robert 证明，借助这些辅助点，任何同源都能在多项式时间内被重建出来。

总结