扭曲爱德华曲线

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对不同的 $(\#E, j(E))$
• 对于扭曲爱德华曲线，有842对不同的 $(\#E, j(E))$
• 对于群阶能被4整除的曲线，有842对不同的 $(\#E, j(E))$
• 对于椭圆曲线，有2014对不同的 $(\#E, j(E))$

我们更仔细地观察了 $\#E$ 中 2 的幂数，得到以下分布

Cureves	Total	odd	2*odd	4*odd	8*odd	16*odd	32*odd	64*odd
original Edwards	43	0	0	0	0	23	6	6
complete Edwards	504	0	0	252	130	66	24	16
Edwards	673	0	0	252	195	122	42	30
twisted Edwards	842	0	0	421	195	122	42	30
4 divides group order	842	0	0	421	195	122	42	30
all	2014	676	496	421	195	122	42	30

通过测试一千多个 $p\equiv1\pmod4$ 素数，我们得到以下结论

Curves	Total	odd	2*odd	4*odd	8*odd
original Edwards	$\approx(1/24)p$	0	0	0	0
complete Edwards	$\approx(1/2)p$	0	0	$\approx(1/4)p$	$\approx(1/8)p$
Edwards	$\approx(2/3)p$	0	0	$\approx(1/4)p$	$\approx(3/16)p$
twisted Edwards	$\approx(5/6)p$	0	0	$\approx(5/12)p$	$\approx(3/16)p$
4 divides group order	$\approx(5/6)p$	0	0	$\approx(5/12)p$	$\approx(3/16)p$
all	$\approx2p$	$\approx(2/3)p$	$\approx(1/2)p$	$\approx(5/12)p$	$\approx(3/16)p$

我们不认可关于蒙哥马利曲线集（或者，扭曲爱德华兹曲线集）和所有椭圆曲线集的统计数据的新颖性；所有这些统计数据都曾被观察过，其中一些已被证实。此外，[4, Abstract] 中指出了完整 Edwards 曲线的 $(1/2)p$。然而，爱德华兹曲线 $(2/3)p$、$(1/4)p$ 和 $(3/16)p$ 似乎是新的观察结果。我们将旧的统计数据作为对比基础。

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

对于 $p\equiv3\pmod4$ 的素数有不同的统计结果，正如我们在定理3.4和3.5中预期的那样。例如，以下是 $p=1019$的表

Cureves	Total	odd	2*odd	4*odd	8*odd	16*odd	32*odd	64*odd
original Edwards	254	0	0	0	127	68	33	10
complete Edwards	490	0	0	236	127	68	33	10
Edwards	744	0	0	236	254	136	66	20
twisted Edwards	744	0	0	236	254	136	66	20
4 divides group order	822	0	0	314	254	136	66	20
all	2012	680	510	314	254	136	66	20

通过测试一千多个 $p\equiv3\pmod4$ 素数，我们得到以下结论

Curves	Total	odd	2*odd	4*odd	8*odd
original Edwards	$\approx(1/4)p$	0	0	0	$\approx(1/8)p$
complete Edwards	$\approx(1/2)p$	0	0	$\approx(1/4)p$	$\approx(1/8)p$
Edwards	$\approx(3/4)p$	0	0	$\approx(1/4)p$	$\approx(1/4)p$
twisted Edwards	$\approx(3/4)p$	0	0	$\approx(1/4)p$	$\approx(1/4)p$
4 divides group order	$\approx(5/6)p$	0	0	$\approx(1/3)p$	$\approx(1/4)p$
all	$\approx2p$	$\approx(2/3)p$	$\approx(1/2)p$	$\approx(1/3)p$	$\approx(1/4)p$

和上面一样，我们不认可关于蒙哥马利曲线集和所有椭圆曲线集的统计数据的新颖性；我们将这些统计数据作为对比基础。

近素数群阶

我们还观察了$\#E$ 的奇数部分是素数的频率，并观察了 $p = 1009$ 的分布

Cureves	prime	2*prime	4*prime	8*prime	16*prime	32*prime
original Edwards	0	0	0	25	22	9
complete Edwards	0	0	48	25	22	9
Edwards	0	0	48	50	44	18
twisted Edwards	0	0	48	50	44	18
4 divides group order	0	0	64	50	44	18
all	148	100	64	50	44	18

当然，较大的素数 p 产生素数 $\#E$ 的机会更小，产生素数 $\#E/2$ 的机会更小，etc。

5、同源：更多曲线

一条不与 Edwards 曲线同构的曲线，甚至与扭曲 Edwards 曲线也不同构的曲线，可能仍与扭曲 Edwards 曲线同源。本节特别表明，每条具有三个 2 阶点的曲线对于扭曲 Edwards 曲线都是 2-同源的。本节给出了一个曲线作为例子，它并不双理等价于扭曲 Edwards 曲线，但与扭曲 Edwards 曲线是 2-同源的。本节还讨论了在原始曲线的奇次子群中使用 2-同源进行标量乘法。

我们使用同源扩大扭曲爱德华曲线的覆盖范围，类似于Brier 和 Joye 在 [9] 中用同源扩大 “$a_4=-3$” Weierstrass 曲线的覆盖范围。我们认为同源对其他形式的曲线也生效。例如，在 $p\equiv3\pmod4$ 的域 $\mathbb{F_p}$上，每条具有 4 阶点的椭圆曲线与雅可比四次曲线 $v^2=u^4-2\delta u^2+1$ 是2 - 同源的；参阅 [6]、[12]、[16]、[17] 和 [3]，获得快速显式公式，在此形式的曲线上执行计算。

定理 5.1 选择一个域 $k$ （$k\ne2$）。在 k 上具有三个 2 阶 $k$ - 有理点的每条椭圆曲线在 $k$ 上与扭曲 Edwards 曲线是 2 同源的。

证明。令 $E$ 是 $k$ 上的椭圆曲线，有三个 2 阶 $k$ - 有理点。将 $E$ 写成Weierstrass 形式 $v^2 = u^3 + a_2u^2 + a_4u + a_6$，二阶点为 $(u_0,0),(u_1,0),(u_2,0)$。不失一般性地假设 $u_0 = 0$；为了处理一般情况，将 u 替换为 $u - u_0$。

多项式 $u^3 + a_2u^2 + a_4u + a_6$ 显然有三个根 $0,u_1,u_2$ ，因此有因式 $u(u-u_1)(u-u_2)$ 。于是 $E$ 可以表示成如下形式

因此 $E$ 与由下式给出的椭圆曲线 $\bar{E}$ 是 2 - 同源的

参见 [22, Chapter III, Example 4.5]的例子。 $E$ 与 $\bar{E}$ 的 2 - 同源由下式给出

由 $\bar{E}$ 到 $E$ 的对偶 2 - 同源由下式给出

椭圆曲线 $\bar{E}$ 和 $E_{M,2(u_1+u_2)/(u_1−u_2),1/(u_1−u_2)}$ 同构，因此由定理 3.2 ，它和曲线 $E_{E,4u_1,4u_2}$ 双理等价。于是原曲线 $E$ 与 $E_{E,4u_1,4u_2}$ 2 - 同源。

一个数值例子。

在 $p ≡ 1 \pmod 4$ 的域 $\mathbb {Fp}$ 上，每条具有三个 2 阶点的曲线已经双理上等价于扭曲 Edwards 曲线。然而，在 $p ≡ 3 \pmod 4$ 的域 $\mathbb {Fp}$ 上，具有三个 2 阶点的曲线在双有理上不等价于扭曲 Edwards 曲线（除非它有 4 阶点）；见定理 3.4。但是，无论是否存在 4 阶点，定理 5.1 均适用。

例如，考虑 [7，附录 A.1，示例 11] 中给出的椭圆曲线。这是一条 Weierstrass 形式的曲线 $y^2 = x^3 + ax + b$ 在素数域 $\mathbb{Fp}$ 上有 n 个点，其中 $p ≡ 3 \pmod 4$

$x^3 + ax + b$ 模 $p$ 有 3 个根，所以这条椭圆曲线有 3 个 2 阶点。根据定理 5.1，它与扭曲 Edwards 曲线是 2 同源的。另一方面，它并不等同于蒙哥马利曲线或扭曲 Edwards 曲线。如果等同的话，根据定理 3.4，它有一个4阶点，所以 n 必须是 8 的倍数。

椭圆曲线密码学中最重要的操作是椭圆曲线的素数阶子群中的标量乘法。考虑上面所示椭圆曲线的 $n/4$ 阶子群中的点 P； $n/4$ 是素数。对于任意整数 $m$ ，计算 $Q = mP$，我们执行以下操作

• 计算 $P'=\phi(P)$ ，其中 $\phi$ 是这个曲线到扭曲 Edwards 曲线的 2 - 同源（在定理 5.1 证明中明确给出）
• 在扭曲爱德华曲线上计算 $Q'=((m/2)\pmod{n/4})P'$。
• 计算 $Q=\hat{\phi}(Q')$，其中 $\hat\phi$ 是对偶同源。

同源和对偶同源很容易计算，因此大部分时间花费在扭曲爱德华兹曲线上的标量乘法。

6、扭曲爱德华曲线的计算

选择一个域 $k$ （$k\ne2$）。在本节中，我们给出了在 $k$ 上扭曲 Edwards 曲线的加法和倍点的快速显式公式。

扭曲爱德华曲线加法法则

令 $(x_1,y_1),(x_2,y_2)$ 是在扭曲爱德华曲线 $E_{E,a,d} : ax^2 + y^2 = 1 + dx^2y^2$ 上的点。两点的加法公式为

中性元素为 $(0, 1)$，$(x_1, y_1)$ 的相反点为 $(−x_1, y_1)$。

对于加法定律的正确性，可以发现它与$\bar x^2 + y^2 = 1 + (d/a)\bar x^2y^2$ 上的 Edwards 加法定律一致（其中 $\bar x = \sqrt ax$ ），这在 [4, 第 3 节] 中被证明是正确的。

这些公式也适用于加倍。如果 $a$ 是 $k$ 中的二次幂并且 $d$ 是 $k$ 中的非二次幂，则这些公式是完备的（即没有例外情况）。后者源自 $E_{E,a,d}$ 同构于 $E_{E,1,d/a}$； $d/a$ 是 $k$ 中的非二次幂，由 [4，定理 3.1]，如果 $d'$ 是非二次幂，则 Edwards 加法定律在 $E_{E,1,d'}$ 上是完备的。

投影扭曲爱德华兹坐标

为了避免反演，我们研究扭曲爱德华兹曲线的投影。

对于 $Z_1\ne0$，齐次点 $(X_1:Y_1:Z_1)$ 表示 $E_{E,a,d}$ 上的仿射点 $(X_1/Z_1, Y_1/Z_1)$。

我们在 Sage 的帮助下，按照 Explicit-Formulas Database 的方法检验了以下加法和倍点公式。

投影扭曲坐标的加法

下面的公式用10M + 1S + 2D + 7add，计算出 $(X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_2)$ ，其中 2D 是一次乘 a 和一次乘 d

• 注：此处的 M 表示乘法，S表示平方，D表示倍点，add表示加法，也就是说这次加法运算需要10次乘法，1次平方，2次倍点，7次加（减）法

投影扭曲坐标的倍点

下面的公式用3M + 4S + 1D + 7add，计算出 $(X_3 : Y_3 : Z_3) = 2(X_1 : Y_1 : Z_1)$ ，其中 1D 是一次乘a：

消去投影坐标中的分母

当 a 是 k 中的二次幂时，这是扭曲 Edwards 曲线 $E_{E,a,d}$ 的另一种算术方法。

当 $x=\sqrt a\bar x,y=\bar y$时，曲线 $E_{E,a,d}:a\bar x^2+\bar y^2=1+d\bar x^2\bar y^2$ 和扭曲爱德华曲线 $E_{E,1,d/a}:x^2 + y^2 = 1 + (d/a)x^2y^2$ 同构，见第 2 章。 以下公式用10M + 1S + 3D + 7add 计算了在 $E_{E,1,d/a}$ 上的加法，其中 3D 是两次乘a，一次乘d：

使用 [4, Section 4] 中的公式，可以用 3M + 4S + 6add 在 $E_{E,1,d/a}$ 上倍点，与曲线系数 $d/a$ 无关。

我们给出的 $E_{E,1,d/a}$ 的加法公式比 $E_{E,a,d}$ 的加法公式慢（由于一次乘以 1）。另一方面，对于 $E_{E,1,d/a}$ 的倍点比 $E_{E,a,d}$ 的倍点更快（由于一次乘以 1）。一些应用程序（例如批量签名验证）的加法比倍点多，而另一些应用程序的加倍比加法多，因此这些公式都是有价值的。

反转扭曲爱德华兹坐标

避免反演的另一种方法是让曲线 $(X^2 + aY^2)Z^2 = X^2Y^2 + dZ^4$ 上的一个点 $(X_1 : Y_1 : Z_1)$ 对应在 $E_{E,a,d}$ 上的仿射点 $(Z_1/X_1, Z_1/Y_1)$ ，其中 $X_1Y_1Z_1\ne0$。

Bernstein 和 Lange 在 [5] 中针对 a = 1 的情况介绍了这些倒置坐标，并观察到坐标会更节省时间。我们将其推广到任意 $a$ 。

反转扭曲坐标中的加法

下面的公式用 9M + 1S + 2D + 7add，计算出 $(X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_2)$ ，中 2D 是一次乘 a 和一次乘 d ：

反转扭曲坐标中的倍点

下面的公式用3M + 4S + 2D + 6add，计算出 $(X_3 : Y_3 : Z_3) = 2(X_1 : Y_1 : Z_1)$ ，其中 2D 是一次乘a和一次乘2d ：

消去反转坐标中的分母

以下公式用 9M + 1S + 3D + 7add 计算了在 $E_{E,1,d/a}$ 上的反转坐标的加法，其中 3D 是两次乘a，一次乘d：

以下公式用 3M + 4S + 3D + 5add 计算了在 $E_{E,1,d/a}$ 上的反转坐标的倍点，其中 3D 是两次乘a，一次乘2d：

更多参数

可以考虑更一般的曲线方程

其加法法则为：

我们没有为这种推广提供明确的公式；这些曲线总是与扭曲 Edwards 曲线同构。然而，我们认为，存在这样的曲线，它的额外参数可以节省一点点计算时间。

7、爱德华与扭曲爱德华

我们引入了扭曲 Edwards 曲线作为 Edwards 曲线的推广。这种推广对实际的加密用途有用吗？

第 4 节表明，在 $p\equiv3\pmod4$ 的域 $\mathbb{F_p}$上，扭曲 Edwards 曲线比 Edwards 曲线覆盖的曲线多得多。特别是，对于此类域上的 “4 * odd” 型的椭圆曲线，爱德华曲线的覆盖率仅为扭曲爱德华曲线覆盖率的 60% 左右。我们可以选择非常小的 $a$，使扭曲 Edwards 曲线基本上与 Edwards 曲线一样快，从而将 Edwards 加法的速度带入更多种类的椭圆曲线。

即使椭圆曲线可以用 Edwards 形式表示，以扭曲 Edwards 形式表示相同的曲线通常也可以节省算术时间。在本节中，我们回顾了以最快速度为目标的实现者所面临的问题。我们举例说明扭曲 Edwards 曲线对面临外部指定曲线的实现者的效果，以及对自由选择自己曲线的实现者的效果。

扭曲如何节省时间

下表总结了 Edwards 曲线上的标准（投影）坐标、扭曲 Edwards 曲线上的标准坐标、Edwards 曲线上的倒置坐标和扭曲 Edwards 曲线上的倒置坐标中的加法和倍点速度。

Coordinates	Source of algorithms	Addition	Doubling
Edwards	[4, §4]	10M+1S+1D (mult by d/a)	3M+4S
Edwards	this paper （clearing denoms）	10M+1S+3D (mult by a, a, d)	3M+4S
Twisted Edwards	this paper	10M+1S+2D(mult by a, d)	3M+4S+1D(mult by a)
Inverted Edwards	[5, §§4–5]	9M+1S+1D(mult by d/a)	3M+4S+1D(mult by d/a)
Inverted Edwards	this paper（clearing denoms）	10M+1S+3D(mult by a, a, d)	3M+4S+3D(mult by a, a, d)
Inverted twisted Edwards	this paper	9M+1S+2D(mult by a, d)	3M+4S+2D(mult by a, d)

如果曲线 E 可表示为 Edwards 曲线，我们有没有理由将 E 的更一般表达式视为扭曲 Edwards 曲线？看一眼上表，答案可能是否定的：扭曲似乎在每个坐标系和每个组操作中都失去一维，而没有获得任何东西。但是，有很多情况答案是肯定的！

具体来说，不是对 $k$ 上的 Edwards 曲线 $E_{E,1, \bar d}$ 执行计算，而是可以对任何 $(a, d)$ ，$k$ 上的扭曲 Edwards 曲线 $E_{E,a,d}$ 执行计算，使得$\bar d= d/a$ 并且 $a$ 是 $k$ 中的二次幂（计算同构很方便，但对于a是一个小整数的平方来说肯定不是必需的）。特别地，在 $\mathbb Fp$ 上的许多曲线都有 $\bar d$ 可表示为 $d/a$，其中 $d$ 和 $a$ 都很小，远小于与 $\bar d$ 模 $p$ 相等的任何整数。在非扭曲 Edwards 情况下，上表中的 1D 是乘 $\bar d$，而在扭曲 Edwards 情况下，2D 是一次乘以 d，一次乘以 a，通常比乘以 $\bar d$ 花费的时间更少。

例如， 在 Edwards 曲线出现之前，[1] 中使用的曲线 “Curve25519” 来记录 Diffie-Hellman 在椭圆曲线上的速度。Curve25519 是 $\mathbb Fp$ 上的特定椭圆曲线，其中 $p = 2^{255} - 19$。Bernstein 和 Lange 在 [4, Section 2] 中指出，Curve25519 可以表示为 Edwards 曲线 $x^2 + y^2 = 1 + (121665/121666)x^2y^2$。我们指出这条曲线与扭曲的 Edwards 曲线 $121666x^2 + y^2 = 1 + 121665x^2y^2$ 同构，并且扭曲 Edwards 曲线提供了更快的计算速度。扭曲 Edwards 曲线上的加法只涉及一次乘 121665 和一次乘 121666，这比一次乘$20800338683988658368647408995589388737092878452977063003340006470870624536394 ≡ 121665/121666 \pmod p$ 要快。

这种现象并非偶然。蒙哥马利曲线 $E_{M,A,B}$ 通常使得 $(A + 2)/4$ 是一个小整数：这加快了 $u$ 坐标的计算，正如蒙哥马利在 [20, page 261, bottom] 中指出的那样。相应的扭曲 Edwards 曲线的 $d/a$ 等于 $(A − 2)/(A + 2)$，这是一个小整数的比，允许以扭曲 Edwards 形式进行快速运算。

Edwards 曲线和扭曲 Edwards 曲线之间的选择，与标准 Edwards 坐标和反 Edwards 坐标之间的选择相互联系。频繁的加法使反转 Edwards 坐标的表现更好。大的 $a, d$ 使反转 Edwards 坐标的表现不尽如人意。

选择扭曲 Edwards 曲线

通常，实现者可以自由选择自己的曲线以获得最佳速度。为了说明这种灵活性的好处，我们研究了几个模数大小在：$2^{160} - 47$ 左右的“小”扭曲 Edwards 曲线，最大素数小于 $2^{160}$ ； $2^{192} - 2^{64} - 1$ (用于 NIST 的 P-192 椭圆曲线的素数)； $2^{224} − 2^{96} + 1$ (用于 NIST 的 P-224 椭圆曲线的素数)；和 $2^{255} - 19$ (在 [1] 中使用的素数)。具体来说，我们列举了数千个小的 (a, d)对，作为扭曲 Edwards 曲线 $E_{E,a,d}$ 的参数，并检查了哪些曲线在 $\mathbb Fp$ 上具有较小的辅因子，即在辅因子 $h$ 较小的情况下具有群阶 $h$·prime。我们给出了一些带有小辅因子、小 a 和小 d 的扭曲 Edwards 曲线示例，支持非常快速的运算。

对于 $p =2^{192} - 2^{64} - 1$，扭曲 Edwards 曲线 $E_{E,102,47}$ : $102x^2 + y^2 = 1 + 47x^2y^2$ 具有辅因子 4。 $E_{E,102,47}$ 的运算速度非常快，其辅因子最小。非平凡的二次扭曲 $E_{E,1122,517}$ 只有辅因子 28，可以防止例如 [1，第 3 节] 中讨论的主动小子群攻击。

对于 $p=2^{224}-2^{96}+1$，扭曲Edwards曲线 $E_{E,12,1}$ 有辅因子3456，它的非平凡二次扭曲 $E_{E,132,11}$ 有辅因子20。系数 $a=12,d=1$ 在这里特别小。辅因子 3456 虽然不是最小的，但仍可考虑用于加密目的。

如果以其他方式防止主动小子群攻击，则可以找到更小的 $(a, d)$ 对。对于 $p=2^{160}-47$ ，扭曲爱德华曲线 $E_{E,23,-6}$ 有辅因子4；相比之下，我们发现的第一条具有小参数 $d$ 和辅因子 4 在同一域上的 Edwards 曲线是 $E_{E,1,268}$。对于 $p=2^{255}-19$，扭曲爱德华曲线 $E_{E,29,-28}$ 有辅因子4，$E_{E,25,2}$ 有辅因子8。

 

References

1. Daniel J. Bernstein, Curve25519: new Diffie-Hellman speed records, in PKC 2006[25] (2006), 207–228. URL: http://cr.yp.to/papers.html#curve25519. Citations in this document: §7, §7, §7.
2. Daniel J. Bernstein, Peter Birkner, Tanja Lange, Christiane Peters, ECM using Edwards curves (2007). URL: http://eprint.iacr.org/2008/016. Citations in this document: §1.
3. Daniel J. Bernstein, Tanja Lange, Explicit-formulas database (2007). URL: http://hyperelliptic.org/EFD. Citations in this document: §5, §6.
4. Daniel J. Bernstein, Tanja Lange, Faster addition and doubling on elliptic curves, in Asiacrypt 2007 [19] (2007), 29–50. URL: http://cr.yp.to/papers.html#newelliptic. Citations in this document: §1, §1, §2, §2, §2, §3, §3, §3, §3, §3,§3, §4, §6, §6, §6, §7, §7.
5. Daniel J. Bernstein, Tanja Lange, Inverted Edwards coordinates, in AAECC 2007 [8] (2007), 20–27. URL: http://cr.yp.to/papers.html#inverted. Citations in this document: §1, §6, §7.
6. Olivier Billet, Marc Joye, The Jacobi model of an elliptic curve and side-channel analysis, in AAECC 2003 [14] (2003), 34–42. MR 2005c:94045. URL: http://eprint.iacr.org/2002/125. Citations in this document: §5.
7. Ian F. Blake, Gadiel Seroussi, Nigel P. Smart, Elliptic curves in cryptography, Cambridge University Press, 2000. ISBN 0–521–65374–6. MR 1 771 549. Citations in this document: §5.
8. Serdar Boztas, Hsiao-Feng Lu (editors), Applied algebra, algebraic algorithms and error-correcting codes: 17th international symposium, AAECC-17, Banga-lore, India, December 2007, proceedings, Lecture Notes in Computer Science, 4851, Springer, 2007. See [5].
9. ́Eric Brier, Marc Joye, Fast point multiplication on elliptic curves through isogenies,in AAECC 2003 [14] (2003), 43–50. Citations in this document: §5.
10. Henri Cohen, Gerhard Frey (editors), Handbook of elliptic and hyperelliptic curve cryptography, CRC Press, 2005. ISBN 1–58488–518–1. MR 2007f:14020. See [11].
11. Christophe Doche, Tanja Lange, Arithmetic of elliptic curves, in [10] (2005), 267–\302. MR 2162729. Citations in this document: §3.
12. Sylvain Duquesne, Improving the arithmetic of elliptic curves in the Jacobi model,Information Processing Letters 104 (2007), 101–105. Citations in this document:§5.
13. Harold M. Edwards, A normal form for elliptic curves, Bulletin of the American Mathematical Society 44 (2007), 393–422. URL: http://www.ams.org/bull/2007-44-03/S0273-0979-07-01153-6/home.html. Citations in this document: §1.Twisted Edwards Curves 17
14. Marc Fossorier, Tom Høholdt, Alain Poli (editors), Applied algebra, algebraic al-gorithms and error-correcting codes: 15th international symposium, AAECC-15,Toulouse, France, May 2003, proceedings, Lecture Notes in Computer Science,2643, Springer, 2003. ISBN 3–540–40111–3. MR 2004j:94001. See [6], [9].
15. Steven D. Galbraith, James McKee, The probability that the number of points on an elliptic curve over a finite field is prime, Journal of the London Mathematical Society 62 (2000), 671–684. URL: http://www.isg.rhul.ac.uk/~sdg/pubs.html. Citations in this document: §4.
16. Huseyin Hisil, Gary Carter, Ed Dawson, New formulae for efficient elliptic curve arithmetic, in [23] (2007). Citations in this document: §5.
17. Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson, Faster group operationson elliptic curves, 25 Feb 2008 version (2008). URL: http://eprint.iacr.org/2007/441. Citations in this document: §5.
18. Hideki Imai, Yuliang Zheng (editors), Third international workshop on practice and theory in public key cryptosystems, PKC 2000, Melbourne, Victoria, Aus-tralia, January 18–20, 2000, proceedings, Lecture Notes in Computer Science, 1751,Springer, 2000. ISBN 978–3–540–66967–8. See [21].
19. Kaoru Kurosawa (editor), Advances in cryptology — ASIACRYPT 2007, Lecture Notes in Computer Science, 4833, Springer, 2007. See [4].
20. Peter L. Montgomery, Speeding the Pollard and elliptic curve methods of factor-ization, Mathematics of Computation 48 (1987), 243–264. ISSN 0025–5718. MR 88e:11130. URL: http://links.jstor.org/sici?sici=0025-5718(198701)48:177243:STPAEC2.0.CO;2-3. Citations in this document: §3, §7.
21. Katsuyuki Okeya, Hiroyuki Kurumatani, Kouichi Sakurai, Elliptic curves with the Montgomery-form and their cryptographic applications, in PKC 2000 [18] (2000), 238–257. Citations in this document: §3, §3.
22. Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathe-matics, 106, Springer, 1986. Citations in this document: §5.
23. Kannan Srinathan, C. Pandu Rangan, Moti Yung (editors), Progress in cryptology—INDOCRYPT 2007: 8th international conference on cryptology in India, Chennai, India, December 2007, proceedings, Lecture Notes in Computer Science, 4859, Springer, 2007. See [16].
24. William Stein (editor), Sage Mathematics Software (Version 2.8.12), The Sage Group, 2008. URL: http://www.sagemath.org. Citations in this document: §3.
25. Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin (editors), 9th international conference on theory and practice in public-key cryptography, New York, NY, USA, April 24–26, 2006, proceedings, Lecture Notes in Computer Science, 3958, Springer, 2006. ISBN 978–3–540–33851–2. See [1]