改進的基于整數拆分形式標量乘快速算法

張 亮

(鄭州工業應用技術學院，河南 鄭州 451150)

基礎理論 doi:10.3969/j.issn.1673-5692.2016.05.007

改進的基于整數拆分形式標量乘快速算法

張 亮

(鄭州工業應用技術學院，河南 鄭州 451150)

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

橢圓曲線密碼；標量乘法；折半運算；整數拆分形式

0 引 言

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

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

1 背景知識介紹

1.1 帶符號整數拆分形式表示

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

(1)

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

(2)

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

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

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

輸入：n,k；

輸出：SIS(k)。

1.對于i從1到n，重復執行：ai=0；

2.令s=1；

3.如果k>0，則執行：

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)，則執行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 折半運算

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

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

(3)

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

(4)

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

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

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

(5)

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

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

輸入：Q=(x3,y3)；

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

1.根據式μ2+μ+a=x3求解μ；

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

4.返回值(x1,y1)。

2 新算法設計

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

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

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

(6)

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

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

第二步：將折半運算應用在拆分數列f(i)的預計算構造中，得到預計算表PHi；

第三步：根據查找預計算表，將標量乘法運算kP轉化為計算一組橢圓曲線上的點的累加和的形式，則可得返回結果。

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

算法3 基于ISIS的標量乘快速算法

輸入：k,P；

輸出：Q=kP。

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

2.構造預計算表PHi；

3.令Q=O，其中O無窮遠點；

4.對于i從1到n，重復執行：

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

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

5.返回Q。

其中，預計算表PHi固定且可預先存儲在應用系統中。則構造預計算表的具體過程如算法4所示：

算法4 預計算表PHi的構造算法

輸入：n,P；

輸出：預計算表PHi。

1.令Q=O；

2.對于i從1到mi，重復執行：

2.1R=Q/2；

2.2PHi=R+P；

2.3Q=PHi+Q；

3.返回PHi。

3 算法性能分析

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

表1 算法3與傳統ISF算法及SISF算法運算量比較

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

表2 不同坐標系下算法3與傳統ISF算法及SISF算法的執行效率比較

4 結 語

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

[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]．中國電子科學研究院學報，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] 石潤華，鐘誠．基于整數拆分的橢圓曲線密碼體制上的快速點乘算法[J]．計算機工程與科學，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]．計算機科學，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—)，男，河南人，講師，主要研究方向為計算機網絡及安全。

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

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

：A

1673-5692(2016)05-490-05