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

袁 勇，唐 剛，陳輝焱，萬宗杰，張德馨

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

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

袁 勇1,2,3，唐 剛3，陳輝焱2，萬宗杰2，張德馨3

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

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

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

0 引 言

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

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

1 MOF算法

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

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

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

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

算法1：MOF算法。

輸入：非零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的點乘算法。

輸出：Q=kP。

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

2)Q=。

3)對于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)栽培甜瓜時，其播種期應(yīng)在定植前30～35天播種；露地栽培甜瓜時，其播種期應(yīng)晚霜前25～30天前播種。

下面通過一個實例來進行說明：

例1：k=15。

漢明重為4。

漢明重為2。

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

例2：k=42。

漢明重為3。

漢明重為6。

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

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

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

2 ZLMOF算法

2.1 ZLMOF算法介紹

算法3：ZLMOF算法。

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

輸出：k的ZLMOF形式。

1)利用算法1計算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。

下面通過具體實例來進行說明。

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

k的MOF表示形式為:

此時漢明重為10。

k的NAF表示形式為：

k的ZLMOF表示形式為7。

第一輪變換MOF：

此時漢明重為7。

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

算法4:ZLMOF計算點乘算法。

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

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

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

2)Q=，w=0。

3)對于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。

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

2.2 ZLMOF算法性能分析

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

k的取值見表1。

表1 9個k的取值

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

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

表3 9個k值不同表示形式下的比特長度

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

下面通過計算復(fù)雜度進一步分析。

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

表4 三種算法的主計算量理論分析

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

3 ZLMOF—滑動窗口算法

3.1 ZLMOF—滑動窗口算法介紹

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

算法5：ZLMOF—滑動窗口算法。

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

輸出：Q=kP。

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

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

4)當(dāng)i≥0時，重復(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中，采用滑動窗口技術(shù)，通過預(yù)計算，以空間換時間，提高運算效率。

3.2 ZLMOF—滑動窗口算法性能分析

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

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

4 Shamir-ZLMOF算法

4.1 Shamir-ZLMOF算法介紹

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

算法6：ZLMOF—滑動窗口算法。

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

輸出：k1P1+k2P2+…+kmPm。

1)預(yù)計算。

(2)計算并存儲：

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

2)主計算。

(1)將標(biāo)量k進行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對應(yīng)的Qa值)。

(5)返回Q。

在算法6中，采用預(yù)計算的方式，以存儲來換空間，達到提高多標(biāo)量乘運算的目的。

4.2 Shamir-ZLMOF算法性能分析

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

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

5 結(jié)束語

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

時間：2016-11-21

國家發(fā)展改革委信息安全專項項目(發(fā)改辦高技[2010]3044號)

袁 勇(1989-)，男,碩士，研究方向為信息安全、橢圓曲線及其密碼方案。

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