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

曹 燁

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110159)

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

曹 燁

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110159)

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

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

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

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

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

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

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

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

(1)簽名雙方共同選擇一個(gè)大素?cái)?shù)p，p的大小應(yīng)該滿(mǎn)足在Zp中計(jì)算離散對(duì)數(shù)不可行。其中Zp為小于p的所有非負(fù)整數(shù)集合，即Zp={0,1,2,……,p-1}；

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

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

2)簽名過(guò)程：簽名方使用自己的私鑰x對(duì)消息M進(jìn)行簽名。

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

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

(3)計(jì)算；S1=gKmodp;

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

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

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

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

3)驗(yàn)證過(guò)程：驗(yàn)證方使用簽名方的公鑰{p,g,y}對(duì)收到的信息進(jìn)行核實(shí)。

(1)計(jì)算V1=gmmodp；

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

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

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

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

令(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和隨機(jī)整數(shù)K的情況下計(jì)算出的數(shù)據(jù)對(duì)(i,j)即是消息M1的一個(gè)有效簽名。

3)ElGamal算法中的隨機(jī)整數(shù)K不論是用于加密/解密、還是用于數(shù)字簽名中，都必須保證其唯一性。也就是說(shuō)，加密/解密時(shí)由于信息是以分塊的形式進(jìn)行操作，故必須為每個(gè)分塊選擇唯一的隨機(jī)整數(shù)K，否則如果用同一K對(duì)多個(gè)分塊進(jìn)行加密/解密，則攻擊者只要知道其中一個(gè)明文分塊，就可以計(jì)算出其他明文分塊，進(jìn)而破解密碼系統(tǒng)。同理，一個(gè)K也不能用在兩次數(shù)字簽名中，否則攻擊者可以利用條件偽造攻擊的方式獲取私鑰x，從而破譯算法。假設(shè)使用同一隨機(jī)參數(shù)K對(duì)消息M1和M2進(jìn)行數(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)等價(jià)于式(5)：

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

(5)

由式(5)進(jìn)一步可得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個(gè)可能的K值代入簽名公式S=gKmodp中進(jìn)行驗(yàn)證，就能找到唯一正確的K值，至此系統(tǒng)被破解[5-6]。

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

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

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

(1)p：大素?cái)?shù)，可公開(kāi)；

(3)x：用戶(hù)的私鑰，滿(mǎn)足1

(4)y：用戶(hù)的公鑰，有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為編程工具進(jìn)行系統(tǒng)仿真。設(shè)置系統(tǒng)參數(shù)如圖1所示。

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

2)簽名算法

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

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

(3)計(jì)算S1=gKmodp；

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

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

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

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

圖2 簽名算法

3)驗(yàn)證算法

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

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

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

(5)計(jì)算v=gv1y-v2modp；

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

圖3 驗(yàn)證簽名成功

圖4 驗(yàn)證簽名失敗

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

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

3.1 正確性驗(yàn)證

v=gv1y-v2modp

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

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

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

=gKmodp

∵S1=gKmodp

∴當(dāng)v=S1時(shí)，該簽名算法正確。

3.2 效率分析

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

1)先不考慮單次模運(yùn)算的計(jì)算復(fù)雜度，分析單次利用擴(kuò)展的歐幾里德算法求模逆過(guò)程中，所需的模運(yùn)算次數(shù)與輸入數(shù)據(jù)x和y之間的關(guān)系。假設(shè)x∈Z且x≥1，y∈Z且y≥1，滿(mǎn)足x>y，構(gòu)造數(shù)列{Ln}:L0=x,L1=y,…,Lk=Lk-2modLk-1(k≥2)。顯然，若運(yùn)算中需要進(jìn)行n次模運(yù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)由于在實(shí)際ElGamal簽名算法中所使用的都是512bit或1024bit的大整數(shù)，所以上述算法的時(shí)間復(fù)雜度顯然大于單次模運(yùn)算的時(shí)間復(fù)雜度。因此，改進(jìn)后的簽名方案比原方案的計(jì)算速度快，運(yùn)行效率高。

3.3 安全性分析

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

進(jìn)行分析，檢測(cè)其安全性。

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

3)已知簽名參數(shù)S1和S2，求解n。由于兩個(gè)隨機(jī)秘密參數(shù)K和d均不可知，故無(wú)法利用離散對(duì)數(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，必須進(jìn)行大整數(shù)的因式分解，才能得到所有滿(mǎn)足條件的(K,d)對(duì)，同時(shí)為了保證K和d在本次簽名中的唯一性，還需要采用窮舉法逐一排除所有不符合要求的(K,d)對(duì)，這會(huì)大大增加計(jì)算工作量和計(jì)算時(shí)間。

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

4 結(jié)論

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

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

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

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

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

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

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

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

(責(zé)任編輯：馬金發(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ù)庫(kù)理論與信息系統(tǒng)，信息安全。

1003-1251(2015)03-0032-05

TP309.7

A