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

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

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

在生成公鑰時，ECDSA簽名過程和ECDH密鑰交換過程中使用的是單標(biāo)量乘算法，在ECDSA驗簽過程中使用的是多標(biāo)量乘算法[3]。單標(biāo)量乘主流算法有倍點——點加二進(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ù)處理，來擴大標(biāo)量k中的0的位數(shù)減少點加的次數(shù)，來加速標(biāo)量乘。然而，窗口w擴大不僅使?jié)h明權(quán)重下降，也導(dǎo)致預(yù)處理的計算復(fù)雜度大幅度增長。目前，文獻(xiàn)[7]所提出的多基鏈思想因其獨特的運算優(yōu)勢也成為了標(biāo)量乘討論的熱點之一。根據(jù)基的個數(shù)，可以分成雙基鏈(Double-Base Chain，DBC)和多基鏈(Multi-Base Chain，MBC)，多基鏈的宗旨是將標(biāo)量生成如下形式：

(1)

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

對于多標(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ǔ)上，將兩個標(biāo)量聯(lián)合表示為

(2)

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

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

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

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

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

因此在構(gòu)建以{2，3}為基底進(jìn)行轉(zhuǎn)化JDBC的形式中，對兩個標(biāo)量進(jìn)行整除基底2和3的操作時，不能整除基底的部分則對兩個標(biāo)量進(jìn)行同時取模3x2y，并對余數(shù)有關(guān)G和P+G的多倍點操作進(jìn)行預(yù)處理，使得兩個標(biāo)量可以同時處理標(biāo)量k2和k1的共同部分。當(dāng)在調(diào)用單標(biāo)量乘的過程中k2是0的情況下，直接對G的預(yù)處理進(jìn)行相應(yīng)的計算，從而保證了單標(biāo)量乘和多標(biāo)量乘算法的正確性。計算形如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)可以得出，擴大取模操作可以進(jìn)一步降低計算復(fù)雜度，對于10 536G+17 434P，JSF計算15次倍點和10次點加共計調(diào)用340次模乘；JDBC進(jìn)行了8次點加、9次倍點和4次三倍點，共計調(diào)用282次模乘；在取模12的時候需要僅進(jìn)行6次點加，7次倍點和2次三倍點，共計調(diào)用198次模乘。

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

(7)

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

(8)

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

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

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

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

輸入：標(biāo)量k1，k2，基點G和點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時進(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ìn)動力系統(tǒng)(AIP)，但不再進(jìn)行其他改裝。計劃建造兩艘該級潛艇。

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

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

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

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

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

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

(HA+D)M，

(9)

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

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

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

(2w-1A+D)M。

(10)

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

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

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

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

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

每當(dāng)單標(biāo)量乘被重新調(diào)用的時候，多標(biāo)量乘也相當(dāng)于重新開始計算，因此所討論的單標(biāo)量乘每組僅調(diào)用1次。通過表4可以發(fā)現(xiàn)，在多標(biāo)量乘運行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對文中方法與其余的聯(lián)合運算10次下的優(yōu)化比率做了比較，從中可以清晰地看出在10次左右時，文中方法所優(yōu)化的比率趨于穩(wěn)定，相對于Shair-D&A、JSF-wNAF和JDBC-DBC優(yōu)化比率分別趨于36%、32%和18%。保證了一組ECDSA簽名驗簽在運行標(biāo)量乘方面，相較于現(xiàn)有的算法有著更低的計算復(fù)雜度。

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

表5 運行速度比較

3 結(jié)束語

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