Edwards曲线安全快速标量乘法运算算法——EDSM.doc

第10期张宝华等：Edwards曲线安全快速标量乘法运算算法EDSM81Edwards曲线安全快速标量乘法运算算法EDSM张宝华1，殷新春2，张海灵2（1. 复旦大学 计算机科学技术学院，上海 200433；2. 扬州大学 信息工程学院，江苏 扬州 225009）摘 要：对Edwards曲线上标量乘法的安全及快速算法进行研究，首先提出新的倍点及点加公式，分析表明，其运算效率优于Edwards曲线上的已有公式；其次给出一种新的安全快速的标量乘法运算算法EDSM算法；最后将EDSM算法与改进的Montgomery算法以及已有的安全快速算法在安全性和效率上进行比较，结果表明，EDSM算法在运算效率方面和安全性方面均有显著的提高。关键词：椭圆曲线；Edwards曲线；标量乘法；旁门攻击；Montgomery方法中图分类号：TP309.7 文献标识码：A 文章编号：1000-436X(2008)10-0076-06EDSM: secure and efficient scalar multiplication algorithm on Edwards curvesZHANG Bao-hua1, YIN Xin-chun2, ZHANG Hai-ling2(1. School of Computer Science, Fudan University, Shanghai 200433, China;2. Institute of Information Technology, Yangzhou University, Yangzhou 225009, China)Abstract: Investigate the secure and efficient algorithm for scalar multiplication on Edwards curves. First, several new addition and doubling formulas were proposed. Analysis shows that our new formulas are more efficient than existed formulas. Then a new scalar multiplication algorithm was forwarded, called EDSM algorithm. Finally, our EDSM algorithm with the improved Montgomery method and other existed secure and efficient algorithms were compared. Experimental results show that our EDSM (scalar multiplication on Edwards curve) algorithm make great improvements in aspects of efficiency and security.Key words: elliptic curve; Edwards curve; scalar multiplication; side-channel attacks; Montgomery method1 引言收稿日期：2008-06-02；修回日期：2008-10-06基金项目：国家自然科学基金资助项目（90607005）；国家高技术研究发展计划（“863”计划）基金资助项目（2007AA012448）；江苏省六大人才高峰项目（06-E-025）Foundation Items: The National Natural Science Foundation of China (90607005); The National High Technology Research and Development of China (863 Program)( 2007AA012448); The Six Scientific Fields Summit of Jiangsu Province (06-E-025)标量乘法运算是椭圆曲线密码体制的关键运算，其速度及安全性直接影响到椭圆曲线密码体制的有效实现。许多年来，人们致力于研究椭圆曲线的各种形式，寻求具有快速、安全特点的标量乘法运算。1985年，Miller1给出了椭圆曲线的Jacobian形式：Y2 = X3+a4XZ2+a6Z6，其上的点 (X:Y:Z)对应于椭圆曲线一般形式y2 = x3+ax+b上的点(x/z2, y/z3)，该曲线上的标量乘法运算若采用NAF2算法，平均每比特需要的计算量是3.33M + 9.33S + 1D，其中，M表示乘法运算，S表示平方运算，D表示乘以a4的运算。考虑安全性，假设在能够抵抗简单能量分析(SPA, simple power analysis)攻击的前提下，若采用固定窗口算法，平均每比特需要的计算量是4.59M + 9.36S + 0.99D。此后，人们研究了大量的椭圆曲线形式，如Weierstr-ass form3、Jacobi intersection4、Hessian5、Jacobi quartics6、Montgomery7和Doche/Icart/Kohel8等，并分析了其上运算的效率以及安全性。2007年，Edwards9提出了一种新的椭圆曲线形式x2+y2 = c2(1+dx2y2)，该曲线的主要优势是其上的群运算规则较简单，且倍点和点加运算具有相同的公式。文献10对Edwards曲线上的群运算进行详细的分析，研究表明Edwards曲线群运算的效率及安全性均优于Jacobian等其他形式的椭圆曲线。本文侧重于对Edwards曲线上的标量乘法的安全快速实现进行研究。2 Edwards曲线及SCA攻击概述2.1 Edwards曲线2007年，Edwards中提出了域k上的一种新的椭圆曲线形式，其定义如下x2+y2 = c2(1+dx2y2)(1)其中，且cd4 ，称为Edwards曲线。研究表明，任何特征值不为2的域上的椭圆曲线均双有理等价于该域或其扩域上的Edwards曲线。以Montgomery形式曲线Curve25519:v2= u3+486662u2 +u mod p为例(其中，p = 225519)，该曲线双有理等价于域Z/p上的Edwards曲线：x2+y2 =1+(121665+ 121666)x2y2，具体内容请参见文献10。2.2 旁门信道攻击椭圆曲线密码体制被广泛应用于智能卡等设备，研究表明，这些设备易受到诸如时间攻击(time attack)11、能耗分析(power analysis)12等SCA攻击。SCA攻击通过精确测量密码设备执行密码操作（如智能卡上签名的生成）所用的时间或能耗轨迹，从而推断出密钥的比特信息。SCA攻击主要分为两类：简单能量分析、差分能量分析(DPA, differential power analysis)13。一般而言，抵抗SPA的防御措施都可通过随机化等方法转变为抵抗DPA的措施14，简略起见，本文所讨论的安全性主要是针对SPA攻击。3 Edwards曲线的群运算法则的研究Edwards曲线上具有如下群运算规则，令P1 = (x1 , y1)和P2 = (x2 , y2)为方程(1)定义的Edwards曲线上的点，令P3 = (x3 , y3) = P1+P2，点加公式如下(2)其中，点(0,c)是单位元，P1 = (x1 , y1)。值得注意的是，当P1 = P2时，公式（2）仍然成立，即Edwards曲线上的倍点运算与点加运算具有相同的公式，符合抵抗SPA防御措施的第二条线索，因此Edwards曲线上的运算具有良好的安全性，这也是Edwards曲线的魅力之一。在下面的分析中， M、S、D定义如前，C表示乘以c的运算，a表示加法或减法运算。为了避免求逆运算，采用标准投影坐标形式。令Edwards曲线E:(X2+Y2)Z2 = c2(Z4+dX2Y2)，其上的(X1:Y1:Z1)对应于仿射坐标下的点(X1/Z1,Y1/Z1)，Z10。令P1 = (X1:Y1: Z1)，P2 = (X2:Y2:Z2)，则P3 = P1+P2 = (X3:Y3:Z3)，其中：X3 = Z1Z2(X1Y2+X2Y1)(Z12Z22-dX1X2Y1Y2)Y3 = Z1Z2(Y1Y2-X1X2)(Z12Z22+dX1X2Y1Y2) Z3 = c(Z12Z22-dX1X2Y1Y2) (Z12Z22+dX1X2Y1Y2)此时，计算X3,Y3, Z3需要10M + 1S +1C +1D +7a。上述公式当P1 = P2时仍然成立，考虑到效率，用(x12+y12)/c代替c(1+dx12y12)，并将(x12+y12)/c 改写为(2c2( x12+y12)/c，上述公式可转变为： X3 = c(X1+Y1)2X12Y12)(X12+Y122(cZ1)2)Y3 = c(X12+Y12)(X12Y12)Z3 = c(X12+Y12) (X12+Y122(cZ1)2)此时，计算X3,Y3, Z3需要3M + 4S + 3C + 6a。详情请参见文献10。为了提高Edwards曲线上倍点和点加运算的效率，给出式(3)、(4)和(5)。式(3)给出了x- coordinate- only的点加公式，x-coordinate-only思想最早由Montgomery提出，他给出了Montgomer- y曲线上的仅依赖于x坐标的群运算公式，由于不需要计算点的y坐标，从而提高了运算的速度。式(4)和式(5)分别给出了y-coordinate-only的点加及倍点公式。令P1 = (X1:Y1:Z1)，P2 = (X2:Y2:Z2)，P3 = P1+P2 = (X3:Y3:Z3)，P3=P1-P2=(X3:Y3:Z3)，若按照X坐标计算，有(3)即假设初始值X1、Z1、X2、Z2、X3、Z3存放在寄存器A、B、C、D、E、F中，具体实现如下 A = A2 B = B2 C = C2 D = D2G = ADBC H = CDdABA = FG B = EH最后寄存器A和B 输出的值即为X3和Z3，计算过程中还需要用到2个额外寄存器G和H。此时，计算X3、Z3需要计算量 6M + 4S + 1D + 2a，若令Z3 = 1，则需要5M + 4S + 1D + 2a。同理，若按照Y坐标计算，有(4)即假设初始值X1、X2、Z1、Z2、X3、Z3存放在寄存器A、B、C、D、E、F中，具体实现如下A = A2 B = B2 C = C2 D = D2G = AD+BC H = CD+dABI=c2G A = F(I-G) B = E(H-c2dG)最后寄存器A和B 输出的值即为Y3和Z3，计算过程中还需要用到2个额外寄存器G和H 。此时，计算Y3、Z3需要 6M + 4S + 1C + 1D + 6a，若令Z3 = 1，则需要5M + 4S + 1C + 1D + 6a。令P4 = 2P1 = (X4:Y4:Z4)，按照Y坐标计算，有(5)假设初始值X1、Z1放在寄存器A和B 中，具体实现如下A = A2 B = B2 C = dA2 D = 2AB B = B2 A = c2 (BC)A = AD B = c(B+Cc2dD)最后寄存器A和B 输出的值即为Y4和Z4，计算过程中还需要用到2个额外寄存器C和D。此时，计算Y4、Z4需要 1M + 4S + 3C + 2D + 4a。在许多椭圆曲线密码协议中，点加运算仅使用x坐标，则式(3)比较适用。式(4)和式(5)可用来构建新的标量乘法运算算法，称之为y-coordinate-only算法，算法如下。输入：m和P，n为m的二进制表示位数输出：mP1) Q0=P，Q1=2P2) For i = n-2 downto 0 do3) If mi = 0 then4) Q0=2Q0，Q1= Q0+ Q15) else6) Q0= Q0+ Q1，Q1=2Q17) 返回Q0其中，步骤4)和步骤6)均采用本文提出的式(4)和式(5)。最后可通过式(6)恢复点mP的x坐标。假设y-coordinate-only算法最后输出的Q0 = (x1, y1)，Q1 = (x2, y2)，且P3=(x3,y3)=Q1Q2，即已知坐标x3、y3、y1、y2，根据公式（2），易得(6)为方便起见，在后面的讨论中，由于C和a的运算量较M、S和D等运算通常可以忽略不计，在后面的讨论中将其忽略。表1给出了Edwards曲线上各种基本运算计算量的比较，其中，reADDs表示重复加法，常用于固定窗口算法和滑动窗口算法中，Mixed addition表示混合坐标加法，即假定其中一个点的Z坐标等于1，Unified addition表示点加与倍点采用相同的公式，Addition(x-coordinate)即采用本文提出的公式(3)，Addition(y-coordinate)、Doubling (y-coordinate)即采用本文提出的式(4)和式(5)。结果表明，本文给出的公式在效率上有明显的提高。表1 Edwards曲线上点加和倍点运算的计算量操作计算量Addition10M + 1S +1DreADDs10M + 1S +1DMixed addition9M + 1S +1DDoubling3M + 4SUnified addition10M + 1S +1DAddition(x-coordinate)6M + 4S +1DAddition(x-coordinate) (Z=1)5M + 4S +1DAddition(y-coordinate)6M + 4S + 1DAddition(y-coordinate) (Z=1)5M + 4S + 1DDoubling(y-coordinate)1M + 4S + 2D4 基于Edwards曲线的EDSM算法4.1 算法概述本节提出一种新的标量乘法运算算法EDS- M(scalar multiplication on Edwards curve)。输入m和P，其中，m为域k上的任意整数，P为Edwards曲线上的点。将m表示成3进制的形式，即m=ml-1ml-2m1m0，其中，mi0,1,2。EDSM算法：1) Q0 = ml1P，Q1 = (ml1+1)P2) 3) ，parallel do 4) Q0= 2Q0+ Q25) Q1= 2Q1+ Q3 6) 返回Q0定理1 EDSM算法输入m和P后，其输出Q0即为mP的值。证明当l = 1时，Q0 = m0P，For循环语句不执行，结论显然成立。当l = 2时，即m = m1m0 = m13+m0，初值Q0 = m1P，Q1 = (m1+1)P。For循环语句一次，即i = 0，mi = m0 有三种情况。1) 若m0=0，则，Q0 = Q4 = m1P；执行parallel do语句，有：Q0=2Q0+Q2 = 2m1P+m1P = 3m1P，Q1=2Q1+Q3=2m1P+(m1+1)P = (3m1+1) P；最后输出Q0 = 3m1P，成立；2) 若m0 = 1，则，Q0 = Q4 = m1P；执行parallel do语句，有：Q0=2Q0+Q2= 2m1P+ (m1+1)P =3m1P+P，Q1=2Q1+Q3=2(m1+1) P+m1 P= 3m1P+ 2P；最后输出Q0 = 3m1P+P，成立；3) 若m0=2，则，Q0=Q4=(m1+1)P；执行parallel do语句，有：Q0= 2Q0+Q2 = 2(m1+1)P+ m1P=3m1P+2P ，Q1= 2Q1+Q3= 2(m1+1)P+(m1+1)P = 3m1P+3P；最后输出Q0 = 3m1P+2P，成立。现假设当l = k时成立，求证l = k+1时是否成立。当l = k+1时，即m = mkmk-1m1P，根据假设，For循环执行k次后输出Q0 = mkmk-1m1P，Q1 = (mkmk-1m1+1)P 。同理，当i = 0，m0有三种情况，即等于0、1或2，采用如上方法易验证，不论m0为何值，最后输出的Q0即为mkmk-1m1m0P的值。因此，当l = k+1时成立。综上，根据归纳假设法，定理1成立。证毕。值得注意的是，EDSM算法中步骤5)和步骤6)不具相关性，因此在智能卡等硬件设备上较易并行实现，即循环体内实际需要的计算量仅为1次倍点和1次点加运算。4.2 效率分析以步骤4)为例，首先进行一次倍点运算2Q0和一次点加运算2Q0+Q2，为了表示清楚，用Q4 = 2Q0 和Q5 = Q4+Q2 代替原来的式子以区分等号左右两边的Q0，最后Q0的值即为Q5。计算过程如下：X4 = c(X0+Y0)2-X02-Y02)(X02+Y02-2(cZ0)2)Y4 = c(X02+Y02)( X02+Y02)Z4 = (X02+Y02) (X02+Y02-2(cZ 0)2)X5 = Z2Z4(X2Y4+X4Y2)(Z22Z42-dX2Y2 X4Y4)Y5 = Z2Z4(X2Y4- X2X4)(Z22Z42+dX2Y2 X4Y4)Z5 = c(Z22Z42-dX2Y2 X4Y4) (Z22Z42+dX2Y2 X4Y4)设有寄存器R1、R2、R3、R4、R5、R6、R7、R8，其中，R1、R2、R3分别存储X0、Y0、Z0的值，R4、R5、R6分别存储X2、Y2、Z2的值，下面给出具体实现过程，最后寄存器R1、R2、R3存储的是Q5的坐标值。R7R1+R2；R3cR3；R1R12；R2R22；R3R32；R7R72；R3R3+R3；R8R1+R2；R2R1R2；R7R7R8；R3R8R3；R1R3R7；R3R3R8；R2R2R8；R1cR1；R2cR2；R3R3R6；R7R1+R2；R8R4+R5；R1R1R4；R2R2R5；R7R7R8；R7R7R1；R7R7R2；R7R7R3；R8R1R2；R8dR8；R2R2R1；R2R2R3；R3R32；R1R3R8；R3R3+R8；R2R2R3；R3R3R1；R1R1R7；R3cR3。易知，上述过程共需计算量13M + 5S + 1D，即EDSM算法循环语句执行一次需要的计算量。以下的讨论中，假定m的二进制表示长度l = 256，则其三进制表示长度l= (log2/log3)l162，若l=162，则EDSM算法平均每比特的计算量为(9M+1S+1D)+(3M+4S)+(1622)(13M+5S+1D)/256 8.17M+3.15S+ 0.63D。4.3 安全性分析EDSM算法中，For循环语句中的指令（步骤4）、5）不依赖于秘密信息m的具体比特位的值，因此EDSM算法对于SPA等攻击是安全的。5 算法比较标量乘法运算算法，著名的有固定窗口算法、带符号的滑动窗口算法以及Montgomery方法等算法，这些算法均可与抵抗SPA攻击的措施（统一的点加及倍点公式、原子化方法15等）结合使用，从而转变为安全的标量乘法运算算法。其中， Montgomery方法需结合本文提出的公式(4)和(5)才可应用到Edwards曲线上的标量乘法运算中去，称之为改进的Montgomery方法。表2给出基于Edwards曲线这些算法是否能够抵抗错误消息攻击、是否需要额外的存储开销以及预计算等方面的比较，可以看出，固定窗口算法和滑动窗口算法均需要额外的存储开销以及预计算，而改进的Montgomery方法和EDSM算法则不需要额外的存储开销和预计算，另外，由于原子化方法添加伪操作，易受到错误消息的攻击并泄露秘密消息的Hamming重量，而固定窗口算法、改进的Montgomery方法和EDSM算法能够抵抗错误消息的攻击，安全性更高。表2 Edwards曲线上各种标量乘法算法的安全性、存储开销及预计算的比较算法抵抗错误消息攻击额外的存储开销预计算固定窗口算法抵抗需要需要滑动窗口算法（统一公式）抵抗需要需要滑动窗口算法（原子化方法）不抵抗需要需要改进的Montgomery方法抵抗不需要不需要在安全性相当的前提下，本文给出基于Edwards曲线各种算法平均每比特的计算量的比较，如表3所示，其中，所有点加运算无特殊说明均采用混合加法算法，表中最后三列比例表示(S,D)相对于M的比例，即(1,1)表示1S=1M，1D=1M，(0.8,0.5)表示1S=0.8M，1D=0.5M，(0.8,0)表示1S= 0.8M，1D= 0M。假定固定窗口算法使用数字集1,2,3,8，大约需要l1.9次倍点运算和l/3+6次reADDs运算，即当l=256时，平均每比特需要254.1/256 0.99次倍点运算和91.4/256 0.36次reADDs运算。将该方法应用到Edwards曲线中标量乘法运算平均每比特的计算量为0.99(3M+4S) = 0.36(10M+1S+1D) = 6.57M+ 4.32S+ 0.36D。对于带符号的滑动窗口算法16，假定窗口宽度为4，采用统一的倍点和点加运算公式策略，则需要7l/6+2.5次点加/倍点运算，同理，当l=256时，将该方法应用到Edwards曲线去，标量乘法运算平均每比特的计算量为301.2/256(10M+1S+1D) = 11.8M+1.18S+1.18D。改进的Montgomery方法平均每比特的计算量为5.98M+7.96S+2.98D。表3 Edwards曲线上各种标量乘法算法每比特计算量的比较算法每比特计算量(1,1)(0.8,0.5)(0.8,0)固定窗口算法6.57M+4.32S+0.36D11.25M10.21M10.03M滑动窗口算法（统一公式）11.8M+1.18S+1.18D14.16M13.34M12.75M改进的Montgo-mery方法5.98M+7.96S+2.98D16.92M13.84M12.35MEDSM算法8.17M+3.15S+0.63D11.95M11.01M10.69M由表3可以看出，在安全性相当的前提下，本文提出的EDSM算法较固定窗口算法效率略低，优势是EDSM算法无需额外的存储开销以及预计算。较滑动窗口算法（统一公式），除无需额外存储开销及预计算外，在(S, D)比率为(1,1)、(0.8,0.5)和(0.8,0)的情况下速度分别提高了近15.6%、17.5%和16.2%。在安全性相当且都无需要额外的存储开销及预计算的情况下，EDSM算法较改进的Montgomery方法在(S, D)比率为(1,1)、(0.8,0.5)和(0.8,0)的情况下速度分别提高了近29.4%、20.4%和13.4%。6 结束语针对Edwards曲线，首先给出了其上的快速倍点及点加公式，然后提出了一种新的标量运算算法，最后详细比较了本文提出的算法与已有算法，研究表明，在安全性相当的前提下，本文提出的EDSM算法无需额外的存储开销和预计算，较滑动窗口算法（统一公式）在(S,D)比率为(1，1)、(0.8，0.5)和(0.8，0)的情况下速度分别提高了近15.6%、17.5%和16.2%，另外，在安全性相当以及都无需额外的存储开销的情况下，EDSM算法较改进的Montgomery方法在(S，D)比率为(1，1)、(0.8，0.5)和(0.8，0)的情况下速度分别提高了近29.4%、20.4%和13.4%。致谢：衷心感谢陈豪教授提出宝贵意见。参考文献：1MILLER V S. Use of elliptic curves in cryptographyA. Proceedings of the Advances in Cryptology-CRYPTO85C. New York: Springer, 1986, 417-426. 2ARNO S, WHEELER F S. Signed digit representations of minimal Hamming weightJ. IEEE Transactions on Computers, 1993, 42(8):1007-1010.3COHEN H, MIYAJI A, ONO T. Efficient elliptic curve exponentiation using mixed coordinatesA. Proceedings of the Advances in Cryptology- ASIACRYPT98C. Berlin: Springer, 1998. 51-65.4LIARDET P Y, SMART N P. Preventing SPA/DPA in ECC systems using the Jacobi formA. Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems-CHES 2001C. Berlin: Springer, 2001, 391-401.5JOYE M, QUISQUATER J J. Hessian elliptic curves and side-channel attackA. Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems-CHES 2001, LNCS 2162C. Berlin: Springer, 2001. 402-410. 6BILLET O, JOYE M. The Jacobi model of an elliptic curve and side-channel analysisA. Applied Algebra, Algebraic Algorithms and Error-Correcting CodesC. Berlin: Springer, 2003. 34-42. 7MONTGOMERY P L. Speeding the Pollard and elliptic curve methods of factorizationJ. Mathematics of Computation, 1987, 48(177): 243-264.8DOCHE C, ICART T, KOHEL D R. Efficient scalar multiplication by isogeny decompositionsA. Public Key Cryptography-PKC 2006C. Berlin: Springer, 2006. 191-206.9EDWARDS H M. A normal form for elliptic curvesJ. American Mathematical Society, 2007,44(3):393-422.10BERNSTEIN D J, LANGE T. Fast addition and doubling on elliptic curvesA. ASIACRYPT 2