曹 燁

(沈陽理工大學 信息科學與工程學院，遼寧 沈陽 110159)

ElGamal數(shù)字簽名方案的安全性分析及改進

曹 燁

(沈陽理工大學 信息科學與工程學院，遼寧 沈陽 110159)

分析了ElGamal算法用于數(shù)字簽名中存在的安全性問題，并在傳統(tǒng)算法基礎上提出一種改進方案，在基于計算離散對數(shù)困難性的前提下，通過與原簽名方案的比較，改進后的數(shù)字簽名算法在安全性和計算效率上均有提高。

公鑰密碼體制；數(shù)字簽名；ElGamal算法；離散對數(shù)；生成元

公鑰密碼學的誕生之所以被稱為密碼學發(fā)展史上最重要的一次革命，其貢獻在于算法中使用了一對完全不同的密鑰，這樣的算法機制為數(shù)字簽名技術的研究和應用提供了理論基礎。在各種基于公鑰密碼體制的數(shù)字簽名方案中，簽名方通常先使用某種散列算法計算出明文消息的散列值，然后用自己的私鑰對該值進行加密生成簽名，驗證方則使用簽名方的公鑰對接收的信息進行完整性檢驗，保證其來源的可靠[1]。但由于公鑰密碼設計的原理都是基于各種復雜的數(shù)學函數(shù)，計算上的復雜性導致其在簽名和驗證過程中的運算速度較慢，執(zhí)行效率不高。因此，本文對傳統(tǒng)ElGamal數(shù)字簽名算法做出適當改進和優(yōu)化，使得改進后的簽名方案在安全性和計算效率上均有提高。

1 傳統(tǒng)ElGamal數(shù)字簽名方案安全性分析

ElGamal算法是1984年由Taher.Elgamal提出的一種公鑰密碼體制算法，該算法的安全性是建立在有限域中計算離散對數(shù)的困難性之上，ElGamal算法主要是為實現(xiàn)數(shù)字簽名目的而設計的[2]。

1.1 傳統(tǒng)算法描述

為了便于與改進簽名方案進行比較，首先列出傳統(tǒng)簽名算法。

1)產(chǎn)生密鑰對：

(1)簽名雙方共同選擇一個大素數(shù)p，p的大小應該滿足在Zp中計算離散對數(shù)不可行。其中Zp為小于p的所有非負整數(shù)集合，即Zp={0,1,2,……,p-1}；

(3)隨機產(chǎn)生正整數(shù)x，滿足1

(4)計算y=gxmodp，則簽名方的密鑰對為公鑰KU={p,g,y}，私鑰KR={x}。

2)簽名過程：簽名方使用自己的私鑰x對消息M進行簽名。

(1)簽名方使用單向散列函數(shù)H計算明文M的散列值m=H(M)，滿足m∈Zp；

(2)隨機選擇整數(shù)K，滿足1≤K≤p-1且gcd(K,p-1)=1；

(3)計算；S1=gKmodp;

(4)計算K在模(p-1)下的乘法逆元K-1≡1mod(p-1)；

(5)利用擴展的歐幾里德算法從m=(x·S1+K·S2)mod(p-1)求出S2，即

S2=K-1(m-x·S1)mod(p-1)

(6)簽名結(jié)果為S=(S1,S2)。

3)驗證過程：驗證方使用簽名方的公鑰{p,g,y}對收到的信息進行核實。

(1)計算V1=gmmodp；

(2)計算V2=yS1(S1)S2modp；

(3)如果V1=V2，則認為簽名正確，反之拒絕簽名[3]。

1.2 傳統(tǒng)算法安全性分析

2)即使不利用隨機整數(shù)K，攻擊者在獲取少量信息的情況下也可以破解算法。假設攻擊者截獲了簽名方發(fā)送給驗證方對于消息M的一個有效簽名(S1,S2)，在滿足a∈Z且a≤p-2，b∈Z且b≤p-2，c∈Z且c≥0，同時gcd(S1·c-S2·b,p-1)條件下，攻擊者通過如下計算可以得到對消息M1的一個有效簽名，攻擊演示如下所述。

令(S1·c-S2·b)-1≡1mod(p-1)

j=S2·i·(S1·c-S2·b)-1mod(p-1)

有H(M1)=i·(c·H(M)+a·S2)(S1·c-S2·b)-1mod(p-1)

∵yi·ii≡gH(M1)modp

∴攻擊者在不知道私鑰x和隨機整數(shù)K的情況下計算出的數(shù)據(jù)對(i,j)即是消息M1的一個有效簽名。

3)ElGamal算法中的隨機整數(shù)K不論是用于加密/解密、還是用于數(shù)字簽名中，都必須保證其唯一性。也就是說，加密/解密時由于信息是以分塊的形式進行操作，故必須為每個分塊選擇唯一的隨機整數(shù)K，否則如果用同一K對多個分塊進行加密/解密，則攻擊者只要知道其中一個明文分塊，就可以計算出其他明文分塊，進而破解密碼系統(tǒng)。同理，一個K也不能用在兩次數(shù)字簽名中，否則攻擊者可以利用條件偽造攻擊的方式獲取私鑰x，從而破譯算法。假設使用同一隨機參數(shù)K對消息M1和M2進行數(shù)字簽名，結(jié)果分別為(S，S1)和(S，S2)，攻擊演示如下所述。

yS·SS1≡gH(M1)modp

(1)

yS·SS2≡gH(M2)modp

(2)

(3)

代入式(1)整理得gH(M2)-H(M1)≡SS2-S1modp

(4)

由于簽名公式S=gKmodp，則式(4)等價于式(5)：

gH(M2)-H(M1)≡gK(S2-S1)mod(p-1)

(5)

由式(5)進一步可得H(M2)-H(M1)≡K(S2-S1)mod(p-1)

(6)

令t=gcd(S2-S1,p-1)，

∵t|(S2-S1)且t|(p-1)

∴有t|(H(M2)-H(M1))成立。

(7)

(8)

(9)

將式(6)、(7)、(8)代入式(9)，則同余式變形為

x′≡K·S′modp′

(10)

最后將這t個可能的K值代入簽名公式S=gKmodp中進行驗證，就能找到唯一正確的K值，至此系統(tǒng)被破解[5-6]。

2 改進ElGamal數(shù)字簽名方案描述

由于傳統(tǒng)算法在簽名階段需要事先進行模逆運算即K-1≡1mod(p-1)，而該運算通常需要利用擴展的歐幾里德算法實現(xiàn)，該算法的計算復雜度相當于大指數(shù)運算，在計算機中執(zhí)行速度較慢，效率較低。故本文在改進方案的簽名階段使用隨機函數(shù)rand( )生成參數(shù)d取代模逆運算，具體實現(xiàn)過程描述如下。

1)設置系統(tǒng)參數(shù)

(1)p：大素數(shù)，可公開；

(3)x：用戶的私鑰，滿足1

(4)y：用戶的公鑰，有y=gxmodp；

(5)H：安全散列函數(shù)。

在硬件環(huán)境為Intel Pentium(R)Core(TM)i3 CPU 2.53GHz、1.92GB內(nèi)存、512M顯卡，使用Microsoft Windows XP Professional Service Pack3操作系統(tǒng)，以VisualC++6.0為編程工具進行系統(tǒng)仿真。設置系統(tǒng)參數(shù)如圖1所示。

圖1 設置系統(tǒng)參數(shù)

2)簽名算法

(1)計算消息M的散列值m，使m=H(M)，滿足m∈Zp；

(2)利用隨機函數(shù)rand()產(chǎn)生兩個整數(shù)K和d，滿足1≤K≤p-1且gcd(K,p-1)=1，1≤d≤p-1且gcd(d,p-1)=1，Kd≠0mod(p-1)；

(3)計算S1=gKmodp；

(4)計算S2=(m-xS1)·dmod(p-1)；

(5)計算n=Kdmod(p-1)；

(6)簽名方將S=(S1,S2,n)作為生成的數(shù)字簽名發(fā)送給驗證方。

對存儲在F盤根目錄下的文件“測試文件1.txt”進行簽名測試，系統(tǒng)仿真如圖2所示。

圖2 簽名算法

3)驗證算法

(1)采用同樣的安全散列函數(shù)計算消息M的散列值m=H(M)；

(3)計算v1=mtmod(p-1)；

(4)計算v2=S1tmod(p-1)；

(5)計算v=gv1y-v2modp；

(6)判斷v=S1，如果等式成立則簽名合法，否則不接受該數(shù)字簽名。

圖3 驗證簽名成功

圖4 驗證簽名失敗

為了檢測驗證算法的正確性，還是以“測試文件1.txt”為例，首先在不同的路徑下建立兩個文件名相同，但文件內(nèi)容不同的“測試文件1.txt”，其中路徑為“F：曹燁測試文件1.txt”的文件是與圖1中完全一樣的正確文件，而另一個路徑為“E：測試文件1.txt”的文件則用來模擬文件受到攻擊后被偽造和篡改的情況——為了掩人耳目，攻擊者修改了截獲文件的內(nèi)容但沒有修改文件名。對兩個不同文件的系統(tǒng)仿真驗證結(jié)果如圖3和圖4所示。

3 改進方案性能分析

3.1 正確性驗證

v=gv1y-v2modp

={(gv1modP)[(gxmodp)-v2modp]}modp，(y=gxmodp)

=[(gv1modp)(g-xv2modp)]mpdp

=g[t·(m-xS1)]mod(p-1)modp

=gKmodp

∵S1=gKmodp

∴當v=S1時，該簽名算法正確。

3.2 效率分析

在改進后的方案中，簽名階段避免了復雜的模逆運算，不用再求隨機參數(shù)K的乘法逆元，只需進行一次簡單的模運算n=Kdmod(p-1)；驗證階段雖然比原算法多了兩個中間參數(shù)V1和V2的計算，但其也都是簡單的模運算，與原方案中需要用擴展的歐幾里德算法實現(xiàn)的模逆運算相比，后者的計算復雜度相當于大指數(shù)運算，遠高于前者的模運算。具體分析如下：

1)先不考慮單次模運算的計算復雜度，分析單次利用擴展的歐幾里德算法求模逆過程中，所需的模運算次數(shù)與輸入數(shù)據(jù)x和y之間的關系。假設x∈Z且x≥1，y∈Z且y≥1，滿足x>y，構(gòu)造數(shù)列{Ln}:L0=x,L1=y,…,Lk=Lk-2modLk-1(k≥2)。顯然，若運算中需要進行n次模運算，則有Ln=gcd(x,y),Ln+1=0。比較斐波那契數(shù)列{Fn}:F0=0,F1=1,…,Fn+2=Fn+Fn+1(n≥0)和數(shù)列{Ln}有：Ln≥F0=0,Ln-1≥F1=1。

3)由于在實際ElGamal簽名算法中所使用的都是512bit或1024bit的大整數(shù)，所以上述算法的時間復雜度顯然大于單次模運算的時間復雜度。因此，改進后的簽名方案比原方案的計算速度快，運行效率高。

3.3 安全性分析

對ElGamal數(shù)字簽名方案進行攻擊，最有效、最快捷的方法是獲取簽名方的私鑰x，但由于私鑰都是簽名方唯一知道他人無法獲得，故安全性分析是在假定攻擊者無法得到私鑰x的情況下對改進簽名方案進行破解，通過驗證公式

進行分析，檢測其安全性。

2)已知簽名參數(shù)S2和n，求解S1。雖然已知g和p，但由于隨機參數(shù)K不可知，故無法通過求解離散對數(shù)得到S1。另外由驗證公式可以看出，公式左邊有S1，右邊y的指數(shù)冪中也有S1，目前對于這類等式還沒有好的計算方法。

3)已知簽名參數(shù)S1和S2，求解n。由于兩個隨機秘密參數(shù)K和d均不可知，故無法利用離散對數(shù)求出n。即使已知n可以求解出K·d的乘積，由于1≤K≤p-1且gcd(K,p-1)=1，1≤d≤p-1且gcd(d,p-1)=1，故要分別得到K和d，必須進行大整數(shù)的因式分解，才能得到所有滿足條件的(K,d)對，同時為了保證K和d在本次簽名中的唯一性，還需要采用窮舉法逐一排除所有不符合要求的(K,d)對，這會大大增加計算工作量和計算時間。

通過以上分析可以看出，改進簽名方案中隨機參數(shù)的加入增加了攻擊者破解系統(tǒng)的難度和時間，所以改進方案比原簽名方案的安全性有所提高[7]。

4 結(jié)論

改進方案在簽名階段增加了一個隨機參數(shù)d用以取代原方案中復雜的模逆運算，目的是提高簽名效率，因此從減少簽名和驗證階段的運算量、加快計算速度方面來說，希望d的取值越小越好，但由于每次簽名時用戶都要隨機選取d值且不能重復使用，而在利用隨機函數(shù)rand()產(chǎn)生d時不一定每次都能得到滿意的取值，另外，d值過小時會減小攻擊者破譯私鑰x的難度，降低簽名方案的安全性，所以簽名方必須認真考量產(chǎn)生隨機參數(shù)d的函數(shù)和d的取值大小。

[1]胡向東，魏琴芳，胡蓉.應用密碼學[M].(第2版).北京：電子工業(yè)出版社，2011：20-26.

[2]Bruce Schneier.應用密碼學協(xié)議、算法與C源程序[M].(第2版).吳世忠等譯.北京：機械工業(yè)出版社，2012：23-24.

[3]余姜德，商林，于志平.ElGamal加密體制在軟件保護技術中的應用[J].計算機與現(xiàn)代化，2005，(5)：87-88.

[4]曹素珍，左為平，張建.一種新的ElGamal數(shù)字簽名方案[J].網(wǎng)絡安全技術與應用，2007，38(4)：40-41.

[5]王慶梅，吳克力，劉鳳玉.具有消息認證功能的多重數(shù)字簽名方案[J].計算機工程，2003，29(19)：14-16.

[6]焦陽，傅德勝.基于ElGamal的有序多重數(shù)字簽名方案[OL/DB].http：//d.wanfangdata.com.cn/Periodical_scdxxb201304017.aspx.

[7]夏峰，馮建平，張瑜.一類ElGamal數(shù)字簽名方案的安全性分析[J].科學技術與工程，2010，10(22)：88-90.

(責任編輯：馬金發(fā))

Security Analysis and Improvement of ElGamal Digital Signature Scheme

CAO Ye

(Shenyang Ligong University,Shenyang 110159,China)

Some security problems of ElGamal algorithm in digital signature are analyzed.And an improved scheme is put forword based on the traditional algorithm.The security and computing efficiency of improved digital signature algorithm is increased in comparison with original signature scheme.This conclusion is based on the difficulty of computing discrete logarithm.

public key cryptosystem;digital signature;ElGamal algorithm;discrete logarithm;generator

2014-09-25

曹燁(1978—)，女，工程師，研究方向：數(shù)據(jù)庫理論與信息系統(tǒng)，信息安全。

1003-1251(2015)03-0032-05

TP309.7

A