特征3有限域上椭圆曲线的Montgomery算法.doc

第10期汪宏等：特征3有限域上椭圆曲线的Montgomery算法29特征3有限域上椭圆曲线的Montgomery算法汪宏1，李宝1，于伟2（1. 中国科学院 研究生院 信息安全国家重点实验室，北京 100049；2. 中国科学技术大学 电子工程与信息科学系，安徽 合肥 230026）摘 要：研究了Montgomery算法在特征3有限域上椭圆曲线的应用。根据Montgomery算法的结构，省去y坐标的计算，提出新的点加和倍点计算公式，加快点乘计算速度。经过理论分析和实验验证，提出的点加和倍点计算公式可节省约15%的运算时间。关键词：椭圆曲线；Montgomery 算法；GF(3m)；点乘中图分类号：TP3 文献标识码：A 文章编号：1000-436X(2008)10-0025-05Montgomery algorithm on elliptic curves over finite fields of character threeWANG Hong1, LI Bao1, YU Wei2(1. State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, Beijing 100049, China;2. Department of Electronic Engineering and Information Science, University of Science and Technology of China, Hefei 230026, China)Abstract: Application of Montgomery algorithm on elliptic curves defined over finite fields of character three was researched. Due to the structure of Montgomery algorithm, y-coordinate was ignored, a new formula to compute point addition and point doubling was proposed to accelerate the scalar point multiplication. According to theoretical analysis and experimental verification, new formula saves about 15 percent running time.Key words: elliptic curve; Montgomery algorithm; GF(3m); scalar multiplication1 引言收稿日期：2008-06-21；修回日期：2008-09-21基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311201）；国家高技术研究发展计划（“863”计划）基金资助项目（2006AA01Z427）Foundation Items: The National Basic Research Program of China (973 Program) (2007CB311201); The National High Technology Research and Development Program of China (863 Program)(2006AA01Z427)椭圆曲线密码是近年来密码学领域研究的热点之一，其具有密钥短、安全性高的特点。椭圆曲线密码学在应用中主要需要点乘的计算，即计算kP，其中P是椭圆曲线上的点，k是整数。椭圆曲线密码算法的效率很大程度上依赖于点乘效率。可以通过多种方法加快点乘速度，例如可以通过对k展开的优化使得点乘中加法次数减少，以提高运算效率，这方面的代表算法有最优带符号二进制表示、adic表示、双基表示等15；还有就是提出的新的算法，比较典型的有窗口算法、梳子算法、Montgomery 算法等2, 6；第3类是改变点的坐标表示，比较典型的坐标表示有仿射坐标、标准射影坐标、Jacobi坐标等。采用最优带符号二进制表示如NAF在不增加任何预计算的情况下能够大大加快点乘的计算速度，但却与使用二进制表示的基本算法一样不能抵抗简单能量攻击7。1987年，Montgomery6提出了一种能够抵抗简单能量攻击的算法。其基本思想是在算法中每个循环均有一个加法和倍点运算，以使每个循环中运算消耗的能量基本相同，称为Montgomery算法。由于Montgomery算法增加了点加运算，因此计算速度较慢。1999年，Lopez J.和Dahab R.在上的椭圆曲线上对Montgomery算法做出了优化8，给出优化的Montgomery算法计算点加和倍点的新公式，省去y坐标的计算，大大提高了算法的计算速度。本文主要基于Montgomery算法以及Lopez J和Dahab R.的思想，对椭圆曲线上的Montgomery 算法给出一种新的加法和倍点公式，使得用新的点加和倍点公式优化后的Montgomery算法的速度比原Montgomery 算法的速度有了明显提升。本文的主要内容安排如下：第2节是椭圆曲线基本概念及Montgomery算法的介绍；第3节对特征3域椭圆曲线上Montgomery 算法给出了新的优化结果；第4节是对优化后的算法效率和实验验证；第5节是结束语。2 椭圆曲线及Montgomery算法定义1 定义在域K上的椭圆曲线E的方程为(1)其中，,且,是E的判别式。式（1）称为椭圆曲线的Weierstrass 方程。Weierstrass方程在不同的特征下可以被简化为不同的方程式。当域K的特征时，式（l）可简化为(2)其中，, 。当域K的特征p=2时，非超奇异的椭圆曲线的方程为(3)其中，且。当域K的特征p=3时，非超奇异的椭圆曲线的方程为(4)其中，。定义在域K上的椭圆曲线E的所有点的集合称为E(K) , E(K)并上一个无穷远点O构成一个交换群，群上的运算法则由“弦切律”定义。例如对于特征为3 域上的椭圆曲线，由式（4）的解连同一个无穷远点O组成。其中,。在的元素之间有一个运算法则能使E构成一个有限加法群，其中无穷远点O是这一加法群的单位元。使用Weierstrass形式的椭圆曲线方程时，点的加法和倍点是2种不同的公式，因此点的加法和倍点运算消耗的能量有着明显的区别。而使用二进制表示计算点乘kP时，算法中每个循环均有倍点运算，而当二进制位为l 时，有加法运算；当二进制位为0时，无加法运算。简单能量攻击可以通过检测算法执行过程中能量的消耗而分析出k 的二进制信息。抵抗简单能量攻击有2种基本方法：在算法的每个循环中均有一个加法和倍点运算；加法和倍点采用统一的计算公式。Montgomery采用第一种方法抵抗简单能量攻击，其基本做法是在每个循环中都做一个点加和倍点运算。算法如下所示。算法1 Montgomery 算法输入：点及整数输出：while do if then else return 在文献8中，Lopez J.和Dahab R.对有限域上的椭圆曲线的Montgomery 算法进行了优化，在每个循环中省略了点的y坐标的计算，只在最后一步恢复y坐标，减少了计算量。其点加和倍点的计算公式如下：(5)最后一步恢复y坐标的公式为(6)文献7采用标准射影坐标避免求逆运算，比采用仿射坐标速度更快。标准射影坐标，。则点加和倍点的计算公式变为：当时(7)当时(8)y坐标计算公式为 (9)用LOPEZ J和DAHAB R提出的新的点加和倍点公式计算Montgomery算法具有很快的速度。Okeya和Sakurai9把以上思想推广到特征大于3的Montgomery形式的椭圆曲线。下面给出特征为3域上的Weierstrass方程上对Montgomery 算法的优化。3 特征3域上椭圆曲线的Montgomery优化算法本节对特征3域上的椭圆曲线的Montgomery 算法进行优化。定义于上的非超奇异椭圆曲线(non-supersingular elliptic curve)的方程为 。的群运算法则可描述如下。若，。设 ，定义，则(10)(11)下面根据Montgomery 算法的特殊结构和有限域特征为3的特点提出新的点加和倍点的计算公式。引理1 设， 。其中。则的坐标可由如下公式决定：(12)证明 当时，由式(10)知将两式相加得由于域的特征为3，则有又,。分别代入上式得因域的特征为3，则等式变为，则当时，由最后得x3表达式以下引理由引理1中给出的坐标计算坐标。引理2 设，且。则的y坐标可由如下公式恢复(13)证明 当时，又,代入得：，当时，即有。注意到Montgomery 算法的每个循环中总是有一个点乘和倍点运算，因此当采用仿射坐标时，可以先将式（12）中的分母通分，可以减少l个求逆，同时增加3个域上乘法，由于3个乘法运算的开销小于l个求逆运算，使用这种方法将提高算法运算速度。改造后的公式如下：(14)下面基于引理1和引理2中新的点加和倍点公式，给出椭圆曲线的仿射坐标下的新的Montgomery 点乘算法算法2 上椭圆曲线Montgomery点乘输入：点及整数 。输出：,while do if then, else, ,return 。使用标准射影坐标，可以进一步减少算法中的求逆运算，使得新算法的速度加快。标准射影坐标,其中,P的标准射影坐标为。代入式(12)、式(13)得(15)(16)(17)利用引理1和引理2以及式(15)、式(16)、式(17)，采用标准射影坐标的新算法如下。算法2 上椭圆曲线Montgomery点乘输入：点及整数 .输出：, ,while do if then, , else, , ,return 4 算法效率分析采用文献10中Smart和Westwood给出的定义在上的椭圆曲线作为测试曲线，曲线方程为：(18)其中，b=Ox5C6A21D1BF0967068295B8EAA7253 DD2BD7A72。椭圆曲线的阶为=3636268544ll3594235847488 l667l8l9384929l6322979。系数b按三进制展开对应多项式基表示。由于，所以式(18)中以为乘数的乘法不消耗时间，而b很大，这里将b 与域中元素相乘消耗的时间近似为一个普通乘法的时间。以I表示求逆，M 表示乘法，C 表示立方，S 表示平方。忽略域上加法运算的时间。由式（10）、式（11）知，普通点加需I + 2M + S，普通倍点需I + 2M + S。而由本文提出的改进后的采用仿射坐标的式（12），加法需I + 2M + S + C，倍点需I + M + S + C。则使用仿射坐标的原算法每个循环需2I + 4M + 2S ，而使用新公式的算法每个循环中需2I + 3M + 2S + ZC，同时减少了y 坐标的存储。若使用式（14），则只需I + 6M + 2S + 2C。当使用标准射影坐标时，算法2的每个循环只需13M + 2C + 2S。这里将与b相乘近似为一个乘法。本文用于测试的硬件平台为1096.728MHz Intel Pentium III、Cache Size 256KB 。操作系统是Fedora core4、linux kernel 2.6.11、编译器gcc4.0.0。计算数论函数库是LiDIA 2.2.0 ，多精度运算函数库是GMP 4.2.2 11。因为乘数的二进制权重对算法的运算时间没有影响，所以取定乘数k为OxA27A7DD357AAEB 3C7568FB1D ，随机选取曲线上1 000个点，作点乘取平均时间。本文测试了算法2、算法 2的平均时间，以及采用原始点加、倍点式(10)和式(11)的仿射和Jacobi坐标形式的Montgomery 算法，结果显示算法2具有最快的速度。上基本运算的平均时间为：乘法M为 1 157ms，立方C为1 584ms，逆运算I为10 121ms。C/M为1.37，I/M为8.75。平方S采用与乘法相同的算法，故看作等同于一个乘法。结果显示采用新的加法和倍点公式，特征3域上椭圆曲线的Montgomery算法比采用原始加法和倍点公式的Montgomery 算法的计算速度更快，由于算法2采用标准射影坐标，减少了求逆运算，因此速度是所有算法中最快的。5 结束语本文对GF(2m)上椭圆曲线的Montgomery 点乘算法进行了优化，使用新的点的加法和倍点公式，从而使得Montgomery算法比原算法的效率