GF(2^m)上椭圆曲线标量乘快速算法研究

Research on Fast Algorithms for Scalar Multiplication of Elliptic Curve over GF(2^m)

摘要: 椭圆曲线密码自提出以来便因其优良的性质而得到了广泛的应用。本文针对椭圆曲线上关键的标量乘运算，根据将耗时较多的求逆转换为乘法的思想，推导出了 上计算 的递推公式，将求逆次数减少到一次。同时提出了计算 的加速算法，比直接计算节省了2次求逆。分析表明，在逆乘率分别大于7.4和5.9时，改进算法的效率优于逐次计算。

Abstract: Elliptic curve cryptography finds numerous applications because of its excellent and unique properties. This paper focused on the scalar multiplication of Elliptic curve. We proposed the recursion formula to compute over based on the idea of trading inversions for multiplications, which reduced the inversion to only once. At the same time, this paper also gave an ac- celerated algorithm for computing , which saved two inversions compared to computing it directly. The result suggests that the proposed algorithms are more efficient than the normal al- gorithms when the ratios are more than 7.4 and 5.9 respectively.

1. 引言

1985年，椭圆曲线密码(ECC)由Miller[1] 和Koblitz[2] 等人分别独立提出。该密码体制一经提出便得到众多密码学研究专家的关注。ECC基于有限域中的离散对数难解问题(DL)，这使得在同样的安全性能下，ECC需要的密钥长度比RSA要短很多。

随着椭圆曲线密码的发展，快速实现成为学着们研究的重点。椭圆曲线的运算分为上层算法和底层算法，其中，上层加速算法是针对椭圆曲线上点的运算，即群的计算；底层算法是针对底层有限域上为实现点之间的运算而做的乘法、求逆、平方等运算。很明显，为了达到更好的计算效率，需要结合上层域以及底层域计算展开改进。这也是椭圆曲线加速算法的一个研究趋势。

在椭圆曲线密码体制中，核心运算就是椭圆曲线的标量乘的运算，它是椭圆曲线密码体制快速实现的关键。在标量乘运算中求逆的耗时是乘法的8倍[3] ，用适量的乘法代替求逆可以明显的提高计算的效率。利用此思想，Guajardo等人[4] 提出了上直接计算、、的算法。Sakai等人[5] 在Guajardo的基础上推导了上的递推公式。Ciet等人[6] 提出了仿射坐标下直接计算的算法，将求逆次数减少到2次。刘连浩等人[7] 在Ciet等人的基础上提出了另一种在仿射坐标系下计算的方法，将求逆次数减少到了1次。

本文首先介绍了椭圆曲线的背景知识，包括定义分类以及椭圆曲线上点的运算法则；其次采取了用乘法替代求逆的方法推导了仿射坐标系下上的递推公式；最后结合Ciet以及刘连浩等人的方法，提出了上另一种计算的方法。

2. 背景知识介绍

2.1. 椭圆曲线的定义及分类[1] [2]

由代数几何学可知，椭圆曲线(Elliptic Curve)在解析平面中表现为一条非奇异的三次平面曲线。一般来讲，椭圆曲线有如下形式的Weierstrass方程：

(1)

(1) 式中的域为有限域，。该方程的所有解连同无穷远点组成的集合E 称为椭圆曲线，记为。

对于任意给定的一条椭圆曲线，总可以选取一组适当的变量代换式，使曲线在仿射坐标下的Weierstrass方程式具有更加简单的形式。本文讨论的是时的椭圆曲线上的算法，此时(1)式可被简化成

(2)

其中且。

在椭圆曲线底层域运算中涉及有加法、减法、乘法、平方、求逆五中运算，通常用、和分别表示求逆、乘法和平方，用表示逆乘率。其中，加法和减法相对其他三种运算来说，耗时可以忽略不计，所以通常不考虑加减法。求逆是最耗时的，一般，通常计[8] 。

2.2. 椭圆曲线上点的运算法则

设点和点是上的任意两个非零点，且，则点加公式以及倍点公式分别由(3)、(4)给出：

1) 点加

(3)

2) 倍点

(4)

其中点加的运算量为，倍点的运算量为。

3. 推导仿射坐标系下3P、的算法

3.1. 3P的推导过程

先算

再算

令

令，则

令

令

令

总共需要计算的量如下：

此过程将计算2次求逆减少为只计算1次求逆，即计算的逆。其计算复杂度为，相比于直接计算的，增加了，这样是为了之后的推导。

3.2. 9P的推导过程

上一部分我们已经计算出了，下面我们计算

令

令

令

令

在上述计算过程中，我们抵消了和，这样是为了在之后的递推计算中减少计算量。其计算复杂度为，比直接计算所需的，增加了，但减少了3次求逆，在逆乘率时，此算法比直接计算有效。

3.3. 27P的推导过程

下面用同样的方法计算，需要计算的量如下：

其计算复杂度为，比直接计算所需的，增加了，但减少了5次求逆，在逆乘率时，此算法比直接计算有效。

3.4.的推导过程及算法性能比较

由之前的推导，我们可以得出计算的递推公式如下：

在此递归过程中，先计算当时的，计算复杂度为。此后步每次需增加，最后还需计算，需要，故总的计算复杂度为：

与此同时，直接计算需要。具体递归过程计算量可见表1。我们可以看到当趋于无穷大且时，此算法比直接计算有效。

4. 改进的算法

文献[7] 中利用求最小公倍数的方法将计算时的3次求逆减少到1次。本文通过同样的方法推导上的改进算法。

先给出一般的计算方法。设点和点是上的任意两个非零点，计算。

先算，运算量为

再算，运算量为

Table 1. The comparison of the improved algorithm and the direct calculation

表1. 改进算法与直接计算的效率比较

再算，运算量为

改进方法如下：

设，，

则，，，以及，已知，下面计算，和。

设

将上式代入得

为了减少求逆次数，我们取、、的最小公倍数，设，则

，，

由于还是未知，接下来计算。

将代入得：

最后根据和计算出。

由于的计算中还含有，将代入得

故在整个计算过程中所有需要计算的量有：

直接按公式计算，需要的计算量为，经过算法改进后，将3次求逆转换为1次求逆，所需要的计算量为，虽然增加了11次乘法和1次平方，但减少了2次求逆，在时，此算法比直接计算有效。

5. 结束语

本文利用了转换求逆为乘法和求取最小公倍数的方法，研究了特征为2的域上计算的递推公式，当趋于无穷大且时改进的算法比直接计算效率更高。利用同样的原理，结合Ciet以及刘连浩等人的方法，推导了计算的方法，在时，改进的算法比直接计算有效。由于在椭圆曲线标量乘中，通常大于8，所以本文的改进算法是有效的。

另外，多基链MBNS作为的有效表示是高度冗余的，可以减少标量乘中的上层运算。将MBNS和本文提出的改进算法相结合将是我们进一步研究的方向。

致  谢

在本论文的写作过程中，我的导师周梦老师倾注了大量的心血，从构思选题到开题报告，再到一遍又一遍地修改每稿中的具体问题，他都给了我极大的支持与帮助，在此我表示衷心感谢。同时我还要感谢国家自然科学基金NSFC 11271040 资助项目的支持，以及在我学习期间给我极大关心和支持的各位老师和朋友。

项目基金

国家自然科学基金 NSFC 11271040资助项目。