離散對數(shù)數(shù)字簽名算法的改進(jìn)

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

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

0 引言

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

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

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

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

(2)簽名過程。

(3)驗(yàn)證過程。

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

1.2 曲娜方案［12］

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

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

(2)簽名過程。

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

(3)驗(yàn)證過程。

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

1.3 李曉峰方案［14］

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

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

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

(2)簽名過程。

(3)驗(yàn)證過程。

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

2 新的改進(jìn)方案

基于公鑰密碼體制的數(shù)字簽名方案因其良好的數(shù)學(xué)特性，很容易遭受攻擊，為了抵抗偽造攻擊，數(shù)字簽名方案一般采取某種消息格式化機(jī)制，例如Hash函數(shù)或消息冗余，使驗(yàn)證者對簽名消息的非隨機(jī)性進(jìn)行驗(yàn)證。本文給出一個(gè)三參數(shù)的改進(jìn)簽名方案，在提高了安全度的情況下將指數(shù)運(yùn)算和模逆運(yùn)算改進(jìn)為最低值2次和0次，方案中使用Hash函數(shù)，可證明其正確性和安全性。改進(jìn)方案中使用了 Hash值的Hamming重量，以當(dāng)前普遍使用的Hash函數(shù)MD5為例，Hash值為128位二進(jìn)制數(shù)，而Hamming重量不大于128(7位二進(jìn)制數(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)簽名過程。

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

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

(3)驗(yàn)證過程。

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

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

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

③驗(yàn)證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)兩個(gè)方程有3個(gè)變量 α，k，x，無法求出其值。

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 復(fù)雜度比較

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

表1 3種方案簽名算法復(fù)雜度比較

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

3 結(jié)束語

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

［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ù)和因子分解具有消息恢復(fù)的簽名方案［J］.計(jì)算機(jī)應(yīng)用，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］.西北師范大學(xué)學(xué)報(bào):自然科學(xué)版，2006，42(3):109-110.

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

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

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

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