對一種改進的ElGamal數字簽名方案的攻擊與改進

周 克 元

(宿遷學院文理學院 江蘇 宿遷 223800)

0 引 言

1976年，Diffie和Hellman提出數字簽名概念[1]，到目前，數字簽名技術得到了長足的發展和極大的應用。數字簽名是現代密碼學中重要的分支，數字簽名技術可廣泛應用于數字文檔的認證性、完整性和不可否認性，是網絡環境下實現數據安全傳輸的重要手段。

數字簽名技術一般依賴的數學難題有離散對數數學難題、因子分解數學難題和橢圓曲線數學難題。ElGamal數字簽名[2]是離散對數數字簽名中的一種主要方案，方案有使用Hash函數和不使用Hash函數兩個研究方向。

Hash函數主要算法有MD5和SHA-1系列，王小云等[3-5]提出了MD5和SHA-1算法的雜湊碰撞，使得使用了MD5和SHA-1的Hash函數的相關密碼算法不再安全，故設計不使用Hash函數的ElGamal離散對數數字簽名方案成為研究的熱點。相關學者對不使用Hash函數的ElGamal數字簽名方案的復雜度和安全性(模指數模逆運算、簽名驗證方程)進行了各種分析和改進，提出了一系列改進方案。但由于構造者在構造簽名方案時考慮得不夠周全或者是一味追求簽名協議的高效，使得有些簽名協議并不安全。曲娜等[6]對原始的ElGamal數字簽名方案進行了改進，減少了模逆運算的次數，張會影等[7]對ElGamal數字簽名方案中的隨機數進行了改進，增加了一個隨機數，提出了一種改進方案，由于該兩種方案中各參數之間的聯系不夠緊密，可被周克元[8]提出的一種偽造攻擊方案攻擊。白荷芳[9]、蘆殿軍[10]、李曉峰[11]亦對ElGamal數字簽名方案進行了研究，提出了相關的改進方案，相關改進方案亦可被文獻[8]中方法偽造簽名攻擊。李麗娟[12]

提出了一種新的ElGamal數字簽名改進方案，聲稱文獻[8]中的攻擊方案無法攻擊成功，經過分析，李麗娟方案安全性不夠，可被包括文獻[8]中攻擊方法在內的多種方法偽造簽名攻擊，本文給出了4種偽造簽名攻擊方法。即到目前為止，已有的相關方案均不安全。本文進一步給出了一個新的改進方案，證明了其正確性和安全性。

1 原始無Hash函數ElGamal數字簽名方案[2]

1.1 參數初始化

1.2 簽名過程

(2) 計算s=(m-rx)k-1mod(p-1)；則(r,s)為m的簽名。

1.3 驗證過程

驗證gm=rsyrmodp，正確則接受簽名，否則拒絕簽名。

2 對ElGamal方案的偽造簽名攻擊

文獻[6-7]對ElGamal方案進行了改進，分別給出了改進方案。ElGamal方案、曲娜方案、張會影方案中驗證方程可統一為gm=(yurv)wmodp，該結構可被周克元偽造簽名攻擊[8]，偽造簽名攻擊思路如下：

選取適當的r、u、v、w的值，將(yurv)wmodp變為gZmodp形式，此時只需設m=Zmod(p-1)，代入驗證方程，則驗證方程一定滿足，從而可以偽造簽名。下面以無Hash函數的ElGamal簽名方案為例給出偽造簽名攻擊方法：

任取整數u,v

證明：驗證方程右=gusyvsgxrmodp=gus+xvs+xrmodp=

gus-xvv-1r+xrmodp=gusmodp=

gmmodp=左

驗證方程成立，所以(r,s)是m的有效簽名。

其他相似的研究中，白荷芳方案[9]驗證方程為ysrrmodp=gmmodp，蘆殿軍方案[10]中驗證方程為gms-1rrs-1modpmodq=ymodpmodq(等價于gmmodpmodq=ysr-rmodpmodq)，李曉峰方案[11]的驗證方程為yrrnnsmodp=gmmodp，顯然均可被文獻[5]中偽造簽名攻擊方法攻擊，具體過程略。

3 李麗娟方案[12]

李麗娟亦對該類方案進行了分析，針對上述m放在指數中可被攻擊的情況，提出一個改進方案，將消息m放在驗證方程的底數中，宣稱可以避免文獻[8]中的攻擊方法，李麗娟方案如下。

3.1 參數初始化

3.2 簽名過程

(2) 計算s=(1-tr-kn)s=(1-tr-kn)x-1modp-1，則(r,s,n)為消息m的有效簽名。

3.3 驗證過程

驗證方程為ysrnnr=gmr+nmodp，正確則接受簽名，否則拒絕簽名。

4 對李麗娟方案的偽造簽名攻擊

李麗娟為防止文獻[8]中的方法攻擊，將驗證方程中含有m項中的m放在底數中，改為mr+u形式。但實際情況卻是可對驗證方程兩邊求(r+u)-1modp-1指數運算，從而求出m，此時將求出的m代入驗證方程，則驗證方程一定滿足，從而偽造簽名成功。文獻[8]中攻擊方法對李麗娟方案的偽造簽名攻擊過程見4.1節。

4.1 偽造簽名攻擊1

任取整數u,v

證明：驗證方程左=ysrmodp=ysguyvmodp=gumodp

右=gmr+nmodp=gg(u-1)(r+1)-1(r+1)modp=

ggu-1modp=gumodp=左

驗證方程成立，所以(r,s,1)是m的有效簽名。

除此之外，李麗娟方案還有其他三種偽造簽名攻擊方法，具體過程如下。

4.2 偽造簽名攻擊2

任取整數a,b

證明：驗證方程左=ysgaybmodp=gamodp

右=gg(a-1)(1+n)-1(1+n)modp=gamodp=左

驗證方程成立，所以(1,s,n)是m的有效簽名。

4.3 偽造簽名攻擊3

任取整數u,v,a,b

r=guyvmodp,n=gaybmodp
s=(vn+br)modp-1
m=g(un+ar-1)(r+n)-1modp

則(r,s,n)是m的有效簽名。其中(r+n)-1modp-1可由歐幾里德擴展算法從(r+n)(r+n)-1modp-1=1中計算出。

證明：驗證方程左=ysgunyvngarybrmodp=

ys+vn+brgun+armodp=

gun+armodp

右=gg(un+ar-1)(r+n)-1(r+n)modp=gun+armodp=左

驗證方程成立，所以(r,s,n)是m的有效簽名。

4.4 偽造簽名攻擊4

任取整數r,s,n

證明：驗證方程右=gmr+nmodp=gysrnnrg-1modp=

ysrnnrmodp=左

驗證方程成立，所以(r,s,n)是m的有效簽名。

4.5 攻擊方法分析

上述給出的4種攻擊方法中的消息m，只是一些特殊的消息，甚至是一些無意義的消息，還不能對任意有意義的消息m進行偽造攻擊，但足可以對李麗娟方案形成威脅。

上述各類攻擊方案攻擊成功的主要原因為在驗證方程中，消息明文m單獨出現，或者僅出現在指數中，或者僅在底數中。若在驗證方程中將m設計為在指數和底數中都出現，則上述攻擊方法將無法求出m的值，從而可以有效避免上述偽造簽名攻擊。下面給出李麗娟方案的改進方案。

5 改進方案設計

5.1 方案具體過程

(2) 簽名過程:

① 隨機任取兩個不同整數k,t

② 計算s=(m-tr-kn)x-1modp-1，則(r,s,n)為消息m的有效簽名，其中x-1可預求逆以減少運算時間。

(3) 驗證過程:驗證方程為ysnrrnmodp=gmmr+nmodp，正確則接受簽名，否則拒絕簽名。

(4) 正確性證明:驗證方程左=gxsmrgtrmngknmodp=gxs+tr+knmr+nmodp=gmmr+nmodp=右。

5.2 安全性分析

(1) 對抗從公鑰中揭露私鑰的攻擊:攻擊者若想從y=gxmodp求出x，該問題為求解離散對數數學難題。

(2) 對抗從簽名中求出私鑰的攻擊:驗證者B接收到A發送的簽名(r,s,n)后，若想利用簽名值從簽名方程s=(m-tr-kn)x-1modp-1中求出發送者A的私鑰x，但簽名方程含有三個未知參數t、k、x，故無法求出發送者A的私鑰x。

(3) 抗替換消息偽造簽名攻擊:驗證者B接收到簽名消息(m;r,s,n)后，用另一消息m′替換原有消息m，進行偽造簽名攻擊，由簽名過程，可計算出r′=rm′m-1modp，n′=nm′m-1modp，但s值的計算需要t、k、x的值，故無法求出s值，替換消息偽造簽名無法成功。

(4) 防止第4節中的4種方法的偽造簽名攻擊:第4節中的四種偽造攻擊方法的本質是設計一些簽名值r、s、n，將其代入驗證方程，由驗證方程求出m的值，再將r、s、n、m代入驗證方程，則驗證方程顯然成立，偽造簽名攻擊成功。

本文改進方案的驗證方程為ysnrrnmodp=gmmr+nmodp，由于m同時出現在指數和底數中，即使驗證方程中的其他參數均已知，也無法求出m的值，故第4節中的四種攻擊方法均無法攻擊成功，改進方案安全。

(5) 防止參數k同態攻擊:假設簽名者使用相同的參數t和不同的k1、k2、k3對消息m1、m2、m3簽名，滿足k3=k1+k2modp-1，簽名分別為：(m1;r1,s1,n1)、(m2;r2,s2,n2)、(m3;r3,s3,n3)，則有：

s1=(m1-tr1-k1n1)x-1modp-1

s2=(m2-tr2-k2n2)x-1modp-1

s3= (m3-tr3-k3n3)x-1modp-1=

(m3-tr3-(k1+k2)n3)x-1modp-1

其中：x、t、k1、k2未知，3個方程4個未知量，無法求解，故同態攻擊無法成功。

6 結 語

本文對各類改進的ElGamal離散對數數字簽名方案進行了分析，對改進方案李麗娟方案進行了攻擊分析，給出了4種攻擊方法，證明了其存在安全缺陷。給出了一個新的改進方案，證明了其正確性和安全性，證明了其可防止偽造簽名攻擊和同態攻擊。很好地解決了無Hash函數的ElGamal數字簽名的改進問題。