《一个门限代理签名方案的进一步改进.doc》由会员分享，可在线阅读，更多相关《一个门限代理签名方案的进一步改进.doc（15页珍藏版）》请在三一文库上搜索。
1、一个门限代理签名方案的进一步改进Further Improvement of a Threshold Proxy Signature Scheme XIE Qi1, YU Xiuyuan2,3 (1.School of Information & Engineering, Hangzhou Teachers College, Hangzhou Zhejiang 310036, China; 2.School of Science, Hangzhou Teachers College, Hangzhou Zhejiang 310036, China; 3.Dept. of Mathematics
2、 & Physics, Quzhou College, Quzhou Zhejiang 324000, China) Abstract:In 1999, Sun, et al presented a threshold proxy signature, which overcame weaknesses of the schemes proposed by Zhang and Kim, et al, respectively. Recently, Li, et al showed that Suns scheme cannt resist the public key substitution
3、 attack, and proposed an improved scheme. However, their improved scheme is still suffer from the public key substitution attack. Additional, a proxy relationship inversion attack on Lis scheme is proposed, it will provides more information in the design of secure proxy signature scheme. Finally, a
4、further improvement scheme is proposed to eliminate the weaknesses. Key words:Digital Signature; Proxy Signature; Threshold Proxy Signature 1 引言 1996年，Mambo等人1首次提出了代理签名的概念，一个代理签名方案允许原始签名人把自己的签名权交给指定的代理人（称为代理签名人），代理签名人能够代表原始签名人生成有效的代理签名。由于代理签名在信息化社会有很好的应用前景，所以代理签名一提出便进行了广泛的关注，并得到了深入的研究，提出了各种各样的代理签名体制
5、。但一个安全的代理签名必须满足不可伪造性、可验证性、不可否认性、可区分性等性质1。为体现原始签名者与代理签名者的公平性，Lee等人2提出代理签名还应该满足强不可伪造性、强可识别性、强不可否认性和阻止滥用性。 为防止滥用代理签名权，1997年Kim等人3和Zhang4分别提出了(t,n) 门限代理签名方案，原始签名人把代理签名密钥分割成n份并分发给n个代理签名人，它要求n个代理签名人中至少t个人的合作才能生成代表原始签名人的代理签名，但是小于t个则不行。Sun等人5指出他们的方案都是不安全的，并基于Zhang的方案提出了一个改进算法。Hsu等人6指出Sun的方案违背了门限代理的原则，他们的方案中
6、代理签名的产生不一定完全遵守规定门限值，并给出了一个改进方案；而李继国等人7指出Sun的方案无法抵抗替换公钥攻击，并给出了一个改进方案。 考虑到当代理签名发生争议时，仲裁者必须知道谁是代理签名的真正签名者，所以代理签名具有不可否认性是个十分重要的性质。1999年，Sun8提出了具有已知签名人的不可否认门限代理签名方案，Hsu等人9指出Sun 的方案无法抵抗合谋攻击并给出了一个改进方案。2004年，Yang等人10提出了一个效率优于Hsu的不可否认门限代理签名方案。2000年基于Kim的方案，Hwang等人11提出了一个不可否认门限代理签名方案，然而Hwang and Chen12给出的原始签名
7、人与一个代理签名人的合谋攻击方案表明他们的方案是不安全的，Tzeng等人13给出了一个更有效的攻击方案原始签名人的假冒攻击指出了文献11的缺陷，并给出了改进方案。 考虑到李继国等人7指出Sun的方案无法抵抗替换公钥攻击，并给出了抵抗替换公钥攻击的一般方法和一个改进方案，并称该改进方案能抵抗替换公钥攻击。然而，本文指出他们的方案依然无法抵抗替换公钥攻击，同时提出了代理关系转换攻击方法，成功地攻击了他们的方案。该攻击方法对设计安全的代理签名有重要的价值。本文提出的两种攻击方法同样能攻击Hsu等人6提出的改进方案；最后给出了门限代理签名的进一步改进方案。 2 文献7的门限代理签名方案简介 设p和q是
8、两个大素数，满足q|(p-1)，随机选取q阶生成元gZ*p；h(?)是单向抗碰撞Hash函数；PGID=EM,Time,Group记录代理人的身份，其中，EM表示代理密钥产生的标记包括参数t和n，Time表示代理签名的有效期限，Group表示原始签名人和代理签名人的身份信息。每个用户Pi的私钥为xiZ*q，公钥为yi=gxi mod p，并得到CA的认证。设P0是原始签名人，G=P1,P2,Pn是n个代理签名人。文献7的方案由代理密钥产生阶段、代理签名产生与验证三个阶段组成。 21 代理密钥产生阶段 (1)原始签名人随机选取RZq，计算并广播=gkmod p。 (2)每个PiG随机选取iRZq
9、，计算ri=gi mod p，使得riZ*p成立，然后广播ri。 (3)原始签名人计算r=ni=1ri，=n-1x0h(r,PGID,y0)+(mod q)，并广播。 (4)每个PiG计算r=ni=1ri，并通过下式检查的正确性：gs=yn-1h(r,PGID,y0)0 mod p 如果成立，每个PiG计算si=+i+xiyih(r,PGID,y0)(mod q)。 (5)每个PiG产生一个t-1阶的秘密多项式： fi(x)=si+a(i,1)x+a(i,t-1)xt-1 mod q 这里，a(i,1),a(i,t-1)是随机数。计算fj(i)（1i,jn，ij）给其他成员，计算并广播ga(u
10、,v)(1un,1vt-1)。每个Pi收到来自Pj的fj(i)（1i,jn，ij）后，通过下式验证fj(i)的正确性： gfj(i)=gsrjyjyjh(r,PGID,y0)-1(ga(j,1)i（ga(j,2)i2(ga(j,t-1)it-1mod p 如果成立，记f(x)=nj=1fj(x)mod q，则计算 xi=f(i)=ni=1si+a1i+at-1it-1 mod q 这里aj=ni=1a(i, j) mod p(j=1,t-1)。 22 代理签名的产生阶段 设D=P1,P2,Pt是t个代理签名人，他们想对消息m生成代表原始签名人的代理签名。他们共同合作执行以下步骤： (1)每个P
11、iD随机地产生一个t-1阶的秘密多项式： fi(x)=a(i,0)+a(i,1)x+a(i,t-1)xt-1 mod q 然后计算并广播fj(i)（1i，jn,ij）和ga(u,v)(1un,1vt-1)给其他成员。每个Pi收到来自Pj的fj(i)（1i， jn,ij）后，通过下式验证fj(i)的正确性： gfj(i)=ga(j,0)(ga(j,1)i(ga(j,2)i2(ga(j,t-1)it-1 mod p 如果成立，则计算： xi=f(i)=a0+a1i+at-1it-1 mod q 这里aj=ti=1a(i,j) mod p(j=0,1,t-1)。 (2)每个PiD计算K=ga0mod
12、 p和Ti=xih(m)+xiK(mod q)，然后把Ti广播给D中的其他代理签名人。当收到所有的Tj(ji)后，每个Pi通过下列方程来验证Tj(ji)的有效性: gTj=gnnk=1rknk=1yykh(r,PGID,y0)k-nnk=1(ga(k,1)jnk=1(ga(k,2)j2 nk=1(ga(k,t-1)jt-1h(m)tk=1ga(k,0)tk=1(ga(k,1)jtk=1(ga(k,2)j2 tk=1(ga(k,t-1)jt-1K mod p 记f?C(x)=tj=1fj(x) mod q f(x)=f(x)h(m)+f?C(x)K mod q (3)每个PiD能对Ti应用Lag
13、range 插值多项式计算： T=f(0)h(m)+f?C(0)K mod q 则(r,PGID,K,T)即为消息m的代理签名。 23 代理签名的验证阶段 验证者收到消息m的代理签名(r,PGID,K,T)后，利用下式来验证代理签名的正确性： gT=(y0ni=1yyii)h(r,PGID,y0)r)h(m)KK mod p 3 文献7的门限代理签名方案的密码学分析 31 攻击1：替换公钥攻击 下面给出原始签名人与某个代理人如Pi合作，利用替换公钥的方法假冒n个代理签名人对任意的消息产生一个有效的代理签名方案。设任取的消息为m，攻击方案如下： （1）由于Pi知道自己代理的子密钥 xi=f(i)
14、=nj=1sj+t-1j=1ajij mod q=x0h(r,PGID,y0)+(n+nj=1j)+h(r,PGID,y0)nj=1xjyj+t-1j=1ajij(mod q) 其中aj=ni=1a(i,j) mod p(j=1,t-1)。计算 =xi(h(r,PGID,y0)-1=x0+(n+nj=1j)(h(r,PGID,y0)-1+nj=1xjyj+t-1j=1ajij(h(r,PGID,y0)-1(mod q) 并把发送给原始签名人。 （2）原始签名人计算新的公钥 y0=y0(r(ga(j,1)i(ga(j,2)i2(ga(j,t-1)it-1)(h(r,PGID,y0)-1mod p
15、 并且按需要修改代理证书PGID为PGID。 （3）原始签名人任取aZ*q，计算r=gamod p。 （4）原始签名人任取bZ*q,计算K=gbmod p。 （5）原始签名人计算T=(h(r,PGID,y0)+a)h(m)+bK(mod q)，则(r,PGID,K,T)即为消息m的有效代理签名，因为代理签名的验证者能验证该代理签名的合法性： (y0ni=1yyii)h(r,PGID,y0)r)h(m)(K)K=(y0(r(ga(j,1)i(ga(j,2)i2 (ga(j,t-1)it-1)(h(r,PGID,y0)-1ni=1yyii)h(r,PGID,y0)r)h(m)(K)K= g(x0+
16、ni=1xiyi+(n+nj=1aj+t-1j=1ajij)(h(r,PGID,y0)-1)h(r,PGID,y0)+a)h(m)+bK= g(h(r,PGID,y0)+a)h(m)+bK=gTmod p 所以，攻击成功。 32 攻击2：代理关系转换攻击 下面给出n个代理签名人合作对任意的消息产生一个代理多重签名方案，验证者能够确信该代理签名是原始签名人P0代表n个代理签名人G=P1,P2,Pn产生的代理多重签名。设任取的消息为m，攻击方案如下： （1）n个代理签名人修改代理证书PGID为PGID，着重修改原始签名群和代理签名人的身份信息和代理关系，其他内容如签名文件的类型、代理时间等按需要修
17、改。 （2）任取bZ*q,计算K=gb mod p。 （3）任取aZ*q,计算r=ga mod p。 （4）计算s=ny0(h(r,PGID,y0)-1=x0y0+y0(h(r,PGID,y0)-1(mod q)。 （5）n个代理签名人中的任一成员如P1修改自己的公钥y1为y1=y1y0(h(r,PGID,y0)-1 mod p 然后，计算群公钥Y=y1y2y3yn mod p。 （6）G=P1,P2,Pn中的每个成员计算并广播Ti。 Ti=(sn-1+xi)h(r,PGID,Y)+an-1)h(m)+bKn-1(mod q) （7）计算T=ni=1Timod q，则(r,PGID,K,T)即
18、为消息m的、由n个代理签名人假冒原始签名人P0产生的、代表G=P1,P2,Pn的有效代理签名。因为代理签名的验证者能从PGID中明确代理关系，而且可以验证该代理签名的合法性： (yy00y1ni=2yi)h(r,PGID,Y)r)h(m)(K)K=(yy00y1y0(h(r,PGID,y0)-1ni=2yi)h(r,PGID,Y)r)h(m)(K)K=g(s+ni=1xi)h(r,PGID,Y)+a)h(m)+bK=gni=1Ti=gTmod p 以上两种攻击方案表明文献7的门限代理签名方案存在安全上的漏洞，这两种攻击方法同样能够攻击文献6的门限代理签名方案。 4 改进方案及其分析 41 改进
19、方案 改进方案的系统参数与文献7的门限代理签名方案相同，它由代理密钥产生阶段、代理签名产生与验证三个阶段组成。 411 代理密钥产生阶段 (1)原始签名人随机选取RZq，计算并广播=gkmod p。 (2)每个PiG随机选取iRZq，计算ri=gi mod p，使得riZ*p成立，然后广播ri。 (3)原始签名人计算r=ni=1ri，=x0y0h(r,PGID,y0,Y)+n(mod q)，然后用(t,n)VSS方案把分配给n个代理人。选取t-1阶的秘密多项式： f0(x)=+a01x+a0t-1xt-1 mod q 将c0i=ga0i mod p（i=1,2,t-1）公开，将s0i=f0(i
20、) mod q密送给每个PiG。 (4)每个PiG计算r=ni=1ri，并通过下式检查s0i的正确性： gs0i=yy0h(r,PGID,y0,Y)0nt-1j=1(c0j)ij mod p (5)每个PiG产生一个t-1阶的秘密多项式： fi(x)=i+xiYh(r,PGID,y0,Y)+a(i,1)x+a(i,t-1)xt-1 mod q 这里，a(i,1),a(i,t-1)是随机数。计算fj(i)(1i,jn,ij)给其他成员，计算并广播ga(u,v)(1un,1vt-1)。每个Pi收到来自Pj的fj(i)(1i,jn,ij)后，通过下式验证fj(i)的正确性： gfj(i)=rjyYh
21、(r,PGID,y0,Y)j-1(ga(j,1)i(ga(j,2)i2(ga(j,t-1)it-1 mod p 如果成立，记f(x)=nj=1fj(x)mod q，每个Pi 计算xi=f(i)，则f(0)=ni=1i+Yh(r,PGID,y0,Y)ni=1xi(mod q)。 412 代理签名的产生阶段 设D=P1,P2,Pt是t个代理签名人，他们想对消息m生成代表原始签名人的代理签名，并共同合作执行以下步骤： (1)每个PiD随机地产生一个t-1阶的秘密多项式： fi(x)=a(i,0)+a(i,1)x+a(i,t-1)xt-1mod q 然后计算并广播fj(i)(1i,jn,ij)和ga(
22、u,v)(1un,1vt-1)给其他成员。每个Pi收到来自Pj的fj(i)(1i,jn,ij)后，通过下式验证fj(i)的正确性： gfj(i)=ga(j,0)(ga(j,1)i(ga(j,2)i2(ga(j,t-1)it-1mod p 如果成立，则计算： xi=f(i)=a0+a1i+at-1it-1mod q 这里aj=ti=1a(i,j)mod p(j=0,1,t-1)。 (2)每个PiD计算K=ga0mod p和Ti=(s0i+xi)h(m,K,r,PGID,y0,Y)+xiK(mod q)，然后将Ti广播给D中的其他代理签名人。当收到所有的Tj(ji)后，每个Pi通过下列方程来验证T
23、j(ji)的有效性： gTj=(yy0h(r,PGID,y0,Y)0t-1j=1(c0j)ijrYYh(r,PGID,y0,Y)nk=1(ga(k,1)j nk=1(ga(k,2)j2nk=1(ga(k,t-1)jt-1)h(m,K,r,PGID,y0,Y)(tk=1ga(k,0) tk=1(ga(k,1)jtk=1(ga(k,2)j2tk=1(ga(k,t-1)jt-1)K mod p 记f(x)=tj=1fj(x)mod q f(x)=(f0(x)+f(x)h(m)+f(x)K mod q (3)每个PiD能对Ti应用Lagrange 插值多项式计算： T=(+f(0)h(m)+f(0)K
24、 mod q 则(r,PGID,K,T)即为消息m的代理签名。 413 代理签名的验证阶段 验证者收到消息m的代理签名(r,PGID,K,T)后，利用下式来验证代理签名的正确性： gT=(yy00YY)h(r,PGID,y0,Y)r)h(m,K,r,PGID,y0,Y)KK mod p 42 改进方案的安全性分析 下面讨论改进的方案能够抵抗我们提出的攻击方法和文献6中提出的攻击方法的攻击。 利用攻击1的方法进行攻击，原始签名人与某个代理人如Pi合作，则可以计算 =(xi+)(h(r,PGID,y0,Y)-1=(x0y0+nj=1xjY)+(n+nj=1j+t-1j=1ajij)(h(r,PGI
25、D,y0,Y)-1(mod q) 原始签名人计算新的公钥y0满足(y0)y0=yy00(r(ga(j,1)i(ga(j,2)i2(ga(j,t-1)it-1)(h(r,PGID,y0,Y)-1 mod p 是不可能的，除非他们能够解离散对数问题。 利用攻击2的方法进行攻击，n个代理签名人合作，其中某个代理人如P1需要修改公钥成y1，需满足(y1)y1=yy11(h(r,PGID,y0,Y)-1 mod p，这也是不可能的，除非他们能够解离散对数问题。另一方面，尽管原始签名人的公钥y0与n个代理签名人的公钥积Y在门限代理签名的验证方程中的表现形式似乎具有对称关系（yy00YY），但n个代理签名人无法修改代理证书PGID，所以验证者不会误认相互之间的代理关系。 由于我们提出的改进方案中结合了文献6中的改进方案，所以也能抵抗文献6中提出的代理签名的产生不一定完全遵守规定门限值的弱点。所以，我们提出的改进方案是安全的。 5 结论 本文对文献7提出的门限代理签名的改进方案进行了密码学分析，指出他们的方案依然无法抵抗替换公钥的攻击，同时提出了一种新的攻击方法代理关系转换攻击，成功地攻击了他们的方案。该攻击方法对设计安全的代理签名有重要价值，提出的两种攻击方法同样能攻击Hsu等人6提出的改进方案。最后给出了门限代理签名的进一步改进方案。