一種改進的橢圓曲線數字簽名方案

栗亞敏 張 平

(河南科技大學數學與統計學院 河南 洛陽 471023)

0 引 言

隨著網絡應用的蓬勃發展和廣泛普及，計算機病毒、黑客、電子犯罪和電子竊聽事件層出不窮，給人們的生活造成極大的隱患，因此，必須要加強網絡安全意識，盡量減少安全漏洞，最大限度地降低網絡安全造成的損失[1]。

數字簽名是當前網絡安全領域的研究熱點之一，數字簽名機制是保障網絡信息安全的手段之一，它可以解決簽名的偽造、抵賴、冒充和篡改問題[2]。數字簽名在實現身份認證、數據完整性、不可抵賴性等功能方面都有著重要的應用。最初提出它的目的是在網絡環境中模擬日常生活中的手工簽名或印章[1]。在數字簽名中，基于橢圓曲線密碼系統的數字簽名具有更高的安全性，橢圓曲線密碼系統是離散對數密碼系統在橢圓曲線上的移植[2]。橢圓曲線密碼體制ECC(Elliptic Curve Cryptography)由Koblitz[3]和Miller[4]分別獨立提出，它是利用有限域上的橢圓曲線有限群代替基于離散對數問題密碼體制中的有限循環群所得到的一類密碼體制[5-6]，它的安全性是基于橢圓曲線離散對數問題(ECDLP)的求解困難性基礎之上。因此，嚴格地說，它不是一種新的密碼體制，它只是已有密碼體制的橢圓曲線型的翻版。橢圓曲線密碼體制的研究歷史并不太長，但由于它自身突出的優點，得到了密碼學界的重視與廣泛推廣[7]。Johnson等[7]在1992年第一次提出橢圓曲線密碼的數字簽名算法(ECDSA)，這一算法被國際化標準組織定義為標準數字簽名算法。2007年，李復才等[8]設計了一種新的無求逆的簽名算法，該算法簡化了運算的復雜程度，保證了算法安全性。2008年，張慶勝等[9]對模乘運算進行了改進，提出了一種新的橢圓曲線數字簽名方案。同年，潘曉君[10]提出了一個新的基于橢圓曲線的數字簽名方案，該方案不需要進行模逆操作，大大提高了簽名的效率。楊青等[11]也提出了一種改進的基于橢圓曲線的數字簽名方案，該方案能夠有效地抵抗生日攻擊，提高數字簽名的安全性。2009年，武美娜等[12]改進了橢圓曲線數字簽名算法，改進算法不需要進行求逆運算，比傳統算法具有更少的時間復雜度。2011年，陳亮等[13]改進ECDSA簽名算法，提出了一種新的橢圓曲線數字簽名方案。此方案在簽名和驗證過程中避免了求逆運算，也減少了點乘。同年，許德武等[14]將ElGamal簽名方案移植到橢圓曲線密碼系統中，改進簽名生成及驗證過程，使用代數運算代替橢圓曲線上的數乘運算，得到了一種新的橢圓曲線數字簽名方案。2013年，周克元[15]設計了一種快速橢圓曲線消息恢復數字簽名方案，該方案僅僅具有2次模乘運算，并且沒有模逆運算。同年，逯玲娜等[16]提出了兩個新的不需要模逆操作的基于橢圓曲線的數字簽名方案。2014年，嚴琳等[17]設計了一種分段快速標量乘算法，并將其運用到了ECDSA方案中，提高了ECDSA方案的效率。2015年，陳輝焱等[18]設計了一種具有前向安全的數字簽名方案，該方案有效地減少了密鑰泄露帶來的損失。2016年，周克元[19]設計了一種具有消息恢復功能的橢圓曲線數字簽名方案，該方案不僅能抗偽造簽名攻擊，還具有前向安全性。隨著數字簽名技術[20-23]的不斷進步，近年來，許多新的橢圓曲線數字簽名方案[24]被相繼提出。

本文重點研究了文獻[9]算法，發現該算法可被替換消息偽造簽名攻擊。本文分析了其原因，提出了一種新的改進方案。

1 文獻[9]方案

1.1 參數選擇

1.2 簽名生成

簽名者A利用上面的參數對消息m進行簽名：

(1)選擇隨機數k∈[1,n-1]；

(2)計算kG=(x1,y1)，r=x1modn；

(3)計算e=SHA1(m)；

(4)計算s=(er)-1(k+d)modn；

(5)簽名結果為(r,s)。

1.3 簽名驗證

驗證者B驗證(r,s)是A對消息m的簽名：

(1)檢驗r,s∈[1,n-1]，若不成立，返回拒絕簽名；

(2)計算e=SHA1(m)；

(3)計算w=(er)smodn，那么就有公式(er)s=(k+d)modn成立；

(4)計算wG-Q=(x2,y2)；

(5)計算v=x2modn，若v=r，則接受該簽名，否則拒絕該簽名。

1.4 安全性分析

在該算法中簽名等式如下：

s=(er)-1(k+d)modn

(1)

可以用另一消息m′替換原有消息m進行偽造簽名。替換消息偽造簽名成功的原因如下：s、e、r已知，由：

s=(er)-1(k+d)modn

(2)

可求得(k+d)modn。然后計算e′=SHA1(m′)，那么就可以計算出：

s′=(e′r)-1(k+d)modn

(3)

從而得到偽造簽名(r,s′)。

另外，高偉等[1]設計的快速簽名等式如下：

s=k-l-rdmodn

(4)

該式也存在這樣的錯誤。

2 改進方案

2.1 參數的選擇

2.2 密鑰生成

(1)選擇x∈[1,n-1]；

(2)計算Y=xG。若Y=O，跳轉至步驟(1)；

(3)公鑰為Y，私鑰為x。

2.3 簽名生成

簽名者A利用上面的參數對消息m進行簽名：

(1)選擇隨機數k∈[1,n-1]；

(2)計算R=kG=(x1,y1)，r=x1modn，若r=0，跳至步驟(1)；

(3)計算e=H(m)；

(4)計算s=ke-rxe2modn(其中e2可以通過預處理提高簽名速度)，如果s=0，則跳至步驟(1)；

(5)簽名結果為(e,s)。

2.4 簽名驗證

驗證者B驗證(e,s)是A對消息m的簽名：

(1)檢驗r,s∈[1,n-1]，若不成立，返回拒絕簽名；

(2)計算e=H(m)；

(3)計算w=xemodn；

(4)計算X=w-1sY+rwG=(x2,y2)；

(5)若X=O，拒絕該簽名；

(6)計算v=x2modn，若v=r，則接受該簽名；否則拒絕該簽名。

2.5 方案正確性證明

若v=r，則：

X=w-1sY+rwG=(xe)-1sY+rwG

(5)

由于s=ke-rxe2modn，故：

X=(xe)-1(ke-rxe2)Y+rwG

(6)

則：

X=x-1(k-rxe)Y+rwG

(7)

即：

X=x-1kY-reY+rwG

(8)

由于Y=xG，那么：

X=kG-rexG+rwG

(9)

又因為w=xemodn，所以：

X=kG

(10)

從而v=r得證。

3 安全性證明

證明：

該證明過程實際上是一個敵手A和算法B之間的交互式游戲。算法B接收一個隨機的ECDLP問題實例Y=xG，他的目標是計算出x。算法B把敵手A作為子程序，算法B扮演敵手A的挑戰者。

1)設置階段。游戲一開始，算法B將系統參數發送給敵手A。算法B要維護LH、LS、LV三張列表，這些表初始為空，其中：列表LH用來跟蹤敵手A對預言機H的詢問；列表LS用于模逆簽名預言機；列表LV用于模逆驗證預言機。

2)查詢階段。

(1)哈希查詢。所有之前被簽名過的(m,e)被儲存在列表LH中，當敵手A對消息m進行哈希查詢時，算法B首先檢查消息m是否已經出現在列表LH中。若已存在，算法B直接將e返回給敵手A；否則，算法B從{0,1}n中任意選擇e，并將(m,e)存儲進列表LH中，然后將e返回給敵手A。

(2)簽名查詢。敵手A向算法B提交消息m，算法B任意選擇隨機數k∈[1,n-1]，然后計算R=kG=(x1,y1)，提取r=x1modn。算法B在列表LH中搜索(m,e)，若列表LH中存在(m,e)，則返回符號“⊥”，查詢終止；否則，算法B計算s=ke-rxe2modn；然后，將簽名結果(e,s)返回給敵手A。

證畢。

由于ECDLP問題是數學難題，目前沒有算法可以解決該問題，因此不存在能夠在t時間內以不可忽略的優勢ε攻破改進方案的敵手。因此，改進方案是安全的。

3.1 不可偽造性

傳統的橢圓曲線數字簽名方案ECDSA方案并沒有嚴格的安全性證明。2005年Brown[28]基于離散對數難解性以及哈希函數具有抗碰撞性的假設，給出了ECDSA方案的不可偽造性證明。該證明同樣適用于改進方案，此處省略了其證明。

3.2 抵抗隨機數攻擊

不同消息使用同一簽名方案進行簽名時，使用相同的隨機數(這種概率非常小)是不行的[29]，因為一旦隨機數相同就可以用一個二階的線性方程組解出私鑰，從而造成密鑰的泄露。

如果使用ECDSA方案對不同消息進行簽名時用相同的隨機數，那么就可以根據方程組：

(11)

解出：

k=(s2-s1)-1(e2-e1)modn

(12)

進而解出私鑰:

x=r-1(s1k-e1)modn

(13)

實際上，有很多方案即使每次使用不同的隨機數，也有可能被該攻擊方法的推廣所破解。比如，記u=xe+smodn，其中：x是私鑰；s是簽名結果中的s；e是被簽名的消息或消息的哈希函數。那么u在區間[0,n-1]的取值是隨機的，攻擊者只需計算eY+sG。如果對消息m1、m2的簽名中計算得：

e1Y+s1G=e2Y+s2Gmodn

(14)

那么就可推出u1=u2modn。因此:

e1x+s1=e2x+s2modn

(15)

從而就可以解出私鑰:

x=(e1-e2)-1(s2-s1)modn

(16)

在通過改進方案使用相同隨機數對不同消息進行簽名時，有如下方程組：

(17)

式中:簽名(e1,s1)和(e2,s2)是已知的;k、x和r是未知的，由于方程組中含有兩個方程三個未知數，因此無法求解方程組。

另外，如果想通過上述攻擊方法的推廣來破解改進方案也是不可能的。因為破解時要求計算不同簽名的某個隨機變量是否取相同的數值，這種概率也是非常小的以至于破解的計算量非常大，比直接計算離散對數還難。假設u取值的概率在區間[0,n-1]上是均勻分布的，那么由生日攻擊[30]的結論得a次不同消息的簽名中存在兩次簽名u1=u2的概率為0.5時，則a≈1.17sqrt(n)，這是一個非常大的數。如果沒有直接的eY與sG值的話，計算難度是非常大的。所以，改進方案可防止針對隨機數的攻擊。

3.3 不可否認性

如果簽名者想要否認自己曾對某個消息進行簽名，那么接受者可以將簽名提供給第三方。第三方可以通過驗證公式來驗證這個簽名是否是簽名者對該消息的簽名。由于第三方在驗證過程中不需要簽名者的協助，所以這就可以防止簽名者否認他的簽名。

3.4 不知明文密文對的攻擊[31]

(1)攻擊者想要直接通過Y=xG解出x是不可實現的，因為這需要求解橢圓曲線上的離散對數的數學難題。

(2)攻擊者想要通過驗證式(18)偽造m′的簽名(e′,s′)是不可實現的，因為攻擊者需要先確定一個r′(或s′)，再去求解s′(或r′)，這都需要求解橢圓曲線上離散對數這個數學難題。

kG=w-1sY+rwG

(18)

3.5 抵抗替換消息偽造簽名攻擊

攻擊者想通過加減乘除將式(19)中的e替換成e′是做不到的，因為該簽名方程涉及e2項。另外，在替換的同時難以保證r′=xmodn(其中k′G=(x,y))。

s=ke-rxe2modn

(19)

由改進方案的安全性分析可知，改進方案的安全性應該不低于ECDSA方案的安全性。與文獻[9]方案相比，改進方案涉及e和e2，大大增加了其對替換消息攻擊的抵抗。

4 效率分析

從算法運算量角度分析，設模乘運算的數據規模是n，1次倍點運算復雜度是O(n2)，1次模逆運算復雜度是O(9n2)(相當于9次倍點運算)，1次模乘運算復雜度是O(n2log2n)[32]。將本文方案的運算量與文獻[9]方案、ECDSA方案的運算量進行對比，結果如表1所示。

表1 方案效率比較

由表1可知，ECDSA的總運算量為:

N1=O[(4log2n+22)n2]

(20)

文獻[9]方案的總運算量為：

N2=O[(4log2n+12)n2]

(21)

本文方案的總運算量為：

N3=O[(6log2n+13)n2]

(22)

本文方案在簽名驗證上雖然無法與文獻[9]方案比較，但是其簽名驗證效率不低于ECDSA方案。影響復雜度的主要運算是模乘運算和模逆運算。本文方案在密鑰生成時與另外兩種方案的復雜度相同。在簽名階段，改進方案比另外兩種方案多了1次模乘運算，少了1次模逆運算；在簽名驗證階段，本文方案雖然比文獻[9]方案多了1次模乘運算、1次模逆運算和1次倍點運算，但是本文方案不僅能防止消息偽造簽名攻擊，還能防止隨機數攻擊?？傮w來說，本文方案加強了安全性，適當犧牲了速度。

5 結 語

本文首先對文獻[9]方案進行重點研究和分析，發現該方案存在替換消息偽造簽名的安全隱患。針對此安全隱患，本文提出了一個新的改進方案，并對其進行安全性證明。本文方案雖然在效率上有待提高，但是其不僅能防止消息偽造簽名攻擊，還能防止針對隨機數的攻擊以及不知明文密文對的攻擊。總的來說，改進后方案在安全性上有了很大的提高。因此，本文方案適用于對效率要求較低、對安全性要求高的應用場合。