栗亞敏 張 平

(河南科技大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院 河南 洛陽 471023)

0 引 言

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

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

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

1 文獻(xiàn)[9]方案

1.1 參數(shù)選擇

1.2 簽名生成

簽名者A利用上面的參數(shù)對消息m進(jìn)行簽名：

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

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

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

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

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

1.3 簽名驗(yàn)證

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

(1)檢驗(yàn)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進(jìn)行偽造簽名。替換消息偽造簽名成功的原因如下：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]設(shè)計的快速簽名等式如下：

s=k-l-rdmodn

(4)

該式也存在這樣的錯誤。

2 改進(jìn)方案

2.1 參數(shù)的選擇

2.2 密鑰生成

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

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

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

2.3 簽名生成

簽名者A利用上面的參數(shù)對消息m進(jìn)行簽名：

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

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

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

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

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

2.4 簽名驗(yàn)證

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

(1)檢驗(yàn)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)

又因?yàn)閣=xemodn，所以：

X=kG

(10)

從而v=r得證。

3 安全性證明

證明：

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

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

2)查詢階段。

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

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

證畢。

由于ECDLP問題是數(shù)學(xué)難題，目前沒有算法可以解決該問題，因此不存在能夠在t時間內(nèi)以不可忽略的優(yōu)勢ε攻破改進(jìn)方案的敵手。因此，改進(jìn)方案是安全的。

3.1 不可偽造性

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

3.2 抵抗隨機(jī)數(shù)攻擊

不同消息使用同一簽名方案進(jìn)行簽名時，使用相同的隨機(jī)數(shù)(這種概率非常小)是不行的[29]，因?yàn)橐坏╇S機(jī)數(shù)相同就可以用一個二階的線性方程組解出私鑰，從而造成密鑰的泄露。

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

(11)

解出：

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

(12)

進(jìn)而解出私鑰:

x=r-1(s1k-e1)modn

(13)

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

e1Y+s1G=e2Y+s2Gmodn

(14)

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

e1x+s1=e2x+s2modn

(15)

從而就可以解出私鑰:

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

(16)

在通過改進(jìn)方案使用相同隨機(jī)數(shù)對不同消息進(jìn)行簽名時，有如下方程組：

(17)

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

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

3.3 不可否認(rèn)性

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

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

(1)攻擊者想要直接通過Y=xG解出x是不可實(shí)現(xiàn)的，因?yàn)檫@需要求解橢圓曲線上的離散對數(shù)的數(shù)學(xué)難題。

(2)攻擊者想要通過驗(yàn)證式(18)偽造m′的簽名(e′,s′)是不可實(shí)現(xiàn)的，因?yàn)楣粽咝枰却_定一個r′(或s′)，再去求解s′(或r′)，這都需要求解橢圓曲線上離散對數(shù)這個數(shù)學(xué)難題。

kG=w-1sY+rwG

(18)

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

攻擊者想通過加減乘除將式(19)中的e替換成e′是做不到的，因?yàn)樵摵灻匠躺婕癳2項(xiàng)。另外，在替換的同時難以保證r′=xmodn(其中k′G=(x,y))。

s=ke-rxe2modn

(19)

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

4 效率分析

從算法運(yùn)算量角度分析，設(shè)模乘運(yùn)算的數(shù)據(jù)規(guī)模是n，1次倍點(diǎn)運(yùn)算復(fù)雜度是O(n2)，1次模逆運(yùn)算復(fù)雜度是O(9n2)(相當(dāng)于9次倍點(diǎn)運(yùn)算)，1次模乘運(yùn)算復(fù)雜度是O(n2log2n)[32]。將本文方案的運(yùn)算量與文獻(xiàn)[9]方案、ECDSA方案的運(yùn)算量進(jìn)行對比，結(jié)果如表1所示。

表1 方案效率比較

由表1可知，ECDSA的總運(yùn)算量為:

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

(20)

文獻(xiàn)[9]方案的總運(yùn)算量為：

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

(21)

本文方案的總運(yùn)算量為：

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

(22)

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

5 結(jié) 語

本文首先對文獻(xiàn)[9]方案進(jìn)行重點(diǎn)研究和分析，發(fā)現(xiàn)該方案存在替換消息偽造簽名的安全隱患。針對此安全隱患，本文提出了一個新的改進(jìn)方案，并對其進(jìn)行安全性證明。本文方案雖然在效率上有待提高，但是其不僅能防止消息偽造簽名攻擊，還能防止針對隨機(jī)數(shù)的攻擊以及不知明文密文對的攻擊?？偟膩碚f，改進(jìn)后方案在安全性上有了很大的提高。因此，本文方案適用于對效率要求較低、對安全性要求高的應(yīng)用場合。