作者：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 \rightarrow Y$，满射意味着 Y 中的每一个值，在 X 中都至少有一个值与之对应；单射意味着 X 中的两个值在 Y 中的对应值必定不同；同时是满射和单射的，则是双射的。）

同源

设 $E_1$ 和 $E_2$ 是一个有限域 $\mathbb{F}_q$ 上的两条椭圆曲线。在这里， $q$ 是某个质数的幂。还要指出，$E_1$ 和 $E_2$ 都在点加法下形成了群；并且，因为 $\mathbb{F}_q$ 是有限的，这两个群自然也是有限的。

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

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

$$\phi: E_1 \longrightarrow E_2$$

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

  • $\phi$ 作用在椭圆曲线的点上；每个点都有一个 $x$ 坐标值和 $y$ 坐标值。所以我们可以写作：$\phi = (\phi_1, \phi_2)$，它以下面这种形式，作用在位于 $E_1$ 上的点 $P = (x, y)$ 上：

    $$\phi(P) = \phi((x, y)) = (\phi_1(x), \phi_2(y))$$

  • 我们希望这个映射是 有理的（rational）。意思是，如果 $\phi = (\phi_1, \phi_2)$ ，那么 $\phi_1$ 和 $\phi_2$ 都只是其分母和分子都是多项式的代数分子式。比如：

    $$\frac{x^3+4x+1}{2x+5}$$

  • 我们希望 $\phi$ 具有这种属性，是因为在数学上有个众所周知的事实：一个有理的映射要么是满射的，要么是常数的。虽然这看起来不重要，然而，一旦我们要定义一些属性并开始了解同源，这就会变得非常有用。

  • 因为 $E_1$ 和 $E_2$ 形成了群，理想情况下，我们希望 $\phi$ 是一个群同态（group homomorphism）。直觉上，这意味着 $\phi$ 将保持群的结构。在数学上，如果 $+_i$ 是 $E_i$ 上的群运算（即 $E_i$ 上的点加法）、而 $P, Q$ 是 $E_1$ 上的两个点，那么：

    • $$\phi(P +_1 Q) = \phi(P) +_2 \phi(Q)$$

如果果我们将 $E_i$ 的单位元（identity）标记为 $\mathcal{O}_i$ ，我们可以作出如下定义。

定义：一个有理的映射 $\phi: E_1 \longrightarrow E_2$ 被称为一个 同源，当 $\phi(\mathcal{O}_1) = \mathcal{O}_2$ 。

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

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

$$\phi(P) = (x^q, y^q)$$

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

自同态

定义：如果 $E_1 = E_2$ ，那么 $\phi$ 被称为一个 “自同态（endomorphism）”。

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

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

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

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

j-不变量

出于我们的目的，我们设 $p \equiv 3 \mod 4$ 是一个质数，并考虑这个有限域 $\mathbb{F}_{p^2}$ 。

注意：为了获得对这个域的直觉，我们可以证明 $\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$ 。除非专门声明，我们现在假设所有椭圆曲线都位于这个有限域。

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

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

$$y^2 = x^3 +ax^2 +bx + c \text{ 其中 } a, b, c \in \mathbb{F}_{p^2}$$

于是我们有

$$j(E) = 1728 \frac{4a^3}{4a^3 + 27b^2}$$

然后，在 $\mathbb{F}_{p^2}$ 上，当且仅当两条椭圆曲线有相同的 $j$ 不变量，那它们就是同构的。这正是我们要寻找的属性。

同源的属性

可分离的 vs. 不可分离的

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

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

这在维尔斯特拉斯公式中是很清楚的：给定一条椭圆曲线 $E_1: y^2 = x^3 +ax^2 +bx + c$，这些公式会形成一条椭圆曲线 $E_2 = E_1/G$ 以及显式映射 $\phi$ 。在未来的博客中我会更详细解释这些公式。

度

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

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

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

$$deg(\phi \circ \psi) = \deg(\phi) \times \deg(\psi)$$

译者注：如果有两个同源 $\phi:E_1 \rightarrow E_2$ 和 $\psi:E_2 \rightarrow E_3$ ，那么两者的结合会产生第三个同源：$\phi \circ \psi:E_1 \rightarrow E_3$ 。

对手同源

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

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

$$\phi: E_1 \longrightarrow E_2$$

是一个度为 $d$ 的同源，那么 $\hat{\phi}$ 也是一个度为 $d$ 的同源，两者的结合会产生：

$$\phi \circ \hat{\phi} = [d],$$

其中 $[d]: E_1 \longrightarrow E_2$ 是乘以 $d$ 的映射。

挠点

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

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

$$ E_1[d] = d^2$$

并且：

$$E_1[d] \cong (\mathbb{Z}/d\mathbb{Z}) \times (\mathbb{Z}/d\mathbb{Z})$$

进阶阅读

[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