对一种改进的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数字签名的改进问题。