《一个改进的前向安全的多重签名方案.doc》由会员分享,可在线阅读,更多相关《一个改进的前向安全的多重签名方案.doc(14页珍藏版)》请在三一文库上搜索。
1、一个改进的前向安全的多重签名方案doi:10.3969/j.issn.1001-3695.2009.06.038 Improved forward secure multi-signature scheme XIA Xiang-sheng1,2,HONG Fan1,CUI Guo-hua1 (1.Dept. of Information Security, College of Computer Science, Huazhong University of Science & Technology, Wuhan 430074, China; 2.Dept.of Computer, Wuhan
2、 Polytechnic University, Wuhan 430023, China) Abstract:This paper gave security analysis of the multisignature schemesLuo et al.s forward-secure multisignature scheme based on ElGamal type.The scheme didnt meet property of forward security whilesome signers key was compromised.LUOs scheme couldt res
3、ist forge attack.And finally,proposed the new improved scheme,analysed its security.The scheme can effectively resist forge attack and coordinate attacks.Its a safe,efficient,practical and forward secure multisignature scheme. Key words:forward security; multisignature; forgery attack; security anal
4、ysis 在现实生活中,有时需要多个人合作签署同一份消息,由此导致了多重签名的产生。多重签名的概念最早是由Itakura等人1提出的,Ohta等人2将多重签名体制分为有序多重签名和广播多重签名,Hardjono等人3提出了基于离散对数困难性假设的多重数字签名。人们对多重签名的研究十分关注,目前已经提出若干多重数字签名方案14。然而,当签名人的签名密钥泄露后,这些方案均不能提供任何保护,之前所产生的多重签名将变成无效。如何减少由于密钥泄露所带来的对系统安全的影响,一直是人们十分关注的研究课题。1997年,Anderson5首次提出了前向安全的概念,前向安全就是将整个有效时间分成若干个周期,在每个
5、周期内使用不同的签名密钥产生签名,而验证签名的公钥在整个有效时间内不变,即使当前周期的签名密钥被泄露,也不影响此周期之前签名的有效性,从而大大减少了由于密钥泄露所带来的对系统安全的影响。文献6首次将前向安全概念引入多重数字签名体制,之后将前向安全机制引入数字签名方案成为研究热点和研究者关注的课题79。罗丽平等人10提出了一个具有前向安全的ElGamal型多重数字签名方案,他们声称该方案不仅具有前向安全性,而且比文献6所提方案计算代价小、简单、实用。本文对罗方案的前向安全的有序多重签名方案进行了安全性分析。 1 罗的前向安全的有序多重签名方案的安全性分析 1.1 罗的前向安全的有序多重签名方案
6、1)系统初始化 签名中心(SC)首先选择一个p,g是GF(p)的生成元,SC选择安全的单向函数H和时间周期T,然后为每个签名人ui选择不同的SKi0(0,p),计算Yi=gSK2T+1i0 mod p(1in)作为验证公钥。ui(1in)选择一对整数ei,di作为公钥和私钥,满足gcd(ei,(p)=1且eidi=1 mod(p-1)将ei发给SC,SC计算SKi=SKeii0 mod p,并将SKi通过安全信道送给ui,ui用私钥di解密得到SKi0=SKdi,SC公布PK=p,g,T,H,Yi,i1,n。 2)密钥的更新 在周期j的开始,每个签名人ui根据前一周期j-1的密钥SKij-1利
7、用SKij=SK2ij-1 mod p-1计算此周期的密钥SKij,将周期号由j-1更新为j,并删除SKij-1。 3)前向安全的有序多重数字签名 在周期j,设有n个签名人按签名顺序u1,u2,un签署同一份信息m,t为SC发送签名的时间标志,要求ui在给定的时间ti内完成签名,SC广播(m,t,ti,i=1,2,n),有序签名操作如下: a)u1收到信息m后,随机选取k1j1,p-1,并计算r1j=gk1jmod p,s1j=H(m,t)SK2T+1-j1j-r1jk1j mod(p-1),将签名消息(m,(s1j,r1j)发给下一位签名人u2并将r1j发给SC。b)每一位签名人ui(i2)
8、收到(m,(si-1j,ri-1j)后,先验证签名的有效性。首先计算ti=ti+t,若(m,(si-1,j,ri-1j)在ti之后到达,则向SC发送一个超时信息,表示对m的签名失败;否则继续验证式(1)是否成立。 gSi-1jrri-1ji-1j=YH(m,t)i mod p(1) 若式(1)不成立,则认为ui-1的签名无效,要求ui-1重发消息签名;否则ui继续执行协议,随机选取kij1,p-1,并计算:rij=gkijmod p,sij=si-1j+H(m,t)SK2T+1-jij-rijkij mod (p-1), 将签名消息(m,(sij,rij))发给下一位签名人ui+1并将rij发
9、给SC。当第n个签名人un的签名完成后,形成的有序多重数字签名消息为(m,(snj,rnj),并将rnj发给SC。 4)前向安全的有序多重数字签名的验证 签名中心首先计算tn=tn+t,若un的消息(m,(snj,rnj)在tn之后到达,则认为签名无效;否则验证式(2)是否成立。 gsnjni=1rrijij=(ni=1Yi)H(m,t) mod p(2) 1.2 罗的前向安全的有序多重签名方案安全性分析 1)验证式(1)是错误的 证明 当i=2时,由s1j=H(m,t)SK2T+1-j1j-r1jk1j mod(p-1)显然有gs1jrr1j1j=(gSK2T+1-j1j)H(m,t)=(g
10、SK2T+110)H(m,t)=YH(m,t)1 mod pYH(m,t)2 mod p。故当i=2时,gsi-1jrri-1ji-1jYH(m,t)i mod p,即验证式(1)是错误的。验证式(1)应改为 gsi-1ji-1h=1rrhjhj=(i-1h=1Yh)H(m,t) mod p(1) 下面用数学归纳法证明改动是正确的。 证明 对i(i2)使用数学归纳法。 a)当i=2时结论显然成立; b)假定当i=(3)时结论成立,即有 gs-1j?乏?-1h=1rrhjhj=(?乏?-1h=1Yh)H(m,t) mod p 那么当i=+1时,因为 sj=s-1j+H(m,t)SK2T+1-jj
11、-rjkj mod(p-1) 所以,gsj?乏?h=1rrhjhj=gs-1j(gSK2T+1-jj)H(m,t)g-rjkj?乏?h=1rrhjhj=gs-1j(gSK2T+1-j0)H(m,t)r-rjjh=1rrhjhj=gs-1jYH(m,t)r-rjj (rrjj ?乏?-1h=1rrhjhj)=(gs-1j?乏?h=1rrhjhj)YH(m,t)=(?乏?-1h=1Yh)YH(m,t)=(?乏?-1h=1Yh)H(m,t) mod p 综合式(1)(2),所以验证式(1)应改为 gsi-1ji-1h=1rrhjhj=(i-1h=1Yh)H(m,t) mod p 2)存在伪造攻击 罗
12、的方案即使验证式(1)改为验证式(1):gsi-1ji-1h=1rrhjhj=(i-1h=1Yh)H(m,t) mod p,仍然存在伪造攻击。若某签名人ui(1in)在第j周期的签名密钥SKij泄露后,则签名人ui-1能够伪造ui任意周期(1jT)的签名,从而使该方案不具有前向安全性质。证明如下: 证明 令a=SK2T+1-jij,因为签名人ui在第j周期的签名密钥SKij已泄露,故对签名人ui-1来说a是可计算的。另一方面,SK2T+1-jij=SK2T+1i0,所以有结论a=SK2T+1i0。在周期,签名人ui-1按正常签名顺序计算出自己的签名(m,(si-1,ri-1),显然ui之前的签
13、名能够通过验证式(1),即有gsi-1i-1h=1 rrhh=(i-1h=1Yh)H(m,t) mod p,ui-1尽管不知道签名人ui在周期的签名密钥SKi,但ui-1仍可计算SK2T+1-i,因为SK2T+1-i=SK2T+1i0=a。ui-1伪造ui的签名(m,(si,ri)过程如下: ui-1随机选取ki1,p-1,并计算: ri=gkimod p(3) si =si-1+aH(m,t)-riki mod (p-1)(4) ui-1将签名消息(m,(si,ri)发给下一位签名人ui+1并将ri发给SC。因为: gsiih=1 rrhh=gsi-1gaH(m,t)g-kiriih=1rr
14、hh= gsi-1(gSK2T+1-i)H(m,t)r-riiih=1rrhh=gsi-1(gSK2T+1i0)H(m,t)i-1h=1rrhh(gsi-1 i-1h=1rrhh)YH(m,t)i=(i-1h=1YhH(m,t)YH(m,t)i=(ih=1Yh)H(m,t) mod p 所以,gsiih=1rrhh=(ih=1Yh)H(m,t) mod p,即(m,(si,ri)能通过验证式(1)。因此,签名人ui-1伪造ui的签名(m,(si,ri)能够通过签名人ui+1的验证。又签名人ui+1到签名人un按既定协议完成签名,显然签名人un在周期的签名(m,(si,ri)能够通过验证式(2)
15、,即式gsnni=1 riir=(ni=1Yi)H(m,t) mod p 的验证。所以签名人ui-1的伪造攻击成功。 2 改进的前向安全的多重签名方案 2.1 系统初始化 签名中心(SC)首先选择安全的大素数p1、p2、p1、p2、q,且满足p1p23 mod 4,选择p=p1p2=(2qp1+1)(2qp2+1)和一个阶为q的gQRp(即gq=1 mod p),SC选择安全的单向函数h和时间周期T;然后为每个签名人ui选择不同的SKi0(0,q),计算Yi=SK-2T+1i0 mod p(1in)作为验证公钥。SC随机选择参数K1,p,选择一对整数e、d作为公钥和私钥,并满足gcd(e,(p
16、)=1,ed=1 mod (p)。其中(p)=(p1-1)(p2-1)为欧拉函数。公开参数p、q、g、h、T、Yi(1in)、e、K,保密SKi0(1in),d。 2.2 密钥更新 在周期j的开始,每个签名人ui根据前一周期j-1的密钥SKij-1利用SKij=SK2ij-1 mod p计算此周期的密钥SKij,将周期号由j-1更新为j,并删除SKij-1。 2.3 前向安全的有序多重数字签名 在周期j,设有n个签名人按签名顺序u1,u2,un签署同一份信息m,t为SC发送签名的时间标志,要求ui在给定的时间ti内完成签名,SC广播(m,t,ti,i=1,2,n),有序签名操作如下: a)u1
17、收到m后,随机选取k1j,w1j(0,q,并计算R1j=gk1j2T+1-jmod p,Z1j=SK1jgw1jmod p,u=h(mjtK),S1j=k1j-w1ju mod q,将签名信息(R1j,Z1j,S1j)传给签名人u2。 b)每一位签名人ui(i2)收到(Ri-1j,Zi-1j,Si-1j)后,先验证签名的有效性。首先计算ti=ti+t,若(Ri-1j,Zi-1j,Si-1j)在ti之后到达,则向SC发送一个超时信息,表示对m的签名失败;否则计算u=h(mjtK),并验证式(5)是否成立。 Ri-1j=gSi-1j2T+1-j(Z2T+1-ji-1ji-1h=1Yh)u mod
18、p(5) 若式(5)不成立,则认为ui-1的签名无效,要求ui-1重发消息签名,否则ui继续执行协议,随机选取kij,wij(0,q),计算 Rij=Ri-1jgkij2T+1-jmod p(6) Zij=Zi-1jSKijgwij mod p(7) Sij=Si-1j+kij-wiju mod q(8) 将签名信息(Rij,Zij,Sij)传给签名人ui+1。当第n个签名人un的签名完成后,形成的有序多重数字签名消息为(Rnj,Znj,Snj),并将(Rnj,Znj,Snj)发给SC。SC首先计算tn=tn+t,若(Rnj,Znj,Snj)在tn之后到达,则向un发送一个超时信息,表示对m的
19、签名失败,请求un重发消息(Rnj,Znj,Snj);否则计算u=h(mjtK),并验证式(9)是否成立。 Rnj=gSnj2T+1-j(Z2T+1-jnjnh=1Yh)u mod p(9) 若式(9)成立,令Z=Zdnj,S=Snjd,U=h(mjtZRnjK),则前向安全的有序多重签名为j,(m,S,Z,U,t);否则SC要求un重发签名消息(Rnj,Znj,Snj)。 2.4 前向安全的有序多重数字签名的验证 签名验证人收到j,(m,S,Z,U,t)后,计算 u=h(mjtK),Y=nh=1Yh mod p R=geS2T+1-j(Ze2T+1-jY)u mod p(10) 验证式(11
20、)是否成立。 U=h(jmtRZK)(11) 如式(11)成立,则多重签名有效;否则多重签名无效。 3 改进方案的正确性证明 定理1 若式(5)成立,则ui-1(i2)的签名(Ri-1j,Zi-1j,Si-1j)是有效的。 证明 对i(i2)使用数学归纳法。 a)当i=2时结论显然成立。 b)假定当i=(N,3)结论成立,即有 R-1j=gS-1j2T+1-j(Z2T+1-j-1j?乏?-1h=1Yh)u mod p 那么,当i=+1时,根据式(6)(8)有 Rj=R-1jgkj2T+1-j= gS-1j2T+1-j(Z2T+1-j-1j?乏?-1h=1Yh)u gkj2T+1-j= g(S-
21、1j+kj)2T+1-j( Z-1jSKj)2T+1-j SK-2T+1-jj?乏?-1h=1Yh)u= g(S-1j+kj)2T+1-j( Z-1jSKj)2T+1-j 所以,当i=+1时,结论也成立。 综上所述,若式(5)成立,则ui-1(i2)的签名(Ri-1j,Zi-1j,Si-1j)是有效的。如果un的签名(Rnj,Znj,Snj)是有效的,由定理1的结论则式(9)显然成立。 定理2 j,(m,S,Z,U,t)是有效的前向安全的多重数字签名。 证明 由已知,则需要证明式(11)成立。 由式(9)(10)有 R=geS2T+1-j(Ze2T+1-jY)u mod p=gedSnj2T+
22、1-j(Zed2T+1-jnjnh=1Yh)u mod p=gSnj2T+1-j(Z2T+1-jnjnh=1Yh)u mod p=Rnj 所以,U=h(jmtRnjZK)=h(jmtRZK)。j,(m,S,Z,U,t)是有效的前向安全的多重数字签名。 4 改进方案的安全性分析 1)改进方案具有前向安全的特性 本方案的前向安全性是基于强RSA假定9和模合数平方剩余难题。当p为合数时,企图通过SKij=SK2i-1j mod p求SKi-1j是一个困难问题。因此,即使攻击者已获得签名人ui当前周期j的签名密钥SKij,他也无法求出ui当前周期j之前的签名密钥SKik(kj),新方案具有前向安全的特
23、性。 2)改进方案能够抵抗伪造攻击 假定知道(j,m,Rnj,Z,t,Yi(i=1,2,n),攻击者企图通过验证式(见式(9)(10)Rnj=R=geS2T+1-j(Ze2T+1-jY)u mod p求S,这相当于求解离散对数问题。若假定他已知(j,m,S,Rnj,t,Yi(i=1,2,n),通过上式求Z,他必须至少求出e-1(mod (p)。其中:(p)为欧拉函数,在大合数p分解未知的情况下,求解e-1(mod (p)是一个十分困难的问题。如果攻击者企图伪造部分多重签名,使得全体多重签名通过验证式,那么本方案要对部分签名验证,所以伪造的部分签名无法通过式(5)和(9)的验证。如果攻击者在已知
24、部分参数的情况下通过式(5)和(9)求解某些参数,以达到伪造部分签名的目的,这也是不可能的。因此,本方案能抵制伪造攻击。 3)改进方案能够抵抗内部攻击 如果攻击者是不诚实的内部签名人ui-1,他向ui或SC提供伪造的签名,ui或SC可以通过验证式(5)或(9)发现ui-1欺诈行为,并要求ui-1的签名,因此,本方案能抵抗内部攻击。如果ui-1通过伪造签名有意延误时间,则SC能够根据ui提供的失败信息进行分析并及时处理。 4)改进方案能够抵抗联合攻击 如果攻击者是不诚实的部分内部签名人集合,企图联合伪造签名实施攻击,则无法通过验证式(5)或(9)。因此,本方案能抵抗联合攻击。 5)改进方案能够抵
25、抗重播攻击 在本方案中引入了时间标志,每次都要对时间进行验证,所以能够抵抗重播攻击。 5 改进方案的性能分析 与王晓明等人所提出的文献6相比,本方案也引入了预计算,在每个周期开始时,签名人可以预先计算g2T+1-j;在每次签名前,可以预先计算gkij2T+1-jmod p和SKijgwij mod p。文献7经过两轮循环才完成有序多重签名,第一轮计算每个签名人的Rij和Zij(包括最后一个签名人的Rlj和Zlj);第二轮将Rlj和Zlj广播给每个签名人以便每个签名人能计算u=h(jmRljZljt),进而计算出Sij。本文在保证安全性质不变的前提下改进了文献6的签名过程,只用一轮循环完成签名,大大提高了签名的效率,且签名的验证过程比文献6简单方便。改进方案也比罗的方案简洁、高效,可进行类似分析。此处不再赘述。 6 结束语 在多重签名过程中,如何减少由于签名者签名密钥泄露所造成的损失是一个亟待解决的问题,但是目前所提出的方案大多数不具有真的前向安全性质。本文给出的新方案在强RSA假定、模合数平方剩余等难解问题假设下是安全有效的。对罗的前向安全的广播多重签名方案可采用类似的方法进行分析与改进。
链接地址:https://www.31doc.com/p-1591609.html