王春玲，武淑敏

(西安工程大学计算机科学学院，陕西西安710048)

密钥可更新的ElGamal有序多重数字签名方案

王春玲，武淑敏

(西安工程大学计算机科学学院，陕西西安710048)

分析了Li和Yang提出的基于ElGamal的有序多重数字签名方案，发现该方案无法抵抗内部成员的伪造攻击.因此提出了一个密钥可更新的ElGamal有序多重数字签名方案.通过使用可信秘密分发中心SDC为各个签名者分发密钥的方法，解决原方案中无法抵抗内部成员攻击的漏洞.同时方案还添加了密钥更新算法，不仅提高了安全性，而且实用性更广.

ElGamal数字签名;有序多重数字签名;内部攻击;密钥更新

0 引言

多重数字签名技术用于同一文档需经过多人签名才能生效的情形，在日常生活工作中具有广泛的应用.多重数字签名主要分为有序多重数字签名(Sequential Multi-Digital Signature)和广播多重数字签名(Broadcasting Multi-Digital Signature).有序多重数字签名是按照一定顺序将电子文件依次发送给签名者进行签名，最后由验证者验证签名的正确性.

自从1983年Itakura和Nakamura提出了第一个多重数字签名方案［1］以后，各种多重数字签名算法相继提出，同时基于ElGamal型的数字签名方案的研究和应用也越来越广泛.Harn和Xu提出了一种ElGamal型数字签名，并根据这种签名方案设计了一种多重数字签名方案［2］，但该方案不能用于有序多重数字签名;1999年李子辰、杨义先设计出一种基于ElGamal型有序和广播多重数字签名［3］，后续的学者们对于ElGamal方案的优化改进也是层出不穷［4-7］.本文在分析研究了Li和Yang的ElGamal有序多重数字签名方案的基础上，根据秘密分发机制，提出了一个密钥可更新的有序多重数字签名算法.该方案不仅提高了安全性，而且具有更广泛的实用性.

1 Li方案的描述

该方案是根据ElGamal签名方案设计的一个有序多重签名方案，包括系统初始化阶段，签名产生阶段，签名验证阶段等3个阶段.

1.1 系统初始化

US为消息发送者，UV为签名验证者，U1，U2，…，Un为消息签名者，选取一个大的素数p，G是GF(p)的本原元，H(.)是一个单向的哈希函数.每个签名者Ui随机选取自己的私钥xi，计算yi=gxi(modp)作为自己的公钥，然后公开p，g，h.

1.2 签名产生阶段

UI确定签名顺序后将要签名的消息发送给第一个签名者U1，U1收到m后，随机选取k1∈［1，p-1］，计算r1=gk1modp，S1=H(m)x1-r1k1modφ(p);将(m，(r1，s1))发送给下一个签名者，将ri发送给后续的每一个签名者.签名者Ui(i≥2)收到(m，(ri-1，si-1))，对其进行验证，验证通过后进行如下操作：

随机选取ki∈［1，p-1］，计算ri=gkimodp，Si=Si-1+H(m)xi-rikimodφ(p);然后将(m，(ri，si))发送给下一个签名者，将ri发送给后续的gk1每一个签名者.

1.3 签名验证阶段

2 原方案漏洞分析

该方案具有内部成员伪造攻击的漏洞，因为在签名验证阶段，系统没有验证每个签名者的公钥，则存在以下可能：不诚实签名者可以随意公布一个假的公钥yi′，然后伪造一个假的签名从而达到破坏多重签名的目的.假设不诚实签名者U′企图伪造合法签名者Ui-1对消息m的签名(m，(ri-1，si-1))，他按如下步骤即可完成伪造签名：

3 新的ElGamal多重数字签名方案

基于以上分析，提出改进方案，在系统初始化阶段，通过采用可信秘密分发中心SDC给每个签名者分发密钥的方法，去掉了原方案中签名者可以随机选取自己私钥的过程，从而能够克服内部成员伪造攻击的漏洞，提高了安全性.同时方案还添加了密钥更新算法和时间戳机制，具有更广的实用价值.

3.1 系统初始化

本方案涉及可信秘密分发中心，消息发送者，消息签名者和签名验证者三方，设US为消息发送者，UV为签名验证者，U1，U2，…，Un为消息签名者，SDC为可信秘密分发中心，初始化过程如下：设p是一个素数，p=mq+1，其中q也是素数，m是整数，g是Zp中阶为q的元素.

步骤一：SDC选择Zq上的k-1次多项式f(x)=a0+a1x+…ak-1xk-1，公开ga0，ga1，…，gak-1，秘密地将xi=f(i)(modq)传送给每个签名者Ui，Ui根据式(1)来验证所收到的密钥xi是否正确：

如果正确，则将xi作为自己的私钥，然后计算yi=gxi(modp)作为公钥.

3.2 签名过程

消息发送者US预先设计签名顺序为(U1，U2，…，Un)，并且确定要发送的消息m，计算H(m，T)，然后将这种签名顺序和时间标志T发送到每一个签名者Ui和验证者UV;要求Ui在给定时间t内完成签名.

步骤一：U1收到需要签名的消息后，随机选取k1∈［1，p-1］，按式(2)计算

然后将签名消息(m，(r1，S1))发送给下一个签名者U2，将k1发送给后续的签名者和验证者.

步骤二：U2收到U1的签名消息后，首先计算T′=T+Δt，如果U1的签名消息在T′之前到达，则按式(3)验证签名的正确性，否则拒绝接受签名.

如果式(3)成立，则U1的签名正确，U2按步骤三继续签名;否则拒绝对消息签名，签名失败.

步骤三：U2随机选取k2∈［1，p-1］，按式(4)计算

然后将签名消息(m，(r2，S2))发送给下一个签名者U3，将r2发送给后续的签名者和验证者，以此类推.

步骤四：签名者Ui(2＜i＜n)传递消息m的部分签名(ri，Si)给Ui+1后，Ui+1首先计算

T′=T+Δt*i，如果签名消息在T′之前到达，则按式(5)验证部分签名的正确性

如果等式成立，则签名正确，Ui+1继续对m进行签名，签名如下：ri+1=gki+1modp.

3.3 验证过程

验证者UV收到最后一个签名者发来的签名(rn，Sn)后，同样计算T′=T+nΔt.若签名结果在T′之前到达，则按式(7)验证，

如果等式成立，则说明签名正确，否则签名失败.

3.4 密钥更新过程

如果某个签名者Ui的密钥xi被盗或者丢失，则向可信秘密分发中心SDC请求密钥的重发，SDC按照如下过程对所有签名者的密钥进行更新.

(1)SDC随机选择Zq中的k-1个随机数δ1，δ2，…，δk-1，定义多项式：δ(x)=δ1x+δ2x2+…δk-1xk-1，并计算εi=gδi(modp)，i=1，2，…，k-1;Δxi=δ(i)，将xi发给对应的每个签名者Ui;

(2)Ui收到xi后，根据式(3)验证xi是否正确：

若xi满足上式，则接收到的xi正确.

(3)Ui按下式更新自己的密钥.并销毁xi.

4 新方案的分析

4.1 外部攻击

该方案是基于离散对数问题的，即每一位签名者都有自己的私钥xi和公钥yi=gxi，外部攻击者要想伪造签名者Ui对消息m的签名，就必须知道签名者Ui的私钥xi和签名者选择的随机数ki，而从公钥yi求解签名者的私钥xi相当于求解离散对数难题;而且在签名过程中，ri=gkimodp，攻击者欲从公开的ri求出随机数ki也相当于求解离散对数问题.

外部攻击者要想伪造最终的签名(rn，Sn)，并通过Uc的验证，就必须知道每个签名者的私钥xi，而每个签名者的私钥xi是可信秘密分发中心SDC惟一分配的，外部攻击者欲从公开的ga0，ga1，…，gak-1获取a0，a1，…，ak-1等同于求解离散对数难题，所以攻击不成功.

4.2 内部攻击

该方案在原方案的基础上加入了密钥分发机制，使得每个签名者的私钥不再由签名者随机选取，而是由可信秘密分发中心SDC分配，而且每个签名者可以根据式(1)验证SDC分发给自己的私钥，从而避免了Li方案的内部成员之间攻击，提高了方案的安全性.

假设某个不诚实的签名者Ui想伪造签名者Ut对消息m的签名，他可以随机选择kt，计算rt=gkt，但是他不能获得签名者Ut的私钥xt.假设他自己随机选择xt，然后计算伪造签名st，由式(4)可知，st是不能通过st+1的验证的，因为随机选择的私钥xt不能满足已知的签名者Ut的公钥，使得yt=gxt.同理，部分签名者(ui，ui+1，…，ut)合谋伪造前i-1个签名者的签名，通过最终的验证者的验证也是行不通的.

4.3 性能分析

该方案虽然抵抗了内部成员之间的攻击，提高了算法的安全性，但是和原方案比较起来，也有不足之处.首先，新方案增加了系统开销，因为在系统初始化时，原方案是每个签名者随机选取自己的私钥，而新方案SDC则需要计算每个签名者的私钥xi，并且要通过安全信道传送给每个签名者，所以增加了方案的通信量.

5 结束语

多重数字签名在电子合同、文件签署、遗嘱签署、电子商务和网络安全等方面有着广泛的应用前景.本文在学习了ElGamal有序多重数字签名的基础上提出了一种密钥可更新的ElGamal有序多重数字签名方案，不仅解决了原方案的内部成员伪造攻击的漏洞，而且在签名成员密钥丢失的情况下可以重新进行密钥分配，大大提高了签名的安全性和实用性，同时方案还引入了hash函数和时间戳机制，有效地提高了签名效率.

［1］ITAKURA K，NAKAMURA K.A public-key cryptosystem suitable for digital multisigature［J］.NEC Research＆Development，1983，71：1-8.

［2］L Harn.New digital signature scheme based on discrete logarithm［J］.Electronics Letters，1994，30(5)：396-398.

［3］李子辰，杨义先.ElGamal多重数字签名方案［J］.北京邮电大学学报，1999，22(2)：30-34.

［4］卢建朱，陈火炎，林飞.ELGamal型多重数字签名算法及其安全性［J］.计算机研究与发展，1999，37(11)：1335-1339.

［5］鞠宏伟，李凤银.基于ElGamal的多重数字签名方案［J］.山东科学，2005，18(3A)：69-72.

［6］柳毅，郝彦君.基于ElGamal密码体制的可验证秘密共享方案［J］.计算机科学，2010，37(3)：80-82.

［7］李佳佳，谢冬，沈忠华.基于变形的ElGamal的(t，n)门限秘密共享方案［J］.杭州师范大学学报，2013(2)：135-139.

［8］许春香，魏仕民，肖国镇.定期更新防欺诈的秘密共享方案［J］.计算机学报，2002，25：657-660.

(School of Computer Science，Xi'an Polytechnic University，Xi'an 710048，China)

A key renewable ElGamal sequential multi-digital signature scheme

WANG Chun-ling，WU Shu-min

Li and Yang's sequential multi-digital signature scheme is analyzed based on ElGamal，which couldn' t resist the masquerading attack of internal members.So a key renewable ElGamal sequential multi-digital signature scheme is presented，which can solve the problem in the original scheme by using the method of trusted SDC (Secret Distribution Center)distribute keys for each signer.Morever，a key update algorithm is added to the secheme，so it is highly secure and practical.

ElGamal digital signature;sequential multi-digital signature;internal attack;key-update

TP 393

A

1674-649X(2014)01-0102-04

编辑、校对：武晖

2013-06-08

王春玲(1968-)，女，陕西省西安市人，西安工程大学副教授，主要从事网络信息安全等方面的研究.E-mail： wangcl1968@yahoo.com.cn