扭曲爱德华曲线

发布于 2022-10-31  717 次阅读






扭曲爱德华曲线

扭曲爱德华曲线

[TOC]

0、摘要

1、原文摘要

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

(同源是指两条椭圆曲线之间的同态)

2、写在前面

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

1、引入

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

Bernstein 和 Lange 在 [4] 中提出用坐标 表示 Edwards 曲线上的 ,并给出其加法和倍点的快速显式公式,声称这些显式公式会节省椭圆曲线加密的时间。他们把其加法法则扩展到曲线。在有限域上,这种形式的曲线相比于 ,会包括更多的曲线。广义形式的所有曲线都同源于曲线

在本文中,我们进一步推广 Edwards 加法法则以覆盖所有曲线 。在一般情况下,我们给出的加法和倍点显式公式几乎和在 这一特殊情况下一样快。我们将 Edwards 加法法则的运算速度推广到了每一条蒙哥马利曲线上;我们还发现,在 的素数域 上,许多蒙哥马利曲线没有被 的情况覆盖。进一步,我们解释了如何使用同源性来覆盖每条曲线的奇数部分(其群阶是4的倍数);在 的素数域 上, 涵盖所有蒙哥马利曲线,但不涵盖群阶为 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.

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

上的爱德华曲线 E 为:。在曲线 E 上的两点的加法运算定义为:

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

Twisted Edwards Curves.

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

定义 2.1(扭曲爱德华曲线) 选择一个域 ),选择两个不同的非零常数 ,扭曲爱德华曲线定义为

时,此曲线为爱德华曲线。

在第三节中,我们将证明每条扭曲爱德华曲线等价于蒙哥马利曲线,反之亦然。椭圆曲线具有 -不变量

Twisted Edwards Curves as Twists of Edwards Curves.

扭曲爱德华曲线是 Edwards 曲线的二次扭曲。映射 是从 的同构。如果 中的二次幂,那么 的同构。

更一般的,对于任何满足 的二次扭曲。相反,扭曲 Edwards 曲线的每个二次扭曲都与扭曲 Edwards 曲线同构;即,扭曲 Edwards 曲线集在二次扭曲下是不变的。

此外,对于扭曲爱德华曲线 是(实际上等价于)扭曲爱德华曲线 。映射 是从 双向有理等价。更一般的,对于任何满足 的二次扭曲。这里也说明了 [4,定理2.1的证明]中使用的已知结论:的二次扭曲。

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

选择一个域 )。在本节,我们将证明在 中的蒙哥马利曲线和在 中的扭曲爱德华曲线等价。

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

定义 3.1(蒙哥马利曲线) 选择一个域 ),确定常数 。蒙哥马利曲线定义为

定理 3.2 选择一个域

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

    特别的,对于两个不同的常数 ,若 ,扭曲爱德华曲线 和蒙哥马利曲线 等价。映射 是从 的双有理等价,其逆变换为

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

    特别的,确定常数 ,当 , 蒙哥马利曲线 和扭曲爱德华曲线 等价。

证明:

  1. 注意到 有定义,且 。若,那么 ,矛盾;若 ,那么 ,矛盾。因此曲线 是蒙哥马利曲线。

    以下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())
    

    例外情况 仅发生在 上的有限多个点 上。相反,对于 ,例外情况 仅发生在 上的有限多个点 上。

  2. 注意到,所以 有定义, 且 那么 ,因此 是扭曲爱德华曲线。

    进一步:

    因此,通过 1 , 双有理等价于

双有理等价中的特殊点。

定理3.2中,对于从 映射 ,当 的点是未定义的。我们更详细的研究这些点

  • 上的点 对应 上的二阶映射点 。该点和 是逆映射 的唯一例外点,其中 映射到无穷远点。
  • 如果 是二次幂 (即 是二次幂),那么还有两个 的点,即 。这些点的阶为2,对应 中去奇异化的阶为2的无穷远点。
  • 如果 是二次幂 (即 是二次幂),那么将有两个 的点,即 。这些点的阶为4,对应 中去奇异化的阶为4的无穷远点。

去扭曲。

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

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

定理3.3 选择一个域 ),令 上的曲线。群 有一个阶为4的元素,当且仅当 双有理等价于 上的一条爱德华曲线。

证明:假设 上与 Edwards 曲线 双有理等价。椭圆曲线加法定律对应于爱德华加法定律;见[4,定理3.2]. 上的点 (1, 0) 为 4 阶点,因此 一定有 4 阶点。

相反,假设 有一个 4 阶点 ,如 [4,定理2.1,证明] ,注意到 ;我们不失一般性假设 的形式为 ;定义 ,可知

下面的Sage程序验证了,当 时,在 的函数域中满足

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())

例外情况 仅出现在 上有限多个 点。相反, ,例外情况 仅出现在 上有限多个点

因此,有理映射 ,逆映射为,是从 到爱德华曲线 的双有理等价。

定理3.4 如果 ,在有限域 k 上,每条蒙哥马利曲线双有理等价于爱德华曲线。

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

情况1: 是二次幂,那么(如前所述) 有一个四阶点

情况2: 是非二次幂,但 是二次幂,那么 有一个四阶点

情况3: 都是非二次幂。因为 是有限的,那么 一定是二次幂。蒙哥马利曲线 有三个 2 阶点 ,有一个 4 阶点 ,那么。此外, 的非平凡二次扭曲,所以 。因此,。曲线 不会有更多的 2 阶点,因此它一定有一个 4 阶点。

在每种情况下, 都有一个 4 阶点。根据定理 3.3, 双有理等价于 Edwards 曲线。

这个定理不能推广到 的情况。例如, 的阶为20,同构于群 。此曲线双有理等价于 ,但它没有 4 阶点,因此不和爱德华曲线等价。

定理3.5 有限域 满足 ,令 为蒙哥马利曲线,使 为二次幂,令 为非二次幂。

和它的非平凡二次扭曲 中的一个,恰好等价于 Edwards 曲线。

特别的, 双有理等价于 Edwards 曲线。

证明。因为 为二次幂, 都包括一个子群,同构于群 。这个子群让群阶有 4 这个因数。因为,于是 其中一个一定被 4 整除而不被 8 整除,这个曲线不能有 4 阶点,而另一条有。第一个陈述遵循定理3.3.

第二个陈述也遵循定理 3.3,因为 上的点 (1, 1) 的阶数为 4。

4、数据

众所周知,当 是一个大素数,在有限域 上大约有 个椭圆曲线同构类。这些椭圆曲线中有多少是双有理等价于扭曲爱德华曲线 ?有多少双有理等价于爱德华曲线 ?有多少双有利等价于完整的爱德华曲线(即具有非二次幂 的爱德华曲线)?有多少双有理等价于原始爱德华曲线 ?这些数据如何随群阶中 2 幂数变化的?

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

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

对于 的素数的结果

时,我们发现

  • 对于原始爱德华曲线,有43对不同的
  • 对于完整爱德华曲线,有504对不同的
  • 对于爱德华曲线,有673对不同的