李超群 吳向前

基于模糊控制器的w2MOF快速標量乘算法

李超群 吳向前

(新疆大學電氣工程學院 新疆 烏魯木齊 830000)

橢圓曲線密碼體制中基點的標量乘是最耗時的一種操作，通過預計算的方式可以有效地提高其效率。借助于更靈活且高效的2MOF表示形式，在此基礎(chǔ)上利用滑動窗口技術(shù)，結(jié)合混合坐標下直接計算2kQ+P的計算方式，對w2MOF算法進行改進。對于滑動窗口技術(shù)下最優(yōu)窗口寬度的選擇，采用預先設(shè)計好的模糊控制器做出決策。根據(jù)目前常用的兩種模糊推理系統(tǒng)，模糊控制器選擇了Mamdani模型。實驗結(jié)果分析，結(jié)合模糊控制器與優(yōu)化的w2MOF算法，平均效率大約提高11.7%，而且比基于wNAF算法的文獻[1]中在曲線NIST-B163上，最優(yōu)窗口w=5下減少了19次點加運算量。

橢圓曲線密碼體制 w2MOF 混合坐標 滑動窗口 模糊控制器

0 引 言

自1985年Koblitz[1]和Miller[2]各自提出橢圓曲線密碼體制(ECC) 以來，與其他目前常用的公鑰密碼系統(tǒng)比較起來，比如RSA密碼系統(tǒng)，基于離散對數(shù)的密碼系統(tǒng)等，ECC具有更快的密鑰交換與簽名速度。此外，在同等安全強度下，ECC需要更小的寬帶，密鑰尺寸以及更快的運算速度。橢圓曲線密碼最基本的運算是基于倍運算與加運算的，而這兩種運算又構(gòu)成了域運算中的平方，加法與求逆。kP是橢圓曲線密碼體制中最主要的運算，而提高標量乘效率的方法主要從兩個方面去著手，一是研究k的有效表示，二是研究橢圓曲線標量乘的底乘域快速算法[3]。

提高k的有效表示，主要是圍繞減小其表示長度，平均漢明權(quán)重去優(yōu)化的。k的最古老的表現(xiàn)形式是不帶符號的二進制串以及帶符號的NAF。文獻[4]提出帶符號二進制串另一種表現(xiàn)形式2MOF，它具有與NAF相同的長度與平均漢明權(quán)重，但是它比NAF更具有靈活性，既可以從右向左掃描，也可以從左向右掃描二進制串，而且它在轉(zhuǎn)換過程中不需要求余與除法，文獻[5]提出了補數(shù)編碼的形式，但比文獻[4]提出的2MOF形式平均漢明權(quán)重大，適合于硬件壞境。在存儲空間容許的范圍內(nèi)，利用滑動窗口技術(shù)，通過預計算的方式可以提高標量乘效率，而最優(yōu)窗口寬度的選擇決定了預計算量與點加運算量。文獻[6]提出了基于wNAF帶預計算的標量乘法，文獻[7]提出了利用模糊控制器的思想，通過預先設(shè)計的模糊推理系統(tǒng)決定最優(yōu)的窗口寬度，并在補數(shù)編碼的表示形式上實行窗口技術(shù)。文獻[8]中通過優(yōu)化其規(guī)則庫，在NAF上實行窗口技術(shù)。另一種提高標量乘效率的方式就是在底層域結(jié)合坐標變換，文獻[9]中給出了混合坐標系下的2kQ+P算法，效率比傳統(tǒng)的倍乘與點加更高。

本文結(jié)合文獻[8]所提出的模糊控制器的思想，通過優(yōu)化規(guī)則庫得到其最優(yōu)窗口寬度，再在滑動窗口技術(shù)上的w2MOF上結(jié)合文獻[9]所提出的快速2kQ+P標量乘進行運算。實驗結(jié)果表明，標量乘效率得到了較大提高。

1 橢圓曲線介紹

1.1 橢圓曲線定義

定義1 定義在域K上的 Weierstrass 方程為[10]：

E:y2+a1xy+a3y=x3+a2x2+a4x+a6

(1)

其中：a1,a2,a3,a4,a6∈K,K為有限域，稱E是域K上的橢圓曲線。在實際中，式(1)可以利用相容性變換進行簡化。當char(K)=2時，若a1≠0 ，則E可以簡化為：

y2+xy=x3+ax2+b

(2)

其中：a,b∈K,Δ=b≠0 。

當char(K)≠2,3時，E可以簡化為：

y2=x3+ax+b

(3)

其中：a,b∈K,Δ=-16(4a3+27b4)≠0 。本文基于式(3)的情形進行討論。

1.2 橢圓曲線的運算法則

E(K)表示滿足于式(3)E上的點P=(x,y)∈K2的集合(外加無窮遠點O)。令P1=(x1,y1),P2=(x2,y2)為仿射坐標系下的點，-P1=(x1,-y1),則：

當P1≠±P2時：

x3= λ12-x1-x2

(4)

y3=(x1-x3)λ1-y1

(5)

當P1=P2時：

x3= λ22-2x1

(6)

y3=(x1-x3)λ2-y1

(7)

其中P3=P1+P2=(x3,y3)為上述兩點的點加或點倍，λ1=(y2-y1)/(x2-x1),λ2= (3x12+ a)/2y1。

1.3 橢圓曲線的標量乘

標量乘可以被定義為重復的加法獲得：

式中，P是橢圓曲線上的一個點，k∈[1,N-1]為正整數(shù)，N為點P的階。在整個ECC體系中，標量乘的效率高低決定了能否將其應(yīng)用到實際場合中去。對標量乘中所涉及到點加與倍點運算，用M、I、S分別表示域K上的乘法、求逆、平方運算，A、J、Jm分別代表仿射坐標、雅可比坐標、優(yōu)化的雅可比坐標，不同坐標下點加與倍點的時間消耗如表1所示。由表1可知，對于求逆運算時間消耗大的解決方法可以轉(zhuǎn)化為其他坐標系下去運算，同一坐標系下的點加與倍點運算量也有差異，比如在仿射坐標下點加運算就快于倍點運算，而在其他坐標系下倍點快于點加。平均情況下，采用J+A=J進行點加運算，2J=J進行倍點運算是提升標量乘法效率的較佳組合。

表1 點加、倍點運算時間消耗[11]

提高標量乘的效率的關(guān)鍵因素首先在k的表示上，如果只是對kP進行重復的點加，那么我們需要(k-1)次點加運算。如果將k表示為如下二進制形式：

其中ki∈{0,1}， 假設(shè)k=39=(100111)2，那么運算量在仿射坐標下由38S+76M+38I降為13S+16M+8I。由上例可知，將k表示成二進制串結(jié)合倍點與點加效率更高，并且串l的長度決定倍點的運算量，串l中非‘0’位決定點加的運算量。

2 優(yōu)化的w2MOF標量乘算法

2.1 k的有效表示

由于標量乘運算中加法與減法具有同等的運算量[6]，所以近年來對k的帶符號二進制表示成為研究的熱點之一，旨在減少k的二進制表示中的非零位數(shù)量。

算法1 二進制串轉(zhuǎn)變?yōu)镹AF[8]

輸入：(el-1,el-2,…,e0)2

輸出：(sl,sl-1,…,s0)NAF

1: k0←0;

2: for i=0 to (l-1) do

3: k(i+1)←[(ei+ki+e(i+1))/2];

4: si←ei+ki-2ki+1;

5: end for;

6： return(sl,sl-1,…,s0)

由NAF表示的二進制形式平均漢明權(quán)重可以減少為(l/3)，但是倍乘數(shù)量還是與二進制形式相同。

2MOF表示法更具有靈活性[4]，使得標量的轉(zhuǎn)換既可以從右向左進行，也可以從左向右進行，并且它的表示與NAF具有相同的平均漢明重量和表示長度，其轉(zhuǎn)換過程算法2所示。

算法2 二進制串轉(zhuǎn)變?yōu)?MOF[4]

輸入：(el-1,el-2,…,e0)2

輸出：(sl,sl-1,…,s0)2MOF

1: e-1←0;

2: i←c+1 for the 1 argest c with dc≠0;

3: sl←0;sl-1←0;…;s0←0;

4: while i≥1 do

5: if ei-1=eithen

6： si←0;i←i-1;

7: else{ei-1≠ei}

8: si←-ei+ei-2;si-1←-ei-2+ei-1;i←i-2;

9: if i=0 then

10: s0←-e0;

11: return(sl,sl-1,…,s0)

2MOF方法相對于NAF方法來說更優(yōu)越，不僅轉(zhuǎn)換過程不需要求模、除法運算，而且平均移動次數(shù)也比NAF少。

2.2 基于滑動窗口技術(shù)的w2MOF標量乘算法

算法3 基于滑動窗口技術(shù)的w2MOF標量乘

輸入：基點P，整數(shù)k，窗口寬度-w

輸出：Q=kP

1. Q=O,計算k=(el-1,el-2,…,e0)2;

2. 利用算法2計算2MOF(k);

3. 計算[n]P,n=(1，3，5，…,(2(2w-(-1)w)/3-1));

4. j=l-1;

5. while j≥0 do

6. if(sj==0)

7. Q←2Q,N←0,j←j-1;end if;

8. else

9. i←maximum(j-w+1,0);

10. while si==0 do

11. i←i+1;

12. end while;

13. for c=1 to (j-i+1) do

14. c=c+1 and Q←2Q;

15. end for;

16. N←(sj…si)2MOF;j←i-1;

17. end else;

18. if(N≥0) Q←Q+[N]P; end if;

19. else Q←Q-[N]P;end else;

20. end while;

21. return (Q)

算法3中期望的運行時間包括預計算時間和在線主計算時間，分別近似為[6]：

1D+((2w-(-1)w)/3-1)A

(8)

(l-1)D+(l/(w+v(w))-1)A

(9)

式中v(w)=4/3-(-1)w/(3·2w-2)代表‘0’在窗口之間移動的平均長度；A表示點加運算，D表示倍點運算。

2.3 優(yōu)化的滑動窗口w2MOF標量乘算法

根據(jù)算法3可以對其進行改進，也就是在掃描到連續(xù)個零位的時候?qū)ζ溥M行統(tǒng)計，然后借助文獻[9]給出的混合坐標下直接計算2kQ+P的算法進行優(yōu)化。

算法4 優(yōu)化的滑動窗口w2MOF標量乘算法

輸入： 基點P，整數(shù)k，窗口寬度-w

輸出： Q=kP

1. 算法3步驟1～步驟4；

2. while j≥0 do

3. n=0;

4. while(sj==0 and j≥0)

5. n←n+1,N←0,j←j-1;

6. end while;

7. if j≥0 then

8. i←maximum(j-w+1,0);

9. while si==0 do

10. i←i+1;

11. end while;

12. N←(sj…si)2MOF;

13. end if;

14. if(N≥0)Q←2n+j-i+1Q+[N]P;end if;

15. else Q←2n+j-i+1Q-[N]P;end else;

16. j←i-1;

17. end while;

18. return (Q)

算法4中在線主運算時間的標量乘法可以采用文獻[9]直接給出的2kQ+P算法優(yōu)化，一次計算2kQ+P的時間消耗為(7.2k+11.4)M,平均情況下算法4的時間消耗近似為[9]：

33.6M+32.8((2w-(-1)w)/3-1)M+(l/(w+

v(w))-1)[7.2(w+v(w)-1)+11.4]M

(10)

2.4 基于模糊控制器的最佳窗口寬度

由式(8)可以發(fā)現(xiàn)滑動窗口技術(shù)運算量的花費依賴于窗口的大小w，而窗口寬度最優(yōu)的選擇既可以減少ECC運算當中的點加操作，也可以減輕系統(tǒng)預計算的負擔。根據(jù)表2可以推出隨著窗口寬度的加大，預計算量也在逐增，點加和倍乘運算量在減少，變化率最大的是預計算量與點加量，所以需要在預計算量與點加量之間有一個折中點，也就是需要根據(jù)自身的環(huán)境選擇一個最佳窗口。文獻[8]提出了利用模糊控制器的思想根據(jù)規(guī)則庫自動地選擇最優(yōu)的窗口寬度，本文在此基礎(chǔ)上進行擴展。

表2 基于滑動窗口方法的不同窗口寬度比較

對于一個模糊控制器而言，主要由輸入、模糊推理系統(tǒng)、輸出三部分組成。在本文中，輸入由預計算量和點加量組成，并且它們都具有三種狀態(tài)(低，中，高)，輸出為窗口大小變化趨勢，也包含三種狀態(tài)(減小，保持，增大)。模糊推理系統(tǒng)是一系列將輸入轉(zhuǎn)變?yōu)檩敵龅囊?guī)則庫的集合，主要有Mamdani和Takagi-Sugeno兩種常用模型，本文中選擇前者。推理系統(tǒng)的規(guī)則如表3所示，規(guī)則前可以賦予一定的權(quán)重，默認為1。

表3 模糊控制器的規(guī)則庫

整個模糊控制系統(tǒng)的流程方框圖由圖1所示。根據(jù)圖所示，首先需要為窗口設(shè)置個初始值，根據(jù)標量k的2MOF編碼利用窗口技術(shù)掃描得到所需的預計算量和點加運算量。將獲得的兩變量輸入到雙輸入單輸出的模糊推理系統(tǒng)，模糊推理系統(tǒng)首先將輸入量模糊化，再將模糊化量通過規(guī)則庫獲得模糊輸出，最后通過去模糊獲得窗口變化的趨勢。

圖1 模糊控制系統(tǒng)工作流程

3 實驗結(jié)果與分析

為了將改進的基于滑動窗口技術(shù)的w2MOF算法與模糊控制器結(jié)合起來，本文通過在eclipse環(huán)境下利用Java語言隨機生成NIST推薦的橢圓曲線分別在k為160、233、283、384 bit下的2MOF表示形式，并將其存入txt文檔。在Matlab環(huán)境下，通過自帶的工具箱函數(shù)讀入txt文檔，經(jīng)過相應(yīng)地處理輸入到設(shè)計好的規(guī)則庫的模糊推理系統(tǒng)，最后得到該環(huán)境下最優(yōu)的窗口寬度。表4列出了不同標量k下的最優(yōu)窗口寬度及相應(yīng)的預計算數(shù)與點加數(shù)。

表4 不同標量k下的最優(yōu)窗口寬度

為便于比較，可按文獻[9]的假設(shè)：1S=0.8 M，1I=30 M。由表4可知，根據(jù)所設(shè)計的模糊推理系統(tǒng)計算出k=160 bit下的最優(yōu)窗口寬度為5，點加運算量為20，預計算量為10，與文獻[8]進行比較，在同樣的標量k下，基于wNAF算法在窗口寬度為5時，所需的點加運算量為39，本文提出的算法減少了19次點加運算量，假設(shè)在仿射坐標下，那么由表1可知減少的運算量為623.2 M?；诨瑒哟翱诩夹g(shù)的算法3與算法4中的預計算階段都采用仿射坐標下的倍乘與點加運算，而在主計算階段算法3中倍乘與點加采用混合坐標下的最優(yōu)計算方式如表1所示，算法4采用混合坐標下直接計算2kQ+P方式。將算法3、算法4應(yīng)用于表4不同標量k下的最優(yōu)窗口寬度中，其時間消耗如表5所示。

表5 算法3與算法4的運算量比較

根據(jù)表5可知，隨著k值的增大，兩種算法的運算量都明顯增加。在曲線NIST B-163上，算法4比算法3效率提高約12%，在曲線NIST B-233上，算法4比算法3效率提高12.2%,在曲線NIST B-283上，算法4比算法3效率提高12.3%,在曲線NIST B-384上，算法4比算法3效率提高10.6%。

4 結(jié) 語

本文首先分析了標量k的有效表示中具有相同長度和平均漢明權(quán)重的主流NAF和2MOF算法，將更有靈活性的2MOF算法與帶預計算的滑動窗口技術(shù)結(jié)合，并利用混合坐標下直接計算2kQ+P的方式提高標量乘的效率。帶預計算的滑動窗口技術(shù)需要根據(jù)自身環(huán)境首先確定最優(yōu)的窗口寬度，提出了利用模糊控制器通過預先設(shè)計的規(guī)則庫來確定窗口寬度的大小。將模糊控制器與優(yōu)化的w2MOF算法結(jié)合，實驗結(jié)果表明，算法4比算法3平均效率提高11.7%，并且與文獻[8]基于wNAF算法的滑動窗口技術(shù)在同樣的窗口下減少了19次點加運算量。

[1] Koblitz N.Elliptic curve cryptosystems[J].Mathematics of computation,1987,48(177):203-209.

[2] Miller V S.Use of elliptic curves in cryptography[C]//Advances in Cryptology—CRYPTO’85 Proceedings. Springer Berlin Heidelberg,1986:417-426.

[3] 賴忠喜,張占軍,陶東婭.橢圓曲線底層域快速算法的研究[J].計算機工程與應(yīng)用,2014,50(3):67-70.

[4] Okeya K,Schmidt-Samoa K,Spahn C,et al.Signed binary representations revisited[C]//Advances in Cryptology-CRYPTO 2004.Springer Berlin Heidelberg,2004:123-139.

[5] Balasubramaniam P,Karthikeyan E.Elliptic curve scalar multiplication algorithm using complementary recoding[J].Applied mathematics and computation,2007,190(1):51-56.

[6] Hankerson D,Vanstone S,Menezes A J.Guide to elliptic curve cryptography[M].Springer,2004.

[7] Huang X,Sharma D.Fuzzy controlling window for elliptic curve cryptography in wireless networks[C]//Computer Sciences and Convergence Information Technology (ICCIT),2010 5th International Conference on.IEEE,2010:521-526.

[8] Kodali R K,Budwal H S,Patel K,et al.Fuzzy controlled scalar multiplication for ECC[C]//TENCON Spring Conference,2013 IEEE.IEEE,2013:352-356.

[9] 李忠,彭代淵.基于滑動窗口技術(shù)的快速標量乘法[J].計算機科學,2012,39(6A):54-56,64.

[10] 周夢,周海波.橢圓曲線快速點乘算法優(yōu)化[J].計算機應(yīng)用研究,2012,29(8):3056-3058.

[11] Mahdavi R,Saiadian A.Efficient scalar multiplications for elliptic curve cryptosystems using mixed coordinates strategy and direct computations[M].Cryptology and Network Security.Springer Berlin Heidelberg,2010:184-198.

FAST W2MOF SCALAR MULTIPLICATION BASED ON FUZZY CONTROLLER

Li Chaoqun Wu Xiangqian

(SchoolofElectricalEngineering,XinjiangUniversity,Urumqi830000,Xinjiang,China)

Scalar multiplication of basis points in elliptic curve cryptosystems is one of the most time-consuming operations, but the efficiency can be improved by the way of pre-computation. By means of more flexible and efficient form of 2MOF representation, and using sliding window technology on this basis, we modified the w2MOF algorithm in combination with the computation mode of directly calculating 2kQ+P on mixed coordinates. For the selection of optimal window width using sliding window technology, we used the pre-designed fuzzy controller to make decision. According to commonly used two kinds of fuzzy inference system, the fuzzy controller chose Mamdani model. Analysis of experimental results showed that with the combination of fuzzy controller and optimised w2MOF algorithm, the average efficiency improved about 11.7%, and compared with the wNAF algorithm-based literature[1], on elliptic curve NIST-B163 and under the optimal window w=5, the amount of point adding operation reduced 19 times.

Elliptic curve cryptosystem w2MOF Mixed coordinates Sliding window Fuzzy controller

2014-12-06。李超群，碩士生，主研領(lǐng)域：公鑰密碼學。吳向前，教授。

TP309.7

A

10.3969/j.issn.1000-386x.2016.04.075