李超群 吳向前

基于模糊控制器的w2MOF快速標(biāo)量乘算法

李超群 吳向前

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

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

橢圓曲線密碼體制 w2MOF 混合坐標(biāo) 滑動(dòng)窗口 模糊控制器

0 引 言

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

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

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

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上的橢圓曲線。在實(shí)際中，式(1)可以利用相容性變換進(jìn)行簡(jiǎn)化。當(dāng)char(K)=2時(shí)，若a1≠0 ，則E可以簡(jiǎn)化為：

y2+xy=x3+ax2+b

(2)

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

當(dāng)char(K)≠2,3時(shí)，E可以簡(jiǎn)化為：

y2=x3+ax+b

(3)

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

1.2 橢圓曲線的運(yùn)算法則

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

當(dāng)P1≠±P2時(shí)：

x3= λ12-x1-x2

(4)

y3=(x1-x3)λ1-y1

(5)

當(dāng)P1=P2時(shí)：

x3= λ22-2x1

(6)

y3=(x1-x3)λ2-y1

(7)

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

1.3 橢圓曲線的標(biāo)量乘

標(biāo)量乘可以被定義為重復(fù)的加法獲得：

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

表1 點(diǎn)加、倍點(diǎn)運(yùn)算時(shí)間消耗[11]

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

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

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

2.1 k的有效表示

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

算法1 二進(jìn)制串轉(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表示的二進(jìn)制形式平均漢明權(quán)重可以減少為(l/3)，但是倍乘數(shù)量還是與二進(jìn)制形式相同。

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

算法2 二進(jìn)制串轉(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方法相對(duì)于NAF方法來說更優(yōu)越，不僅轉(zhuǎn)換過程不需要求模、除法運(yùn)算，而且平均移動(dòng)次數(shù)也比NAF少。

2.2 基于滑動(dòng)窗口技術(shù)的w2MOF標(biāo)量乘算法

算法3 基于滑動(dòng)窗口技術(shù)的w2MOF標(biāo)量乘

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

輸出：Q=kP

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

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

3. 計(jì)算[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中期望的運(yùn)行時(shí)間包括預(yù)計(jì)算時(shí)間和在線主計(jì)算時(shí)間，分別近似為[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’在窗口之間移動(dòng)的平均長度；A表示點(diǎn)加運(yùn)算，D表示倍點(diǎn)運(yùn)算。

2.3 優(yōu)化的滑動(dòng)窗口w2MOF標(biāo)量乘算法

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

算法4 優(yōu)化的滑動(dòng)窗口w2MOF標(biāo)量乘算法

輸入： 基點(diǎn)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中在線主運(yùn)算時(shí)間的標(biāo)量乘法可以采用文獻(xiàn)[9]直接給出的2kQ+P算法優(yōu)化，一次計(jì)算2kQ+P的時(shí)間消耗為(7.2k+11.4)M,平均情況下算法4的時(shí)間消耗近似為[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)滑動(dòng)窗口技術(shù)運(yùn)算量的花費(fèi)依賴于窗口的大小w，而窗口寬度最優(yōu)的選擇既可以減少ECC運(yùn)算當(dāng)中的點(diǎn)加操作，也可以減輕系統(tǒng)預(yù)計(jì)算的負(fù)擔(dān)。根據(jù)表2可以推出隨著窗口寬度的加大，預(yù)計(jì)算量也在逐增，點(diǎn)加和倍乘運(yùn)算量在減少，變化率最大的是預(yù)計(jì)算量與點(diǎn)加量，所以需要在預(yù)計(jì)算量與點(diǎn)加量之間有一個(gè)折中點(diǎn)，也就是需要根據(jù)自身的環(huán)境選擇一個(gè)最佳窗口。文獻(xiàn)[8]提出了利用模糊控制器的思想根據(jù)規(guī)則庫自動(dòng)地選擇最優(yōu)的窗口寬度，本文在此基礎(chǔ)上進(jìn)行擴(kuò)展。

表2 基于滑動(dòng)窗口方法的不同窗口寬度比較

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

表5 算法3與算法4的運(yùn)算量比較

根據(jù)表5可知，隨著k值的增大，兩種算法的運(yùn)算量都明顯增加。在曲線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é) 語

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

[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].計(jì)算機(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] 李忠,彭代淵.基于滑動(dòng)窗口技術(shù)的快速標(biāo)量乘法[J].計(jì)算機(jī)科學(xué),2012,39(6A):54-56,64.

[10] 周夢(mèng),周海波.橢圓曲線快速點(diǎn)乘算法優(yōu)化[J].計(jì)算機(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)域：公鑰密碼學(xué)。吳向前，教授。

TP309.7

A

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