ElGamal数字签名方案的安全性分析及改进

曹 烨

(沈阳理工大学 信息科学与工程学院，辽宁 沈阳 110159)

ElGamal数字签名方案的安全性分析及改进

曹 烨

(沈阳理工大学 信息科学与工程学院，辽宁 沈阳 110159)

分析了ElGamal算法用于数字签名中存在的安全性问题，并在传统算法基础上提出一种改进方案，在基于计算离散对数困难性的前提下，通过与原签名方案的比较，改进后的数字签名算法在安全性和计算效率上均有提高。

公钥密码体制；数字签名；ElGamal算法；离散对数；生成元

公钥密码学的诞生之所以被称为密码学发展史上最重要的一次革命，其贡献在于算法中使用了一对完全不同的密钥，这样的算法机制为数字签名技术的研究和应用提供了理论基础。在各种基于公钥密码体制的数字签名方案中，签名方通常先使用某种散列算法计算出明文消息的散列值，然后用自己的私钥对该值进行加密生成签名，验证方则使用签名方的公钥对接收的信息进行完整性检验，保证其来源的可靠[1]。但由于公钥密码设计的原理都是基于各种复杂的数学函数，计算上的复杂性导致其在签名和验证过程中的运算速度较慢，执行效率不高。因此，本文对传统ElGamal数字签名算法做出适当改进和优化，使得改进后的签名方案在安全性和计算效率上均有提高。

1 传统ElGamal数字签名方案安全性分析

ElGamal算法是1984年由Taher.Elgamal提出的一种公钥密码体制算法，该算法的安全性是建立在有限域中计算离散对数的困难性之上，ElGamal算法主要是为实现数字签名目的而设计的[2]。

1.1 传统算法描述

为了便于与改进签名方案进行比较，首先列出传统签名算法。

1)产生密钥对：

(1)签名双方共同选择一个大素数p，p的大小应该满足在Zp中计算离散对数不可行。其中Zp为小于p的所有非负整数集合，即Zp={0,1,2,……,p-1}；

(3)随机产生正整数x，满足1

(4)计算y=gxmodp，则签名方的密钥对为公钥KU={p,g,y}，私钥KR={x}。

2)签名过程：签名方使用自己的私钥x对消息M进行签名。

(1)签名方使用单向散列函数H计算明文M的散列值m=H(M)，满足m∈Zp；

(2)随机选择整数K，满足1≤K≤p-1且gcd(K,p-1)=1；

(3)计算；S1=gKmodp;

(4)计算K在模(p-1)下的乘法逆元K-1≡1mod(p-1)；

(5)利用扩展的欧几里德算法从m=(x·S1+K·S2)mod(p-1)求出S2，即

S2=K-1(m-x·S1)mod(p-1)

(6)签名结果为S=(S1,S2)。

3)验证过程：验证方使用签名方的公钥{p,g,y}对收到的信息进行核实。

(1)计算V1=gmmodp；

(2)计算V2=yS1(S1)S2modp；

(3)如果V1=V2，则认为签名正确，反之拒绝签名[3]。

1.2 传统算法安全性分析

2)即使不利用随机整数K，攻击者在获取少量信息的情况下也可以破解算法。假设攻击者截获了签名方发送给验证方对于消息M的一个有效签名(S1,S2)，在满足a∈Z且a≤p-2，b∈Z且b≤p-2，c∈Z且c≥0，同时gcd(S1·c-S2·b,p-1)条件下，攻击者通过如下计算可以得到对消息M1的一个有效签名，攻击演示如下所述。

令(S1·c-S2·b)-1≡1mod(p-1)

j=S2·i·(S1·c-S2·b)-1mod(p-1)

有H(M1)=i·(c·H(M)+a·S2)(S1·c-S2·b)-1mod(p-1)

∵yi·ii≡gH(M1)modp

∴攻击者在不知道私钥x和随机整数K的情况下计算出的数据对(i,j)即是消息M1的一个有效签名。

3)ElGamal算法中的随机整数K不论是用于加密/解密、还是用于数字签名中，都必须保证其唯一性。也就是说，加密/解密时由于信息是以分块的形式进行操作，故必须为每个分块选择唯一的随机整数K，否则如果用同一K对多个分块进行加密/解密，则攻击者只要知道其中一个明文分块，就可以计算出其他明文分块，进而破解密码系统。同理，一个K也不能用在两次数字签名中，否则攻击者可以利用条件伪造攻击的方式获取私钥x，从而破译算法。假设使用同一随机参数K对消息M1和M2进行数字签名，结果分别为(S，S1)和(S，S2)，攻击演示如下所述。

yS·SS1≡gH(M1)modp

(1)

yS·SS2≡gH(M2)modp

(2)

(3)

代入式(1)整理得gH(M2)-H(M1)≡SS2-S1modp

(4)

由于签名公式S=gKmodp，则式(4)等价于式(5)：

gH(M2)-H(M1)≡gK(S2-S1)mod(p-1)

(5)

由式(5)进一步可得H(M2)-H(M1)≡K(S2-S1)mod(p-1)

(6)

令t=gcd(S2-S1,p-1)，

∵t|(S2-S1)且t|(p-1)

∴有t|(H(M2)-H(M1))成立。

(7)

(8)

(9)

将式(6)、(7)、(8)代入式(9)，则同余式变形为

x′≡K·S′modp′

(10)

最后将这t个可能的K值代入签名公式S=gKmodp中进行验证，就能找到唯一正确的K值，至此系统被破解[5-6]。

2 改进ElGamal数字签名方案描述

由于传统算法在签名阶段需要事先进行模逆运算即K-1≡1mod(p-1)，而该运算通常需要利用扩展的欧几里德算法实现，该算法的计算复杂度相当于大指数运算，在计算机中执行速度较慢，效率较低。故本文在改进方案的签名阶段使用随机函数rand( )生成参数d取代模逆运算，具体实现过程描述如下。

1)设置系统参数

(1)p：大素数，可公开；

(3)x：用户的私钥，满足1

(4)y：用户的公钥，有y=gxmodp；

(5)H：安全散列函数。

在硬件环境为Intel Pentium(R)Core(TM)i3 CPU 2.53GHz、1.92GB内存、512M显卡，使用Microsoft Windows XP Professional Service Pack3操作系统，以VisualC++6.0为编程工具进行系统仿真。设置系统参数如图1所示。

图1 设置系统参数

2)签名算法

(1)计算消息M的散列值m，使m=H(M)，满足m∈Zp；

(2)利用随机函数rand()产生两个整数K和d，满足1≤K≤p-1且gcd(K,p-1)=1，1≤d≤p-1且gcd(d,p-1)=1，Kd≠0mod(p-1)；

(3)计算S1=gKmodp；

(4)计算S2=(m-xS1)·dmod(p-1)；

(5)计算n=Kdmod(p-1)；

(6)签名方将S=(S1,S2,n)作为生成的数字签名发送给验证方。

对存储在F盘根目录下的文件“测试文件1.txt”进行签名测试，系统仿真如图2所示。

图2 签名算法

3)验证算法

(1)采用同样的安全散列函数计算消息M的散列值m=H(M)；

(3)计算v1=mtmod(p-1)；

(4)计算v2=S1tmod(p-1)；

(5)计算v=gv1y-v2modp；

(6)判断v=S1，如果等式成立则签名合法，否则不接受该数字签名。

图3 验证签名成功

图4 验证签名失败

为了检测验证算法的正确性，还是以“测试文件1.txt”为例，首先在不同的路径下建立两个文件名相同，但文件内容不同的“测试文件1.txt”，其中路径为“F：曹烨测试文件1.txt”的文件是与图1中完全一样的正确文件，而另一个路径为“E：测试文件1.txt”的文件则用来模拟文件受到攻击后被伪造和篡改的情况——为了掩人耳目，攻击者修改了截获文件的内容但没有修改文件名。对两个不同文件的系统仿真验证结果如图3和图4所示。

3 改进方案性能分析

3.1 正确性验证

v=gv1y-v2modp

={(gv1modP)[(gxmodp)-v2modp]}modp，(y=gxmodp)

=[(gv1modp)(g-xv2modp)]mpdp

=g[t·(m-xS1)]mod(p-1)modp

=gKmodp

∵S1=gKmodp

∴当v=S1时，该签名算法正确。

3.2 效率分析

在改进后的方案中，签名阶段避免了复杂的模逆运算，不用再求随机参数K的乘法逆元，只需进行一次简单的模运算n=Kdmod(p-1)；验证阶段虽然比原算法多了两个中间参数V1和V2的计算，但其也都是简单的模运算，与原方案中需要用扩展的欧几里德算法实现的模逆运算相比，后者的计算复杂度相当于大指数运算，远高于前者的模运算。具体分析如下：

1)先不考虑单次模运算的计算复杂度，分析单次利用扩展的欧几里德算法求模逆过程中，所需的模运算次数与输入数据x和y之间的关系。假设x∈Z且x≥1，y∈Z且y≥1，满足x>y，构造数列{Ln}:L0=x,L1=y,…,Lk=Lk-2modLk-1(k≥2)。显然，若运算中需要进行n次模运算，则有Ln=gcd(x,y),Ln+1=0。比较斐波那契数列{Fn}:F0=0,F1=1,…,Fn+2=Fn+Fn+1(n≥0)和数列{Ln}有：Ln≥F0=0,Ln-1≥F1=1。

3)由于在实际ElGamal签名算法中所使用的都是512bit或1024bit的大整数，所以上述算法的时间复杂度显然大于单次模运算的时间复杂度。因此，改进后的签名方案比原方案的计算速度快，运行效率高。

3.3 安全性分析

对ElGamal数字签名方案进行攻击，最有效、最快捷的方法是获取签名方的私钥x，但由于私钥都是签名方唯一知道他人无法获得，故安全性分析是在假定攻击者无法得到私钥x的情况下对改进签名方案进行破解，通过验证公式

进行分析，检测其安全性。

2)已知签名参数S2和n，求解S1。虽然已知g和p，但由于随机参数K不可知，故无法通过求解离散对数得到S1。另外由验证公式可以看出，公式左边有S1，右边y的指数幂中也有S1，目前对于这类等式还没有好的计算方法。

3)已知签名参数S1和S2，求解n。由于两个随机秘密参数K和d均不可知，故无法利用离散对数求出n。即使已知n可以求解出K·d的乘积，由于1≤K≤p-1且gcd(K,p-1)=1，1≤d≤p-1且gcd(d,p-1)=1，故要分别得到K和d，必须进行大整数的因式分解，才能得到所有满足条件的(K,d)对，同时为了保证K和d在本次签名中的唯一性，还需要采用穷举法逐一排除所有不符合要求的(K,d)对，这会大大增加计算工作量和计算时间。

通过以上分析可以看出，改进签名方案中随机参数的加入增加了攻击者破解系统的难度和时间，所以改进方案比原签名方案的安全性有所提高[7]。

4 结论

改进方案在签名阶段增加了一个随机参数d用以取代原方案中复杂的模逆运算，目的是提高签名效率，因此从减少签名和验证阶段的运算量、加快计算速度方面来说，希望d的取值越小越好，但由于每次签名时用户都要随机选取d值且不能重复使用，而在利用随机函数rand()产生d时不一定每次都能得到满意的取值，另外，d值过小时会减小攻击者破译私钥x的难度，降低签名方案的安全性，所以签名方必须认真考量产生随机参数d的函数和d的取值大小。

[1]胡向东，魏琴芳，胡蓉.应用密码学[M].(第2版).北京：电子工业出版社，2011：20-26.

[2]Bruce Schneier.应用密码学协议、算法与C源程序[M].(第2版).吴世忠等译.北京：机械工业出版社，2012：23-24.

[3]余姜德，商林，于志平.ElGamal加密体制在软件保护技术中的应用[J].计算机与现代化，2005，(5)：87-88.

[4]曹素珍，左为平，张建.一种新的ElGamal数字签名方案[J].网络安全技术与应用，2007，38(4)：40-41.

[5]王庆梅，吴克力，刘凤玉.具有消息认证功能的多重数字签名方案[J].计算机工程，2003，29(19)：14-16.

[6]焦阳，傅德胜.基于ElGamal的有序多重数字签名方案[OL/DB].http：//d.wanfangdata.com.cn/Periodical_scdxxb201304017.aspx.

[7]夏峰，冯建平，张瑜.一类ElGamal数字签名方案的安全性分析[J].科学技术与工程，2010，10(22)：88-90.

(责任编辑：马金发)

Security Analysis and Improvement of ElGamal Digital Signature Scheme

CAO Ye

(Shenyang Ligong University,Shenyang 110159,China)

Some security problems of ElGamal algorithm in digital signature are analyzed.And an improved scheme is put forword based on the traditional algorithm.The security and computing efficiency of improved digital signature algorithm is increased in comparison with original signature scheme.This conclusion is based on the difficulty of computing discrete logarithm.

public key cryptosystem;digital signature;ElGamal algorithm;discrete logarithm;generator

2014-09-25

曹烨(1978—)，女，工程师，研究方向：数据库理论与信息系统，信息安全。

1003-1251(2015)03-0032-05

TP309.7

A