張 亮

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

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

0 引 言

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

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

1 背景知識(shí)介紹

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

對(duì)于任一正整數(shù)都可以由一組長(zhǎng)度有限的數(shù)列(f(1),f(2),…,f(n))表示，只需滿足這個(gè)數(shù)列的和不大于這個(gè)整數(shù)。文獻(xiàn)[8]從具體的數(shù)學(xué)模型中抽象出了數(shù)列f(n)的定義，并采用歸納法給出了該定理正確性的證明。假設(shè)存在一組無(wú)窮數(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基于帶符號(hào)整數(shù)拆分形式的編碼算法過(guò)程如下面算法1所示：

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

輸入：n,k；

輸出：SIS(k)。

1.對(duì)于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 折半運(yùn)算

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

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

(3)

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

(4)

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

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

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

(5)

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

算法2 橢圓曲線折半運(yùn)算操作算法

輸入：Q=(x3,y3)；

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

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

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

4.返回值(x1,y1)。

2 新算法設(shè)計(jì)

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

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

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

(6)

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

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

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

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

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

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

輸入：k,P；

輸出：Q=kP。

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

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

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

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

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

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

5.返回Q。

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

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

輸入：n,P；

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

1.令Q=O；

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

2.1R=Q/2；

2.2PHi=R+P；

2.3Q=PHi+Q；

3.返回PHi。

3 算法性能分析

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

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

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

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

4 結(jié) 語(yǔ)

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

[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] 艾樹(shù)峰．二元域乘法器的研究[J]．中國(guó)電子科學(xué)研究院學(xué)報(bào)，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]．計(jì)算機(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] 石潤(rùn)華，鐘誠(chéng)．基于整數(shù)拆分的橢圓曲線密碼體制上的快速點(diǎn)乘算法[J]．計(jì)算機(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)的固定基點(diǎn)標(biāo)量乘快速算法[J]．計(jì)算機(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—)，男，河南人，講師，主要研究方向?yàn)橛?jì)算機(jī)網(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ù)研究計(jì)劃項(xiàng)目(142300410283)；河南省軟科學(xué)研究計(jì)劃項(xiàng)目(142400410179)；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(12B520063，14B520065)；河南省高等學(xué)校青年骨干教師資助計(jì)劃項(xiàng)目(2013GGJS-230)

：A

1673-5692(2016)05-490-05