扭曲爱德华曲线

0、摘要

1、原文摘要

本文主要介绍了扭曲爱德华兹曲线，它是对最近引入的爱德华曲线的一般化。扭曲爱德华兹曲线包含了更多有限域上的曲线，特别是蒙哥马利椭圆曲线。本文讲介绍如何通过同源覆盖更多曲线，给出了投影和倒置坐标中扭曲 Edwards 曲线的显式公式；并会说明扭曲爱德华兹曲线为爱德华曲线节省了时间。

（同源是指两条椭圆曲线之间的同态）

2、写在前面

由于最近比赛有很多扭曲爱德华曲线的题目，并且目前国内也没有什么关于扭曲爱德华曲线的详细介绍，就把这篇详细介绍扭曲曲线的文章做了一下翻译。鉴于本人水平、时间有限，译文难免有一些问题，欢迎各位师傅和我交流。原文链接：https://eprint.iacr.org/2008/013.pdf

1、引入

Edwards 在 [13] 中推广了欧拉和高斯的一个例子，给非二进制域 $k$ 上的曲线 $x^2 + y^2 = c^2(1 + x^2y^2)$ 引入了一个加法法则。 他说，如果 $k$ 是代数闭的，则 $k$ 上的每条椭圆曲线都可以表示为 $x^2 + y^2 = c^2(1 + x^2y^2)$ 的形式。然而在有限域上，只有一小部分椭圆曲线可以用这种形式表示。

Bernstein 和 Lange 在 [4] 中提出用坐标 $(X : Y : Z)$ 表示 Edwards 曲线上的 $(x, y) = (X/Z, Y /Z)$ ，并给出其加法和倍点的快速显式公式，声称这些显式公式会节省椭圆曲线加密的时间。他们把其加法法则扩展到曲线$x^2+y^2=c^2(1+dx^2y^2)$。在有限域上，这种形式的曲线相比于 $x^2 + y^2 = c^2(1 + x^2y^2)$ ，会包括更多的曲线。广义形式的所有曲线都同源于曲线 $x^2 + y^2 = 1 + dx^2y^2$。

在本文中，我们进一步推广 Edwards 加法法则以覆盖所有曲线 $ax^2+y^2=1+dx^2y^2$。在一般情况下，我们给出的加法和倍点显式公式几乎和在 $a = 1$ 这一特殊情况下一样快。我们将 Edwards 加法法则的运算速度推广到了每一条蒙哥马利曲线上；我们还发现，在 $p \equiv 1 \pmod 4$ 的素数域 $F_p$ 上，许多蒙哥马利曲线没有被 $a = 1$ 的情况覆盖。进一步，我们解释了如何使用同源性来覆盖每条曲线的奇数部分（其群阶是4的倍数）；在 $p \equiv 3 \pmod 4$ 的素数域 $Fp$ 上， $a = 1$ 涵盖所有蒙哥马利曲线，但不涵盖群阶为 4 的倍数的所有曲线。我们的总结对于许多已经存在 Edwards 形式表达的曲线也很有意义；我们解释了扭曲如何节省算术时间。关于将扭曲 Edwards 曲线成功应用于椭圆曲线分解方法的内容，请参见 [2]。

在第 2 节中，我们会回顾 Edwards 曲线，介绍扭曲 Edwards 曲线，并说明每条扭曲 Edwards 曲线是 Edwards 曲线的扭曲。在第 3 节中，我们会说明每条蒙哥马利曲线都可以表示为扭曲爱德华兹曲线，反之亦然。在第 4 节中，我们会介绍椭圆曲线（在各种素数域上）可以表示为 Edwards 曲线、扭曲 Edwards 曲线、“4 倍奇数”扭曲 Edwards 曲线等的百分比。在第 5 节中，我们使用同源覆盖更多曲线：具体的，它表明每条群阶为 4 的倍数且没有阶为 4 的点的曲线与扭曲 Edwards 曲线是 2 - 同源的。在第 6 节中，我们把 Edwards 加法定律、[4] 中的显式公式和 [5] 中的“逆”公式推广到扭曲 Edwards 曲线。在第 7 节中，我们分析了这种推广对密码应用的好处。

2、爱德华曲线和扭曲爱德华曲线

本节，我们将在 [4] 的推广下简要回顾爱德华曲线及其加法定律。然后，我们会引入扭曲爱德华曲线并讨论它和爱德华曲线之间的关系。

Review of Edwards Curves.

在整篇文章中，我们讨论的椭圆曲线都定义在非二进制域 $k$ 上。

$k$ 上的爱德华曲线 E 为：$x^2+y^2=1+dx^2y^2,d\in{k}$。在曲线 E 上的两点$(x_1,y_1),(x_2,y_2)$的加法运算定义为：

点 $(0, 1)$ 是加法法则的中性元素。点 $(0, -1)$ 的阶数为 2。点 $(1, 0)$ 和 $(-1, 0)$ 的阶数为 4。点 $(x_1, y_1)$ 在 E 上的逆元是 $(-x_1, y_1)$。加法法则是强统一的：即，它也可以用于倍点。加法法则也适用于中性元素和逆元。如果 $d$ 是 $k$ 中的非方数，则如 [4，定理 3.3] 中所证明的那样，这个加法法则是完备的：它适用于所有的输入。

Twisted Edwards Curves.

4 阶点的存在限制了 $k$ 上 Edwards 形式的椭圆曲线的数量。通过引入扭曲 Edwards 曲线，我们将这组爱德华曲线放到一组形状相似的椭圆曲线中。

定义 2.1（扭曲爱德华曲线） 选择一个域 $k$ （$k\ne2$），选择两个不同的非零常数 $a,d\in k$，扭曲爱德华曲线定义为

当 $a=1$ 时，此曲线为爱德华曲线。

在第三节中，我们将证明每条扭曲爱德华曲线等价于蒙哥马利曲线，反之亦然。椭圆曲线具有 $j$-不变量 $16(a^2+14ad+d^2)^3/ad(a-d)^4$。

Twisted Edwards Curves as Twists of Edwards Curves.

扭曲爱德华曲线$E_{E,a,d}:ax^2+y^2=1+dx^2y^2$是 Edwards 曲线$E_{E,1,d/a}:\bar x^2+\bar y^2=1+(d/a)\bar x^2\bar y^2$的二次扭曲。映射$(\bar x,\bar y)\mapsto(x,y)=(\bar x\sqrt a,\bar y)$ 是从 $E_{E,1,d/a}$ 到 $E_{E,a,d}$ 在 $k(\sqrt a)$ 的同构。如果 $a$ 是 $k$ 中的二次幂，那么 $E_{E,1,d/a}$ 和 $E_{E,a,d}$ 在 $k$ 的同构。

更一般的，对于任何满足$\bar d/\bar a=d/a$ 的 $\bar a,\bar d$， $E_{E,a,d}$ 是 $E_{E,\bar a,\bar d}$ 的二次扭曲。相反，扭曲 Edwards 曲线的每个二次扭曲都与扭曲 Edwards 曲线同构；即，扭曲 Edwards 曲线集在二次扭曲下是不变的。

此外，对于扭曲爱德华曲线 $E_{E,a,d}:ax^2+y^2=1+dx^2y^2$是（实际上等价于）扭曲爱德华曲线 $E_{E,d,a}:dx^2+y^2=1+ax^2y^2$。映射 $(\bar x,\bar y)\mapsto(x,y)=(\bar x,1/\bar y)$ 是从 $E_{E,a,d}$ 到 $E_{E,d,a}$ 双向有理等价。更一般的，对于任何满足$\bar d/\bar a=a/d$ 的 $\bar a,\bar d$ ， $E_{E,a,d}$ 是 $E_{E,\bar a,\bar d}$ 的二次扭曲。这里也说明了 [4，定理2.1的证明]中使用的已知结论：$E_{E,1,d}$是$E_{E,1,1/d}$的二次扭曲。

3、蒙哥马利曲线和爱德华曲线

选择一个域 $k$ （$k\ne2$）。在本节，我们将证明在 $k$ 中的蒙哥马利曲线和在 $k$ 中的扭曲爱德华曲线等价。

如果可以，将 Weierstrass 曲线转换为蒙哥马利曲线的标准算法（e.g.，参见 [11，第 13.2.3.c 节]）可以与我们从蒙哥马利曲线到扭曲爱德华兹曲线的显式转换相结合。

定义 3.1（蒙哥马利曲线） 选择一个域 $k$ （$k\ne2$），确定常数 $A\in k\backslash\{-2,2\}$ 与 $B\in k \backslash{\{0\}}$。蒙哥马利曲线定义为

定理 3.2 选择一个域 $k$ （$k\ne2$）

1. 对于每个 $k$ 中的扭曲爱德华曲线和在 $k$ 中的蒙哥马利曲线等价。

   特别的，对于两个不同的常数 $a,d\in k$，若 $A = 2(a + d)/(a − d), B = 4/(a − d)$，扭曲爱德华曲线 $E_{E,a,d}$ 和蒙哥马利曲线 $E_{M,A,B}$ 等价。映射$(x,y)\mapsto(u,v)=((1+y)/(1-y),(1+y)/(1-y)x)$ 是从 $E_{E,a,d}$ 到 $E_{M,A,B}$ 的双有理等价，其逆变换为 $(u,v)\mapsto(x,y)=(u/v,(u-1)/(u+1))$。

2. 相反，$k$ 上的每条蒙哥马利曲线都双有理地等价于在 $k$ 上的扭曲 Edwards 曲线。

   特别的，确定常数 $A\in k\backslash\{-2,2\}$ 与 $B\in k \backslash{\{0\}}$，当 $a = (A + 2)/B,d = (A − 2)/B$， 蒙哥马利曲线 $E_{M,A,B}$ 和扭曲爱德华曲线 $E_{E,a,d}$ 等价。

证明：

1. 注意到 $a\ne d$ $A,B$ 有定义，且 $A\in k\backslash\{-2,2\} ,B\in k \backslash{\{0\}}$ 。若$A=2$，那么 $a+d=a-d$ 则$d=0$，矛盾；若 $A=-2$，那么 $a+d=d-a$ 则 $a=0$ ，矛盾。因此曲线 $E_{M,A,B}$ 是蒙哥马利曲线。

   以下Sage程序验证了定理 3.2中的映射

   R.<a,d,x,y>=QQ[]
   A=2*(a+d)/(a-d)
   B=4/(a-d)
   S=R.quotient(a*x^2+y^2-(1+d*x^2*y^2))
   u=(1+y)/(1-y)
   v=(1+y)/((1-y)*x)
   0==S((B*v^2-u^3-A*u^2-u).numerator())
   

   例外情况 $y=1,x=0$ 仅发生在 $E_{E,a,d}$ 上的有限多个点 $(x,y)$ 上。相反，对于 $x=u/v,y=(u-1)/(u+1)$，例外情况 $v=0,u=-1$ 仅发生在 $E_{M,A,B}$ 上的有限多个点 $(x,y)$ 上。

2. 注意到$B\ne 0$，所以 $a,d$ 有定义， 且 $A\ne-2$ 那么 $a\ne 0,d\ne0,a\ne d$ ，因此 $E_{E,a,d}$ 是扭曲爱德华曲线。

   进一步：

   因此，通过 1 ， $E_{E,a,d}$ 双有理等价于 $E_{M,A,B}$。

双有理等价中的特殊点。

定理3.2中，对于从 $E_{M,A,B}$ 到 $E_{E,a,d}$ 映射 $(u,v)\mapsto(x,y)=(u/v,(u-1)/(u+1))$ ，当 $v=0$ 或 $u+1=0$ 在 $E_{M,A,B}:Bv^2=u^3+Au^2+u$ 的点是未定义的。我们更详细的研究这些点

• $E_{M,A,B}$ 上的点 $(0,0)$ 对应 $E_{E,a,d}$ 上的二阶映射点 $(0,-1)$ 。该点和 $(0,1)$ 是逆映射 $(x,y)\mapsto((1+y)/(1-y),(1+y)/(1-y)x)$ 的唯一例外点，其中 $(0,1)$ 映射到无穷远点。
• 如果 $(A+2)(A-2)$ 是二次幂 （即 $ad$ 是二次幂），那么还有两个 $v=0$ 的点，即 $((-A\pm\sqrt{(A+2)(A-2)})/2,0)$ 。这些点的阶为2，对应 $E_{E,a,d}$ 中去奇异化的阶为2的无穷远点。
• 如果 $(A-2)/B$ 是二次幂 （即 $d$ 是二次幂），那么将有两个 $u=-1$ 的点，即 $(-1,\pm{\sqrt{(A-2)/B}})$。这些点的阶为4，对应 $E_{E,a,d}$ 中去奇异化的阶为4的无穷远点。

去扭曲。

根据定理 3.2，每条蒙哥马利曲线 $E_{M,A,B}$ 双有理等价于扭曲 Edwards 曲线，因此等价于 Edwards 曲线的二次扭曲。换句话说， $E_{M,A,B}$ 有一个二次扭曲形式，它双有理等价于爱德华曲线。

我们现在陈述两种不需要扭曲的情况。定理 3.3 指出，每条具有 4 阶点的椭圆曲线双有理等价于 Edwards 曲线。定理 3.4 指出，在 $\#k ≡ 3 \mod 4$ 的有限域 k 上，每条蒙哥马利曲线双有理等价于爱德华曲线。

定理3.3 选择一个域 $k$ （$k\ne2$），令 $E$ 是 $k$ 上的曲线。群 $E(k)$ 有一个阶为4的元素，当且仅当 $E$ 双有理等价于 $k$ 上的一条爱德华曲线。

证明：假设 $E$ 在 $k$ 上与 Edwards 曲线 $E_{E,1,d}$ 双有理等价。椭圆曲线加法定律对应于爱德华加法定律；见[4，定理3.2]. $E_{E,1,d}$ 上的点 (1, 0) 为 4 阶点，因此 $E$ 一定有 4 阶点。

相反，假设 $E$ 有一个 4 阶点 $(u_4,v_4)$ ，如 [4，定理2.1，证明] ，注意到 $u_4\ne0,v_4\ne0$；我们不失一般性假设 $E$ 的形式为 $v^2=u^3+(v_4^2/u_4^2-2u_4)u^2+u_4^2u$；定义 $d=1-4u_4^3/v_4^2$，可知 $d\notin{\{0,1\}}$。

下面的Sage程序验证了，当 $x=v_4u/u_4v,y=(u-u_4)/(u+u_4)$ 时，在 $E$ 的函数域中满足 $x^2+y^2=1+dx^2y^2$。

R.<u,v,u4,v4>=QQ[]
d=1-4*u4^3/v4^2
S=R.quotient((v^2-u^3-(v4^2/u4^2-2*u4)*u^2-u4^2*u).numerator())
x=v4*u/(u4*v)
y=(u-u4)/(u+u4)
0==S((x^2+y^2-1-d*x^2*y^2).numerator())

例外情况 $u_4v=0,u=-u_4$ 仅出现在 $E$ 上有限多个 $(u,v)$ 点。相反，$u=u_4(1+y)/(1-y),v=v_4(1+y)/(1-y)x$ ，例外情况 $y=1,x=0$ 仅出现在 $E_{E,1,d}$ 上有限多个点 $(x,y)$ 。

因此，有理映射 $(u,v)\mapsto(x,y)=(v_4u/u_4v,(u-u_4)/(u+u_4))$，逆映射为$(x,y)\mapsto(u,v)=(u_4(1+y)/(1-y),v_4(1+y)/(1-y)x)$，是从 $E$ 到爱德华曲线 $E_{E,1,d}$ 的双有理等价。

定理3.4 如果 $\#k ≡ 3 \pmod 4$ ，在有限域 k 上，每条蒙哥马利曲线双有理等价于爱德华曲线。

证明：确定 $A\in k\backslash\{-2,2\} ,B\in k \backslash{\{0\}}$ ，我们使用Okeya、Kurumatani 和 Sakurai [21] 的想法，以 Suyama 在 [20，第 262 页] 中的观察结果为基础，证明蒙哥马利曲线 $E_{M,A,B}$ 有一个阶点 4 . 当 #$k$ 是素数时，这个结论可以从[21, Theorem 1] 中得到，但是为了保持这篇论文的独立性，我们还是做一个直接证明。

情况1：$(A+2)/B$ 是二次幂，那么（如前所述）$E_{M,A,B}$ 有一个四阶点 $(1,\sqrt{(A+2)/B})$。

情况2：$(A+2)/B$ 是非二次幂，但$(A-2)/B$ 是二次幂，那么 $E_{M,A,B}$ 有一个四阶点 $(-1,\sqrt{(A-2)/B})$。

情况3：$(A+2)/B$ ，$(A-2)/B$ 都是非二次幂。因为 $k$ 是有限的，那么 $(A+2)(A-2)$ 一定是二次幂。蒙哥马利曲线 $E,_{M,A,A+2}$ 有三个 2 阶点 $(0,0),((-A\pm\sqrt{(A+2)(A-2)})/2,0)$，有一个 4 阶点 $(1,1)$，那么$\#E_{M,A,A+2}(k) ≡ 0 \pmod 8$。此外，$E_{M,A,B}$ 是 $E_{M,A,A+2}$ 的非平凡二次扭曲，所以 $\#E_{M,A,B}(k)+\#E_{M,A,A+2}(k)=2\#k+2\equiv0\pmod8$。因此，$\#E_{M,A,B}(k)\equiv0\pmod8$。曲线 $E_{M,A,B}$ 不会有更多的 2 阶点，因此它一定有一个 4 阶点。

在每种情况下，$E_{M,A,B}$ 都有一个 4 阶点。根据定理 3.3，$E_{M,A,B}$ 双有理等价于 Edwards 曲线。

这个定理不能推广到 $\#k\equiv1\pmod4$ 的情况。例如，$\mathbb{F_{17}}$ 的阶为20，同构于群 $\mathbb{Z}/2\times \mathbb{Z}/10$。此曲线双有理等价于 $E_{E,11,7}$ ，但它没有 4 阶点，因此不和爱德华曲线等价。

定理3.5 有限域 $k$ 满足 $\#k\equiv1\pmod 4$，令 $E_{E,A,B}$ 为蒙哥马利曲线，使 $(A+2)(A-2)$ 为二次幂，令$\delta$ 为非二次幂。

$E_{E,A,B}$ 和它的非平凡二次扭曲 $E_{E,A,\delta B}$ 中的一个，恰好等价于 Edwards 曲线。

特别的， $E,_{M,A,A+2}$ 双有理等价于 Edwards 曲线。

证明。因为 $(A+2)(A-2)$ 为二次幂， $E_{E,A,B}$ 和 $E_{E,A,\delta B}$ 都包括一个子群，同构于群 $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}$。这个子群让群阶有 4 这个因数。因为$\#E_{M,A,B}(k)+\#E_{M,A,\delta B}(k)=2\#k+2\equiv4\pmod8$，于是 $E_{E,A,B}$ 和 $E_{E,A,\delta B}$ 其中一个一定被 4 整除而不被 8 整除，这个曲线不能有 4 阶点，而另一条有。第一个陈述遵循定理3.3.

第二个陈述也遵循定理 3.3，因为 $E_{E,A,A+2}$ 上的点 (1, 1) 的阶数为 4。

4、数据

众所周知，当 $p$ 是一个大素数，在有限域 $\mathbb F_p$ 上大约有 $2p$ 个椭圆曲线同构类。这些椭圆曲线中有多少是双有理等价于扭曲爱德华曲线 $ax^2+y^2=1+dx^2y^2$ ？有多少双有理等价于爱德华曲线 $x^2+y^2=1+dx^2y^2$ ？有多少双有利等价于完整的爱德华曲线（即具有非二次幂 $d$ 的爱德华曲线）？有多少双有理等价于原始爱德华曲线 $x^2+y^2=c^2(1+x^2y^2)$ ？这些数据如何随群阶中 2 幂数变化的？

我们通过枚举所有完整的 Edwards 曲线、所有 Edwards 曲线、所有扭曲 Edwards 曲线（涵盖所有同构类的有限 $a$ 集）和 Weierstrass 形式的所有椭圆曲线（具有类似限制）来计算模各种素数 $p$ 的结果。我们将每条曲线双有理等价地，转换为椭圆曲线 $E$，然后计算 $(\#E, j(E))$，其中 $\#E$ 是 E 上的点数，$j(E)$ 是 $E$ 的 $j$ - 不变量。回想一下，$j (E) = j(E')$ 当且仅当 $E'$ 是 $E$ 的一个扭曲，并且除了少数同构类之外，扭曲由 $\#E$ 区分。

这些实验的某些部分以前已经进行过。参见如，[15]。然而，文献中的信息不足以我们将 Edwards 曲线（和完整的 Edwards 曲线）与扭曲 Edwards 曲线进行比较。

对于 $p\equiv1\pmod4$ 的素数的结果

$p=1009$ 时，我们发现

• 对于原始爱德华曲线，有43对不同的 $(\#E, j(E))$
• 对于完整爱德华曲线，有504对不同的 $(\#E, j(E))$
• 对于爱德华曲线，有673对不同的