• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

      2010-07-17 08:55:58殷新春張海靈楊婷
      通信學(xué)報 2010年1期
      關(guān)鍵詞:標(biāo)量基數(shù)整數(shù)

      殷新春,張海靈,楊婷

      (揚(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.

      猜你喜歡
      標(biāo)量基數(shù)整數(shù)
      一次性傷殘就業(yè)補(bǔ)助金的工資基數(shù)應(yīng)如何計算?
      千萬不要亂翻番
      一種高效的橢圓曲線密碼標(biāo)量乘算法及其實(shí)現(xiàn)
      巧妙推算星期幾
      一種靈活的橢圓曲線密碼并行化方法
      一類整數(shù)遞推數(shù)列的周期性
      『基數(shù)』和『序數(shù)』
      聚焦不等式(組)的“整數(shù)解”
      單調(diào)Minkowski泛函與Henig真有效性的標(biāo)量化
      標(biāo)量電子能級束縛態(tài)的計算
      松原市| 多伦县| 泗阳县| 吉隆县| 平度市| 札达县| 洛扎县| 曲水县| 呼图壁县| 华坪县| 礼泉县| 汤阴县| 措美县| 忻城县| 汤阴县| 太谷县| 高雄市| 贺州市| 雷州市| 将乐县| 汤阴县| 迁安市| 北辰区| 贺州市| 措勤县| 永宁县| 邵东县| 芷江| 静乐县| 弥勒县| 苍溪县| 大方县| 墨竹工卡县| 响水县| 石门县| 龙山县| 响水县| 辽宁省| 承德市| 八宿县| 乌拉特中旗|