韋 敏，肖 鑫，沈 雁，周克元

(宿遷學院二系，江蘇 宿遷 223800)

0 引言

自1976年Diffie和Hellman提出數(shù)字簽名［1］后，數(shù)字簽名技術(shù)獲得了長足的進展和極大的應用，數(shù)字簽名方案一般基于一個或多個數(shù)學難題，常見的有基于因子分解的RSA簽名方案［2］、基于離散對數(shù)的El-Gamal簽名方案［3］、基于橢圓曲線的 ECDSA 方案［4］，有的是基于雙難題的數(shù)字簽名方案［5-6］，另外還有消息恢復簽名［7］、代理簽名［8］、盲簽名［9］、群簽名［10］等一系列應用。其中ElGamal數(shù)字簽名方案［3］是重要的一種方案，但方案中有4次指數(shù)運算和1次模逆運算，運算量較大。研究者對ElGamal方案進行了各種推廣和改進，對于ElGamal數(shù)字簽名方案的改進有2種思路，第一種是在不降低其安全性的情況下，對指數(shù)運算和模逆運算進行改進減少其次數(shù)，從而降低復雜度，已有一系列的改進方案［11-12］;第二種是針對El-Gamal數(shù)字簽名容易受到攻擊的情況，在不改變其結(jié)構(gòu)的情況下增加參數(shù)以增加安全性，已有一系列的改進方案［13-14］，但復雜度一般沒有得到較好的改進。本文給出一種新的改進方案，通過增加一個參數(shù)以增加安全性，同時又降低了算法復雜度，與各種改進比較，效率更高。

1 已有離散對數(shù)數(shù)字簽名方案

1.1 ElGamal數(shù)字簽名方案［3］

(1)參數(shù)初始化。

(2)簽名過程。

(3)驗證過程。

接收者接收到m和(r，s)后，首先計算h(m)，驗證yrrs=gh(m)mod p，正確則接受簽名，否則拒絕簽名。

1.2 曲娜方案［12］

對ElGamal方案中指數(shù)運算和模逆運算的最新改進為曲娜方案，方案中指數(shù)運算為3次，模逆運算為0次。方案如下:

(1)參數(shù)初始化。

(2)簽名過程。

設待簽消息為m，隨機選擇0＜k＜q，計算 r=gkmod p，s=(m －kr)x－1mod(p －1)，則簽名為(r，s)。

(3)驗證過程。

接收者接收到 m和(r，s)后，驗證等式 ysrr=gmmod p，正確則接受簽名，否則拒絕簽名。

1.3 李曉峰方案［14］

李曉峰通過增加一個參數(shù)提高了攻擊的難度，增加了安全性，但方案中指數(shù)運算高達6次，模逆運算為1次。方案如下:

(1)參數(shù)初始化。

參數(shù)同1.1節(jié)(1)。

(2)簽名過程。

(3)驗證過程。

接收者接收到 m 和(r，λ，δ)后，驗證 gm=yrrλλδmod p，正確則接受簽名，否則拒絕簽名。

2 新的改進方案

基于公鑰密碼體制的數(shù)字簽名方案因其良好的數(shù)學特性，很容易遭受攻擊，為了抵抗偽造攻擊，數(shù)字簽名方案一般采取某種消息格式化機制，例如Hash函數(shù)或消息冗余，使驗證者對簽名消息的非隨機性進行驗證。本文給出一個三參數(shù)的改進簽名方案，在提高了安全度的情況下將指數(shù)運算和模逆運算改進為最低值2次和0次，方案中使用Hash函數(shù)，可證明其正確性和安全性。改進方案中使用了 Hash值的Hamming重量，以當前普遍使用的Hash函數(shù)MD5為例，Hash值為128位二進制數(shù)，而Hamming重量不大于128(7位二進制數(shù))。研究發(fā)現(xiàn)Hash值的Hamming重量對消息的變化很敏感，若消息變化，Hamming重量發(fā)生變化的概率為92%以上［15］。

2.1 算法描述

(1)參數(shù)初始化。

參數(shù)同1.1節(jié)(1)。且h()為安全Hash函數(shù)，ham()為求Hamming重量的函數(shù)，待簽消息為m(m＜p－1)。

(2)簽名過程。

③計算s=(ω+αr+x)mod(p－1)。

簽名為(r，s，β，u)。

(3)驗證過程。

接收者收到 m 和(r，s，β，u)后，驗證步驟為:

①計算e=h(m)，ω=ham(e);

②計算γ=(s－ω+βe+u)mod(p－1);

③驗證gγmod p=rymod p，正確則接受簽名，否則拒絕簽名。

(4)正確性證明。

2.2 安全性分析

(1)對抗從公鑰中揭露私鑰的攻擊。

攻擊者想從y=gxmod p求出x為求解離散對數(shù)問題。

(2)對抗從簽名中求出私鑰的攻擊。

接收者 B 接收到簽名組(r，s，β，u)，B 即知 r，s，β，e，w，m，u，但 k=(αr+ βe+u)mod(p －1)和 s=(ω+αr+x)mod(p－1)兩個方程有3個變量 α，k，x，無法求出其值。

(3)抗替換消息偽造簽名攻擊。

B接收到A發(fā)送的簽名消息后，用另一消息m'替換原有消息m進行偽造簽名不可行。攻擊過程如下:

①計算e'=h(m')，ω'=ham(e');

②由s=(ω+αr+x)mod(p－1)可計算出αr+x;

③計算 s'=(ω'+αr+x)mod(p－1);

得 m'的偽造簽名為(r，s'，β，u)。

④驗證:計算 γ'=(s'－ω'+βe'+u)mod(p－1)=(αr+βe'+u+x)mod(p－1)≠(k+x)mod(p－1)，則 gγ'mod p≠rymod p，所以替換消息偽造簽名失敗。

(4)抗替換隨機數(shù)k的偽造簽名攻擊。

B接收到A發(fā)送的簽名消息后，用k'=(k+t)mod q替換k進行偽造簽名攻擊:

①任取t，設k'=(k+t)mod(p－1);

②計算r'=gk'mod p=(gkgt)mod p=(rgt)mod p;

③因不知k'值，故只能假設有表達式k'=(α'r'+β'e+u')mod(p －1)，其中 k'，α'，β'，u'未知;

④由s=(ω+αr+x)mod(p－1)可計算出αr+x，若要偽造簽名，需求出s'=(ω+α'r'+x)mod(p－1)，其中有2 個未知變量 α'，x，且 α'r'+x≠(αr+x)mod(p－1)，所以無法偽造簽名。

2.3 復雜度比較

將曲娜方案［12］、李曉峰方案［14］與本文改進算法進行復雜度比較，結(jié)果見表1。

表1 3種方案簽名算法復雜度比較

本文改進算法中指數(shù)運算達到了最低值2次，并且無求逆，雖然算法中增加了Hash函數(shù)運算，但h()長度遠小于m長度，對應的指數(shù)運算要快得多，所以綜合比較本文方案比曲娜方案、李曉峰方案速度要快得多。

3 結(jié)束語

本文給出了ElGamal數(shù)字簽名方案及相關(guān)改進方案，提出了一種新的改進方案，證明了其正確性和安全性，與ElGamal方案相比增加了一個參數(shù)以提高安全性，同時模指數(shù)運算達到最低2次，模逆運算達到最低0次，與已有的方案比較，復雜度有較大程度降低。

［1］Diffie Whitfield，Hellman E Martn.New direction in cryptography［J］.IEEE Transactions on Information Theory，1976，22(6):644-654.

［2］Rivest R，Shamir A，Adleman L.A method for obtaining digital signature and public-key cryptosystems［J］.Communications of the ACM，1978，21，(2):120-126.

［3］ElGamal T.A public keycryptosystem and a signature scheme based on discrete logarithms［J］.IEEE Transactions on Information Theory，1985，31(4):469-472.

［4］Johson D，Menezes A，Vanstone S.The elliptic curve digital signature algorithm(ECDSA)［J］.International Journal of Information Security，2001，1(1):36-63.

［5］邵祖華.基于因數(shù)分解和離散對數(shù)的數(shù)字簽名協(xié)議［J］.通信保密，1998(4):36-41.

［6］袁喜鳳，孫艷蕊，孫金青，等.基于離散對數(shù)和因子分解具有消息恢復的簽名方案［J］.計算機應用，2007，27(10):2459-2460.

［7］Nyberg K，Rueppel R A.Message recovery for signature schemes based on the discrete logarithm［J］.Designs，Codes and Cryptography，1996，7(1-2):61-68.

［8］Mambo M，Usuda K，Okamoto E.Proxy signatures:Delegation of the power to sign messages［J］.IEICE Trans.Fundam.，1996，79(9):1338-1354.

［9］Chaum D.Blind signatures for untraceable payments［C］//Advances in Cryptology Crypto’82.1982:199-203.

［10］Chaum D，Heyst V E.Group signatures［C］//Proceedings of EUROCRYPT’91.1991:257-265.

［11］白荷芳，王彩芬.對一種變形ElGamal簽名體制的分析［J］.西北師范大學學報:自然科學版，2006，42(3):109-110.

［12］曲娜，杜洪軍，顏達，等.ElGamal數(shù)字簽名算法的一種變形［J］.吉林大學學報:信息科學版，2009，27(6):590-594.

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

［14］李曉峰，趙海，王家亮，等.基于增加一個隨機數(shù)的El-Gamal數(shù)字簽名算法的改進［J］.東北大學學報:自然科學版，2010，31(8):1102-1104.

［15］侯愛琴，高寶建，張萬緒，等.基于橢圓曲線的一種高效率數(shù)字簽名［J］.計算機應用與軟件，2009，26(2):58-60.