作者：Maria Corte-Real Santos

来源：https://www.mariascrs.com/2020/11/06/isogenies-for-crypto.html

原文出版于 2020 年 11 月，文中提到的 SIKE/SIDH 算法已在 2022 年发现有致命漏洞，但本文的主要目的是讲述基本概念。

2020 年 7 月 22 日，NIST（美国国家标准及技术研究所）的后量子密码学标准化工作的第三轮最终评估发布了。公钥加密和密钥握手算法的候选之一是 SIKE，这是一种基于 “同源（isogenies）” 的密钥封装机制（KEM）。想要基本理解这一方案的非专业认识可能会发现，SIKE 协议的理解门槛非常高，因为在进入密码学的部分之前，你需要先懂得大量数学背景知识。本文希望为同源以及相关的概念提供一个简短的介绍（希望做得到！）。在后续篇章中，我会将这些概念运用到密码学中，介绍 SIDH（它是作为 SIKE 基础的密钥交换协议）。

假设你已具有这些知识：

• （有限域上的）椭圆曲线
  • 它是什么
  • 它们如何靠点加法（addition of point）形成一个 “群（group）”
• 少量 群论
• 函数的基本属性，比如 “满射（surjectivity）”、“单射（injectivity）”、“双射（bijectivity）”，等等

译者注：

• 在数学上，一个 “域” 是指一个集合，在其中，加减乘除都有意义，并且其操作跟有理数上的对应操作一样。
• 一个由某种操作形成的 “群” 则意味着，在该集合内，该操作满足结合律、任意两个元素在该操作下生成的元素都属于该群、每个元素都有逆元素，该集合有个单位元（ideneity element） —— 群内任何其它元素与该单位元作这种操作都会得出自身。
  • 对一个椭圆曲线点加法群来说，它的单位元是一个无穷远点；任何点与它相加都会得到自身。
• 设有映射 f:X→Y，满射意味着 Y 中的每一个值，在 X 中都至少有一个值与之对应；单射意味着 X 中的两个值在 Y 中的对应值必定不同；同时是满射和单射的，则是双射的。）

同源

设 E1 和 E2 是一个有限域 Fq 上的两条椭圆曲线。在这里， q 是某个质数的幂。还要指出，E1 和 E2 都在点加法下形成了群；并且，因为 Fq 是有限的，这两个群自然也是有限的。

注：通常，在数学论文中，我们用 Ei(K) 来表明我们在讨论凭 K 取值的点（k-valued points）。我这里不用这个记号，因为我们只考虑有限域上的椭圆曲线。

假设我们要考虑这两条椭圆曲线的一种映射：

ϕ:E1⟶E2

但是，且慢，说有一个从某条椭圆曲线到另一条椭圆曲线的映射，是什么意思呢？我们可能还好奇，这个映射要满足什么属性，我们才会说它是 “好的”（在几何和代数的双重意义上）？

• ϕ 作用在椭圆曲线的点上；每个点都有一个 x 坐标值和 y 坐标值。所以我们可以写作：ϕ=(ϕ1,ϕ2)，它以下面这种形式，作用在位于 E1 上的点 P=(x,y) 上：ϕ(P)=ϕ((x,y))=(ϕ1(x),ϕ2(y))
• 我们希望这个映射是 有理的（rational）。意思是，如果 ϕ=(ϕ1,ϕ2) ，那么 ϕ1 和 ϕ2 都只是其分母和分子都是多项式的代数分子式。比如：x3+4x+12x+5
• 我们希望 ϕ 具有这种属性，是因为在数学上有个众所周知的事实：一个有理的映射要么是满射的，要么是常数的。虽然这看起来不重要，然而，一旦我们要定义一些属性并开始了解同源，这就会变得非常有用。
• 因为 E1 和 E2 形成了群，理想情况下，我们希望 ϕ 是一个群同态（group homomorphism）。直觉上，这意味着 ϕ 将保持群的结构。在数学上，如果 +i 是 Ei 上的群运算（即 Ei 上的点加法）、而 P,Q 是 E1 上的两个点，那么：
  • ϕ(P+1Q)=ϕ(P)+2ϕ(Q)

如果果我们将 Ei 的单位元（identity）标记为 Oi ，我们可以作出如下定义。

定义：一个有理的映射 ϕ:E1⟶E2 被称为一个 同源，当 ϕ(O1)=O2 。

事实证明，如果一个映射是 有理的，并且 将单位元映射成自身，那么这个同源天然是一个群同态，这正是我们想要的一种属性。此外，同源要么是单位元映射（一个常数映射，将单位元映射成自身），要么必然是满射的。

在有限域 Fq 上，有一个非常著名的同源叫做 “弗罗贝尼乌斯映射（Frobenius Map）”。设 P=(x,y) ，这个映射是这样的：

ϕ(P)=(xq,yq)

很容易就能检查它不是一个同源，所以我鼓励你自己试一试，确保你理解了这个定义！

自同态

定义：如果 E1=E2 ，那么 ϕ 被称为一个 “自同态（endomorphism）”。

定义：一个自同态 ϕ 如果是双射的，那么它是一个 “同构（isomorphism）”。请记住，ϕ 要么是常数（单位元），要么是满射的，所以我们只需要检查 ϕ 是不是单射的。

这些自同态非常酷，因为一条椭圆曲线 E 的自同态的集合，与一个零映射（将一切都映射为零）一起，就可以在点层面的加法和 “乘法”—— 通过组合同态们，即 (f×g)=f(g(x)) —— 的操作下，形成一个 “环（ring）”。直觉上，变成一个环意味着加法和乘法都有用，而且彼此可以互动。更准确地说，成为一个环意味着：

• 它是由加法生成的一个群
• 在它之上的乘法满足结合律，并且乘法有一个单位元（群内任何其它元素与之相乘将得出同一元素）
• 乘法对加法满足分配律

我们将这个环写作 End(E) 。

j-不变量

出于我们的目的，我们设 p≡3mod4 是一个质数，并考虑这个有限域 Fp2 。

注意：为了获得对这个域的直觉，我们可以证明 $\mathbb{F}{p^2}等于将i附加到\mathbb{F}{p}，其中i^2 + 1 = 0（i为虚数），写作\mathbb{F}{p}(i)。这意思是，我们可以看\mathbb{F}{p^2}中的元素看成这样的形式u + iv，其中u, v \in \mathbb{F}_p$ 。除非专门声明，我们现在假设所有椭圆曲线都位于这个有限域。

现在，我们不是要分别地考察单条的椭圆曲线，而是，当且仅当 E1 和 E2 是同构的，我们就把他们当成 “同一条” 椭圆曲线。更准确地说，我们考虑的是椭圆曲线的等价类（equivalence class），其中，当且仅当 E1 和 E2 是同构的，它们就是等价的。为此，我们需要某种不变量，j当且仅当 E1 和 E2 是同构的，该不变量在两者上就是一样的，从而我们可以标记每一个等价类。所以，我们引入 j-不变量。

将椭圆曲线 E 写成魏尔斯特拉斯形式（Weierstrass Form），即：

y2=x3+ax2+bx+c 其中 a,b,c∈Fp2

于是我们有

j(E)=17284a34a3+27b2

然后，在 Fp2 上，当且仅当两条椭圆曲线有相同的 j 不变量，那它们就是同构的。这正是我们要寻找的属性。

同源的属性

可分离的 vs. 不可分离的

同源密码学的论文中常常出现一个词：“可分离的（separable）”。一般来说，一个同源要么是 可分离的，要么是 不可分离的 。它们的定义不是很重要，但为了数学推导顺利进行，我们希望同源是可分离的。

关于可分离的同源，最重要的事情就是：它们是有限子群之间的一一对应关系。什么意思呢 ？基本上，一条椭圆曲线 E1 上的点的每一个子群 G ，都可以产生一个唯一的同源 ϕ:E1⟶E2，该同源的 “核（kernel）” 为 G （回顾一下，ϕ 的核是一个 E 上的点的集合，它会被映射成单位元 O1），反之亦然。如果是这种情况，余域（输出曲线）有时会被写成 E1/G 而不是 E2 。

这在维尔斯特拉斯公式中是很清楚的：给定一条椭圆曲线 E1:y2=x3+ax2+bx+c，这些公式会形成一条椭圆曲线 E2=E1/G 以及显式映射 ϕ 。在未来的博客中我会更详细解释这些公式。

度

定义：一个非零的可分离同源的 度（degree） 是其核中的元素的数量。等价地（虽然对我们的目的不太重要），它也是这个同源作为一个有理的映射的度（需要你想要一个精确的定义，请看 Silverman 的 《椭圆曲线代数学》的第 21 页）。

我们可以将同构视作特殊的同源，其核仅仅有一个元素 O ，也就是，一个度为 1 的同源。

度与同源的结合（composition）有重要的关系：

deg(ϕ∘ψ)=deg(ϕ)×deg(ψ)

译者注：如果有两个同源 ϕ:E1→E2 和 ψ:E2→E3 ，那么两者的结合会产生第三个同源：ϕ∘ψ:E1→E3 。

对手同源

我们知道同构映射会有一个逆映射，两者相结合会得到一个恒等映射（ideneity map）。但同源呢？它有类似的东西吗？

一般来说，同源没有逆，基督城，每一个同源 ϕ 都有唯一的一个 对手 同源，我们标记为 ϕ^ 。两者的结合不会产生恒等映射，而是：如果

ϕ:E1⟶E2

是一个度为 d 的同源，那么 ϕ^ 也是一个度为 d 的同源，两者的结合会产生：

ϕ∘ϕ^=[d],

其中 [d]:E1⟶E2 是乘以 d 的映射。

挠点

考虑乘以 d 的映射。那么 E1 上的所有满足 [d]P=O1 的点 P ，所构成的群可以写成 E1[d] ，叫做 “d-挠点（d-torsion points）”。本质上， d 挠点只是 d 阶元素，只不过在大多数论文中，它们都被称为 d 挠点，所以我觉得我应该介绍一下这个术语。

一个值得记住的有用事实是，如果 d 与 q 互质（回忆一下，q 是我们正在研究的有限域的大小），那么：

E1[d]=d2

并且：

E1[d]≅(Z/dZ)×(Z/dZ)

进阶阅读

[1] Supersingular Isogeny Key Exchange for Beginners, by Craig Costello

[2] Rational Points on Elliptic Curves, by Joseph H. Silverman and John Tate

[3] Arithmetic of Elliptic Curves, by Joseph H. Silverman

Maria Corte-Real Santos2026-05-11
https://www.btcstudy.org/2026/05/11/isogenies-for-cryptography/