离散对数数字签名算法的改进

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

(宿迁学院二系，江苏 宿迁 223800)

0 引言

自1976年Diffie和Hellman提出数字签名［1］后，数字签名技术获得了长足的进展和极大的应用，数字签名方案一般基于一个或多个数学难题，常见的有基于因子分解的RSA签名方案［2］、基于离散对数的El-Gamal签名方案［3］、基于椭圆曲线的 ECDSA 方案［4］，有的是基于双难题的数字签名方案［5-6］，另外还有消息恢复签名［7］、代理签名［8］、盲签名［9］、群签名［10］等一系列应用。其中ElGamal数字签名方案［3］是重要的一种方案，但方案中有4次指数运算和1次模逆运算，运算量较大。研究者对ElGamal方案进行了各种推广和改进，对于ElGamal数字签名方案的改进有2种思路，第一种是在不降低其安全性的情况下，对指数运算和模逆运算进行改进减少其次数，从而降低复杂度，已有一系列的改进方案［11-12］;第二种是针对El-Gamal数字签名容易受到攻击的情况，在不改变其结构的情况下增加参数以增加安全性，已有一系列的改进方案［13-14］，但复杂度一般没有得到较好的改进。本文给出一种新的改进方案，通过增加一个参数以增加安全性，同时又降低了算法复杂度，与各种改进比较，效率更高。

1 已有离散对数数字签名方案

1.1 ElGamal数字签名方案［3］

(1)参数初始化。

(2)签名过程。

(3)验证过程。

接收者接收到m和(r，s)后，首先计算h(m)，验证yrrs=gh(m)mod p，正确则接受签名，否则拒绝签名。

1.2 曲娜方案［12］

对ElGamal方案中指数运算和模逆运算的最新改进为曲娜方案，方案中指数运算为3次，模逆运算为0次。方案如下:

(1)参数初始化。

(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］

李晓峰通过增加一个参数提高了攻击的难度，增加了安全性，但方案中指数运算高达6次，模逆运算为1次。方案如下:

(1)参数初始化。

参数同1.1节(1)。

(2)签名过程。

(3)验证过程。

接收者接收到 m 和(r，λ，δ)后，验证 gm=yrrλλδmod p，正确则接受签名，否则拒绝签名。

2 新的改进方案

基于公钥密码体制的数字签名方案因其良好的数学特性，很容易遭受攻击，为了抵抗伪造攻击，数字签名方案一般采取某种消息格式化机制，例如Hash函数或消息冗余，使验证者对签名消息的非随机性进行验证。本文给出一个三参数的改进签名方案，在提高了安全度的情况下将指数运算和模逆运算改进为最低值2次和0次，方案中使用Hash函数，可证明其正确性和安全性。改进方案中使用了 Hash值的Hamming重量，以当前普遍使用的Hash函数MD5为例，Hash值为128位二进制数，而Hamming重量不大于128(7位二进制数)。研究发现Hash值的Hamming重量对消息的变化很敏感，若消息变化，Hamming重量发生变化的概率为92%以上［15］。

2.1 算法描述

(1)参数初始化。

参数同1.1节(1)。且h()为安全Hash函数，ham()为求Hamming重量的函数，待签消息为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为求解离散对数问题。

(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发送的签名消息后，用另一消息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)抗替换随机数k的伪造签名攻击。

B接收到A发送的签名消息后，用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］与本文改进算法进行复杂度比较，结果见表1。

表1 3种方案签名算法复杂度比较

本文改进算法中指数运算达到了最低值2次，并且无求逆，虽然算法中增加了Hash函数运算，但h()长度远小于m长度，对应的指数运算要快得多，所以综合比较本文方案比曲娜方案、李晓峰方案速度要快得多。

3 结束语

本文给出了ElGamal数字签名方案及相关改进方案，提出了一种新的改进方案，证明了其正确性和安全性，与ElGamal方案相比增加了一个参数以提高安全性，同时模指数运算达到最低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］邵祖华.基于因数分解和离散对数的数字签名协议［J］.通信保密，1998(4):36-41.

［6］袁喜凤，孙艳蕊，孙金青，等.基于离散对数和因子分解具有消息恢复的签名方案［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数字签名算法的一种变形［J］.吉林大学学报:信息科学版，2009，27(6):590-594.

［13］曹素珍，左为平，张建.一种新的ElGamal数字签名方案［J］.网络安全技术与应用，2007(10):40-41.

［14］李晓峰，赵海，王家亮，等.基于增加一个随机数的El-Gamal数字签名算法的改进［J］.东北大学学报:自然科学版，2010，31(8):1102-1104.

［15］侯爱琴，高宝建，张万绪，等.基于椭圆曲线的一种高效率数字签名［J］.计算机应用与软件，2009，26(2):58-60.