改進(jìn)的基于整數(shù)拆分形式標(biāo)量乘快速算法

張 亮

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院，河南 鄭州 451150)

基礎(chǔ)理論 doi:10.3969/j.issn.1673-5692.2016.05.007

改進(jìn)的基于整數(shù)拆分形式標(biāo)量乘快速算法

張 亮

(鄭州工業(yè)應(yīng)用技術(shù)學(xué)院，河南 鄭州 451150)

標(biāo)量乘運算是橢圓曲線密碼的關(guān)鍵運算。為有效提高橢圓曲線密碼標(biāo)量乘法的運算效率，給出了一種改進(jìn)的帶符號整數(shù)拆分形式標(biāo)量乘快速算法。首先通過對標(biāo)量進(jìn)行帶符號的整數(shù)拆分形式編碼，然后將標(biāo)量乘運算轉(zhuǎn)化為由一組橢圓曲線上的點累加和形式進(jìn)行計算，同時在預(yù)計算階段采用更為高效的折半運算代替倍點運算。算法性能分析的結(jié)果表明：與已有的基于整數(shù)拆分形式標(biāo)量乘快速算法相比，新算法的能夠大幅提升運算效率，在應(yīng)用橢圓曲線密碼的各種系統(tǒng)中具有較好的實際應(yīng)用價值。

橢圓曲線密碼；標(biāo)量乘法；折半運算；整數(shù)拆分形式

0 引 言

橢圓曲線密碼體制(Elliptic Curve Cryptogram, ECC)是于1985年Koblitz N與Miller V最早提出來的。ECC是將離散對數(shù)有限循環(huán)群替換成有限域上的橢圓曲線有限群所構(gòu)造的密碼體制，算法的安全性是建立在橢圓曲線對數(shù)問題的難解性之上的，同其余傳統(tǒng)的密碼算法相比，具備所需密鑰長度更短，存儲空間更小等優(yōu)點[1-2]。其核心運算主要是計算在橢圓曲線群上的標(biāo)量乘法運算，它的運算速度決定著密碼系統(tǒng)整體執(zhí)行效率的關(guān)鍵。國內(nèi)外的研究學(xué)者在橢圓曲線密碼的標(biāo)量乘法運算方面做出了許多建設(shè)性的工作，為逐步提高橢圓曲線密碼的運算效率，加快推進(jìn)橢圓曲線密碼實際應(yīng)用做了大量貢獻(xiàn)。采用m_ary算法是橢圓曲線密碼標(biāo)量乘法運算的傳統(tǒng)運算方式，主要是通過多次使用點加操作與倍點操作來計算[3]。近年來，其它一些標(biāo)量乘快速算法也被較多的提出來[4-5]。其中，文獻(xiàn)[6]中石潤華等人提出了一種基于整數(shù)拆分的標(biāo)量乘快速算法，并結(jié)合預(yù)計算的方法，能有效提升標(biāo)量乘法的計算效率。文獻(xiàn)[7]中Kundsen E等人則提出了一種基于折半運算的橢圓曲線密碼的快速標(biāo)量乘算法，其中所提算法采用的折半運算比倍點操作能夠提升大約一倍的效率。

通過分析基于整數(shù)拆分形式快速標(biāo)量乘法的特性，可以將整數(shù)拆分形式轉(zhuǎn)換成帶符號的形式，從而能有效減少拆分次數(shù)。同時由于折半運算的效率要優(yōu)于倍點運算，因而在標(biāo)量乘算法的預(yù)計算階段，可以用更加高效折半運算操作替代標(biāo)量乘法運算中的倍點操作來進(jìn)行計算，從而給出一種改進(jìn)的基于帶符號整數(shù)拆分形式標(biāo)量乘快速算法(Improved fast scalar multiplication based on Signed Integer Splitting form，ISIS)，該算法可以有效提升橢圓曲線密碼標(biāo)量乘的計算效率。同傳統(tǒng)的基于整數(shù)拆分形式標(biāo)量乘算法相比，給出的改進(jìn)算法能有效提升標(biāo)量乘法的運算效率。

1 背景知識介紹

1.1 帶符號整數(shù)拆分形式表示

對于任一正整數(shù)都可以由一組長度有限的數(shù)列(f(1),f(2),…,f(n))表示，只需滿足這個數(shù)列的和不大于這個整數(shù)。文獻(xiàn)[8]從具體的數(shù)學(xué)模型中抽象出了數(shù)列f(n)的定義，并采用歸納法給出了該定理正確性的證明。假設(shè)存在一組無窮數(shù)列{f(1),f(2),…,f(n),…}，則有：

(1)

其中，n可以為任意的正整數(shù)。則稱式(1)為拆分?jǐn)?shù)列。

(2)

其中，ai表示拆分系數(shù)，則稱式(2)正整數(shù)k的整數(shù)拆分形式，記為SIS(k)。

整數(shù)k基于帶符號整數(shù)拆分形式的編碼算法過程如下面算法1所示：

算法1 整數(shù)k帶符號整數(shù)拆分形式的編碼算法

輸入：n,k；

輸出：SIS(k)。

1.對于i從1到n，重復(fù)執(zhí)行：ai=0；

2.令s=1；

3.如果k>0，則執(zhí)行：

3.1 如果k=1，則ai=s,k=0；

3.2 否則i=2；

3.3 如果(!(f(i-1)

3.3.1 如果k>((f(i)-1)/2)，則執(zhí)行k=f(i)-k，ai=s，s=-s；

3.3.2 否則k=k-f(i-1),ai-1=s；

4.返回SIS(k)=(an,an-1,…,a1)。

1.2 折半運算

假定在二進(jìn)制域F2m上定義了一個橢圓曲線E，如式(3)所示：

E:y2+xy=x3+ax+b,a,b∈F2m,b≠0

(3)

在橢圓曲線E上定義一個點P=(x1,y1)，而且這個點滿足P∈E(F2m)，并且有P≠-P。則在仿射坐標(biāo)系下計算倍點操作運算2P=(x3,y3)，其中坐標(biāo)值如式(4)所示：

(4)

由文獻(xiàn)[9]所給定理可以看出，在一個橢圓曲線上能夠定義倍點運算的一種逆操作運算，如以下定理1所示：

定理1(折半運算)假定在橢圓曲線E上有一個n階子群{G}(n是奇數(shù))，倍點操作和折半操作在子群{G}上自同構(gòu)。則對任一點Q∈{G}，都將存在一個點P∈{G}，滿足Q=2P。

橢圓曲線上定義倍點運算的逆操作運算稱為折半運算，其是表示在二進(jìn)制域F2m中，當(dāng)Q=(x3,y3)為定點時，可計算出定義在橢圓曲線E上的點P=(x1,y1)。即根據(jù)式(4)計算出μ,x1,y1，計算公式如式(5)所示：

(5)

橢圓曲線上的折半運算操作如算法2所示[10]：

算法2 橢圓曲線折半運算操作算法

輸入：Q=(x3,y3)；

輸出：P=1/2Q=(x1,y1)。

1.根據(jù)式μ2+μ+a=x3求解μ；

2.計算η=y3-(μ+1)x3；

4.返回值(x1,y1)。

2 新算法設(shè)計

所給的基于折半運算和帶符號整數(shù)拆分形式的標(biāo)量乘快速算法，其基本思想是：首先通過將一個正整數(shù)標(biāo)量拆分成以類基(f(1),f(2),…,f(n))相加的表示形式，且拆分系數(shù)為{-1,0,1}中之一，然后標(biāo)量乘中的倍點運算用更高效的折半運算代替，同時結(jié)合預(yù)計算的方法，將標(biāo)量乘法運算轉(zhuǎn)化成為計算橢圓曲線上一組點的累加和的形式。則基于ISIS標(biāo)量乘法運算如式(6)所示：

=a1·f(1)P+a2·f(2)P+…+an·f(n)P

=a1·PH1+a2·PH2+…+an·PHn

(6)

其中，mi為拆分?jǐn)?shù)列的折半運算編碼長度，mmax為最大長度。如果拆分?jǐn)?shù)列f(i)的折半運算編碼長度不足mmax位時，可將剩余的(ji-m)位全部補充為0。PHi為采用折半運算的預(yù)計算表。下面給出基于折半運算和帶符號整數(shù)拆分形式標(biāo)量乘快速算法的具體執(zhí)行過程：

第一步：計算出已知標(biāo)量k的帶符號整數(shù)拆分編碼SIS(k)=(an,an-1,…,a1)；

第二步：將折半運算應(yīng)用在拆分?jǐn)?shù)列f(i)的預(yù)計算構(gòu)造中，得到預(yù)計算表PHi；

第三步：根據(jù)查找預(yù)計算表，將標(biāo)量乘法運算kP轉(zhuǎn)化為計算一組橢圓曲線上的點的累加和的形式，則可得返回結(jié)果。

則基于折半運算和帶符號整數(shù)拆分形式的標(biāo)量乘快速算法如算法3所示：

算法3 基于ISIS的標(biāo)量乘快速算法

輸入：k,P；

輸出：Q=kP。

1.計算出已知標(biāo)量k的帶符號整數(shù)拆分表示形式SIS(k)=(an,an-1,…,a1)；

2.構(gòu)造預(yù)計算表PHi；

3.令Q=O，其中O無窮遠(yuǎn)點；

4.對于i從1到n，重復(fù)執(zhí)行：

4.1 如果ai=1，則Q=Q+PHi；

4.2 如果ai=-1，則Q=Q-PHi；

5.返回Q。

其中，預(yù)計算表PHi固定且可預(yù)先存儲在應(yīng)用系統(tǒng)中。則構(gòu)造預(yù)計算表的具體過程如算法4所示：

算法4 預(yù)計算表PHi的構(gòu)造算法

輸入：n,P；

輸出：預(yù)計算表PHi。

1.令Q=O；

2.對于i從1到mi，重復(fù)執(zhí)行：

2.1R=Q/2；

2.2PHi=R+P；

2.3Q=PHi+Q；

3.返回PHi。

3 算法性能分析

算法3中，步驟2采用算法4中基于折半運算的預(yù)計算表構(gòu)造算法，其運算量為mavg(H+2A)，其中mavg為拆分?jǐn)?shù)列f(i)基于折半運算的平均編碼長度。步驟4的主循環(huán)運算中，令navg為平均執(zhí)行循環(huán)操作的次數(shù)，且有navg≈2/3·n，則主循環(huán)運算所需運算量為navgA。因此算法3所需總的運算量為mavgH+(navg+2mavg)A。令p為傳統(tǒng)的整數(shù)拆分編碼長度，pavg為傳統(tǒng)基于整數(shù)拆分標(biāo)量乘算法平均執(zhí)行循環(huán)操作次數(shù)，lavg為拆分?jǐn)?shù)列的平均二進(jìn)制編碼長度，則傳統(tǒng)基于整數(shù)拆分形式的標(biāo)量乘算法所需總運算量為lavgD+(pavg+2lavg)A。令t為傳統(tǒng)的整數(shù)拆分編碼長度，tavg為帶符號的基于整數(shù)拆分標(biāo)量乘算法平均執(zhí)行循環(huán)操作次數(shù)，savg為帶符號拆分?jǐn)?shù)列的平均二進(jìn)制編碼長度，則帶符號的基于整數(shù)拆分形式的標(biāo)量乘算法所需總運算量為savgD+(tavg+2savg)A。其中，H表示折半運算，D表示倍點運算，A表示點加運算。表1給出了算法3與傳統(tǒng)基于整數(shù)拆分形式標(biāo)量乘算法(ISF)以及基于帶符號的整數(shù)拆分形式標(biāo)量乘算法(SISF)的運算量比較。

表1 算法3與傳統(tǒng)ISF算法及SISF算法運算量比較

由表2可知，與傳統(tǒng)基于整數(shù)拆分表示形式標(biāo)量乘算法相比，預(yù)計算的運算效率提升了約39.65%～46.89%，主循環(huán)的運算效率提升了約29.04%。與基于帶符號的整數(shù)拆分表示形式標(biāo)量乘算法相比，預(yù)計算的運算效率提升了約30.83%～39.13%，主循環(huán)的運算效率保持不變，這事因為算法3采用的是帶符號整數(shù)拆分形式編碼，與基于帶符號的整數(shù)拆分表示形式標(biāo)量乘算法的編碼長度相同，且類基拆分?jǐn)?shù)列及符號相同，則有相同的拆分?jǐn)?shù)列二進(jìn)制編碼長度。綜上所述，則可知算法3總的計算效率與已有的基于整數(shù)拆分表示形式標(biāo)量乘相比提升了大約22.24%～41.76%。這是因為通過將標(biāo)量采用帶符號的整數(shù)拆分形式表示，可以相對減少標(biāo)量的編碼長度，從而可以提升預(yù)計算階段和主循環(huán)階段的運算效率，同時在預(yù)計算階段通過采用折半運算替代倍點運算，可以進(jìn)一步提高標(biāo)量乘法的運算效率，而由于主循環(huán)運算階段只包含點加操作運算，不需應(yīng)用折半運算。因此所給算法3能有效提升標(biāo)量乘運算的效率，可以很好地滿足各種橢圓曲線密碼系統(tǒng)的需求，特別是對存儲空間和時間都比較高但資源卻受限的模塊或系統(tǒng)之中。

表2 不同坐標(biāo)系下算法3與傳統(tǒng)ISF算法及SISF算法的執(zhí)行效率比較

4 結(jié) 語

橢圓曲線密碼中的標(biāo)量乘運算主要是反復(fù)進(jìn)行點加運算和倍點運算，是提升橢圓曲線密碼算法效率的關(guān)鍵。通過分析標(biāo)量的整數(shù)拆分表示形式可知，采用帶符號的整數(shù)拆分編碼方法和折半運算，利用折半運算替代倍點運算，通過計算基于折半運算的預(yù)計算表，因為折半運算同倍點運算相比，其運算效率較高，因而可以有效提高標(biāo)量乘的運算效率，所給算法在橢圓曲線密碼標(biāo)量乘算法中能夠大幅提高運算效率。由算法性能分析可知，所給算法能夠較好地用于各類密碼應(yīng)用模塊中，有較好的研究意義與實際應(yīng)用價值。

[1] Antao S, Bajard J, Sousa L.Elliptic curve point multiplication on gpus [C]//Proceedings of the 21th IEEE Int.Conf.on Application-Specific Systems, Architectures and Processors, 2010:192-199.

[2] 艾樹峰．二元域乘法器的研究[J]．中國電子科學(xué)研究院學(xué)報，2009，4(3)：320-322．

[3] Purohit G N, Rawat S A.Fast scalar multiplication in ECC using the multi base number system [J].International Journal of Computer Science Issues, 2011, 8(1):131-137.

[4] 王正義，趙俊閣．ECC抗功率分析攻擊的等功耗編碼算法[J]．計算機工程，2012，38(10)：111-113．

[5] WU Tao, LIU Li-tian.Elliptic curve point multiplication by generalized mersenne numbers[J].Journal of Electronic Science and Technology, 2012, 10(3):199-208.

[6] 石潤華，鐘誠．基于整數(shù)拆分的橢圓曲線密碼體制上的快速點乘算法[J]．計算機工程與科學(xué)，2005，27(5)：66-67.

[7] Knudsen E.Elliptic scalar multiplication using point halving [C]//Advances in Cryptology-ASIACRYPT’99.New Youk:Springer-Verlag, 1999, 1716(274):135-149.

[8] Morain F, Olivos J.Speeding up the computations on an elliptic curve using addition-subtraction chains [J].Theoretical Informatics and Applications, 1990, 24(6):120-126.

[9] Purohit G N, Rawat S A, Kumar M.Elliptic curve point multiplication using MBNR and point halving [J].International Journal of Advanced Networking and Applications, 2012, 3(5):1329-1337．

[10]王玉璽，張串絨，張柄虹．一種改進(jìn)的固定基點標(biāo)量乘快速算法[J]．計算機科學(xué)，2013，40(10)：135-138.

[11]Fong K, Hankerson D, Lopez J, et al.Field inversion and point halving revisited[J].IEEE Transactions on Computers, 2004, 53(8):1047-1059．

[12]Barua R, Pandey S K, Pankaj R.Efficient window-based scalar multiplication on elliptic curves using double- base number system [C]//Lecture Notes in Computer Science, Berlin:Springer-Verlag, 2007:351-360．

張 亮(1983—)，男，河南人，講師，主要研究方向為計算機網(wǎng)絡(luò)及安全。

E-mail:wangzy7134@163.com

Improved Fast Scalar Multiplication Algorithm Based on Signed Integer Splitting Form

ZHANG Liang

(Zhengzhou University of industrial technology, Henan Zhengzhou 451150, China)

The scalar multiplication is the key operation in elliptic curve cryptography.To improve the efficiency of scalar multiplication effectively, a novel improved fast scalar multiplication algorithm based on signed integer splitting algorithm for elliptic curve cryptography is proposed.Firstly, the scalar is coded by signed integer splitting form, and then the scalar multiplication is transformed into a accumulate sum form by a group of points in elliptic curve.Meanwhile, point halving which higher efficient is used to replace point doubling on the stage of pre-computation.The results of performance analysis show that the proposed scheme could improve the operation efficient of scalar multiplication greatly for elliptic curve cryptography by comparing with existed scalar multiplication algorithm based on integer splitting.Hence the proposed scheme could has better practical value in different systems which applying the elliptic curve cryptography.

ellipse curve cryptography；scalar multiplication；point halving；integer splitting form

2015-12-01

2016-03-01

河南省基礎(chǔ)與前沿技術(shù)研究計劃項目(142300410283)；河南省軟科學(xué)研究計劃項目(142400410179)；河南省教育廳科學(xué)技術(shù)研究重點項目(12B520063，14B520065)；河南省高等學(xué)校青年骨干教師資助計劃項目(2013GGJS-230)

：A

1673-5692(2016)05-490-05