賴忠喜，張占軍

臺(tái)州職業(yè)技術(shù)學(xué)院機(jī)電工程學(xué)院，浙江臺(tái)州318000

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

賴忠喜，張占軍

臺(tái)州職業(yè)技術(shù)學(xué)院機(jī)電工程學(xué)院，浙江臺(tái)州318000

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

橢圓曲線密碼體制；標(biāo)量乘法；底層域運(yùn)算；仿射坐標(biāo)；雅克比坐標(biāo)

1　引言

1985年，Koblitz和Miller分別提出了一種新的公鑰算法—橢圓曲線密碼體制（Elliptic Curve Cryptography，ECC），由于其安全性高和實(shí)現(xiàn)性能優(yōu)等獨(dú)特的優(yōu)勢(shì)逐步成為國內(nèi)外學(xué)者研究的重點(diǎn)［1-2］。實(shí)現(xiàn)橢圓曲線密碼體制最耗時(shí)的運(yùn)算是橢圓曲線標(biāo)量乘法，即kP的計(jì)算，其運(yùn)算速度從整體上決定了ECC的實(shí)現(xiàn)效率［3］。研究標(biāo)量乘法通?？蓮膬蓚€(gè)方面來考慮，一方面是研究標(biāo)量k的有效表示，盡量減少上層的運(yùn)算，如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）等表示形式。另一方面是對(duì)底層域快速算法進(jìn)行研究，以減少底層域的運(yùn)算量。目前文獻(xiàn)中，對(duì)提高底層域運(yùn)算效率的方法可以歸納為：

（1）通過坐標(biāo)變換，避免求逆。Mahdavi［7］等人對(duì)點(diǎn)P進(jìn)行坐標(biāo)變換（標(biāo)準(zhǔn)投影坐標(biāo)、Jacobian坐標(biāo)、改進(jìn)的Jacobian坐標(biāo)、Chudnovsky坐標(biāo)等），這種方法通過改變點(diǎn)的坐標(biāo)形式，繼而不要求逆，提高了運(yùn)算效率。

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

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

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

2　背景知識(shí)

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

2.1仿射坐標(biāo)系下的運(yùn)算法則

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

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

由式（1）和式（2）可知，素?cái)?shù)域FP上完成點(diǎn)加運(yùn)算和倍點(diǎn)運(yùn)算的運(yùn)算量分別為I+2M+S和I+2M+2S。

2.2雅克比坐標(biāo)系下的運(yùn)算法則

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

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

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

通過分析存儲(chǔ)中間結(jié)果可知，雅克比坐標(biāo)下下計(jì)算2P所需的運(yùn)算量為4M+6S。

3　雅克比坐標(biāo)系下2kP的改進(jìn)

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

表1　算法1的運(yùn)算量

算法1雅克比坐標(biāo)系下計(jì)算2kP的改進(jìn)算法

4　雅克比坐標(biāo)系下3kP的改進(jìn)

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

表2　算法2的運(yùn)算量

算法2雅克比坐標(biāo)計(jì)算3kP的改進(jìn)算法

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

表3列出了素?cái)?shù)域上在雅克比坐標(biāo)系下不同運(yùn)算的開銷。

表3　素?cái)?shù)域中不同運(yùn)算的開銷（雅克比坐標(biāo)系）

5　仿射坐標(biāo)系下計(jì)算3kP的改進(jìn)算法

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

表4　算法3的運(yùn)算量

算法3仿射坐標(biāo)系下計(jì)算3kP的改進(jìn)算法

6　結(jié)束語

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

［1］賴忠喜，張占軍，陶東婭.橢圓曲線中直接計(jì)算7P的方法及其應(yīng)［J］.計(jì)算機(jī)應(yīng)用，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ù)的快速標(biāo)量乘算法［J］.計(jì)算機(jī)科學(xué)，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］徐凱平，鄭洪源，劉錦峰，等.橢圓曲線密碼體制中快速標(biāo)量乘方法研究［J］.計(jì)算機(jī)工程與應(yīng)用，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］周夢(mèng)，周海波.橢圓曲線快速點(diǎn)乘算法優(yōu)化［J］.計(jì)算機(jī)應(yīng)用研究，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

浙江省教育廳科研項(xiàng)目資助（No.Y201533946）。

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

2013-11-17

2014-01-13

1002-8331（2015）22-0115-04

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