計算Montgomery形式橢圓曲線上標(biāo)量乘kP+mQ+lR的新算法

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

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

3、，而Montgomery則引入了另一種形式的橢圓曲線3，并提出了一種和Weierstrass曲線上標(biāo)量乘完全不同的計算方法，與原有的方法相比有如下的優(yōu)點：它不需要預(yù)計算（原始的算法），所以可以在存儲空間有限的條件下實現(xiàn)（例如智能卡等）；利于并行計算；它的運(yùn)算時間可以認(rèn)為是固定的，而不依賴于的Hamming重量等。而且在研究橢圓曲線上的標(biāo)量乘的算法的同時，很多研究者6,12,17還獨(dú)立地發(fā)現(xiàn)Montgomery算法3可以有效地抵抗計時攻擊4。這更使得它成為現(xiàn)在橢圓曲線密碼學(xué)中最熱門的課題之一。Lopez與Dahab將Montgomery算法擴(kuò)展到了特征為2的域上，并且提出了一個有恢復(fù)-坐標(biāo)過程的

4、標(biāo)量乘的算法6。Katsuyuki Okeya和Kouichi Sakurai給出了在特征不是2的有限域上的Montgomery形式橢圓曲線上的恢復(fù)y坐標(biāo)的方法8。Katsuyuki Okeya、Hiroyuki Kurumatani和Kouichi Sakurai對于Montgomery-形式橢圓曲線和Weierstrass-形式橢圓曲線之間的相互轉(zhuǎn)化進(jìn)行了研究5。他們給出了具有Montgomery-形式的橢圓曲線的充要條件，還提出了一個選取階恰好是4光滑的Montgomery曲線的算法。一些協(xié)議如ECDSA的驗證部分需要計算。Katsuyuki Okeya和Kouichi Sakurai建

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

6、素的有限域，其中。對于，由下式定義的橢圓曲線稱為一個Montgomery形式的橢圓曲線：上的有理點全體構(gòu)成一個有限可換群，其無窮原點是，于是，在Weierstrass形式的橢圓曲線上的所有密碼協(xié)議都可以應(yīng)用到Montgomery形式的曲線上。2.2 Montgomery形式橢圓曲線上點的運(yùn)算首先給出Montgomery形式的曲線上的點在仿射坐標(biāo)下的點計算公式。令和為Montgomery形式橢圓曲線上的兩個點，則點由下面公式給出：，其中。在仿射情況下，點加需要三次乘法、一次平方和一次求逆；點倍需要五次乘法、兩次平方和一次求逆。接下來，令，并且記點的倍點為。則的坐標(biāo)可由下面的公式不使用Y坐標(biāo)而計算

7、3：l 點加公式，。l 點倍公式，。點加公式需要四次乘法、兩次平方（當(dāng)時可以減少一次乘法）；點倍公式需要三次乘法、兩次平方（這時需要預(yù)先計算）。最后給出在射影坐標(biāo)下點運(yùn)算的公式：令和為Montgomery形式橢圓曲線上的兩個點，則點由下面公式給出：l 點加公式：，。共用15次乘法，2次平方。l 點倍公式：，共用12次乘法，6次平方。2.3 Montgomery形式橢圓曲線上標(biāo)量乘的算法使用Montgomery算法計算標(biāo)量乘的過程是：首先要計算，然后根據(jù)n的二進(jìn)制表示的每個比特是0還是1來決定由計算還是。例如要計算，具體計算的過程是：從上面的例子可以看出，除了計算一共用了9次點加和點倍。一般的講

8、，計算，一共需要次點倍和次點加。而且計算次數(shù)是只依賴于n的比特長度而不依賴于n具體的二進(jìn)制表示的。2.4 Montgomery形式橢圓曲線上恢復(fù)y坐標(biāo)的算法對于某些協(xié)議，比如建立密鑰方案ECDH以及簽名產(chǎn)生ECDSA-S7，只是需要的x坐標(biāo)，如上的Montgomery算法是足夠的。但是對于其他的一些協(xié)議，例如ECDSA的驗證、ECSVDP-MQVC、ECVP-NR和ECVP-DSA7都還需要標(biāo)量乘的y坐標(biāo)。于是我們在使用Montgomery算法計算了之后，還需要恢復(fù)出來的坐標(biāo)。在下面就給出恢復(fù)y坐標(biāo)的方法。假設(shè)有Montgomery形式橢圓曲線上的點，且有。則這需要五次乘法、一次平方和一次求逆

9、。（另外這時候需要和的仿射坐標(biāo)，由射影坐標(biāo)得到和的仿射坐標(biāo)還需要兩次求逆和兩次乘法）。當(dāng)使用射影坐標(biāo)時，令，為Montgomery形式曲線上的點，定義：，。則有。這共需要十二次乘法和一次平方。再得到仿射坐標(biāo)還需要一次求逆和兩次乘法。另外Katsuyuki Okeya and Kouichi Sakurai中還給出了另外一種計算的方法，采用了不同的思路，但是需要十三次乘法和一次平方8。3 計算Montgomery-形式曲線上 為下文敘述的簡便，我們用表示。令、和是、和的二進(jìn)制表示，并令、，我們的目的即是計算。定義：令為一個0-1向量，定義：；。定義：令， 。則可以由計算出來，最后可以由計算，最后

10、如果需要恢復(fù)y坐標(biāo)的話再計算并恢復(fù)y坐標(biāo)。易于驗證，可以寫成：則由計算的具體方法是：，。在進(jìn)行這個算法之前需要預(yù)先計算、。這樣每一次由計算需要五次點運(yùn)算（一次點加四次點倍或者五次點加）。可見只在計算是才會被使用到，于是若中不包含，則在中不需要計算。而當(dāng)且僅當(dāng)。這種情況的概率可以認(rèn)為是，于是每一個循環(huán)的點運(yùn)算次數(shù)實際上可以認(rèn)為是：。4 結(jié)論與算法復(fù)雜度比較由第三節(jié)中提出的算法計算的過程是：先計算，然后進(jìn)行次循環(huán)，最后計算兩次點運(yùn)算得到和（如果不需要恢復(fù)y坐標(biāo)，則之需要算一個點），共需要：次點運(yùn)算。預(yù)計算部分，我們建議使用“Montgomery的法術(shù)”，這樣可以用計算個數(shù)的逆(具體的計算過程可以參

11、見Cohen著作中的描述)。先由計算，共用：（注意到計算和時只需要求一次逆）。再計算，這用，于是在預(yù)計算部分共用。對于恢復(fù)y坐標(biāo)，在時候，應(yīng)該使用由射影坐標(biāo)恢復(fù)Y，再得到仿射坐標(biāo)的方法，共用。最終的時間復(fù)雜度是：如果使用的是Montgomery的方法單獨(dú)計算，再相加并恢復(fù)y-坐標(biāo)，則總的時間復(fù)雜度是：。假定：，12，我們給出上述的諸運(yùn)行時間：計算標(biāo)量乘的域中運(yùn)算次數(shù)（以下表示n的比特數(shù)目運(yùn)算次數(shù)都轉(zhuǎn)化為域中乘法）128 bit256 bit512 bit2845.455568.65811015.13620.2715314218.621.4%22.1%22.5%表1 新舊算法運(yùn)算次數(shù)的比較可以看

12、到與傳統(tǒng)的方法相比計算，新的算法都提高了20%以上，說明這個算法是有實際的優(yōu)勢的。另外，在實際的應(yīng)用中，很多時候預(yù)計算是可以通過一次計算而多次使用的，這時候預(yù)計算的時間復(fù)雜度便可以忽略不計，新算法的提高將更為可觀。而且，這個算法可以應(yīng)用到SME算法13 §14.88上，假定要計算（長度為bit），將分為長度為的三段，即：，令，則可以用來計算。另外，這個方法是具有可擴(kuò)展性的，可以擴(kuò)展到計算，乃至，這個算法將在后續(xù)的工作中進(jìn)行具體的描述。參考文獻(xiàn)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