基于多基數(shù)系統(tǒng)的優(yōu)化多標(biāo)量乘快速算法

殷新春，張海靈，楊婷

(揚(yáng)州大學(xué) 計算機(jī)科學(xué)與工程系，江蘇 揚(yáng)州 225009)

1 引言

自Koblitz和Miller[1]分別提出橢圓曲線密碼體制(ECC, elliptic curve cryptography)以來，一直得到眾多密碼學(xué)家及密碼學(xué)研究者的青睞。標(biāo)量乘法，即已知域內(nèi)整數(shù)k和橢圓曲線上一點(diǎn)P，求kP的運(yùn)算。它是 ECC中最基本最耗時的運(yùn)算，也是EC-DH、EC-NR、EC-DSA等協(xié)議的核心部分[2]。一些基于ECC的密碼協(xié)議需要計算多標(biāo)量乘，如ECDSA的驗(yàn)證部分需要計算kP+lQ，以及多重數(shù)字簽名[3]等。

一種計算多標(biāo)量乘的方法是分別計算m個標(biāo)量乘kiPi的值，再對其進(jìn)行求和，但這個方法效率不高。為了提高計算效率，較直接有效的方法就是改進(jìn)標(biāo)量的表示，如非鄰接型(NAF)、聯(lián)合稀疏型(JSF)及窗口法[1,4]等。雙基數(shù)系統(tǒng)(DBNS, dou ble-base number system)由Dimitrov等人首先提出，隨后研究者將其應(yīng)用到多標(biāo)量乘算法中[5～9]；2007年，文獻(xiàn)[10]給出了5P的計算公式，設(shè)計實(shí)現(xiàn)了基于多基數(shù)鏈的單標(biāo)量乘算法。

本文旨在解決 Dimitrov等在文獻(xiàn)[6]Further Work中提出的實(shí)現(xiàn)kP+lQ + mR問題，采用多基數(shù)系統(tǒng)(MBNS, multi-base number system)表示標(biāo)量，提出了快速的多標(biāo)量乘算法。

2 相關(guān)知識

2.1 橢圓曲線

定義1 定義在域K上的Weierstrass方程：

所確定的平面曲線稱為橢圓曲線；其中a1、a2、a3、a4、a6∈K，K為有限域。滿足式(1)的(x,y)稱為K域上的點(diǎn)；此外，橢圓曲線還定義一個特殊的無窮點(diǎn)O；即域K上的點(diǎn)集和一個無窮遠(yuǎn)點(diǎn)O組成域K上的橢圓曲線E。

表1 點(diǎn)加、倍點(diǎn)計算開銷

2.2 整數(shù)的多基數(shù)表示

設(shè)B= {b1,…,bl}是一個小整數(shù)的集合，則任何一個整數(shù)k都可以表示成的形式。本文主要研究的是B= {2, 3, 5}的情況，具體定義如下。

定義2 設(shè)集合B= {2, 3, 5}，則k可以表示成如下形式：

該形式即為整數(shù)的多基數(shù)表示。

當(dāng)B= {2, 3}時，即為整數(shù)的雙基數(shù)表示。DBNS是高冗余的，而且表示長度非常短；與DBNS相比，MBNS冗余度更高，表示長度也更短。如僅考慮si=1情況下，整數(shù)100的雙基數(shù)表示共有402個，而它的多基數(shù)表示就有8 425個。bi、ti、qi的大小影響標(biāo)量乘中2倍點(diǎn)、3倍點(diǎn)和5倍點(diǎn)運(yùn)算的運(yùn)算次數(shù)，而m?1為標(biāo)量乘中點(diǎn)加的次數(shù)。一個160 bit的大整數(shù)如果使用雙基數(shù)系統(tǒng)來表示需要大約 23項(xiàng)，而如果使用多基數(shù)系統(tǒng)則需要約 15項(xiàng)就可以了[10]，因此與使用雙基數(shù)系統(tǒng)計算標(biāo)量乘相比，使用多基數(shù)系統(tǒng)能夠大大提高橢圓曲線標(biāo)量乘法的計算效率。

通常采用貪婪算法將整數(shù)k轉(zhuǎn)化為多基數(shù)表示，下面給出轉(zhuǎn)換算法：

算法1：多基數(shù)轉(zhuǎn)換貪婪算法

3 MBNS滑動窗口多點(diǎn)乘算法

傳統(tǒng)多標(biāo)量乘算法Shamir方法，是將tbit的標(biāo)量kj(1≤j≤m)寫成一個m×t的代表矩陣，再進(jìn)行預(yù)計算和存儲。本文用多基數(shù)表示標(biāo)量kj，提出了MBNS滑動窗口同時多點(diǎn)乘算法。

3.1 MBNS滑動窗口同時多點(diǎn)乘算法

在MBNS滑動窗口同時多點(diǎn)乘算法中，tbit的標(biāo)量kj被劃分成為窗口寬度為w的個窗口。

首先，要加大對農(nóng)業(yè)科技投入的力度，加強(qiáng)對農(nóng)業(yè)科學(xué)研究的投入。注重農(nóng)業(yè)技術(shù)的改造與創(chuàng)新，使各項(xiàng)技術(shù)能夠因地制宜地發(fā)揮應(yīng)有的作用，同時把自主開發(fā)和引進(jìn)新技術(shù)相結(jié)合，提高安徽省的農(nóng)業(yè)科技水平。

在新算法中，采用了從左向右的滑動窗口的技術(shù)，即處理完第i個窗口后，跳過連續(xù)的零位，取接下來的連續(xù)w位置入第i+ 1個窗口中。由于一個數(shù)的多基數(shù)表示長度決定了點(diǎn)加的次數(shù)，而對于不同的w值，小于2w的所有元素的多基數(shù)表示并不相同，即w值不同，其所需點(diǎn)加次數(shù)也不相同。表2給出了不同窗口寬度下的平均點(diǎn)加次數(shù)，記為aw。

表2 窗口寬度w及其對應(yīng)平均點(diǎn)加數(shù)

在這里假設(shè)P、Q、R已知，則算法為定點(diǎn)標(biāo)量乘。對于這種標(biāo)量乘法，其預(yù)計算表不需頻繁更換，所以建立預(yù)計算表在整個橢圓曲線加密體制中所占比重不大，在這里主要討論其賦值階段的開銷。由于算法采用了滑動窗口技術(shù)，實(shí)際計算窗口數(shù)小于d。

在算法賦值階段，對每個窗口除需對其多基數(shù)表示計算點(diǎn)加外，即；還需分別對i(i= 3)個標(biāo)量求和，即為。算法所需總的點(diǎn)加次數(shù)為：，賦值階段算法總的開銷近似為ADDw+ (d?1)wD，這里D為倍點(diǎn)運(yùn)算。

3.2 交錯MBNS滑動窗口同時多點(diǎn)乘算法

由于 NAF在標(biāo)量的所有帶符號表示中具有最少的非零位，因此如果對算法 2中的標(biāo)量采用w-NAF編碼，再對其進(jìn)行處理，則具有更少的點(diǎn)加次數(shù)。

若使用w-NAF編碼，則預(yù)計算階段僅需計算小于2w?1的奇數(shù)項(xiàng)。例如，w取值為5，則只需計算?15到 15之間的奇數(shù)項(xiàng)。因而不同窗口寬度下的平均點(diǎn)加次數(shù)aw不同于算法2，具體見表 3。

表3 窗口寬度w及其對應(yīng)平均點(diǎn)加數(shù)

由于寬度為w的NAF其平均非零數(shù)字的密度近似為，因而在賦值階段，算法 3的點(diǎn)加次數(shù)為：，算法總開銷近似為：ADDw+(d?1)wD。

4 算法分析

這節(jié)將分別比較傳統(tǒng)Shamir算法、交錯NAF方法、Sliding MBNS及I-MBNS。為了進(jìn)行比較，各算法分別取不同的窗口寬度，具體為：Shamir算法取w=2、交錯 NAF法取w∈{4,…,8}、Sliding MBNS 及 I-MBNS 取w∈{10,…,16}。

表4給出了算法在二進(jìn)制域及素數(shù)域中，標(biāo)量長度分別為160bit、192bit及230bit的性能分析。在二進(jìn)制域中，求逆運(yùn)算與乘法運(yùn)算的效率比通常被認(rèn)為是 8；而在素數(shù)域中，平方運(yùn)算與乘法運(yùn)算的效率比為0.8。

表4 算法性能分析

從表4中可以看出，二進(jìn)制域上Sliding MBNS算法在t= 192bit時比 Shamir算法計算量減少了11%，比交錯NAF方法減少了10%；I-MBNS算法計算量分別減少了 13%及 5%。素數(shù)域上 Sliding MBNS算法較之交錯NAF方法效率并未得到很大改善，I-MBNS算法計算量減少了5%。

圖1和圖2分別顯示了在二進(jìn)制域及素數(shù)域標(biāo)量長度t= 160bit時算法計算量與窗口寬度的具體變化情況。從圖中可以看出，Sliding MBNS算法與I-MBNS算法的計算量均隨著窗口寬度w的不斷增長而逐漸減少。

圖1 二進(jìn)制域算法時間復(fù)雜度

圖2 素數(shù)域算法時間復(fù)雜度

5 結(jié)束語

本文給出了結(jié)合文獻(xiàn)[10]提出的 5倍點(diǎn)公式，提出了利用多基數(shù)系統(tǒng)計算橢圓曲線多標(biāo)量乘的高效算法。需要強(qiáng)調(diào)的是，利用多基數(shù)系統(tǒng)計算橢圓曲線標(biāo)量乘不僅能夠提高標(biāo)量乘的運(yùn)算效率，使得基于橢圓曲線的密碼體制實(shí)現(xiàn)更加便捷和高效，而且由于雙基數(shù)系統(tǒng)表示的高度冗余性，多次計算同一個標(biāo)量乘，計算過程可以完全不同，因此使用雙基數(shù)系統(tǒng)計算橢圓曲線標(biāo)量乘也可以抵抗某些邊信道攻擊[11,12]。

[1]HANKERSON D, MENEZES A J, VANSTONE S A.Guide to Ellip-tic Curve Cryptography[M].Springer-Verlag, 2003.

[2]劉鐸, 戴一奇.計算橢圓曲線上多標(biāo)量乘的快速算法[J].計算機(jī)學(xué)報, 2008, 31(7):1131-1137.LIU D, DAI Y Q.A new algorithm of elliptic curve multi-scalar multiplication[J].Chinese Journal of Computers, 2008, 31(7): 1131- 1137.

[3]CHEN T S, HUANG K H, CHUNG Y F.Digital multi-signature scheme based on the elliptic curve cryptosystem[J].Journal of Computer Science and Technology, 2004,19(4): 572-inside back cover.

[4]SOLINAS J.Low-weight binary representations for pairs of integers[R].Centre for Applied Cryptographic Research, University of Waterloo, Ontario, Canada: Technical Report CORR 2001-41, 2001.

[5]ADIKARI J, DIMITROV V, IMBERT L.Hybrid binary- ternary joint sparse form and its application in elliptic curve cryptography[EB/OL].http://eprint.iacr.org/2008/.

[6]ADIKARI J, DIMITROV V, MISHRA P.Fast multiple point multiplication on elliptic curves over prime and binary fields using the double-base number system[EB/OL].http://eprint.iac r.org/2008/.

[7]DOCHE C, KOHEL D R.Double-base number system for multi-scalar multiplications[EB/OL].http://eprint.iacr.org/2008/.

[8]LONGA P, GEBOTYS C.Fast multibase methods and other several optimizations for elliptic curve scalar multiplication[A].The 12th International Conference on Practice and Theory in Public Key Cryptography[C].Berlin: Springer, 2009.443-462.

[9]殷新春, 侯紅祥, 謝立.基于雙基數(shù)系統(tǒng)的快速標(biāo)量乘算法[J].計算機(jī)科學(xué).2008, 35(6): 186-189, 195.YIN X C, HOU H X, XIE L.Fast scalar multiplication based on DBNS[J].Computer Science, 2008, 35(6): 186-189.

[10]MISHRA P K, DIMITROV V S.Efficient quintuple formulas for elliptic curves and efficient scalar multiplication using multi-base number representation[EB/OL].http://eprint.iacr.org/2007.

[11]KOCHER C, JAFFE J, JN B.Differential power analysis[A].Proceedings of Advances in Cryptology[C].Berlin: Springer, 1999.388-397.

[12]郝艷華, 李磊, 王育民.利用多基鏈計算橢圓曲線標(biāo)量乘的高效算法[J].電子科技大學(xué)學(xué)報.2008, 37(6): 868-871.HAO Y H, LI L, WANG Y M.Efficient scalar multiplication algorithm using multi-base chains[J].Journal of University of Electronic Science and Technology of China.2008, 37(6): 868-871.