袁 勇，唐 剛，陳輝焱，萬(wàn)宗杰，張德馨

(1.西安電子科技大學(xué)，陜西 西安 710071；2.北京電子科技學(xué)院，北京 100070；3.中國(guó)軟件評(píng)測(cè)中心，北京 100044)

基于MOF算法改進(jìn)的標(biāo)量乘算法研究

袁 勇1,2,3，唐 剛3，陳輝焱2，萬(wàn)宗杰2，張德馨3

(1.西安電子科技大學(xué)，陜西 西安 710071；2.北京電子科技學(xué)院，北京 100070；3.中國(guó)軟件評(píng)測(cè)中心，北京 100044)

標(biāo)量乘運(yùn)算是橢圓曲線密碼方案中最耗費(fèi)時(shí)間的運(yùn)算，因此標(biāo)量乘的運(yùn)算速度決定了橢圓曲線密碼方案的執(zhí)行速度。為了提高標(biāo)量乘的執(zhí)行速度，人們提出了很多方案，如NAF、MOF等。在研究大量標(biāo)量乘算法的基礎(chǔ)上，提出了一種基于MOF算法的改進(jìn)型ZLMOF算法。改進(jìn)的算法與原算法相比，在漢明重基本保持不變的前提下，比特串長(zhǎng)度上降到了最低，從而進(jìn)一步減少了點(diǎn)加運(yùn)算的次數(shù)。然后結(jié)合滑動(dòng)窗口算法提出了一種比NAF—滑動(dòng)窗口算法更加高效的ZLMOF—滑動(dòng)窗口算法，ZLMOF—滑動(dòng)窗口算法比NAF—滑動(dòng)窗口算法需要更少的點(diǎn)加運(yùn)算次數(shù)。又結(jié)合Shamir算法，提出了一種比Shamir—NAF算法更加高效的Shamir—ZLMOF多標(biāo)量乘算法。Shamir—ZLMOF多標(biāo)量乘算法比Shamir—NAF算法需要更少的點(diǎn)加運(yùn)算次數(shù)。

標(biāo)量乘；ZLMOF算法；ZLMOF—滑動(dòng)窗口算法；Shamir—ZLMOF算法；橢圓曲線

0 引 言

公鑰密鑰的概念由W.Diffie和M.Hellman[1]提出。R.Rivst、A.Shamir和L.Adleman提出了第一種實(shí)用的公鑰密碼算法—RSA算法[2]。N.Koblitz[3]和V.Miller[4]提出了橢圓曲線密碼體制。ECC與RSA、DSA相比，具有更高的單比特安全性,因此ECC的密鑰尺寸和系統(tǒng)參數(shù)較小。除此之外，在對(duì)短消息進(jìn)行加解密時(shí)，ECC帶寬要求比RSA和DSA低得多。因此ECC在現(xiàn)在保密通信中，特別是在密碼芯片、智能卡和移動(dòng)通信終端設(shè)備中的優(yōu)勢(shì)越來(lái)越明顯。所以對(duì)ECC進(jìn)行研究具有十分重要的實(shí)際意義。

在橢圓曲線密碼體制中，最耗費(fèi)時(shí)間的運(yùn)算就是標(biāo)量乘運(yùn)算。因此標(biāo)量乘運(yùn)算的速度就決定了密碼方案的運(yùn)算速度。為了滿足密碼方案的需要，已經(jīng)提出了很多標(biāo)量乘算法，如二進(jìn)制標(biāo)量乘算法[5]、DR標(biāo)量乘算法[6]、NAF標(biāo)量乘算法[6]、MOF標(biāo)量乘算法[7]、補(bǔ)數(shù)標(biāo)量乘算法[8]、固定窗口算法[9]和滑動(dòng)窗口算法[10]等等。文中主要針對(duì)MOF算法進(jìn)行研究，針對(duì)MOF算法變換形式進(jìn)行變換時(shí)會(huì)出現(xiàn)漢明重不但不會(huì)降低反而會(huì)增加的現(xiàn)象，提出了ZLMOF變換生成算法，緊接著利用連續(xù)倍點(diǎn)運(yùn)算性質(zhì)提出了ZLMOF算法。在ZLMOF算法的基礎(chǔ)上，利用滑動(dòng)窗口技術(shù)提出了ZLMOF—滑動(dòng)窗口算法。通過(guò)利用預(yù)計(jì)算進(jìn)一步提高計(jì)算效率。由于ZLMOF表示形式相比NAF表示形式不但在大多數(shù)情況下比特串的長(zhǎng)度要短，而且0更加集中。因此ZLMOF—滑動(dòng)窗口算法的計(jì)算效率比NAF—滑動(dòng)窗口算法要高。由于在密碼方案中，很多時(shí)候會(huì)用到多標(biāo)量乘運(yùn)算，因此人們提出了直接算法、Shamir算法、Shamir—NAF算法和JSF算法等等[11-12]。文中結(jié)合Shamir算法和ZLMOF算法，提出了一種比Shamir—NAF算法更加高效的Shamir—ZLMOF算法。

1 MOF算法

MOF算法原理:對(duì)任一標(biāo)量k，可以表示成形如MOF(k)=(2k)2-(k)2的形式(MutualOppositeForm)。

Okeya在文獻(xiàn)[7]中進(jìn)一步指出標(biāo)量k的MOF表示形式具有以下性質(zhì):

(1)相鄰的非零比特的符號(hào)是相反的。

具體MOF表示生成算法如下：

算法1：MOF算法。

輸入：非零n比特二進(jìn)制串k=kn-1kn-2…k1k0；

輸出：k的MOF形式mkn-1mkn-2…mk1mk0

1)mkn=kn-1。

2)i從n-1到0重復(fù)執(zhí)行。

(1)mki=ki-1-ki；

(2)mk0=-k0。

3)返回mknmkn-1…mk1mk0。

算法2：MOF的點(diǎn)乘算法。

輸出：Q=kP。

1)利用MOF表示生成算法計(jì)算k的MOF形式。

2)Q=。

3)對(duì)于i從l到0，重復(fù)執(zhí)行

(1)Q=2Q；

(2)若ki=1，則Q=Q+P；

(3)若ki=-1，則Q=Q-P。

4)返回Q。

冬春季溫室、塑料大棚等設(shè)施內(nèi)栽培甜瓜時(shí)，其播種期應(yīng)在定植前30～35天播種；露地栽培甜瓜時(shí)，其播種期應(yīng)晚霜前25～30天前播種。

下面通過(guò)一個(gè)實(shí)例來(lái)進(jìn)行說(shuō)明：

例1：k=15。

漢明重為4。

漢明重為2。

通過(guò)例1可以發(fā)現(xiàn)標(biāo)量k的MOF表示比起二進(jìn)制表示的漢明重減少了一半。下面再來(lái)看一個(gè)例子。

例2：k=42。

漢明重為3。

漢明重為6。

通過(guò)例2可以發(fā)現(xiàn)標(biāo)量k的MOF表示形式的漢明重非但沒(méi)有比二進(jìn)制的表示形式減少，反而擴(kuò)大了一倍。

通過(guò)上面兩個(gè)例子可以發(fā)現(xiàn),標(biāo)量k的MOF表示并非對(duì)任意的標(biāo)量k都可以起到降低漢明重的作用，有時(shí)甚至?xí)O大地增加漢明重。除此之外，還可以發(fā)現(xiàn)，即使標(biāo)量k的MOF表示形式并未造成漢明重的增加，但是比特串的長(zhǎng)度卻增加了，這無(wú)疑就增加了一次倍點(diǎn)運(yùn)算。

為了解決上面的問(wèn)題，利用左移變換的性質(zhì)進(jìn)一步優(yōu)化，從而將標(biāo)量k的帶符號(hào)的二進(jìn)制表示形式的漢明重降到最低，比特串的長(zhǎng)度降到最短，0和1更加集中。將這種新的算法稱為ZLMOF算法。下面具體來(lái)看一下基于MOF算法改進(jìn)的標(biāo)量乘算法。

2 ZLMOF算法

2.1 ZLMOF算法介紹

算法3：ZLMOF算法。

輸入：非零n比特二進(jìn)制串k=kn-1kn-2…k1k0；

輸出：k的ZLMOF形式。

1)利用算法1計(jì)算k的MOF形式mknmkn-2…mk1mk0。

2)un+1=0。

3)i從0到n重復(fù)執(zhí)行。

(1)當(dāng)mkimki+1=-1:

②否則，ui=1，ui+1=0，i=i+2，執(zhí)行3)。

(2)否則，ui=mki，i=i+1，執(zhí)行3)。

4)輸出k的LMOF表示形式。

5)i從n-1到2重復(fù)執(zhí)行：

(1)若uiui-2=-1且ui-1=0：

①若ui=1，則vi=0，vi-1=1，vi-2=1，i=i+3，執(zhí)行5)；

(2)否則，vi=ui，i=i+1，執(zhí)行5)。

6)若u2u0≠-1或u1≠0，則v2=u2，v1=u1，v0=u0

7)輸出k的ZLMOF。

下面通過(guò)具體實(shí)例來(lái)進(jìn)行說(shuō)明。

例3：k=(1100111011101010)，二進(jìn)制表示的漢明重為10。

k的MOF表示形式為:

此時(shí)漢明重為10。

k的NAF表示形式為：

k的ZLMOF表示形式為7。

第一輪變換MOF：

此時(shí)漢明重為7。

例3再一次驗(yàn)證了MOF表示形式有時(shí)不但起不到降低漢明重的作用,還會(huì)增加漢明重。通過(guò)例3可以看出，ZLMOF表示形式的漢明重降到了NAF的水平，達(dá)到了最低。除此之外，ZLMOF表示形式的比特長(zhǎng)度比起NAF形式要短，這樣就降低了倍點(diǎn)運(yùn)算的次數(shù)。除此之外，在ZLMOF表示形式中0更加集中，這樣便可以通過(guò)連續(xù)倍點(diǎn)運(yùn)算進(jìn)一步提高倍點(diǎn)運(yùn)算的效率。

算法4:ZLMOF計(jì)算點(diǎn)乘算法。

輸入：非零n比特二進(jìn)制串k=kn-1kn-2…k1k0；

輸出：標(biāo)量乘kP的值。

1)用算法3計(jì)算k的ZLMOF形式。

2)Q=，w=0。

3)對(duì)于i從n-1到0，重復(fù)執(zhí)行：

(1)當(dāng)ki=0，則w=w+1，i=i+1，執(zhí)行3)；

(2)Q=2wQ，w=0；

(3)若ki=1，則Q=Q+P；

4)i=i+1。

5)返回Q。

通過(guò)算法4可以發(fā)現(xiàn)，由于ZLMOF具有較短的比特長(zhǎng)度，因此它的倍點(diǎn)運(yùn)算次數(shù)比NAF大多數(shù)情況下要少。除此之外，在ZLMOF的點(diǎn)乘運(yùn)算中，采用了連續(xù)被點(diǎn)運(yùn)算。因此，即使在點(diǎn)加和倍點(diǎn)運(yùn)算次數(shù)相同的情況下，速度也會(huì)明顯提高。

2.2 ZLMOF算法性能分析

下面隨機(jī)選取9個(gè)隨機(jī)k值直觀地分析一下幾種算法表示形式的漢明重及比特長(zhǎng)度的大小。

k的取值見表1。

表1 9個(gè)k的取值

對(duì)表1中的標(biāo)量k分別進(jìn)行二進(jìn)制表示、NAF表示、MOF表示和ZLMOF表示，然后對(duì)9個(gè)k值在不同表示形式下的漢明重和比特長(zhǎng)度進(jìn)行了計(jì)算，具體結(jié)果見表2和表3。

表2 9個(gè)k值不同表示形式下的漢明重

表3 9個(gè)k值不同表示形式下的比特長(zhǎng)度

通過(guò)表2和表3可以發(fā)現(xiàn)，MOF表示形式有時(shí)不但起不到降低漢明重的作用，甚至還會(huì)造成漢明重的增加。在ZLMOF表示形式中漢明重不但與NAF表示形式的漢明重相同，而且在大多數(shù)情況下比特串的長(zhǎng)度更加短，從而降低了倍點(diǎn)運(yùn)算次數(shù)。

下面通過(guò)計(jì)算復(fù)雜度進(jìn)一步分析。

表4是二進(jìn)制算法、NAF算法和ZLMOF算法的計(jì)算復(fù)雜性比較。

表4 三種算法的主計(jì)算量理論分析

通過(guò)表4的計(jì)算復(fù)雜性分析，可以發(fā)現(xiàn)：ZLMOF算法盡管倍點(diǎn)運(yùn)算次數(shù)有時(shí)會(huì)比NAF算法要多1，但是整體的點(diǎn)加運(yùn)算卻比二進(jìn)制算法明顯要少。ZLMOF算法與NAF算法相比，點(diǎn)加次數(shù)相同但是整體倍點(diǎn)運(yùn)算次數(shù)卻要少。同時(shí)ZLMOF的點(diǎn)乘算法中采用了連續(xù)倍點(diǎn)運(yùn)算，因此ZLMOF算法的計(jì)算效率比NAF算法的計(jì)算效率高。即使NAF算法也采用連續(xù)倍點(diǎn)運(yùn)算，但由于ZLMOF表示形式中0更加集中，因此ZLMOF連續(xù)倍點(diǎn)的執(zhí)行效率也會(huì)更高。

3 ZLMOF—滑動(dòng)窗口算法

3.1 ZLMOF—滑動(dòng)窗口算法介紹

將滑動(dòng)窗口算法與文中設(shè)計(jì)的ZLMOF算法相結(jié)合，提出了一種比NAF—滑動(dòng)窗口算法更加高效的ZLMOF—滑動(dòng)窗口算法。具體的算法流程如下：

算法5：ZLMOF—滑動(dòng)窗口算法。

輸入：窗口寬度為w，正整數(shù)k,P∈E(Fq)；

輸出：Q=kP。

2)對(duì)于u∈{1,3,…,2w-1+2w-2+2w-3-1}，計(jì)算Pu=uP。

3)Q=∞,i=l-1。

4)當(dāng)i≥0時(shí)，重復(fù)執(zhí)行：

(1)若ki=0，則t=1,u=0;

(3)Q=2tQ;

(4)若u>0，則Q=Q+Pu;

(5)否則，Q=Q-Pu;

(6)i=i-t。

5)返回Q。

在算法5中，采用滑動(dòng)窗口技術(shù)，通過(guò)預(yù)計(jì)算，以空間換時(shí)間，提高運(yùn)算效率。

3.2 ZLMOF—滑動(dòng)窗口算法性能分析

表5 兩種算法計(jì)算復(fù)雜度比較

由于ZLMOF表示形式的0和1更加集中，因此ZLMOF—滑動(dòng)窗口算法在計(jì)算過(guò)程中的實(shí)際點(diǎn)加次數(shù)比理論值要少，因此ZLMOF—滑動(dòng)窗口算法的實(shí)際計(jì)算速度比起NAF—滑動(dòng)窗口算法要快很多。

4 Shamir-ZLMOF算法

4.1 Shamir-ZLMOF算法介紹

將Shamir算法與文中設(shè)計(jì)的ZLMOF算法相結(jié)合，提出了一種比Shamir-NAF算法更加高效的Shamir-ZLMOF算法。具體的算法流程如下：

算法6：ZLMOF—滑動(dòng)窗口算法。

輸入：k1,…,km∈Fq，P1,…,Pm∈E(Fq)；

輸出：k1P1+k2P2+…+kmPm。

1)預(yù)計(jì)算。

(2)計(jì)算并存儲(chǔ)：

Qa=(P1,P2,…,Pm)·(i1,i2,…,im)T

2)主計(jì)算。

(1)將標(biāo)量k進(jìn)行ZLMOF表示：

ki=(ki,l-1,…,ki,1,ki,0)ZLMOF

(3)Q=，j=l-1，w=0。

(4)當(dāng)j從l-1到0，重復(fù)執(zhí)行：

①Q(mào)=2Q；

②如果bj≠0，則Q=Q+Qa(Qa為與bj相同的a對(duì)應(yīng)的Qa值)。

(5)返回Q。

在算法6中，采用預(yù)計(jì)算的方式，以存儲(chǔ)來(lái)?yè)Q空間，達(dá)到提高多標(biāo)量乘運(yùn)算的目的。

4.2 Shamir-ZLMOF算法性能分析

表6 三種算法計(jì)算復(fù)雜度比較

通過(guò)表6中的數(shù)據(jù)可以發(fā)現(xiàn)，Shamir-ZLMOF算法的倍點(diǎn)運(yùn)算盡管比Shamir算法有時(shí)要多1，但是點(diǎn)加運(yùn)算的次數(shù)比起Shamir算法要少很多。Shamir-ZLMOF算法的點(diǎn)加運(yùn)算次數(shù)與Shamir-NAF算法相同，但是倍點(diǎn)運(yùn)算次數(shù)大多數(shù)情況下要少。因此Shamir-ZLMOF算法比起以上兩種算法具有更高的執(zhí)行效率。

5 結(jié)束語(yǔ)

文中首先分析了當(dāng)前主流的標(biāo)量乘和多標(biāo)量乘算法。在對(duì)MOF算法研究的基礎(chǔ)上利用左移性質(zhì)提出了ZLMOF算法，然后利用Homer規(guī)則采用連續(xù)倍點(diǎn)運(yùn)算，進(jìn)一步提高算法的效率。ZLMOF算法的倍點(diǎn)運(yùn)算效率比起像NAF等傳統(tǒng)算法明顯要高。緊接著結(jié)合滑動(dòng)窗口法提出了ZLMOF—滑動(dòng)窗口算法，采用預(yù)計(jì)算進(jìn)一步提高運(yùn)算速率。同時(shí)，結(jié)合Shamir算法和ZLMOF算法提出了Shamir—ZLMOF算法。新算法比傳統(tǒng)的Shamir—NAF算法效率要高。

[1]DiffieW,HellmanM.Newdirectionsincryptography[J].IEEETransactionsonInformationTheory,1976,22(6):644-654.

[2]RivestRL,ShamirA,AdlemanLM.Amethodforobtainingdigitalsignaturesandpublickeycryptosystem[J].CommunicationsoftheACM,1987,21(2):120-126.

[3]KoblitzN.Ellipticcurvecryptosystems[J].MathematicsofComputation,1987,48(177):203-209.

[4]MillerVS.Useofellipticcurvesincryptography[C]//Advanceincryptology.[s.l.]:Springer,1986:417-426.

[5]HuangX,ShahP,SharmaD.FastalgorithminECCforwirelesssensornetwork[C]//Proceedingsoftheinternationalmulticonferenceofengineersandcomputerscientists.[s.l.]:[s.n.],2010:17-19.

[6]BalasubramaniamP,KarthikeyanE.Ellipticcurvescalarmultiplicationalgorithmusingcomplementaryrecoding[J].AppliedMathematicsandComputation,2007,190(1):51-56.

[7]OkeyaK.Signedbinaryrepresentationsrevisited[C]//ProceedingsofCRYPTO'04.[s.l.]:[s.n.],2004:123-139.

[8]KodaliPK,BudwalHS.HighperformancescalarmultiplicationforECC[C]//Internationalconferenceoncomputercommunicationandinformatics.Piscataway:IEEE,2013:1-4.

[9]SolinasJA.Animprovedalgorithmforarithmeticonafamilyofellipticcurves[C]//Advancesincryptology.[s.l.]:[s.n.],1997:357-371.

[10]ShahPG,HuangX,SharmaD.Slidingwindowmethodwithflexiblewindowsizeforscalarmultiplicationonwirelesssensornetworknodes[C]//Internationalconferenceonwirelesscommunicationandsensorcomputing.[s.l.]:IEEE,2010:1-6.

[11]SolinasJA.Low-weightbinaryrepresentationsforpairsofintegers[R].[s.l.]:CentreforAppliedCryptographicResearch,2001.

[12]ZhangJZ,KouYZ,WangT,etal.Faultanalysisonellipticcurvecryptosystemswithslidingwindowmethod[J].JournalonCommunications,2012,33(1):71-78.

[13]YongKL,IngridV.AcompactarchitectureforMontgomeryellipticcurvescalarmultiplicationprocessor[M].[s.l.]:Springer,2007:115-127.

Research on Improved Scalar Multiplication Algorithm Based on MOF

YUAN Yong1,2,3,TANG Gang3,CHEN Hui-yan2,WAN Zong-jie2,ZHANG De-xin3

(1.Xidian University，Xi’an 710071,China;2.Beijing Electronic Science & Technology Institute,Beijing 100070,China;3.China Software Testing Center,Beijing 100044,China)

Scalar multiplication in elliptic curve cryptography scheme takes up the most computing time to consume,so the scalar multiplication operation determines the efficiency of the implementation of cryptographic schemes.In order to improve the execution speed of scalar multiplication,many solutions have been suggested,such as NAF,MOF and so on.After studying a great large number of scalar multiplication algorithm,a ZLMOF algorithm is proposed based on the MOF algorithm.Under the Hamming weight almost remaining unchanged,the minimum length of bit string of the improved algorithm reduces to perfect than that of the original algorithm and then reduces the frequency of the point addition.Then a more efficient ZLMOF-sliding window algorithm is presented combined with sliding window algorithm than NAF-sliding window algorithm and then reduces the frequency of the point addition.Finally,a more efficient Shamir-ZLMOF multi-scalar multiplication algorithm is put forward to refer to the Shamir algorithm than the Shamir-NAF algorithm and then reduces the frequency of the point addition.

scalar multiplication;ZLMOF algorithm;ZLMOF-sliding window algorithm;Shamir-ZLMOF algorithm;elliptic curve

2015-09-01

2015-12-15

時(shí)間：2016-11-21

國(guó)家發(fā)展改革委信息安全專項(xiàng)項(xiàng)目(發(fā)改辦高技[2010]3044號(hào))

袁 勇(1989-)，男,碩士，研究方向?yàn)樾畔踩E圓曲線及其密碼方案。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1633.006.html

TP301.6

A

1673-629X(2016)12-0111-06

10.3969/j.issn.1673-629X.2016.12.025