面向ECDSA的低復(fù)雜度多標(biāo)量乘算法設(shè)計(jì)

黃 海，那 寧，劉志偉，于 斌，趙石磊

(哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150080)

數(shù)字簽名往往是通過公鑰密碼來進(jìn)行的，與物理簽名相比，具有不能被他人更改的特性，通過身份認(rèn)證和密鑰協(xié)商可以保證通信安全[1]。在數(shù)字簽名體系中，與同為公鑰密碼體制的RSA算法相比，橢圓曲線密碼(Elliptic Curve Cryptography，ECC)的加密和解密使用的密鑰長度較短，可以減少存儲(chǔ)空間和功耗，適合在有限的硬件資源上體現(xiàn)[2]。根據(jù)橢圓曲線密碼應(yīng)用或密碼協(xié)議所規(guī)定的運(yùn)算規(guī)程，現(xiàn)有的協(xié)議常見的有橢圓曲線密碼數(shù)字簽名算法(Elliptic Curve Cryptography Signature Algorithm，ECCSA)，橢圓曲線密碼密鑰交換協(xié)議(Elliptic Curve cryptography Diffie-Hellman，ECDH)和加密解密機(jī)制。橢圓曲線密碼算法性能依賴于標(biāo)量乘算法運(yùn)算性能，標(biāo)量乘又可分解為點(diǎn)加(計(jì)算P+G，計(jì)算量用A表示)、倍點(diǎn)(計(jì)算2P，計(jì)算量用D表示)、三倍點(diǎn)(計(jì)算3P，計(jì)算量用T表示)和五倍點(diǎn)(計(jì)算5P，計(jì)算量用Q表示)等運(yùn)算。

在生成公鑰時(shí)，ECDSA簽名過程和ECDH密鑰交換過程中使用的是單標(biāo)量乘算法，在ECDSA驗(yàn)簽過程中使用的是多標(biāo)量乘算法[3]。單標(biāo)量乘主流算法有倍點(diǎn)——點(diǎn)加二進(jìn)制方法(Doubling and Addition method，D&A)[4]，非鄰接表示形(Non-Adjacent-ForM，NAF)[5]和帶窗口的非鄰接表示形(window width-Non-Adjacent-Form，wNAF)[6]等算法，標(biāo)量非‘0’概率分別為1/2、1/3和1/(w+1)。這些算法核心思想是通過額外的預(yù)處理，來擴(kuò)大標(biāo)量k中的0的位數(shù)減少點(diǎn)加的次數(shù)，來加速標(biāo)量乘。然而，窗口w擴(kuò)大不僅使?jié)h明權(quán)重下降，也導(dǎo)致預(yù)處理的計(jì)算復(fù)雜度大幅度增長。目前，文獻(xiàn)[7]所提出的多基鏈思想因其獨(dú)特的運(yùn)算優(yōu)勢也成為了標(biāo)量乘討論的熱點(diǎn)之一。根據(jù)基的個(gè)數(shù)，可以分成雙基鏈(Double-Base Chain，DBC)和多基鏈(Multi-Base Chain，MBC)，多基鏈的宗旨是將標(biāo)量生成如下形式：

(1)

以多基鏈為優(yōu)化方向的算法存在一個(gè)構(gòu)建多基鏈時(shí)間長短的問題。根據(jù)貪心法生成的思想，若構(gòu)建的鏈過大，則會(huì)導(dǎo)致標(biāo)量乘運(yùn)行變慢；若構(gòu)建一個(gè)最優(yōu)的鏈，則又會(huì)導(dǎo)致用在構(gòu)建的時(shí)間上過長。文獻(xiàn)[8]優(yōu)化了三基鏈并提出了優(yōu)化的5P運(yùn)算，重新排序了基底有關(guān){2.3.5}的運(yùn)算順序。文獻(xiàn)[9]通過設(shè)計(jì)一個(gè)基于偽四維投射坐標(biāo)的多基鏈算法來優(yōu)化構(gòu)建多基鏈的方式，從而使得整體開銷相對(duì)于常規(guī)算法降低了8.7%，文獻(xiàn)[10]對(duì)雙基鏈進(jìn)行優(yōu)化后可以保證相對(duì)比wNAF優(yōu)化了超過60%。文獻(xiàn)[11]設(shè)計(jì)了一種基于2，3的雙基鏈保證比NAF優(yōu)化超過45%。

對(duì)于多標(biāo)量乘算法，主流的算法有Shamir[12]，聯(lián)合稀疏形式(Joint Sparse Form，JSF)[13]，聯(lián)合雙基鏈算法(Joint Double-Base Chain，JDBC)和聯(lián)合多基鏈算法(Joint Multi-Base Chain，JMBC )。Shamir和JSF的漢明權(quán)重分別為3/4和2/3。JMBC在MBC的基礎(chǔ)上，將兩個(gè)標(biāo)量聯(lián)合表示為

(2)

文獻(xiàn)[14]提出了一種高效的轉(zhuǎn)換聯(lián)合三基方式。該方法設(shè)計(jì)很簡單，使用的硬件較少。文獻(xiàn)[15]對(duì)JSF算法和JMBC進(jìn)行了分析比對(duì)，并在三基鏈的基礎(chǔ)上進(jìn)一步優(yōu)化，大大提高了ECDSA的速度。文獻(xiàn)[16]對(duì)JMBC的算法思想進(jìn)行了詳細(xì)的描述和分析。文獻(xiàn)[17]指出A、D、T和Q在雅克比坐標(biāo)下的花費(fèi)分別為12M+4S，4M+6S，6M+10S和15M+10S，其中M和S分別表示模乘和模平方，模乘和模平方本質(zhì)上都是模乘，這里可以近似將模乘和模平方視為同一運(yùn)算(模乘和模平方的計(jì)算比例約為0.8M=1S[18])。只需通過統(tǒng)計(jì)上述操作的模乘次數(shù)即可評(píng)估復(fù)雜度。ECC的整體運(yùn)算是在有限域上運(yùn)行的，其模乘等操作均有取模運(yùn)算，可以保證數(shù)據(jù)不會(huì)出現(xiàn)數(shù)據(jù)越界情況。并且，多基鏈所出現(xiàn)的非0位和0位的概率并不固定，無法通過分析獲得私鑰值，可以保證其私鑰的安全性。由于在ECC系統(tǒng)既要用到單標(biāo)量乘算法也要用到多標(biāo)量乘算法，且為了追求效率常常采用不同的多標(biāo)量乘算法和單標(biāo)量乘算法分別進(jìn)行運(yùn)算處理，這意味著未考慮其他情況下重新進(jìn)行標(biāo)量乘算法的調(diào)用會(huì)導(dǎo)致計(jì)算復(fù)雜度的提升。

目前關(guān)于上述問題的解決方法，文獻(xiàn)[19]在KSS曲線下提出了一種傾斜的Frobenius映射技術(shù)，并在其基礎(chǔ)上設(shè)計(jì)了一個(gè)快速算法。文獻(xiàn)[20]設(shè)計(jì)了一種基于“平行點(diǎn)倍(點(diǎn)加和倍點(diǎn)平行)”的適用于單標(biāo)量乘算法和多標(biāo)量乘算法的并行結(jié)構(gòu)，并保證所用的時(shí)間和NAF算法幾乎相同。文獻(xiàn)[21]通過基于窗口的方法進(jìn)行了加速，使其相對(duì)于shamir和NAF優(yōu)化了至少7.9%。文獻(xiàn)[22]使用了GLV方法來進(jìn)行多標(biāo)量乘算法的優(yōu)化，保證在三維或四維GLV方法性能最好。文獻(xiàn)[23]利用三維GLV方法探索了在r坐標(biāo)系上的快速標(biāo)量乘法。構(gòu)造并實(shí)現(xiàn)了兩種三維微分加成鏈，比使用DJB鏈的雙標(biāo)量乘法快約6%。文獻(xiàn)[24]以2，3，7為基底的多基鏈整數(shù)表示形式及兩種多標(biāo)量乘快速算法，在素?cái)?shù)域上，至少比傳統(tǒng)算法優(yōu)化3.1%。文獻(xiàn)[25]使用了雙基分解方法并進(jìn)行對(duì)Montgomery曲線和Edwards曲線混合來進(jìn)行加速。

筆者通過整除基底{2，3}并對(duì)二者不能整除的部分取模3x2y的方式來構(gòu)建JDBC表示形式，同時(shí)對(duì)余數(shù)進(jìn)行預(yù)處理來進(jìn)一步降低計(jì)算復(fù)雜度，從而保證了在減少預(yù)處理的前提下避免了因分別運(yùn)算處理導(dǎo)致的計(jì)算復(fù)雜度提升的問題。

1 低計(jì)算復(fù)雜度多標(biāo)量乘算法設(shè)計(jì)

無論在ECDSA的簽名過程，ECDH密鑰交換和ECC的密鑰生成過程使用的private_keyG單標(biāo)量乘算法，還是在ECDSA驗(yàn)簽過程中使用到k1G+k2public_key多標(biāo)量乘算法(G是橢圓曲線上的一個(gè)公共點(diǎn)，private_key是私鑰，public_key是對(duì)應(yīng)private_key的公鑰)，都存在著對(duì)k1G進(jìn)行計(jì)算。

因此在構(gòu)建以{2，3}為基底進(jìn)行轉(zhuǎn)化JDBC的形式中，對(duì)兩個(gè)標(biāo)量進(jìn)行整除基底2和3的操作時(shí)，不能整除基底的部分則對(duì)兩個(gè)標(biāo)量進(jìn)行同時(shí)取模3x2y，并對(duì)余數(shù)有關(guān)G和P+G的多倍點(diǎn)操作進(jìn)行預(yù)處理，使得兩個(gè)標(biāo)量可以同時(shí)處理標(biāo)量k2和k1的共同部分。當(dāng)在調(diào)用單標(biāo)量乘的過程中k2是0的情況下，直接對(duì)G的預(yù)處理進(jìn)行相應(yīng)的計(jì)算，從而保證了單標(biāo)量乘和多標(biāo)量乘算法的正確性。計(jì)算形如mG+nP的多標(biāo)量轉(zhuǎn)換則如下所示：

(3)

假設(shè)有多標(biāo)量乘10 536G+17 434P，常見的方法有JDBC、JSF和Shamir。若采用JDBC，轉(zhuǎn)化為

(4)

若采用JSF，轉(zhuǎn)化為

(5)

Shamir形式只是進(jìn)行二進(jìn)制展開，這里不進(jìn)行說明。

使用筆者提出的方法，轉(zhuǎn)換結(jié)果如下所示：

(6)

通過式(4)～(6)可以得出，擴(kuò)大取模操作可以進(jìn)一步降低計(jì)算復(fù)雜度，對(duì)于10 536G+17 434P，JSF計(jì)算15次倍點(diǎn)和10次點(diǎn)加共計(jì)調(diào)用340次模乘；JDBC進(jìn)行了8次點(diǎn)加、9次倍點(diǎn)和4次三倍點(diǎn)，共計(jì)調(diào)用282次模乘；在取模12的時(shí)候需要僅進(jìn)行6次點(diǎn)加，7次倍點(diǎn)和2次三倍點(diǎn)，共計(jì)調(diào)用198次模乘。

若僅僅是計(jì)算private_keyG，假設(shè)計(jì)算21 057G，常見的方式是wNAF方法，窗口為4的情況下其展開式如下所示：

(7)

單標(biāo)量乘法以模12為例通過轉(zhuǎn)換后，進(jìn)行最多對(duì)3x2y以下的G的預(yù)計(jì)算進(jìn)行查找，就可以得到此次的結(jié)果，其轉(zhuǎn)換流程如下所示：

(8)

通過比對(duì)可以發(fā)現(xiàn)，wNAF需要4次點(diǎn)加，15次倍點(diǎn)，共計(jì)調(diào)用214次模乘；而式(8)僅需要3次點(diǎn)加、5次倍點(diǎn)和4次三倍點(diǎn)共調(diào)用162次模乘。通過式(6)和式(8)可以發(fā)現(xiàn)，在驗(yàn)簽過程中所使用的多標(biāo)量乘算法中有關(guān)P+G和G預(yù)處理部分，在簽名、密鑰交換的過程中對(duì)于G的處理仍然可以使用。

由此可見，根據(jù)式(3)推導(dǎo)，該方法理論推導(dǎo)無誤且相較于現(xiàn)有方法有一定優(yōu)化。在此基礎(chǔ)上，設(shè)計(jì)算法如算法1所示，其中步驟①～③是進(jìn)行預(yù)處理操作，步驟④～是進(jìn)行聯(lián)合多基鏈轉(zhuǎn)換，通過預(yù)處理的方式進(jìn)一步地降低了計(jì)算量。步驟～是進(jìn)行標(biāo)量乘。通過文中的方法，可以保證對(duì)于G的預(yù)處理既可以在單標(biāo)量乘中運(yùn)用，又可以在多標(biāo)量乘計(jì)算中運(yùn)用。在多標(biāo)量乘的計(jì)算過程中，僅僅需要對(duì)P+G重新進(jìn)行預(yù)計(jì)算即可，若標(biāo)量k1和k2相等的時(shí)候通過這樣的預(yù)計(jì)算也會(huì)進(jìn)一步降低計(jì)算數(shù)量。其算法流程圖如圖1所示。

圖1 筆者所提出的算法流程圖

算法1低計(jì)算復(fù)雜度多標(biāo)量乘算法。

輸入：標(biāo)量k1，k2，基點(diǎn)G和點(diǎn)P

輸出：標(biāo)量乘結(jié)果Q

① 預(yù)處理Gi=iG，i∈{小于3x2y的數(shù)}

② 如果k2==0或P=None：

③ 預(yù)處理(P+G)i=i(P+G)，i∈{小于3x2y的數(shù)}

④i賦值為0

⑤k1>0或k2>0時(shí)進(jìn)行循環(huán)步驟③～

⑥ 若k1≡0(mod)3且k2≡0(mod)3則執(zhí)行步驟⑦～⑧

⑦ 將3賦值給bi；0賦值給Digit1i；0賦值給Digit2i

⑧ 將k1/3的結(jié)果賦值給k1；將k2/3的結(jié)果賦值給k2

⑨ 否則若k1≡0(mod)2且k2≡0(mod)2則執(zhí)行步驟⑩～

⑩ 將2賦值給bi；0賦值給Digit1i；0賦值給Digit2i

僅剩1艘服役的677型“拉達(dá)”級(jí)將改裝不依賴空氣推進(jìn)動(dòng)力系統(tǒng)(AIP)，但不再進(jìn)行其他改裝。計(jì)劃建造兩艘該級(jí)潛艇。

2 低計(jì)算復(fù)雜度多標(biāo)量乘算法設(shè)計(jì)

由于筆者所提出的算法涉及到與單標(biāo)量乘和多標(biāo)量乘進(jìn)行多方面的比較，因此要與多個(gè)算法聯(lián)合進(jìn)行比較，且MBC表示形式生成后諸如點(diǎn)加、倍點(diǎn)和三倍點(diǎn)的次數(shù)難以評(píng)估，所以筆者將通過python環(huán)境搭建curve-P256模型運(yùn)行10 000次來取模乘使用次數(shù)的平均值用于統(tǒng)計(jì)分析，并得到如表1所示的結(jié)果。

當(dāng)x和y值大于3時(shí)，其模乘計(jì)算次數(shù)是大于JDBC和窗口為5的wNAF方法的計(jì)算量，因此文中暫不考慮x和y均大于3的情況。通過表1可以發(fā)現(xiàn)，當(dāng)取模12時(shí)(即3122)，無論單標(biāo)量乘的計(jì)算量還是多標(biāo)量乘的計(jì)算量均是最小。故得到文中最優(yōu)取模數(shù)為12并用于與其他算法比較。

通過模型驗(yàn)證后可以發(fā)現(xiàn)，所生成的多基鏈長度均小于轉(zhuǎn)換前的私鑰長度，每一輪有限域運(yùn)算后都會(huì)進(jìn)行取模限制結(jié)果長度，且所調(diào)用倍點(diǎn)等操作的分布并不均勻，無法通過分析數(shù)據(jù)出現(xiàn)規(guī)律而分析得到的私鑰，從而保證了數(shù)據(jù)的安全性。

表1 不同取模下文中方法計(jì)算復(fù)雜度

在比較多標(biāo)量乘和單標(biāo)量乘在一組ECDSA中調(diào)用時(shí)，應(yīng)通過選取同等漢明權(quán)重的算法來進(jìn)行相應(yīng)的比較。比如，MBC和JMBC，二者的算法均是無法通過計(jì)算得到其平均計(jì)算量，需要通過程序的運(yùn)行來得到平均的運(yùn)行次數(shù)；為了便于統(tǒng)計(jì)，這里采用DBC和JDBC進(jìn)行比較。因此可以保證shamir算法單個(gè)標(biāo)量的漢明權(quán)重與D&A不會(huì)一致。wNAF算法最優(yōu)窗口下沒有與之對(duì)應(yīng)漢明權(quán)重的算法，則采用JSF算法一起運(yùn)算進(jìn)行比較。因此，需要對(duì) D&A-shamir，wNAF-JSF，DBC-JDBC進(jìn)行聯(lián)合比較，同時(shí)對(duì)單標(biāo)量乘和多標(biāo)量乘各自進(jìn)行比較才能得到最終的性能分析。D&A、wNAF、Shamir和JSF的正式計(jì)算復(fù)雜度公式如下所示：

(HA+D)M，

(9)

其中，H代表標(biāo)量非'0'概率。wNAF算法需要對(duì)其最優(yōu)窗口性能進(jìn)行分析比較，通過表2可以發(fā)現(xiàn)窗口為5是wNAF的最優(yōu)窗口。

表2 不同窗口wNAF算法計(jì)算復(fù)雜度

預(yù)計(jì)算復(fù)雜度公式為

(2w-1A+D)M。

(10)

表3描述了各個(gè)算法的預(yù)處理和正式處理計(jì)算復(fù)雜度。對(duì)于多標(biāo)量乘而言，雖然筆者所提的方法相較于Shamir算法、JSF算法而言多使用一定預(yù)計(jì)算，但將整體的計(jì)算量優(yōu)化了至少27.40%。對(duì)于JDBC算法而言，采用了相對(duì)于JDBC小的預(yù)計(jì)算，將整體計(jì)算量降低了9.84%。僅僅對(duì)單標(biāo)量乘，至少優(yōu)化了3.88%。

表3 計(jì)算復(fù)雜度的比較

對(duì)于一組ECDSA使用單標(biāo)量乘和多標(biāo)量乘算法，表4分別通過標(biāo)量漢明權(quán)重相似的多標(biāo)量乘算法與單標(biāo)量乘算法進(jìn)行比較。

表4 多標(biāo)量乘與單標(biāo)量乘的聯(lián)合計(jì)算量比較

圖2 10次以內(nèi)聯(lián)合多標(biāo)量乘計(jì)算復(fù)雜度優(yōu)化比率

每當(dāng)單標(biāo)量乘被重新調(diào)用的時(shí)候，多標(biāo)量乘也相當(dāng)于重新開始計(jì)算，因此所討論的單標(biāo)量乘每組僅調(diào)用1次。通過表4可以發(fā)現(xiàn)，在多標(biāo)量乘運(yùn)行1～3次的情況下，相較于JDBC-DBC，至少保證優(yōu)化了16.65%；相較于Shair-D&A算法而言，可以優(yōu)化32.72%以上；相較于JSF-wNAF算法，可以優(yōu)化20.05%以上。由于從表4中看出其優(yōu)化有增加趨勢，故圖2對(duì)文中方法與其余的聯(lián)合運(yùn)算10次下的優(yōu)化比率做了比較，從中可以清晰地看出在10次左右時(shí)，文中方法所優(yōu)化的比率趨于穩(wěn)定，相對(duì)于Shair-D&A、JSF-wNAF和JDBC-DBC優(yōu)化比率分別趨于36%、32%和18%。保證了一組ECDSA簽名驗(yàn)簽在運(yùn)行標(biāo)量乘方面，相較于現(xiàn)有的算法有著更低的計(jì)算復(fù)雜度。

為了評(píng)估標(biāo)量乘算法的性能，通過對(duì)所設(shè)計(jì)的算法進(jìn)行Python建模，使用Python 3.6版本在Core i5-1035G1@1.00 GHz 四核PC上對(duì)curveP256曲線進(jìn)行性能評(píng)估。為保證統(tǒng)計(jì)結(jié)果相對(duì)接近，分別采用各算法最優(yōu)情況時(shí)運(yùn)行10 000次，取其平均運(yùn)行時(shí)間來進(jìn)行比較。表5就對(duì)不同算法的運(yùn)行速度進(jìn)行了分析，從表中可以發(fā)現(xiàn)，文中所提的方法在單標(biāo)量乘運(yùn)算中至少可以提高14.80%的運(yùn)行速度，在多標(biāo)量乘的情況下至少可以提升36.91%的速度。

表5 運(yùn)行速度比較

3 結(jié)束語

在對(duì)現(xiàn)有的問題進(jìn)行分析的前提下，筆者提出了一種面向ECDSA的低復(fù)雜度多標(biāo)量乘算法。該算法通過選取模3x2y以下的數(shù)進(jìn)行預(yù)處理，在JMBC標(biāo)量乘思想的基礎(chǔ)上，通過適當(dāng)?shù)臄U(kuò)大預(yù)處理來減少標(biāo)量乘的計(jì)算量。在ECDSA的簽名或ECDH過程中，在第一次預(yù)計(jì)算時(shí)先對(duì)G進(jìn)行相應(yīng)的預(yù)處理，當(dāng)遇到ECDSA驗(yàn)簽過程時(shí)，對(duì)P+G進(jìn)行整體的預(yù)計(jì)算。在生成標(biāo)量k1和k2的MBC表示形式時(shí)，結(jié)合模3x2y運(yùn)算，并保證在模12時(shí)得到最優(yōu)的結(jié)果。計(jì)算過程中若存在兩個(gè)標(biāo)量之間的差值，則需要通過對(duì)G點(diǎn)的點(diǎn)加操作來進(jìn)行調(diào)節(jié)。同時(shí)該算法在k2為0的情況下也可以計(jì)算單標(biāo)量乘算法。實(shí)驗(yàn)結(jié)果表明，在curve-P256曲線下相較于其他算法至少降低了約3.88%以上的復(fù)雜度，在聯(lián)合運(yùn)算的情況下至少可以降低約16.65%以上的復(fù)雜度，運(yùn)行時(shí)間減少了約14.80%以上，預(yù)計(jì)算點(diǎn)相較于wNAF和JDBC算法至少減少了約25.00%。綜上所述，筆者所提的方法在計(jì)算復(fù)雜度計(jì)算量以及運(yùn)算速度上均對(duì)以往的方法有一定提高。