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

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

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

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

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

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

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

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

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

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

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

11、見(jiàn)Cohen著作中的描述)。先由計(jì)算，共用：（注意到計(jì)算和時(shí)只需要求一次逆）。再計(jì)算，這用，于是在預(yù)計(jì)算部分共用。對(duì)于恢復(fù)y坐標(biāo)，在時(shí)候，應(yīng)該使用由射影坐標(biāo)恢復(fù)Y，再得到仿射坐標(biāo)的方法，共用。最終的時(shí)間復(fù)雜度是：如果使用的是Montgomery的方法單獨(dú)計(jì)算，再相加并恢復(fù)y-坐標(biāo)，則總的時(shí)間復(fù)雜度是：。假定：，12，我們給出上述的諸運(yùn)行時(shí)間：計(jì)算標(biāo)量乘的域中運(yùn)算次數(shù)（以下表示n的比特?cái)?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)的方法相比計(jì)算，新的算法都提高了20%以上，說(shuō)明這個(gè)算法是有實(shí)際的優(yōu)勢(shì)的。另外，在實(shí)際的應(yīng)用中，很多時(shí)候預(yù)計(jì)算是可以通過(guò)一次計(jì)算而多次使用的，這時(shí)候預(yù)計(jì)算的時(shí)間復(fù)雜度便可以忽略不計(jì)，新算法的提高將更為可觀。而且，這個(gè)算法可以應(yīng)用到SME算法13 §14.88上，假定要計(jì)算（長(zhǎng)度為bit），將分為長(zhǎng)度為的三段，即：，令，則可以用來(lái)計(jì)算。另外，這個(gè)方法是具有可擴(kuò)展性的，可以擴(kuò)展到計(jì)算，乃至，這個(gè)算法將在后續(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