论文翻译：未通过预选计算的椭圆曲线上的快速乘法（GF(2^m)）

时间：2020-02-24 23:16:50 阅读：82 评论：0 收藏：0 [点我收藏+]

摘要：本文提出了一种计算非超奇异椭圆曲线上椭圆标量乘法的算法定义为GF(2^m)。该算法是基于采用了文章[8]方法的文章[1]中所述方法的优化版本。我们的算法在硬件和软件上都很容易实现，适用于GF(2^m)上的任何椭圆曲线，不需要预先计算一个点的倍数，平均速度比标准草案IEEE P1363中描述的加减法要快。此外，与投影法相比，该方法需要更少的内存，并且对于相同二进制的所有乘数，标量乘法所需的计算量是固定的。因此，改进的方法对于在受限环境下实现椭圆曲线具有许多令人满意的特性。

关键词：GF(2^m)上的椭圆曲线；点乘法；

1介绍

椭圆曲线密码学最初是由Koblitz[5]和Miller[12]提出的，现在在实现公钥协议(如DiffieHellman密钥协议)方面越来越普遍。这些密码系统的安全性依赖于椭圆曲线上离散对数问题的预和的难解性。由于有限域上的椭圆曲线没有已知的次指数型算法，因此可以认为域、密钥和其他参数的大小比其他公钥密码体制（如具有相同安全级别的RSA）短。对于内存和/或计算能力等资源有限的应用程序，这尤其是一个优势。

GF(2^m)上的椭圆曲线特别有吸引力，因为有限的邻域操作可以在硬件和软件上非常有效地实现。例如，硬件实现GF(2^155)的文章[1]和软件实现GF(2^191)的文章[19]。

给定一个椭圆点P和一个大整数k，其大小与基础场大小相同，椭圆标量乘法操作kP被定义为将P与自身相加k次得到的椭圆点。这种运算类似于乘法群的指数运算，是椭圆曲线密码系统中最耗时的运算。

本文考虑了随机整数k和随机点P的kP的计算。提出了一种高效的标量乘法算法，该算法是文章[1]中算法的优化版本。所提出的算法适用于GF(2^m)上的随机椭圆曲线的硬件和软件实现。

2 以前的工作

计算kP的基本方法是IEEE P1363[14]标准草案中的加减法。此方法是对众所周知的“add-and-double”（或二进制）方法的改进版本，该方法不需要预先计算。对于随机乘法器k，该算法在仿射坐标系下平均执行⁸/₃log₂k场乘法和⁴/₃log₂k场逆，在射影坐标系下平均执行8¹/₃log2k场乘法。

一些二进制方法(用于乘法组中的取幂)的建议推广，如k-ary方法、有符号窗口方法，可以扩展到在有限域上计算椭圆标量乘法[11]。这些算法基于预计算的使用和乘法器的重新编码方法。在文章[3]中，在不同的条件下分析了几种算法。然而，当内存非常昂贵时，大多数建议的优化可能不值得。

在GF(2^m)上定义的一些特殊椭圆曲线类允许有效的实现。对于异常曲线，已知最快的计算kP的算法在文章[17]中给出;对于定义在小子域上的曲线，文章[13]给出了有效的算法。

文献[4,16,7]提出了一些加速方法，如k元法和基于窗口的方法。这些方法适用于GF（2^m）上随机椭圆曲线的软件实现。

Montgomery[8]提出了一种计算kP的不同方法。该方法基于二进制方法，利用已知差分的两点之和的x坐标计算其坐标。该方法使用了二进制方法的以下变体：

技术分享图片

注意，该方法保持不变关系是P2-P1=P，并在每次迭代中执行加法和加倍。在文献[9]中，Montgomery的方法被用于减少在GF（2^m）上的超奇异曲线中添加点所需的寄存器数量。然而，作者观察到Montgomery方法在储存方面的好处是以牺牲速度为代价的。

从GF（2^m）上椭圆曲线的硬件实现的角度出发，很少有文章讨论计算kP的有效方法。在文献[1]中，Montgomery方法适用于GF（2^m）上的非超奇异椭圆曲线。然而，为实现每次迭代而给出的公式在域乘法方面并不高效。

在这篇论文中，我们将提出一个有效地实现Montgomery的方法计算kP的非超奇异椭圆曲线上的GF(2^m)。

论文的其余部分组织如下。在第3节中，我们简要介绍了GF(2^m)上的椭圆曲线。第四部分对提出的算法进行了描述和分析。第5节给出了基于LiDIA的算法的运行时间。附录中给出了该算法的实现。

3 GF(2m)上的椭圆曲线

这里对椭圆曲线作了简要的介绍，关于特征2的有限域上的椭圆曲线的更多信息见文献[10,14]。设GF（2^m）为特征二的有限域。将GF（2^m）上的非超奇异椭圆曲线 E 定义为下列方程的解集(x,y)∈GF(2^m)×GF(2^m)，

其中a和b∈GF(2^m)，b≠0时，用无穷远的点O表示。

众所周知，在被称为“切线和弦”的加法运算下，E以O为群恒等式，形成一个交换有限群。加法规则的显式有理公式涉及有限域内的几种算术运算(加法、平方、乘法和逆运算)。在射影坐标中添加两个点的公式可在[10,7]中找到。在仿射坐标中，椭圆群的运算如下所示。设P=(x1,y1)∈E；然后-P=(x1,x1+y1)。对于所有P∈E，O+P=P+O=P。如果Q=(x2,y2)∈E和Q≠-P，则P+Q=(x3,y3)，其中

技术分享图片

请注意，2P的x坐标与p的y坐标无关，这一观察结果将用于改进方法的推导。

4 改进方法

本节介绍了计算kP的改进方法。我们首先在仿射坐标系中提出了一种算法，该算法要求在每个坐标系中有两个域的反转。然后提出了一个具有更多场乘法的“射影”版本，但是在计算结束时只有一个场反转。

4.1仿射版本

将Montgomery方法[8]推广到GF（2^m）上的椭圆曲线需要实现算法1的步骤3的公式。在下文中，我们给出了仅使用P1、p2和P的x坐标执行算法1所需的算术运算的有效公式。在算法1的第 i 次迭代结束时，得到了kP和（k+1）P的x坐标，并给出了kP的y坐标的简单恢复公式。

引理1：设P1=（x1，y1），P2=（x2，y2）为椭圆点。然后P1+P2，x3的x坐标可以计算如下。

技术分享图片

证明：由于p1和p2是椭圆点，因此y₁^2+y₂^2+x₁y₁+x₂y₂+x₁^3+x₂^3=0。结果很容易从公式（1）中得出。

下面的引理说明如何计算两个差已知的点相加的x坐标。

引理2：设P=（x，y），P1=（x1，y1），P2=（x2，y2）为椭圆点。假设P2=P1+P，那么P1+P2，x3的x坐标可以根据P，P1和P2的x坐标计算，如下所示：

技术分享图片

证明：案例P=O直接从(1)开始。应用公式(3)，我们得到P2+P1的x坐标可以重写为：

技术分享图片

同样，P2-P1的x坐标满足：

技术分享图片

将(5)和(6)相加即可得到结果。

下一个引理允许在P坐标以及P1和P1+P的x坐标已知时计算P1的y坐标。

引理3：设P=（x，y），P1=（x1，y1），P2=（x2，y2）为椭圆点。假设P2=P1+P并且x≠0。则p1的y坐标可以用P的坐标，p1和p2的x坐标如下：

技术分享图片

证明：由于P2=P1+P，我们从（3）中得到y1满足以下方程：

技术分享图片

因此：

技术分享图片

下面的算法基于引理2和3，在仿射坐标系下实现了Montgomery方法。（下表为算法2A：Montgomery标量乘法）

技术分享图片

注意，在步骤4的每次迭代中，算法2A执行两个字段反转、一个一般字段乘法、一个乘以常数b、两个平方和四个加法；因此，计算kP的字段操作总数在以下引理中给出。

引理4：为了计算kP，算法2A在GF(2m)中进行的实地操作次数如下：

技术分享图片

备注：对算法2A的进一步改进是使用优化的例程乘以常数b。另一个潜在的改进是从步骤4开始并行计算x1和x2，因为这些计算彼此独立。

4.2投影版本

当GF（2^m）中的场反演相对昂贵时（例如如果m≥128，基于Fermat定理的场反演要求GF（2^m）中至少有7个乘法），那么使用分数场算法进行椭圆曲线计算可能具有计算优势。

设P，P1和P2是曲线E上的点，使得P2=P1+P。对于i∈{1,2}，将Pi的x坐标用x i/Zi代替，。从引理2，当2pii的x坐标转换成射影坐标时有：

技术分享图片

类似地，投影坐标中P1+P2的x坐标可以用分数X3/Z3来计算，其中:

技术分享图片

加法公式需要三个一般场乘法，一个乘x（即P的x坐标，在计算kP时是固定的）、一个平方和两个加法；倍增需要一个一般场乘法、一个乘常数b、五个平方和一个加法。下一个算法描述了基于这些公式的方法。（算法2P:Montgomery标量乘法）

技术分享图片

附录中给出了程序Madd、Mdouble和Mxy的实现。

引理5：算法2P在GF(2^m)中执行的操作次数如下:

技术分享图片

备注：由于算法2的两个版本的复杂性不取决于k的二进制表示中的1（或0）的数目，这可能有助于防止定时攻击。另一方面，使用限制乘法器（例如，具有较小的Hamming权重）不能直接加快算法2A和2P的速度，这与二进制方法等方法相比是一个缺点。然而，从实用的角度来看，密码应用程序中的大多数协议都使用随机乘法器。

4.3复杂性比较

在后半部分中，我们假设GF（2^m）中的加法和平方运算相对较快。现在我们将加减法的复杂度与所提方法的复杂度进行比较。这是一个公平的比较，因为两种方法都不使用预计算。对于随机乘法器k，用文献[14]中给出的在射影坐标下的加减法进行了8.3log2k的场乘法；因此我们期望算法2P平均快28%。然而，如果我们使用文献[7]中给出的公式来实现射影方案中的群运算，那么算法2P大约比加减法快14%。在下表中，我们总结了这些方法的复杂性。

表1：算法2P与其它算法的复杂度比较（a=0,1）。

技术分享图片

现在我们从场乘法的角度推导了加法-减法（使用仿射坐标）的代价。如第2节所述，该方法平均执行⁸/₃log₂k场乘法和⁴/₃log₂k场逆。因此，总代价是¹/₃(4r+8)乘，其中r是逆运算与乘法的代价比。这表明，对于r>2.5的有限域GF（2^m）的实现（参见示例[1,19,4]），算法2P比加减法具有计算优势。

5运行时间

在本节中，我们给出了我们在软件中得到的算法在有限域GF(2^m)上的运行时间，其中m = 163,191和239。为了表示有限域，我们使用了一个基于c++的库LiDIA[6]。该有限域实现采用多项式基表示，且不可约模尽可能稀疏。我们使用了Sun UltraSPARC 300MHz的机器。为了进行比较，我们在表2中列出了GF(2m)中基本算术运算的时间。

表2：使用LiDIA的GF(2m)的平均运行时间(微秒)

技术分享图片

注意，一个字段的逆要花费9次以上的字段乘法；因此，在字段逆运算与字段乘法相比相对昂贵的情况下，使用LiDIA可以说明所提出算法的性能。

在表3中，我们给出了用几种方法计算标量乘法的平均运行时间。这些值是通过以下试验获得的：我们在GF(2^m)上选择10条随机椭圆曲线(a = 0)，然后在每条曲线上随机选择100个小于2m的整数点P。我们在射影坐标下实现了二进制方法（在文献[10]中）、加减法（在文献[14]中）和算法2P。从表3可以看出，我们提出的方法平均比加减法快27-29%，比二元法快51%。这些结果表明，表1所示的算法2P的理论改进在实际实现中得到了验证。

表3：计算mP的平均运行时间(毫秒)。

技术分享图片

6 结论

本文提出了一种计算椭圆标量乘法的有效方法，该方法是[1]算法的优化版本。该方法在随机选择的椭圆曲线上精确地进行6[log₂k]＋10场乘法来计算kP，硬件和软件都易于实现，无需预计算，适用于任何GF（2^n）的实现，平均比加减法快，并且比基于投影格式的方法占用更少的寄存器。因此，该方法对于椭圆曲线在移动设备、智能卡等约束环境中的应用具有一定的实用价值。

7 附录

Mdouble（加倍算法）