1、計算Montgomery形式橢圓曲線上標量乘kP+mQ+lR的新算法本研究得到國家自然科學基金資助項目90304014資助。劉鐸清華大學計算機科學與技術系，北京，100084。Email: bat01戴一奇清華大學計算機科學與技術系，北京，100084。Email: dyq摘要：基于Montgomery形式橢圓曲線上的密碼體制具有速度快、安全性高、形式簡單和適于并行的優(yōu)點，現在是橢圓曲線密碼學研究的一個熱點。但是對于在Montgomery形式的橢圓曲線上的標量乘的算法還長期停留在只能計算kP的階段。Toru Akishita給出了計算kP+lQ的方法9，主要是為了解決協(xié)議中的問題。在本文中將這

2、個方法擴展到計算kP+mQ+lR的方法，這樣不僅僅在一些協(xié)議中可以使用，而且也可以將基于預計算的SME算法13等應用到Montgomery形式的橢圓曲線上，加快標量乘的速度，同時達到抵抗計時攻擊的效果。在文章的最后對于新的算法與傳統(tǒng)的算法，在時間復雜度上做了一些比較。關鍵詞：橢圓曲線；密碼學； Montgomery形式橢圓曲線；標量乘中圖分類號：TP391文獻標識碼：A1 簡介橢圓曲線密碼體制首先由Neal Koblitz1和Victor Miller2兩人獨立地提出，近來得到越來越廣泛地關注，進行了很多算法和實際實現方面的研究。橢圓曲線的標準Weierstrass形式是（對于特征大于3的域）

3、，而Montgomery則引入了另一種形式的橢圓曲線3，并提出了一種和Weierstrass曲線上標量乘完全不同的計算方法，與原有的方法相比有如下的優(yōu)點：它不需要預計算（原始的算法），所以可以在存儲空間有限的條件下實現（例如智能卡等）；利于并行計算；它的運算時間可以認為是固定的，而不依賴于的Hamming重量等。而且在研究橢圓曲線上的標量乘的算法的同時，很多研究者6,12,17還獨立地發(fā)現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曲線的算法。一些協(xié)議如ECDSA的驗證部分需要計算。Katsuyuki Okeya和Kouichi Sakurai建

5、議先用普通的方法計算，再使用Montgomery的方法計算，并且恢復的y坐標，最后計算8。而Toru給出了一種類似Montgomery算法的方法直接計算9。在本文中，我們對于Toru的算法進行了擴展，使之可以用于計算。本文的組織形式是：在第二部分中，回顧了Montgomery曲線的定義和Montgomery的算法；在第三部分中提出了一個直接計算的類Montgomery算法；在最后一部分中對于新的算法和傳統(tǒng)的方法作了一些比較。2 Montgomery形式的橢圓曲線和Montgomery算法2.1 Montgomery形式橢圓曲線的定義首先定義曲線的Montgomery形式：令為一個素數，為有個元

6、素的有限域，其中。對于，由下式定義的橢圓曲線稱為一個Montgomery形式的橢圓曲線：上的有理點全體構成一個有限可換群，其無窮原點是，于是，在Weierstrass形式的橢圓曲線上的所有密碼協(xié)議都可以應用到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坐標的算法對于某些協(xié)議，比如建立密鑰方案ECDH以及簽名產生ECDSA-S7，只是需要的x坐標，如上的Montgomery算法是足夠的。但是對于其他的一些協(xié)議，例如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坐標。易于驗證，可以寫成：則由計算的具體方法是：，。在進行這個算法之前需要預先計算、。這樣每一次由計算需要五次點運算（一次點加四次點倍或者五次點加）?？梢娭辉谟嬎闶遣艜皇褂玫?，于是若中不包含，則在中不需要計算。而當且僅當。這種情況的概率可以認為是，于是每一個循環(huán)的點運算次數實際上可以認為是：。4 結論與算法復雜度比較由第三節(jié)中提出的算法計算的過程是：先計算，然后進行次循環(huán)，最后計算兩次點運算得到和（如果不需要恢復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、到與傳統(tǒng)的方法相比計算，新的算法都提高了20%以上，說明這個算法是有實際的優(yōu)勢的。另外，在實際的應用中，很多時候預計算是可以通過一次計算而多次使用的，這時候預計算的時間復雜度便可以忽略不計，新算法的提高將更為可觀。而且，這個算法可以應用到SME算法13 §14.88上，假定要計算（長度為bit），將分為長度為的三段，即：，令，則可以用來計算。另外，這個方法是具有可擴展性的，可以擴展到計算，乃至，這個算法將在后續(xù)的工作中進行具體的描述。參考文獻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