计算Montgomery形式椭圆曲线上标量乘kP+mQ+lR的新算法

1、计算Montgomery形式椭圆曲线上标量乘kP+mQ+lR的新算法本研究得到国家自然科学基金资助项目90304014资助。刘铎清华大学计算机科学与技术系，北京，100084。Email: bat01戴一奇清华大学计算机科学与技术系，北京，100084。Email: dyq摘要：基于Montgomery形式椭圆曲线上的密码体制具有速度快、安全性高、形式简单和适于并行的优点，现在是椭圆曲线密码学研究的一个热点。但是对于在Montgomery形式的椭圆曲线上的标量乘的算法还长期停留在只能计算kP的阶段。Toru Akishita给出了计算kP+lQ的方法9，主要是为了解决协议中的问题。在本文中将这

2、个方法扩展到计算kP+mQ+lR的方法，这样不仅仅在一些协议中可以使用，而且也可以将基于预计算的SME算法13等应用到Montgomery形式的椭圆曲线上，加快标量乘的速度，同时达到抵抗计时攻击的效果。在文章的最后对于新的算法与传统的算法，在时间复杂度上做了一些比较。关键词：椭圆曲线；密码学； Montgomery形式椭圆曲线；标量乘中图分类号：TP391文献标识码：A1 简介椭圆曲线密码体制首先由Neal Koblitz1和Victor Miller2两人独立地提出，近来得到越来越广泛地关注，进行了很多算法和实际实现方面的研究。椭圆曲线的标准Weierstrass形式是（对于特征大于3的域）

3、，而Montgomery则引入了另一种形式的椭圆曲线3，并提出了一种和Weierstrass曲线上标量乘完全不同的计算方法，与原有的方法相比有如下的优点：它不需要预计算（原始的算法），所以可以在存储空间有限的条件下实现（例如智能卡等）；利于并行计算；它的运算时间可以认为是固定的，而不依赖于的Hamming重量等。而且在研究椭圆曲线上的标量乘的算法的同时，很多研究者6,12,17还独立地发现Montgomery算法3可以有效地抵抗计时攻击4。这更使得它成为现在椭圆曲线密码学中最热门的课题之一。Lopez与Dahab将Montgomery算法扩展到了特征为2的域上，并且提出了一个有恢复-坐标过程的

4、标量乘的算法6。Katsuyuki Okeya和Kouichi Sakurai给出了在特征不是2的有限域上的Montgomery形式椭圆曲线上的恢复y坐标的方法8。Katsuyuki Okeya、Hiroyuki Kurumatani和Kouichi Sakurai对于Montgomery-形式椭圆曲线和Weierstrass-形式椭圆曲线之间的相互转化进行了研究5。他们给出了具有Montgomery-形式的椭圆曲线的充要条件，还提出了一个选取阶恰好是4光滑的Montgomery曲线的算法。一些协议如ECDSA的验证部分需要计算。Katsuyuki Okeya和Kouichi Sakurai建

5、议先用普通的方法计算，再使用Montgomery的方法计算，并且恢复的y坐标，最后计算8。而Toru给出了一种类似Montgomery算法的方法直接计算9。在本文中，我们对于Toru的算法进行了扩展，使之可以用于计算。本文的组织形式是：在第二部分中，回顾了Montgomery曲线的定义和Montgomery的算法；在第三部分中提出了一个直接计算的类Montgomery算法；在最后一部分中对于新的算法和传统的方法作了一些比较。2 Montgomery形式的椭圆曲线和Montgomery算法2.1 Montgomery形式椭圆曲线的定义首先定义曲线的Montgomery形式：令为一个素数，为有个元

6、素的有限域，其中。对于，由下式定义的椭圆曲线称为一个Montgomery形式的椭圆曲线：上的有理点全体构成一个有限可换群，其无穷原点是，于是，在Weierstrass形式的椭圆曲线上的所有密码协议都可以应用到Montgomery形式的曲线上。2.2 Montgomery形式椭圆曲线上点的运算首先给出Montgomery形式的曲线上的点在仿射坐标下的点计算公式。令和为Montgomery形式椭圆曲线上的两个点，则点由下面公式给出：，其中。在仿射情况下，点加需要三次乘法、一次平方和一次求逆；点倍需要五次乘法、两次平方和一次求逆。接下来，令，并且记点的倍点为。则的坐标可由下面的公式不使用Y坐标而计算

7、3：l 点加公式，。l 点倍公式，。点加公式需要四次乘法、两次平方（当时可以减少一次乘法）；点倍公式需要三次乘法、两次平方（这时需要预先计算）。最后给出在射影坐标下点运算的公式：令和为Montgomery形式椭圆曲线上的两个点，则点由下面公式给出：l 点加公式：，。共用15次乘法，2次平方。l 点倍公式：，共用12次乘法，6次平方。2.3 Montgomery形式椭圆曲线上标量乘的算法使用Montgomery算法计算标量乘的过程是：首先要计算，然后根据n的二进制表示的每个比特是0还是1来决定由计算还是。例如要计算，具体计算的过程是：从上面的例子可以看出，除了计算一共用了9次点加和点倍。一般的讲

8、，计算，一共需要次点倍和次点加。而且计算次数是只依赖于n的比特长度而不依赖于n具体的二进制表示的。2.4 Montgomery形式椭圆曲线上恢复y坐标的算法对于某些协议，比如建立密钥方案ECDH以及签名产生ECDSA-S7，只是需要的x坐标，如上的Montgomery算法是足够的。但是对于其他的一些协议，例如ECDSA的验证、ECSVDP-MQVC、ECVP-NR和ECVP-DSA7都还需要标量乘的y坐标。于是我们在使用Montgomery算法计算了之后，还需要恢复出来的坐标。在下面就给出恢复y坐标的方法。假设有Montgomery形式椭圆曲线上的点，且有。则这需要五次乘法、一次平方和一次求逆

9、。（另外这时候需要和的仿射坐标，由射影坐标得到和的仿射坐标还需要两次求逆和两次乘法）。当使用射影坐标时，令，为Montgomery形式曲线上的点，定义：，。则有。这共需要十二次乘法和一次平方。再得到仿射坐标还需要一次求逆和两次乘法。另外Katsuyuki Okeya and Kouichi Sakurai中还给出了另外一种计算的方法，采用了不同的思路，但是需要十三次乘法和一次平方8。3 计算Montgomery-形式曲线上 为下文叙述的简便，我们用表示。令、和是、和的二进制表示，并令、，我们的目的即是计算。定义：令为一个0-1向量，定义：；。定义：令， 。则可以由计算出来，最后可以由计算，最后

10、如果需要恢复y坐标的话再计算并恢复y坐标。易于验证，可以写成：则由计算的具体方法是：，。在进行这个算法之前需要预先计算、。这样每一次由计算需要五次点运算（一次点加四次点倍或者五次点加）。可见只在计算是才会被使用到，于是若中不包含，则在中不需要计算。而当且仅当。这种情况的概率可以认为是，于是每一个循环的点运算次数实际上可以认为是：。4 结论与算法复杂度比较由第三节中提出的算法计算的过程是：先计算，然后进行次循环，最后计算两次点运算得到和（如果不需要恢复y坐标，则之需要算一个点），共需要：次点运算。预计算部分，我们建议使用“Montgomery的法术”，这样可以用计算个数的逆(具体的计算过程可以参

11、见Cohen著作中的描述)。先由计算，共用：（注意到计算和时只需要求一次逆）。再计算，这用，于是在预计算部分共用。对于恢复y坐标，在时候，应该使用由射影坐标恢复Y，再得到仿射坐标的方法，共用。最终的时间复杂度是：如果使用的是Montgomery的方法单独计算，再相加并恢复y-坐标，则总的时间复杂度是：。假定：，12，我们给出上述的诸运行时间：计算标量乘的域中运算次数（以下表示n的比特数目运算次数都转化为域中乘法）128 bit256 bit512 bit2845.455568.65811015.13620.2715314218.621.4%22.1%22.5%表1 新旧算法运算次数的比较可以看

12、到与传统的方法相比计算，新的算法都提高了20%以上，说明这个算法是有实际的优势的。另外，在实际的应用中，很多时候预计算是可以通过一次计算而多次使用的，这时候预计算的时间复杂度便可以忽略不计，新算法的提高将更为可观。而且，这个算法可以应用到SME算法13 §14.88上，假定要计算（长度为bit），将分为长度为的三段，即：，令，则可以用来计算。另外，这个方法是具有可扩展性的，可以扩展到计算，乃至，这个算法将在后续的工作中进行具体的描述。参考文献1 Koblitz,N., Elliptic curve cryptosystems, Mathematics of computation v

13、ol.48， pp.203-209, 19872 Miller,V., Uses of elliptic curve in cryptography, In CRYPTO85, Lecture Notes in Computer Science, LNCS218, pp.417-426, Springer-Verlag, 19863 Montgomery,P.L., Speeding the Pollard and elliptic curve methods of factorizations, Mathematics of computation. vol.48, pp.243-264,1

14、9874 Kocher,C., Timing attacks on implementations of Diffle-Hellman, RSA, DSS, and other systems, CRYPTO96, LNCS1109, Springer-Verlag,， 19975 Katsuyuki Okeya, Hiroyuki Kurumatani, and Kouichi Sakurai, Elliptic curves with the Montgomery-form and their cryptographic applications, PKC2000, pp.238-257,

15、 Springer-Verlag, 20016 Julio Lopez and Ricardo Dahab, Fast multiplication on elliptic curves over GF(2m) without precomputing, CHES99, LNCS 1717, pp.316-327, Springer-Verlag, 20007 IEEE P1363 Standard specifications for public-key cryptography8 Katsuyuki Okeya and Kouichi Sakurai, Efficient ellipti

16、c curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve, CHES2001, LNCS2162, pp.126-141, Springer-Verlag, 20029 Toru Akishita, Fast Simultaneous scalar multiplication on elliptic curve with Montgomery form, SAC2001, LNCS 2259

17、, pp.255-267, Springer-Verlag, 200210 H.Cohen, A course in computational algebraic number theory, GTM138, Spring-Verlag, 199311 National Institute for Standards and Technology, Recommended elliptic curves for federal government use.12 Lim, C.H. and Hwang, H.S., Fast implementation of elliptic curve

18、arithmetic in GF(pm), PKC00, LNCS1751, pp.405-421, Springer-Verlag, 2001Boca Raton,1997The Algorthm of Computing kP+mQ+lR on a Montgomery-Form Elliptic CurveLIU Duo， DAI YiqiThe Department of Computer Science and Technology, Tsinghua University, Beijing, 100084,Abstract: Montgomery-form elliptic cryptology is more quick and secure than the traditional public key cryptosystems. It is also fit to be implemented in parallel. So it is a hot spot of cryptographic research