NAF點乘算法的并行計算研究*

趙前進 ，李西萍，戴紫彬，張永福

(1.解放軍信息工程大學 電子技術學院，河南 鄭州450004；2.第四軍醫(yī)大學，陜西 西安710023)

橢圓曲線密碼算法(ECC)是目前公認最有效的公鑰密碼算法，1985年由MILLER V和KOBLITZ N獨立提出的[1-2]。在ECC密碼算法中，點乘運算是最主要運算，決定著ECC密碼算法的實現(xiàn)效率。如果將定義在橢圓曲線上的點p自相加k次，把計算結果記作kp，則稱根據(jù)k計算kp的運算為點乘運算。在對常用點乘算法研究的基礎上，本文對NAF點乘算法(二進制NAF和窗口NAF點乘算法)進行了改進，改進后的NAF點乘算法具備了并行調度點加和點倍的特點,與原算法相比效率有明顯提高。

1 二進制NAF點乘算法的并行計算

減少k的二進制表示時,非0元素的個數(shù)可以提高點乘算法的效率。對k進行重新編碼，即k=(km-1,km-2,…,k0)2，其中 ki∈{0,±1}，最高位 km-1≠0，且沒有相鄰的非 0元素，稱該式為非相鄰有符號二進制表示方式NAF(Non-Adjacent Form)，并記作 NAF(k)。 用 NAF(k)代替了k的二進制表示就是二進制NAF點乘算法[3,5-6]。對k進行NAF編碼的算法和二進制NAF點乘算法見參考文獻[3]、[6]。把 k進行 NAF編碼后，ki≠0的概率為 1/3。點加用ECADD表示，點倍用ECDBL表示，則二進制NAF點乘算法的期望計算時間為:m/3 ECADD+m ECDBL。

[4]通過增加輸入的方式對Double-and-Add點乘算法進行了改進，改進后的算法具有并行運算的特點。在二進制NAF點乘算法中，假設i輪迭代的輸入值為 Q，根據(jù)對 ki值的判斷，返回值 Q′可能是 2Q-P、2Q、2Q+P。根據(jù)這個特點，本文對二進制NAF點乘算法進行了并行改進:每輪迭代輸入增加為Q-P、Q和Q+P、返回值 Q′為 Q[1]-P、Q[1]、Q[1]+P作為下一輪迭代的輸入，其中 Q[1]的值可能是 2Q-P、2Q和 2Q+P作為結果輸出。改進后的算法如圖1所示。

首先用歸納法證明Q[0]=Q[1]-P，Q[2]=Q[1]+P。當m取最小值2時：

因此m=2時,Q[0]=Q[1]-P,Q[2]=Q[1]+P成立。設當 m=k時，Q[0]=Q[1]-P,Q[2]=Q[1]+P成立，則當 m=k+1時：

因此 Q[0]=Q[1]-P，Q[2]=Q[1]+P。

而且,若 ki=-1，則 Q[1]′=2Q[1]-P;若 ki=0，則 Q[1]′=2Q[1]；若 ki=1，則 Q[1]′=2Q[1]+P。 因此 Q[1]與二進制NAF點乘算法[3,6]的輸出值是等價的。由此證明了圖1所示算法的正確性。

圖2是依據(jù)圖1算法給出的并行二進制NAF點乘算法的運算流程。

通過圖2可以看出，圖1所示算法可以使用2個點加和1個點倍運算單元并行運算完成一輪迭代，共需要進行m-1輪迭代。而一般點倍運算略快于點加運算，所以圖1所示算法期望計算時間為(m-1)ECADD。

2 窗口NAF點乘算法的并行計算

窗口NAF點乘算法與二進制NAF點乘算法具有相同的運算流程,同樣可以對窗口NAF點乘算法作并行改進：每輪迭代增加 2w-1個輸入,使輸入為 Q-(2w-1-1)P、...、Q-3P、QP、Q、Q+P、Q+3P、…、Q+(2w-1-1)P，根據(jù) ki的值選擇相應Q+kiP做點倍運算，并依次與其他輸入做點加運算，將運算結果按升序排列為 Q[1]-(2w-1-1)P、...、Q[1]-3P、Q[1]-P、Q[1]、Q[1]+P、Q[1]+3P、… 、Q[1]+(2w-1-1)P 作為 下 一 輪迭代的輸入，其中 Q[1]的值可能是 2Q-|ki|P、2Q、2Q+|ki|P，作為結果輸出。改進后的算法如圖3所示。

以窗口值 w=3為例，返回值為 Q2，給出了如圖 4所示的并行的窗口NAF點乘算法的運算流程。當窗口值時，圖3所示算法可以使用4個點加和1個點倍運算單元并行運算完成一輪迭代，共需要(m-w)輪迭代，所以圖3所示算法的期望計算時間為(m-w)ECADD。

3 分析驗證

改進后的二進制NAF點乘算法和窗口NAF點乘算法增加了迭代時輸入值的個數(shù)，點加和點倍可以并行計算，從而提高了效率，但資源消耗隨之增加。原始NAF點乘算法串行調度點加和點倍，只需要1個點倍和1個點加運算單元。改進后的二進制NAF點乘算法需要2個點加和1個點倍運算單元并行計算。而改進后的窗口NAF點乘算法，隨著窗口寬度的增加，需要的點加運算單元數(shù)量呈指數(shù)增加。表1為算法改進前后的期望計算時間和資源消耗對比。

本文以NIST推薦的二進制域上的163位隨機橢圓曲線，在ALTERA公司的EP2S90F1508C3器件上進行了實驗，表2給出了實驗結果的比較。窗口NAF點乘算法取窗口值w=3。由于隨著窗口寬度的增加，非0元素個數(shù)減少，效率隨之降低。本文對常用的NAF點乘算法進行了分析和改進，對點乘算法進行并行化處理，使得點乘算法可以并行調度點倍和點加運算，使改進后的算法具有并行運算的特點，該算法是提高點乘運算效率的一種重要途徑，同時提高了算法的安全性[4]。經(jīng)過實驗，本文提出的并行算法與原算法相比，在實現(xiàn)效率上有明顯提高。

表1 期望計算時間和資源消耗對比

表2 算法改進前后計算時間比較

參考文獻

[1]MILLER V S.Use of elliptic curves in cryptography[C].CRYPTO′85,1986:417-426.

[2]KOBLITZ N.Elliptic curve cryptosystems[J].Mathematics of computation,1987,48(4):203-209.

[3]HANKERSON D.橢圓曲線密碼學引導譯[M].張煥國,譯.北京：電子工業(yè)出版社,2005.

[4]IZU T,TAKAGI T.A fast parallel EC multiplication resistant against side channel attacks[R].CACR University of Waterloo.2002.

[5]劉雙根,李 萍.胡予濮.橢圓曲線密碼中標量乘算法的改進方案[J].計算機工程,2006,32(17):28-29.

[6]陶 然,陳麗燕.橢圓曲線密碼體制中點乘的快速算法[J].北京理工大學學報,2005,25(8):701-704.