橢圓曲線底層域快速算法的優(yōu)化

賴忠喜，張占軍

臺州職業(yè)技術學院機電工程學院，浙江臺州318000

橢圓曲線底層域快速算法的優(yōu)化

賴忠喜，張占軍

臺州職業(yè)技術學院機電工程學院，浙江臺州318000

為了提高橢圓曲線底層域運算的效率，基于將乘法轉換為平方運算的思想，提出在素數(shù)域FP上用雅克比坐標直接計算2kP和3kP的改進算法，其運算量分別為（3k-1）M+（5k+3）S和（6k-1）M+（9k+3）S，與DIMITROY和周夢等人所提的算法相比，算法效率分別提升了6.25%和5%。另外，利用相同的原理，給出了素數(shù)域FP上用在仿射坐標系直接計算3kP的改進算法，其運算量為I+（6k+1）M+（9k+1）S，與周夢和殷新春等人所提的算法相比，效率分別提升了3.4%和24%。

橢圓曲線密碼體制；標量乘法；底層域運算；仿射坐標；雅克比坐標

1　引言

1985年，Koblitz和Miller分別提出了一種新的公鑰算法—橢圓曲線密碼體制（Elliptic Curve Cryptography，ECC），由于其安全性高和實現(xiàn)性能優(yōu)等獨特的優(yōu)勢逐步成為國內(nèi)外學者研究的重點［1-2］。實現(xiàn)橢圓曲線密碼體制最耗時的運算是橢圓曲線標量乘法，即kP的計算，其運算速度從整體上決定了ECC的實現(xiàn)效率［3］。研究標量乘法通?？蓮膬蓚€方面來考慮，一方面是研究標量k的有效表示，盡量減少上層的運算，如k的三元表示、非相鄰表示（Non-adjacent form，NAF）、w-NAF、雙基數(shù)系統(tǒng)［4-5］（Double-base number system，DBNS）及多基數(shù)系統(tǒng)［6］（Multi-Base Number System，MBNS）等表示形式。另一方面是對底層域快速算法進行研究，以減少底層域的運算量。目前文獻中，對提高底層域運算效率的方法可以歸納為：

（1）通過坐標變換，避免求逆。Mahdavi［7］等人對點P進行坐標變換（標準投影坐標、Jacobian坐標、改進的Jacobian坐標、Chudnovsky坐標等），這種方法通過改變點的坐標形式，繼而不要求逆，提高了運算效率。

（2）將求逆運算轉換為乘法運算。Sakai［8］等人利用求逆轉化為乘法的思想推導出了FP上計算2kP的算法。Dimitroy［9］等人提出了雅克比坐標系下直接計算2kP和3kP的算法。Ciet［10］等人利用分母的最小公倍數(shù)思想，對2P+Q、3P、3P+Q、4P、4P+Q等底層域運算進行優(yōu)化。Mishra［6］等人利用除法多項式提出了計算5P的快速算法。之后殷新春［3］等人推導出仿射坐標系下直接計算3kP的快速算法，徐凱平［11］等人改進了計算5P的算法并給出了在仿射坐標系下直接計算5kP的快速算法，Duc-Phong［12］改進了計算4P算法，進一步提高了效率。

（3）將乘法運算轉換為平方運算。Joye［13］利用轉換乘法為平方的思想，改進了雅克比坐標系下的P+Q和2P運算，Patrick［14］改進了雅克比坐標系下直接計算3P、5P、7P等運算，之后周夢［15］等人改進了雅克比坐標系下計算3P和3kP的算法，并給出了FP上計算2kP和3kP的改進算法。所有的這些算法減少了底層域的運算量，加快了橢圓曲線標量乘的運算速度。

本文利用將乘法轉化為平方運算的思想，提出在素數(shù)域FP上用雅克比坐標直接計算2kP和3kP的改進算法，與DIMITROY和周夢等人所提的算法相比，新算法效率分別提升了6.25%和5%。另外，本文給出了素數(shù)域FP上用仿射坐標系直接計算3kP的改進算法。與周夢和殷新春等人所提的算法相比，新算法效率分別提升了3.4%和24%。

2　背景知識

定義在素數(shù)域FP上的橢圓曲線E:y2=x3+ax2+b；（a，b∈FP且，Δ=4a3+27b3≠0）的點滿足該曲線方程的所有解稱為該橢圓曲線上的有理點，橢圓曲線E上的所有有理點再加上一個被稱為無窮遠的點O構成了一個加法交換群，橢圓曲線E的群運算是按照橢圓曲線群運算法則完成的，其中所涉及的運算有加、減、乘、求逆和平方五種基本運算，分別用I、S、M表示域FP上求逆，平方和乘法運算。五種基本運算中，加法和減法相對于其他運算來說，所用時間可忽略不計［11］。這里假設I= 10M，S=0.6M［15］。

2.1仿射坐標系下的運算法則

令P=（x1，y1）∈E（FP），Q=（x2，y2）∈E（FP），P≠±Q，則P+Q=（x3，y3）∈E（FP）可由式（1）計算：

令P=（x1，y1）∈E（FP），P≠-P，則2P=（x3，y3）∈E（FP）可由式（2）計算：

由式（1）和式（2）可知，素數(shù)域FP上完成點加運算和倍點運算的運算量分別為I+2M+S和I+2M+2S。

2.2雅克比坐標系下的運算法則

令c=2，d=3，則雅克比投影坐標P=（X，Y，Z）與仿射坐標P′=（x，y）=（X/Z2，Y/Z3）相對應。在雅克比坐標系下橢圓曲線方程為E:Y2=X3+axZ4+bZ6。

令P=（X1，Y1，Z1）∈E，Q=（X2，Y2，Z2）∈E，P≠±Q，則P+Q=（X3，Y3，Z3）可由式（3）計算

令P=（X1，Y1，Z1）∈E，P≠-P，則2P=（X3，Y3，Z3）可由式（4）計算。

通過分析存儲中間結果可知，雅克比坐標下下計算2P所需的運算量為4M+6S。

3　雅克比坐標系下2kP的改進

如果將標量表示成2k的形式，那么直接計算2kP會大大提高計算效率。文獻［9］給出了雅克比坐標系下直接計算2kP的詳細計算過程，本章利用將求逆轉化為乘法的思想和等式2ab=（a+b）2-a2-b2在文獻［9］的基礎上改進了雅克比坐標系下直接計算2kP的算法，具體步驟如算法1所示，具體運算量見表1。

表1　算法1的運算量

算法1雅克比坐標系下計算2kP的改進算法

4　雅克比坐標系下3kP的改進

如果將標量表示成3k的形式，那么直接計算3kP會大大提高計算效率。文獻［15］利用轉換乘法為平方運算的代數(shù)方法，給出了雅克比坐標下計算3kP的算法，本章延續(xù)將乘法轉化為平方的思想，利用等式2ab=（a+b）2-a2-b2在文獻［15］的基礎上進一步改進雅克比坐標系下直接計算3kP的算法，具體步驟如算法2所示，具體運算量見表2。

表2　算法2的運算量

算法2雅克比坐標計算3kP的改進算法

在算法2中，當分析計算 B3i-1運算量時，由于已在上個循環(huán)計算出來，所以計算 B3i-1只需（k-1）M+（k-1）S運算，經(jīng)過分析可知算法2總的運算量為（6k-1）M+（9k+3）S。比文獻［15］中計算3kP時的運算量6kM+10kS相比，減少了（0.6k-0.8）M，效率提升了5%。比文獻［9］中計算3kP時的運算量（11k-1）M+（4k+2）S相比，減少了（2k-0.6）M，效率提升了14.9%。

表3列出了素數(shù)域上在雅克比坐標系下不同運算的開銷。

表3　素數(shù)域中不同運算的開銷（雅克比坐標系）

5　仿射坐標系下計算3kP的改進算法

令P=（x1，y1）∈E（FP），3kP=（x3k，y3k）∈E（FP）。本章延續(xù)上章相同的思想，在文獻［15］的基礎上給出了仿射坐標系下直接計算3kP的改進算法，具體步驟如算法3所示，具體運算量見表4。

表4　算法3的運算量

算法3仿射坐標系下計算3kP的改進算法

6　結束語

本文利用將乘法化為平方的思想，研究了域K（FP）特征大于3的橢圓曲線，給出了雅克比標系下直接計算2kP和3kP的改進算法，與文獻［9］和文獻［15］中計算2kP和3kP的運算量相比，新算法分別節(jié)省了（0.4k+0.6）M和（0.6k-0.8）M的運算量，運算效率分別提升了6.25%和5%，另外，利用相同的思想，本文在仿射坐標系下給出計算3kP的改進算法，與文獻［15］和文獻［3］中計算3kP運算量相比，新算法分別減少了（0.4k-0.2）M和（3.6k-1）M運算，算法的運算效率分別提升了3.4%和24%。下一步工作應考慮將乘法轉換為平方的思想應用在計算5P、7P、5kP和7kP等底層域算法中。

［1］賴忠喜，張占軍，陶東婭.橢圓曲線中直接計算7P的方法及其應［J］.計算機應用，2013，33（7）：1870-1874.

［2］Hankerso D，Menezes A，Vanstone S.Guide to elliptic curve cryptography［M］.New York：Springer-verlag，2004：76-81.

［3］殷新春，侯洪祥，謝立.基于雙基數(shù)的快速標量乘算法［J］.計算機科學，2008，35（6）：186-195.

［4］Dimitrov V S，Imbert L，Mishra P K.Fast elliptic curve pointmultiplicationusingdouble-basechains［EB/OL］.［2007-04-10］.http//eprint.iacr.org/2005/069.

［5］Dimitrov V S，Jullien G A.A new number representation with applications［J］.IEEE Circuits and Systems Magazine，2003（2）：6-23.

［6］Mishra P K，Dimitrov V.Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multibase number representation［C］//Proceedings of the 10th Information Security Conference.Berlin：Springer-Verlag，2007：390-406.

［7］Mahdavi R，Saiadian A.Efficient scalar multiplications for elliptic curve cryptosystems using mixed coordinates strategy and direct computations［M］//Cryptology and Network Security.Berlin Heidelberg：Springer，2010：184-198.

［8］Sakuraik S.Efficient scalar multiplications on elliptic curves with direct computations of several doublings［J］.IEEE Transactions on Fundamentals，2001，E84-A（1）：120-129.

［9］Dimitroy V，Imvert L，Mishra P K.Efficient and secure elliptic curve point multiplication using double base chain［C］//Proceedings of the 11th International Conference on the Theory and Application of Cryptology and Information Security. LNCS 3788.Chennai：Springer-Verlag，2005：59-78.

［10］Ciet M，Joye M，Lauter K，et al.Trading inversions for multiplications in elliptic curve cryptography［J］.Designs Codes and Cryptography，2006，39（2）：189-206.

［11］徐凱平，鄭洪源，劉錦峰，等.橢圓曲線密碼體制中快速標量乘方法研究［J］.計算機工程與應用，2011，47（15）：112-115.

［12］Le Duc-Phong.Fast quadrupling of a point in elliptic curve cryptography［EB/OL］.［2011-06-10］.http//eprint.iacr. org/2011/039.

［13］Joye M.Fast point multiplication on elliptic curves without pre-computation［C］//Procof the2ndInternational Workshop on Arithmetic of Finite Fields，Siena.Berlin：Springer，2008：36-46.

［14］Longa P.High-speed elliptic curve and pairing-based Cryptography［D］.Ottawa：University of Ottawa，2011.

［15］周夢，周海波.橢圓曲線快速點乘算法優(yōu)化［J］.計算機應用研究，2012，29（8）：3056-3058.

Optimizing fast field operation in elliptic curves.

LAI Zhongxi，ZHANG Zhanjun

College of Mechanical and Electrical Engineering，Taizhou Vocational Technical，Taizhou，Zhejiang 318000，China

To raise the efficiency of field operation on elliptic curve，based on the idea of trading multiplications for squares，two modified algorithms are proposed to compute 4P and 5P directly over prime fieldFPin terms of affine coordinates，their computational complexity are（3k-1）M+（5k+3）Sand（6k-1）M+（9k+3）Srespectively，which are improved to 6.25%and 5%respectively than those of Dimitroy’s and Zhou meng’s method.Moreover，using the same idea，an improved method is given to compute3kPdirectly in terms of affine coordinates，its computational complexity is I+（6k+1）M+（9k+1）S，and the efficiency of the new method is improved to 3.4%and 24%respectively than those of Zhong meng’s and Yin xin-chun’s method.

elliptic curve cryptosystem；scalar multiplication；field operation；affine coordinate；jacobian coordinate

A

TP309.7

10.3778/j.issn.1002-8331.1311-0238

浙江省教育廳科研項目資助（No.Y201533946）。

賴忠喜（1984—），男，講師，CFF會員，主要研究方向：信息安全、智能控制；張占軍（1979—），男，講師，主要研究方向：信息安全、智能控制。E-mail：laizhongxi@163.com

2013-11-17

2014-01-13

1002-8331（2015）22-0115-04

CNKI網(wǎng)絡優(yōu)先出版：2014-04-01，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0238.html