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

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

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

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

(1)

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

對于多標量乘算法，主流的算法有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的漢明權重分別為3/4和2/3。JMBC在MBC的基礎上，將兩個標量聯(lián)合表示為

(2)

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

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

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

1 低計算復雜度多標量乘算法設計

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

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

(3)

假設有多標量乘10 536G+17 434P，常見的方法有JDBC、JSF和Shamir。若采用JDBC，轉化為

(4)

若采用JSF，轉化為

(5)

Shamir形式只是進行二進制展開，這里不進行說明。

使用筆者提出的方法，轉換結果如下所示：

(6)

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

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

(7)

單標量乘法以模12為例通過轉換后，進行最多對3x2y以下的G的預計算進行查找，就可以得到此次的結果，其轉換流程如下所示：

(8)

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

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

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

算法1低計算復雜度多標量乘算法。

輸入：標量k1，k2，基點G和點P

輸出：標量乘結果Q

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

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

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

④i賦值為0

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

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

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

⑧ 將k1/3的結果賦值給k1；將k2/3的結果賦值給k2

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

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

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

2 低計算復雜度多標量乘算法設計

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

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

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

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

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

(HA+D)M，

(9)

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

表2 不同窗口wNAF算法計算復雜度

預計算復雜度公式為

(2w-1A+D)M。

(10)

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

表3 計算復雜度的比較

對于一組ECDSA使用單標量乘和多標量乘算法，表4分別通過標量漢明權重相似的多標量乘算法與單標量乘算法進行比較。

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

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

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

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

表5 運行速度比較

3 結束語

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