一种共享验证门限的多代理多重签名方案

赵之洛,　缪祥华,　唐　鸣,　张　斌

(昆明理工大学 信息工程与自动化学院, 昆明 650500)



一种共享验证门限的多代理多重签名方案

赵之洛,缪祥华,唐鸣,张斌

(昆明理工大学 信息工程与自动化学院, 昆明 650500)

针对已有的共享可验证门限多代理多重签名方案不能抵抗合谋攻击及不真正具有共享验证的问题,基于大数分解的困难性(RSA)、离散对数问题(DLP)、单向哈希函数和(t,n)门限共享机制，提出了一种新的共享可验证的门限多代理多重签名方案。该方案中,任意t1个或更多的原始签名者可以将签名权委托给代理签名群;任意t2个或更多的代理签名者可以代表原始签名者依据授权进行代理签名;任意t3个或更多的指定验证者能够合作完成对代理签名有效性的验证。结果表明,该签名方案能够满足代理签名的安全性要求。

代理签名; 门限多代理多重签名; 共享验证; RSA; 单向哈希函数

0　引　言

1997年,Kim和Zhang等将(t,n)门限共享体制和代理签名相互结合,首次提出了门限代理签名方案[1-2]。在(t,n)门限代理签名方案中,不少于t个代理签名者能代表原始签名者签名,但在一般的门限代理签名方案中,最终签名的有效性验证均是采用单独的验证者来完成的,这是理想化的情况[1-6]。在多数实际情况下,是需要授权的验证人一起才能验证代理签名的有效性,例如电子商务中的电子投标和电子选举等[7-8]。

2004年,Tzeng等[9]提出了一个不可否认的可共享验证的多代理多重签名方案。随后,Bao等[10]指出Tzeng等的方案不能抵抗构造攻击,敌手可以在截获的一个有效的代理签名之后构造一个能够通过验证的伪造代理签名。2007年,Hsu等[11]又指出Tzeng等的方案不能抵抗合谋攻击,任何一个验证者都能在无需其他验证者帮助的情况下验证代理签名的有效性。2009年,Kang等[12]指出Hsu等的方案也容易受到内部攻击,并且文献[8-10]的方案不具有(t1,n1)门限性质。2011年,王志波等[13]针对Tzeng等的方案不能抵抗伪造攻击和不具有共享验证的性质,提出了一个基于离散对数的不可否认和可共享验证的多代理多重签名方案,但是该方案不能抵抗合谋攻击,在秘密份额生成阶段,每个原始签名者的秘密份额为f(IDi),每个UOi知道IDi的值,那么t1个或多于t1个内部恶意者合谋即可恢复出秘密多项式,并获得群密钥XO和秘密份额f(IDi),同理,代理群和验证群也会受到同样的攻击,每个群的私钥和每个用户的秘密份额都会泄露,从而每个恶意验证者都能在没有其他成员的帮助下完成签名验证,即不具有共享验证性,所以文献[13]的方案存在安全缺陷。

因此,针对已有方案的缺陷,综合已提出各种方案的研究成果,笔者提出一种新的可共享验证的门限多代理多重签名方案,该方案弥补已有方案的缺陷,可以抗合谋攻击和伪造攻击,满足门限代理签名的安全性要求[14-15]。

1　基本原理

1.1大整数分解难题

设N=pq,其中p、q是两个大素数。整数e和d满足ed≡1modφ(N),其中φ(N)=(p-1)(q-1),是欧拉函数,那么下面三种假设是计算不可行的:

(1)对N进行因式分解;

(2)已知C和e,求一个整数M使得Me≡CmodN;

(3)已知M和C,求一个整数d使得Cd≡MmodN。1.2离散对数难题

1.3单向哈希函数

一个单向哈希函数h(·)可以作用在任意长度的消息上,对于函数h(·),可以在一个确定的多项式时间内从x计算出y=h(x)。但是已知y=h(x)求x是计算不可行的。

单向哈希函数的弱抗碰撞是指:对于给定的x1,要找到一个x2满足h(x1)=h(x2)是计算上不可行的。

单向哈希函数的强抗碰撞是指:要找到一对不同的消息x1和x2,使得h(x1)=h(x2)是计算上不可行的。

1.4(t,n)门限共享机制

在(t,n)门限共享机制中,将一个密钥D按照一定的计算方式碎化,分配给n个不同的用户保管。t或者t个以上的用户一起合作可以恢复出密钥D,并且少于t个用户合作不能恢复出密钥D。(t,n)门限共享机制的过程可以用数学方式表达如下:

(1)选择一个大素数N,生成一个t-1次多项式:

f(x)=D+a1x+a2x2+…+ai-1xi-1modN,

(2)秘密份额分发过程:假设xi(i=1,2,…,t-1)代表n个不同用户,那么每个用户得到的秘密份额就是si=f(xi)modN。

(3)密钥恢复过程:需要t或t个以上的用户合作,才能通过拉格朗日插值公式将密钥D恢复出来:

2　多重签名过程

2.1系统初始化阶段

在签名系统中假设存在一个可信的秘密份额分发中心(Share Distribution Center, SDC),主要负责生成系统参数,秘密选取p=2p′+1和q=2q′+1为两个强素数,其中,p′和q′是两个大素数;N是p和q的乘积,即N=pq;r=2p′q′;E满足E和r互素(GCD(E,r)=1)且E≈1050;α是有限域GF(q)中的本原元;h(·)是一个单向哈希函数;Mw是委托证书,其中记录了所有原始签名者、代理签名者以及签名验证者的身份标志,参数(t1,n1)、(t2,n2)、(t3,n3)和有效的授权代理时间等;IDO表示实际参与的原始签名者的身份,IDP表示实际参与的代理签名者的身份。其中{p,q,p′,q′,α,r}保密,{N,E,h(·)}公开。

2.2秘密份额生成阶段

SDC执行以下步骤:

(3)SDC分别为GO、GP、GV生成构造t1-1、t2-1和t3-1次秘密多项式如下:

(3)每个UOi∈DO通过公开信道将δOi发送给指定秘书(Designated Clerk, DC)。

(4)当DC接受到所有的δOi后,验证下面的等式:

(1)

如果式(1)成立,则说明UOi∈DO是合法的原始签名者,δOi和kOi的值是合法的。如果不成立,DC要求原始签名者重新发送一个合法值。然后,DC计算δO:

(5)DC向GP公示(δO,Mw,K,IDO)。

当收到(δO,Mw,K,IDO)之后,每个UPi∈GP验证下面的等式:

(2)

如果式(2)成立,每个UPi∈GP计算δPi作为自己的代理签名密钥:

如果不成立,则拒绝接受此δO,并向原始签名人询问一个合法值。

2.4代理签名生成阶段

(3)当接收到这些SPj之后,DC需要验证其有效性,计算下面等式是否成立:

2.5共享验证阶段

(1)根据Mw、IDO、IDP,每个验证者UVi∈DV可以从CA处获得原始签名者和代理签名者的公钥。并且能够知道实际参与的原始签名者和实际参与的代理签名者。

(4)每个UVi∈DV可以通过下式验证消息M的代理签名的有效性:

3　正确性分析

定理1在代理授权份额生成阶段,每个代理签名人UPi∈DP可以通过验证:

来确定代理授权的有效性。

证明:

所以,

证毕。

定理2在代理签名验证阶段,签名验证人可以通过:

证明:

那么,

又因为,

αRdbtmodN，

所以,

VE=αERdbtmodN。

因此,

证毕。

4　安全性分析

该方案的安全性主要是基于RSA问题、单向哈希函数求逆难题以及(t,n)门限秘密分享方案的安全性。

4.1不可伪造性

4.2不可否认性和共享验证性

4.3密钥的依赖性

4.4私钥的安全性

5　结束语

基于RSA密码体制提出了一种新的可共享可验证的((t1,n1),(t2,n2),(t3,n3))门限多代理多重签名方案。该方案中的影子密钥作为秘密份额,其安全性受到RSA问题难解性的保护,内部恶意者合谋攻击也无法获得秘密多项式和群私钥。在授权份额和代理签名的生成过程中加入单向哈希函数,保证合法的授权和代理签名不被伪造。同时,任意t3个以上的验证者可以合作验证签名的有效性。该方案从根本上克服了已有方案的缺陷,并符合代理签名的安全性要求。

[1]KIM S, PARK S, WON D. Proxy signatures revisited[C]//Proceedings of the 1st International Conference. [S. 1.]: Springer, 1997: 223-232.

[2]ZHANG K. Threshold proxy signature schemes[C]//Proceedings of the 1st International Workshop. [S.l.]: Springer, 1998: 282-290.

[3]HWANG MINSHIANG, LUJUILIN, LIN IUONCHANG.A practical (t,n) threshold proxy signature scheme based on the RSA cryptosystem[J]. IEEE Transactions on Knowledge and Data Engineering, 2003, 15(6): 1552-1560.

[4]HSU C L, WU T S, WU T C.New nonrepudiable threshold proxy signature scheme with known signers[J]. The Journal of Systems and Software, 2001, 58(2): 119-124.

[5]王勇兵. 门限混合代理多重签名方案[J]. 计算机工程, 2012, 38(9): 131-133.

[6]周孟创. 秘密共享与代理签名及其应用研究[D]. 郑州: 解放军信息工程大学, 2012.

[7]覃征, 闫焱, 王立. 特殊签名及其在电子商务中的应用[J]. 计算机应用研究, 2003, 20(6): 1-3.

[8]王晓明, 符方伟. 指定验证人的(t,n)门限代理签名方案[J]. 软件学报, 2005, 16(6): 1190-1196.

[9]TZENG S F, YANG C Y, HWANG M S. A nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Future Generation Coputer Systens, 2004, 20(5): 887-893.

[10]BAO H, CAO Z, WANG S. Improvement on tong et als nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Applied Mathematics and Computation, 2005, 169(2): 1419-1430.

[11]CHIENLUNG HSU, KUOYU TSAI, PEILING TSAI. Cryptanalysis and improvement of nonrepudiable threshold multi-proxy multi-signature schemewith shared verification[J]. Information Sciences, 2007, 177(2): 543-549.

[12]BAOYUAN KANG, COLIN BOYD, ED DAWSON. A novel nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J]. Computers and Electrical Engineering, 2009, 35(1): 9-17.

[13]王志波, 李雄, 杜萍. 共享可验证的不可否认门限多代理多重签名方案[J]. 计算机工程与应用, 2011, 47(9): 93-127.

[14]SAMAMEH MASHHADI. Analysis of frame attack on hsu et al’s non-repudiable threshold[J]. Scientia Iranica, 2012, 19(3): 674-679.

[15]刘幼萍, 吴铤, 王辉. 强不可伪造的代理多签名方案[J]. 计算机应用, 2012, 32(S1): 68-73.

(编辑李德根)

A shared verification threshold multi-proxy multi-signature scheme

ZHAOZhiluo,MIAOXianghua,TANGMing,ZHANGBin

(College of Information Engineering & Automation, Kunming University of Science & Technology, Kunming 650500, China)

This paper features a novel shared verification threshold multi-proxy multi-signature scheme as an alternative to existing shared verification threshold multi-proxy multi-signature scheme which suffers from its inability to resist collusion attack and its actual absence of the property of shared verification. This scheme draws on the difficulty in factorizing large integer(RSA), discrete logarithm problem(DLP), the one-way Hash function, and the (t,n) threshold secret sharing scheme. The scheme is unique in that anyt1or more of original signers can delegate the signing capability to the proxy group; anyt2or more of proxy signers can sign a message on behalf of the original group for a specified verifier group; and anyt3or more of verifiers can perform a joint verification of the validity of the proxy signature from the proxy group. The analysis shows that the scheme can fulfill the security requirements of proxy signature.

proxy signature; threshold multi-proxy multi-signature scheme; shared verification; RSA; one-way hash function

2013-11-21

云南省科技厅社发项目(2011CA019)

赵之洛(1988-),男,江苏省东台人,硕士,研究方向:信息安全理论与技术及代理数字签名,E-mail:zeki2008@163.com。

10.3969/j.issn.2095-7262.2014.03.020

TP309

2095-7262(2014)03-0317-06

A