無模逆運(yùn)算的橢圓曲線數(shù)字簽名算法

肖 帥，王緒安，潘 峰

1.武警工程大學(xué) 網(wǎng)絡(luò)與信息安全武警部隊重點(diǎn)實驗室，西安710086

2.武警工程大學(xué) 密碼工程學(xué)院，西安710086

1 引言

數(shù)字簽名算法（DSA）是1991 年8 月由美國國家研究所（NIST）提出的標(biāo)準(zhǔn)和技術(shù)[1-3]，它的安全性是基于離散對數(shù)（DL）在Zp*的素數(shù)階子群中的計算不可追溯性的問題（DLP）。作為信息與數(shù)據(jù)安全的核心技術(shù)之一，它可以實現(xiàn)身份認(rèn)證、數(shù)據(jù)完整性保護(hù)、防篡改、防冒充和不可否認(rèn)性等數(shù)據(jù)傳輸中的重要需求[4]。Johson等人[2]在2001年提出了橢圓曲線數(shù)字簽名（Elliptic Curve Digital Signature，ECDSA）算法，它是通過2 次模逆運(yùn)算、3次標(biāo)量乘運(yùn)算來實現(xiàn)數(shù)字簽名的過程的。橢圓曲線數(shù)字簽名是重要的信息保護(hù)技術(shù)之一，它通過為信息增加簽名，有效保護(hù)了信息的完整性、不可否認(rèn)性、認(rèn)證性、不可偽造性，目前這一算法得到了廣泛認(rèn)可和應(yīng)用[5]。圖1顯示的是ECDSA的發(fā)展歷程。

圖1 ECDSA發(fā)展歷程

橢圓曲線數(shù)字簽名算法（ECDSA）是對數(shù)字簽名算法（DSA）的模擬。橢圓曲線密碼（ECC）由Koblitz N[6]和Miller V[7]于1985 年發(fā)明，是目前安全性最高的公鑰加密算法，它是基于橢圓曲線的一種公鑰體制。相較其他公鑰體制，橢圓曲線密碼的單位比特強(qiáng)度要高一些。橢圓曲線密碼體制的主要優(yōu)勢是計算參數(shù)更小，密鑰更短[8]，運(yùn)算速度更快，簽名也更加短小[9]，效率也更高[10]。因此橢圓曲線密碼性能優(yōu)良，應(yīng)用廣泛，尤其適用于存儲空間、處理能力、帶寬及功耗受限的場合[11]。

表1 顯示的是基于公鑰密碼的數(shù)字簽名體制的分類：在這三種分類中，ECDLP 是最難解的，除幾類特殊橢圓曲線外，至今仍沒有ECDLP的有效求解算法。

表1 基于公鑰密碼的數(shù)字簽名體制分類

數(shù)字簽名應(yīng)用廣泛，電子商務(wù)和網(wǎng)絡(luò)安全認(rèn)證的核心技術(shù)就是數(shù)字簽名，最近大火的區(qū)塊鏈技術(shù)，其底層技術(shù)之一就是數(shù)字簽名。由于數(shù)字簽名方案是許多保密協(xié)議的核心構(gòu)造塊，因此提高數(shù)字簽名方案的效率是非常重要的[12]。

在對ECDSA 的深入研究過程中，一般一致認(rèn)為影響ECDSA 簽名耗時主要有兩個計算因素[13]：一是標(biāo)量乘法運(yùn)算[14]，標(biāo)量乘法運(yùn)算是已知橢圓曲線上兩個點(diǎn)：基點(diǎn)G 和隨機(jī)數(shù)k，求kG 的運(yùn)算過程。另外一個也是最主要的運(yùn)算就是模逆運(yùn)算，由于在乘法運(yùn)算中至少要進(jìn)行1次求逆運(yùn)算，而模逆運(yùn)算所需要消耗的時間是乘法運(yùn)算的10倍[2]，所以耗時主要由求逆運(yùn)算產(chǎn)生。針對ECDSA 計算的耗時問題，對求逆運(yùn)算和標(biāo)量乘運(yùn)算的各種改進(jìn)的方案[15-21]相繼被提出，詳見表2。

表2 對求逆運(yùn)算和標(biāo)量乘運(yùn)算的各種改進(jìn)的方案

本文在分析研究經(jīng)典的橢圓曲線密碼理論的基礎(chǔ)上，針對經(jīng)典ECDSA 方案中存在的耗時和偽造攻擊的問題，通過引入雙參數(shù)和避免求逆運(yùn)算，提出了一種改進(jìn)的能實現(xiàn)高效率的數(shù)字簽名方案。

2 預(yù)備知識

2.1 方案參數(shù)與釋義說明

本文方案描述所涉及的參數(shù)符號及釋義如表3所示。

表3 參數(shù)符號與釋義

2.2 橢圓曲線密碼體制

橢圓曲線密碼體制可以看作是舊的離散對數(shù)（DL）的橢圓曲線類似物，ZP*的子群被有限域上橢圓曲線上的點(diǎn)群所代替。以下是ECC的一般結(jié)構(gòu)：

設(shè)P ∈(FP)，點(diǎn)Q 是P 的倍數(shù)，即存在正整數(shù)X ，使得q Xp，然后用給定的p 和q 定義ECDLP?；跈E圓曲線離散對數(shù)問題，產(chǎn)生了橢圓曲線密碼體制。

設(shè)E 為橢圓曲線，p 為E 上的一個點(diǎn)，如果存在正整數(shù)N ，使得NP=0，則n 是點(diǎn)P 的階數(shù)，其中O 是無窮大點(diǎn)。

橢圓曲線公鑰密碼（ECC）體制的構(gòu)造如下：

選擇域Fp，橢圓曲線E，選擇點(diǎn)P(xp,yp)，n 為E上的素數(shù)階。公開信息：有限域Fp，曲線方程E，點(diǎn)P及其階n，計算Q=dP，取Q 點(diǎn)為公鑰，整數(shù)D 為密鑰。

要向Alice發(fā)送秘密信息M ，需要執(zhí)行以下步驟：

（1）在域Fp 中將明文M 表示為元素M ；

（2）隨機(jī)選取[1,n-1]中的整數(shù)k；

（3）計算點(diǎn)(x1,y1)=kP；

（4）計算點(diǎn)(x2,y2)=kQ，如果x2=0，則重新選擇k；

（5）計算c=mx2；

（6）發(fā)送(x1,y1,c)給Alice。

當(dāng)Alice接收到密文時，使用密鑰D 計算密文。

這里Q=dP 是公開的。如果破譯者能夠解決橢圓曲線上的離散對數(shù)問題，就可以從dP 中還原出d ，完成解密[22]。

2.3 橢圓曲線離散對數(shù)問題（ECDLP）

橢圓曲線離散對數(shù)問題是對于橢圓曲線E( GF( q))上任意兩點(diǎn)G 和Q，有Q=dG，在已知G 和Q 的前提下求出小于q 的正整數(shù)d。己知d 和G 計算Q 比較容易，但是已知Q 和G 計算d 則很困難，這便是橢圓曲線加密體制的核心。橢圓曲線密碼體制的安全性基于橢圓曲線離散對數(shù)問題，也就是求解ECDLP 算法的時間復(fù)雜度。

3 ECDSA數(shù)字簽名原理與方案分析

3.1 ECDSA數(shù)字簽名方案描述

ECDSA 是ECC 與DSA 的結(jié)合，整個簽名過程與DSA類似，所不一樣的是簽名中采取的算法為ECC，最后簽名出來的值也是分為r,s。

（1）方案建立

U 為簽名者，V 為驗證者：

①U 構(gòu)建橢圓曲線城參數(shù)T=(p,a,b,G,n,h)；

②U 建立密鑰對(du,Qu)，且有Qu=duG；

③U 選擇一個hash數(shù)；

④U 將hash函數(shù)和橢圓曲線域參數(shù)T 傳給V 。

（2）簽名算法

①選擇一個臨時密鑰對(k,r)，其中R=kG=(xR,yR)和域參數(shù)T 相關(guān)。

②令r=xRmod n，如果r=0，返回1。

③計算待簽消息的hash值H=H(m)，將H 轉(zhuǎn)換成整數(shù)e。

④計算s=k-1(e+rdu)(mod n )，如果s=0，返回1。

⑤輸出S=(r,s)為數(shù)字簽名。

（3）驗證算法

V 通過驗證從U 發(fā)來的數(shù)字簽名來判斷所接收消息以及對方身份的真?zhèn)巍?/p>

①如果r,s ?[1 ,n-1] ，驗證不通過。

②計算待簽消息的hash值H=Hash(M) ，將H 轉(zhuǎn)換成整數(shù)e。

③計算u1=es-1( mod n ),u2=rs-1(mod n )。

④計算R=(xR,yR)=u1G+u2Qu，如果R=0，驗證失敗。

⑤令v=xR(mod n )，如果v=r ，驗證成功，否則驗證失敗。

3.2 ECDSA數(shù)字簽名方案分析

在ECDSA 方案中，公鑰的產(chǎn)生算法是Qu=duG ，在簽名的生成和驗證過程中需要分別計算k-1mod n 和s-1mod n，即需要進(jìn)行模逆運(yùn)算。若模乘運(yùn)算的數(shù)據(jù)規(guī)模為n ，則一次模乘運(yùn)算的復(fù)雜度為O(n2ln n)。表4分析了ECDSA方案的算法復(fù)雜度。

表4 ECDSA算法復(fù)雜度分析

可以看到，簽名算法和驗證算法運(yùn)算很復(fù)雜，都有模逆運(yùn)算。前文中已經(jīng)提到，在現(xiàn)有的橢圓曲線加密或者簽名過程中，主要的運(yùn)算負(fù)擔(dān)來自求逆運(yùn)算，求逆是最復(fù)雜費(fèi)時的操作，一次求逆的時間大約相當(dāng)于80 次點(diǎn)乘運(yùn)算。如果可以減少甚至是避免模逆運(yùn)算無疑有助于數(shù)字簽名效率的提升。

4 改進(jìn)的ECDSA方案

由以上分析可知，在簽名或者驗證階段，如果可以減少甚至是避免模逆運(yùn)算無疑有助于數(shù)字簽名效率的提升。但在著力提高運(yùn)算效率的同時也應(yīng)兼顧安全問題，基于此，本文提出了一種新的ECDSA的改進(jìn)方案。

4.1 改進(jìn)方案的算法描述

設(shè)ECC 參數(shù)為T={a,b,G,n,h}，用戶使用私鑰A( d,Q )對消息m 進(jìn)行簽名，圖2顯示了簽名和驗證的具體過程。

（1）A隨機(jī)選擇一個整數(shù)k，k ∈[1,n-1]；

（2）計算kG=(x1,y1) ，將x 轉(zhuǎn)換成整數(shù)xˉ；

（3）隨機(jī)選擇1組α,β ∈[1,n-1] ，α,β 滿足條件k=αr+βm；

圖2 改進(jìn)的算法流程圖

（4）計算待簽名的消息m 的哈希值e，e=H(m)；

（5）計算r=xˉ1mod n；其中若r=0，則跳轉(zhuǎn)到（1）；（6）計算s=r(α+ed)mod n；若s=0，則跳轉(zhuǎn)到（1）；（7）(r,s,β)即為簽名m 的信息.用戶B收到m 和(r,s,β)后，對簽名進(jìn)行如下驗證：

①驗證r,s,β 是否屬于區(qū)間[1,n-1]內(nèi)的整數(shù)，若三者中任何一個參數(shù)驗證失敗，則拒絕簽名；

②計算e=H(m)；

③計算γ=(s+βm)mod n，u=er mod n；

④計算γG-uQ=(x′,y′)；

⑤計算v=x′mod n；

⑥若v=r，則驗證簽名成功。

在以上改進(jìn)方案的算法描述細(xì)節(jié)部分，步驟（1）至步驟（3）中關(guān)于隨機(jī)數(shù)k 的選取，進(jìn)行分析說明，以表明方案中隨機(jī)數(shù)選取的合理性和隨機(jī)性。

通過（1），確定了一個整數(shù)k，k 是在[1,n-1]區(qū)間隨機(jī)選取的，在（3）中，等式的兩邊都要進(jìn)行模n 運(yùn)算，由于n 為素數(shù)，r,m 為已知信息，k 被隨機(jī)選取后，再從[1,n-1]區(qū)間任意選取一個α，則一定存在一個滿足等式k=αr+βm 的整數(shù)β，且β ∈[1,n-1]，所以改進(jìn)方案的構(gòu)造具有合理性和隨機(jī)性。

對改進(jìn)算法的正確性證明如下，若(r,s,β)是對m的簽名信息，則：

因此

所以有ν=x′=x=r mod n

4.2 改進(jìn)方案的算法分析

（1）抗替換信息的偽造攻擊

A發(fā)送(r,s,β)信息給接收方C后，接收方C可以用偽造消息m′來代替m 進(jìn)行簽名。

C偽造簽名過程如下：

①由于s,e，r 為已知量，C 由s=r(α+ed)mod n 可計算出(α+ed)mod n；

②使用替換的消息m′，計算e'=H(m') ；

③計算滿足條件k=αr+βm 的α,β；

④計算s′=r(α+e′d)mod n；

⑤偽造簽名計算s′=r(α+e′d)mod n，(r,s′,β )為m′的簽名數(shù)據(jù)。

B收到(r,s',β )簽名信息后，進(jìn)行如下簽名驗證，計算：

因此簽名無效。

（2）替換隨機(jī)數(shù)的偽造攻擊

接收方C收到簽名消息(r,s,β)后，可以偽造隨機(jī)數(shù)k′來代替k 進(jìn)行簽名。C偽造簽名過程如下：

①由于s,e,r 已知，B 由s=r(α+ed)mod n 計算出(α+ed)mod n；

②隨機(jī)生成一個整數(shù)t，計算k'=k+t，其中k',k 都是未知的；

③計算k'G=(k+t)G=kG+tG=(x′,y′)；

④計算r'=x'mod n；

⑤計算滿足條件k′=α′r′+β′m 的α′,β′；

⑥計算e=H( )m ；

⑦計算s′=r′(α′+ed)mod n。

B 收到( r′,s',β′ )簽名信息后，進(jìn)行如下簽名過程：計算γ′=(s′+β′m)mod n=(α′r′+er′d+β′m)mod n ≠(x1,y1)，因此簽名無效，通過以上分析可知，改進(jìn)的ECDSA算法可以有效抵御接收者偽造簽名。

4.3 改進(jìn)方案的性能分析

4.3.1 安全性分析

方案的構(gòu)造通常不難，但首要的是要考慮到它的安全性，否則即使數(shù)字簽名計算效率再高，也毫無意義。在本文的改進(jìn)方案中，即使非法用戶設(shè)法得到了A或B的私鑰，也很難獲取到會話密鑰。由QA=dAG 可知，如果攻擊者在竊取QA和G 后推出了dA，那么就意味著他解決了離散對數(shù)難題，而這是不可能的，因此攻擊者無法獲得私鑰。具體安全性有以下幾個方面。

（1）抗偽造攻擊

對于發(fā)送方A和接收方B，雖然e,r′,α′，(α+ed)mod n是公開已知的，但是接收方B驗證出來的x′與x 不同，所以可以有效地抵抗偽造攻擊。

（2）防數(shù)據(jù)篡改

通過對消息進(jìn)行哈希運(yùn)算可以實現(xiàn)數(shù)據(jù)的完整性，一旦數(shù)據(jù)遭到篡改，哈希數(shù)值將會發(fā)生變化，從前述步驟中可以看出，如果哈希值不相同，則簽名無法通過。

（3）抗中間人攻擊

在傳統(tǒng)的通信過程中，公鑰是公開的，私鑰可以是隨機(jī)數(shù)r 或分發(fā)給用戶的d 。攻擊者選取隨機(jī)數(shù)rc∈[1,n-1]，截獲A發(fā)給B的QA=dAG ，B發(fā)給A的QB=dBG ，將dAG,dBG 修改成rcG ，協(xié)商之后，A與非法用戶共享密鑰dAdBG，A誤認(rèn)為B是共享的，B與非法用戶共享dAdBG，而B認(rèn)為A是共享的，實際A和B沒有共享密鑰。當(dāng)A發(fā)送信息給B時用dArcG 對信息進(jìn)行加密，非法用戶截獲之后進(jìn)行解密，偽造信息，用dAdBG 加密后發(fā)送給B，這樣就欺騙了用戶A和B，而事實上A和B是不知情的，這樣正常的密鑰協(xié)商就受到了影響。因此，在不清楚對方真實身份的情況下，通信雙方建立的密鑰會話易遭受中間人攻擊。在本文方案中通信的雙方實現(xiàn)了身份的雙向認(rèn)證，非法用戶不能偽裝成任何一方，從而有效地防止了中間人攻擊。

（4）抗抵賴性

接收方根據(jù)發(fā)送方發(fā)送的(r,s,β)，防止發(fā)送方事后抵賴。

4.3.2 效率分析

在本文的方案中，簽名和驗證過程均沒有模逆運(yùn)算，通過具體的數(shù)值來分析改進(jìn)方案的效率變化。在數(shù)字簽名過程中耗時主要集中在乘法、逆運(yùn)算和標(biāo)量乘運(yùn)算，可分別簡記為[l],[i],[h ] ，鑒于加法等運(yùn)算對耗時的影響因素較小，故可忽略不計。1次求逆運(yùn)算約相當(dāng)于10次乘法運(yùn)算，即[i] =10[l ]，根據(jù)文獻(xiàn)[18]，標(biāo)量乘運(yùn)算是滿足在163b 下[h ] =75[i] + 173[l ]=750[l ]+173[l ]=923[l]，設(shè)模乘運(yùn)算的數(shù)據(jù)規(guī)模為m，表5是改進(jìn)后的新方案與經(jīng)典的ECDSA 方案的耗時對比，由表5 分析可知，本文改進(jìn)的方案在簽名上的計算效率比經(jīng)典的ECDSA 方案提高了0.96%，在驗證上的計算效率比ECDSA方案提高了50.2%。

表5 兩種方案耗時對比

4.3.3 仿真實驗

在本文的改進(jìn)方案中，簽名和驗證過程均沒有求逆運(yùn)算，理論上無疑會極大提升數(shù)字簽名的效率，使用MATLAB編程模擬仿真來進(jìn)行驗證，檢測效率如圖3所示，從圖中可以直觀地看到兩種方案的運(yùn)算復(fù)雜度與數(shù)據(jù)規(guī)模的關(guān)系。

由圖3可看到，相較經(jīng)典的ECDSA方案，在同等的數(shù)據(jù)規(guī)模下，本文的改進(jìn)方案中數(shù)據(jù)復(fù)雜度始終較低，實驗仿真結(jié)果與本文的理論分析相吻合，即本文的改進(jìn)方案可以提高數(shù)字簽名的計算效率。

圖3 復(fù)雜度與數(shù)據(jù)規(guī)模對比

5 改進(jìn)的ECDSA方案在電子商務(wù)中的應(yīng)用

信息化網(wǎng)絡(luò)時代，電子商務(wù)的飛速發(fā)展使得人們足不出戶就可以享受方便快捷的服務(wù)。電子商務(wù)對信息的保密性、數(shù)據(jù)完整性、不可否認(rèn)性有較高要求。人們在享受網(wǎng)上交易帶來的便捷服務(wù)的同時，也日益關(guān)注信息安全。RSA 簽名算法曾被廣泛使用來保護(hù)交易信息的安全，隨著MD5算法被破解，SHA-1算法受到挑戰(zhàn)和ECDSA在理論上的日益成熟，ECDSA算法的優(yōu)越性日益凸顯，電子商務(wù)的安全越來越需要ECDSA來保證。

將改進(jìn)的ECDSA方案與時下飛速發(fā)展的電子商務(wù)進(jìn)行結(jié)合，在交易信息的加解密模型中通過構(gòu)建Meneses-Vanstone 密碼體制來對數(shù)據(jù)進(jìn)行加解密操作?；诟倪M(jìn)的橢圓曲線Meneses-Vanstone（MV）密碼體制構(gòu)造數(shù)據(jù)加解密模型。

數(shù)據(jù)加密模型如圖4所示。

圖4 電子數(shù)據(jù)加密模型

在電子商務(wù)交易過程中主要是客戶端與服務(wù)器端的互動，客戶端即加密的一方，為電子商務(wù)中數(shù)據(jù)信息的發(fā)送方。

（1）客戶端將待發(fā)送傳輸?shù)臄?shù)據(jù)信息格式化處理生成消息串(m1,m2)。

（2）用數(shù)據(jù)信息的接收方服務(wù)器端的公鑰QB和客戶端的私鑰dA按照MV 密碼體制對(m1,m2)進(jìn)行加密形成密文(x2,y2)。

（3）客戶端將自己的公鑰QA和加密信息( QA,( x2,y2))一起發(fā)送給接收方服務(wù)器端。

MV加密過程如下：

（1）獲得服務(wù)器端的公鑰QB，計算( x1,y1)=dAQB，如果x1,y1=0，則客戶端重新選擇私鑰dA，同時生成新的公鑰。

（2）計算x2=m1x1mod p,y2=m2y1mod p。

MV解密過程如下：

（1）獲得客戶端的公鑰QA，計算( x1,y1)=dBQA。

（2）計算m1=mod p,m2=mod p。

數(shù)據(jù)解密模型如圖5所示。

圖5 電子數(shù)據(jù)解密模型

服務(wù)器端即解密方，為電子商務(wù)交易中數(shù)據(jù)信息的接收方。服務(wù)器端接收到客戶端發(fā)送過來的加密信息( x2,y2)，首先使用客戶端的公鑰QA和服務(wù)器端的私鑰dB對加密信息按照MV密碼體制進(jìn)行解密生成( )m1,m2，然后再將其逆向轉(zhuǎn)換為客戶端明文消息。

MV 加密體制并沒有限制消息明文必須嵌入橢圓曲線上，這種體制的優(yōu)點(diǎn)是不需要將待加密的數(shù)據(jù)進(jìn)行數(shù)據(jù)類型轉(zhuǎn)換操作，從而降低了成本，同時提高了數(shù)據(jù)加解密效率。無模逆的橢圓曲線數(shù)字簽名算法，使運(yùn)算負(fù)擔(dān)減少，從而加快數(shù)字簽名和驗證簽名的速度，進(jìn)而使電子商務(wù)交易過程安全高效。

6 結(jié)束語

本文在對經(jīng)典的橢圓曲線數(shù)字簽名進(jìn)行分析的基礎(chǔ)上，指出其存在的局限性，由此進(jìn)行了方案的改進(jìn)。改進(jìn)的方案引入了雙參數(shù)，進(jìn)行標(biāo)量乘運(yùn)算2 次，在簽名和驗證過程中均沒有使用模逆運(yùn)算，理論分析證明了本文方案的安全性，仿真實驗證明了改進(jìn)方案提高了數(shù)字簽名的計算效率。最后將改進(jìn)的方案應(yīng)用到電子商務(wù)中，構(gòu)建了電子商務(wù)交易過程中電子數(shù)據(jù)的加解密模型。