基于MOF算法改進的標量乘算法研究

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

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

基于MOF算法改進的標量乘算法研究

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

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

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

標量乘；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的密鑰尺寸和系統參數較小。除此之外，在對短消息進行加解密時，ECC帶寬要求比RSA和DSA低得多。因此ECC在現在保密通信中，特別是在密碼芯片、智能卡和移動通信終端設備中的優勢越來越明顯。所以對ECC進行研究具有十分重要的實際意義。

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

1 MOF算法

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

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

(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重復執行。

(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，重復執行

(1)Q=2Q；

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

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

4)返回Q。

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

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

例1：k=15。

漢明重為4。

漢明重為2。

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

例2：k=42。

漢明重為3。

漢明重為6。

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

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

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

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重復執行。

(1)當mkimki+1=-1:

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

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

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

5)i從n-1到2重復執行：

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

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

(2)否則，vi=ui，i=i+1，執行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形式要短，這樣就降低了倍點運算的次數。除此之外，在ZLMOF表示形式中0更加集中，這樣便可以通過連續倍點運算進一步提高倍點運算的效率。

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

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

輸出：標量乘kP的值。

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

2)Q=，w=0。

3)對于i從n-1到0，重復執行：

(1)當ki=0，則w=w+1，i=i+1，執行3)；

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

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

4)i=i+1。

5)返回Q。

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

2.2 ZLMOF算法性能分析

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

k的取值見表1。

表1 9個k的取值

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

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

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

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

下面通過計算復雜度進一步分析。

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

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

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

3 ZLMOF—滑動窗口算法

3.1 ZLMOF—滑動窗口算法介紹

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

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

輸入：窗口寬度為w，正整數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)當i≥0時，重復執行：

(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中，采用滑動窗口技術，通過預計算，以空間換時間，提高運算效率。

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

表5 兩種算法計算復雜度比較

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

4 Shamir-ZLMOF算法

4.1 Shamir-ZLMOF算法介紹

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

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

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

輸出：k1P1+k2P2+…+kmPm。

1)預計算。

(2)計算并存儲：

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

2)主計算。

(1)將標量k進行ZLMOF表示：

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

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

(4)當j從l-1到0，重復執行：

①Q=2Q；

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

(5)返回Q。

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

4.2 Shamir-ZLMOF算法性能分析

表6 三種算法計算復雜度比較

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

5 結束語

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

國家發展改革委信息安全專項項目(發改辦高技[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