橢圓曲線快速算法的改進

摘要:從二進制域上元素間的算術(shù)運算和橢圓曲線上元素間的運算兩個層次，對橢圓曲線進行了基于標量乘法的加速運算，改進了橢圓曲線快速算法。進一步對運算效率進行了分析和比較。

關(guān)鍵詞:橢圓曲線;快速算法;算法分析

中圖分類號:TP311文獻標識碼:A文章編號:1009-3044(2009)24-687-02

The Amelioration of ECC Accelerating Operation

LI Yan-hai， MA Yin-di

(Department of Mathematics， Shaanxi University of Technology， Hanzhong 723000， China)

Abstract: The accelerating operation of ellipse curve is given based on scalar quantity multiplication， and the operation is improved from two facets which are arithmetic operations in element of binary system and the operation in element of ellipse curve. Then the efficiency of algorithm is analyzed and compared with RSA.

Key words: ellipse curve; accelerating operation; algorithm analyses

橢圓曲線加密體制ECC[1]是一種能適應(yīng)未來通信技術(shù)和信息安全技術(shù)發(fā)展的新型密碼體制，相對于以往基于RSA[2]加密算法具有安全性能更好、計算量小和處理速度快、存儲空間占用小、帶寬要求低等優(yōu)勢。在安全性要求差不多的情況下，使用較短密鑰的ECC比使用RSA具有計算上的優(yōu)勢，所以目前ECC已成為公鑰密碼體制中的研究熱點。

雖然ECC的速度比RSA等公鑰體制快，實際上相對于對稱密鑰密碼體制仍然很慢，于是提高ECC的計算速度成為ECC研究的一項重要任務(wù)。加速ECC算法可分為兩個獨立的步驟:第一步，加速底層域運算。尋找適當?shù)幕岣哂蛑谐朔e運算、逆運算的速度是加速底層運算速度的有效方法.目前普遍采用的是多項式基和正規(guī)基，這是一種普適性方案，速度的改善很有限.對于具體的域，可選基的自由度更大，所以可以進一步優(yōu)化計算。第二步，加速群運算。尋找一般的或針對某些域和橢圓曲線(ECC)的特殊方法，優(yōu)化ECC的加法、倍乘運算.典型的有:利用特殊域結(jié)構(gòu)、具體橢圓曲線的結(jié)構(gòu)，提出了許多快速算法。該文主要從關(guān)于有限域F2m上元素間的算術(shù)運算和關(guān)于橢圓曲線上元素間的運算兩方面對ECC運算作了改進和分析。

1 ECC快速算法的改進及分析

1.1 二進制域上的ECC加速運算的改進

1) 將F2m上的元素用最優(yōu)正規(guī)基表示

在F2m中最優(yōu)正規(guī)基ONB[3]只對某些m值存在.多項式集合{x，x21，…，x2m-2，x2m-1}為F2m上的ONB.故F2m中的每一個元素可以表示成m維向量。

令a=(a0，a1，…， am-2，am-1)，b=(b0，b1，…bm-2，bm-1)是F2m中的兩個元素，則:

加法運算:可以通過將向量a，b表示的相應(yīng)位異或得到。

平方運算:可以通過向量表示的循環(huán)移位完成.

乘法運算:設(shè)c=(c0，c1，…，cm-2 ，cm-1)，其中系數(shù)ck用公式(1)計算得到。

式中所有下標都模m處理，其中λi，j為矩陣λ的元素[4]。

乘法逆運算:F2m中的乘法[5]可在L(m-1)+W(m-1)-2次域乘法內(nèi)完成。

2) 標量乘法快速算法

令P∈E(F2m)，求Q=nP。

1) 算法的主要思想

將整數(shù)n表示成二進制數(shù)(ni-1ni-2… n1n0)，ni-1≠0，且nj∈(0，1)，0≤j≤i-2。將二進制數(shù)從高位開始平均分組，i=kt+r，每組k個二進制位，分成t組，r為剩余的二進制位個數(shù)，r

2) 算法

輸入:P=(x，y); 輸出:Q=nP

(1) 計算并保存pe0，pe1，…，pet-1和prr，設(shè)|ei|和|rr|分別表示ei和rr的數(shù)值。

Ⅰ. P[0] ←O(無窮遠點)

Ⅱ. 計算前2k-1個標量乘法，分別保存在數(shù)組p[2k]中

for i=0 to 2k-2p[i+1]=p[i]+P;

(2) 計算t組的和

Ⅰ. Q←O

Ⅱ. for i=t to 0

{ 執(zhí)行Q←2kQ; Q←Q+p[|ei|] };

(3) 加上余數(shù)的標量乘

Ⅰ. Q←2rQ+p[|rr|];

Ⅱ. 返回Q;

3) 算法分析

第(1)步中的步驟Ⅱ需要(2k-3)次加法和1次加倍，第(2)步中的步驟Ⅱ需要計算kt次加倍和t次加法，第(3)步中的步驟Ⅰ需要1次加法。所以算法的復(fù)雜性為(kt+1)次加倍，(2k-2+t)次加法.一旦我們確定了n，關(guān)鍵是選擇k，使得加倍運算和加法運算盡量少。

可以列出方程組:

得到f >2k+(n/k) -k+(n-1)，這里k取整數(shù)，且對于給定的n，可以通過程序遍歷k(1≤k≤n/2)，求得f的最小值。這里得到的k就是我們所要得值。

我們假定n是161位表示的二進制數(shù)的位數(shù)，則k取4時，計算量最小，為161次加倍，54次加法。

如果直接計算標量乘法nP，則需要2kt+r-1次加法和1次加倍.這是隨著n呈指數(shù)級增長的.所以，n越大，算法節(jié)省的計算量越大。

4) 算法驗證

在Intel P3 930MHz處理器，128M內(nèi)存，linux 2.4環(huán)境下

(1) 這里選用NIST推薦的曲線和域參數(shù)

Degree 163 Binary Field from fips186-2: t^163 + t^7 + t^6 + t^3 + 1

Pseudorandom curve E: y^2 + xy = x^3 + x^2 + b，

a=1，b = 2 0a601907 b8c953ca 1481eb10 512f7874 4a3205fd

Base point order:

n=5846006549323611672814742442876390689256843201587

Base point P:

Px=3f0eba16286a2d57ea0991168d4994637e8343e36

Py=0d51fbc6c71a0094fa2cdd545b11c5c0c 797324f1

Cofactor h = 2

(2) 用上面的算法對橢圓上的點作一次標量乘法(n=161)所需時間為:0.14 seconds

(3) 而用直接加倍[6]的方法對橢圓上的點作一次標量乘法(n=161)所需時間為:0.17 seconds

1.2 二進制域上元素間運算的分析

求逆運算是最費時的，考慮(xk，yk)=2kP的計算。通過省略計算中間點2P， 22P，…， 2k-1P，可以節(jié)省k-1次求逆運算，但引入了多余的乘法運算。在實際應(yīng)用中m≥160，所以1次逆運算大于5次乘法運算[1].這里設(shè)一個比較因子對于直接求2kP，隨著k值的增加，比較因子越小[6]。

但是隨著k值增加，(xk，yk)的表達式也越來越復(fù)雜，難免出錯，所以在實際應(yīng)用中，應(yīng)合理選取k。

將此直接求k倍點的方法應(yīng)用于上面的快速計算nP的算法中，在n取161位，k=4時，可直接求出2kQ。

經(jīng)驗證，在以上所提的實驗環(huán)境下，測得運算時間相當于原來的85.71%。通過將本文提到的兩種改進方法混合使用，測得運算時間為原來的72.54%。

2 小結(jié)

橢圓曲線的實現(xiàn)效率直接影響到其推廣程度，該文主要從關(guān)于二進制域上元素間的算術(shù)運算和橢圓曲線中元素間的運算兩個方面對ECC計算作了分析，實現(xiàn)了標量乘法的快速計算。經(jīng)驗證，在linux 2.4的系統(tǒng)實驗環(huán)境中，將該文所提出的改進方法混合使用，可以節(jié)省13.17%的運算時間，運算速度更快。

參考文獻:

[1] Koblitz N.Ellipticcurvecryptosystems[J].Mathematics of Computation， 1987， 48 (177):203-209.

[2] IEEE std 1363-2000. IEEE Standard Specification for Public-Key Cryptography[S].2000-01-30.

[3] R M Wilson. Optimal Normal bases in GF(pn)[J]. Discrete Applied Mathematics， 1988/89， 22: 149-161.

[4] I.F. Blake， G. Seroussi， N. P. Smart. Elliptic Curves in Cryptography， LMS Lecture Notes Series[M ]. Cambridge University Press， Vol. 265， July， 1999.

[5] Muller V. Fast multiplication on elliptic curvers over small fields of characteristic two[J]. Journal of Cryptology， 1998，11.

[6] Yasuyuki， Kouichi. Speeding Up Elliptic Schalar Multiplication Using Multi-doubling [J].IEICE Transations， 2002， E85-A (5): 1075-1083.