门限签名

2024-08-16

门限签名（共6篇）

门限签名篇1

0引言

数字签名是实现认证的主要技术手段之一,是密码学的重要研究内容。门限签名方案是一种特殊的数字签名方案,是由Desmedt 和Frankel[1]提出的。它让n个成员共享群体密钥,当参与签名的成员数大于或等于t时,就能代表群体产生签名,任何验证者都可以用群公钥验证签名的有效性。

1994年台湾学者提出了合谋攻击问题[2],当群中t个或更多成员合谋,可以获取其他成员的私钥,因而可以任意伪造另外一组成员的有效签名。1998年,Wang[3]等提出了两个新的能够抵抗合谋攻击的门限签名方案。文献[4]指出文献[3]是不可抵抗合谋攻击的。文献[5,6]中分别提出了一个门限签名方案,并声称新方案可以抵抗共谋攻击。通过对方案进行安全性分析,我们发现这两个方案都存在安全漏洞,并针对每个方案分别提出了一种伪造攻击方式。通过伪造攻击,任何人都可以对任意消息生成能通过验证的有效签名。从而说明这两个方案不仅不能抵抗合谋攻击,连最基本的不可伪造性都不具备。

1文献[5]方案

IDC代表一个可信的身份代码分配中心,DC为签名合成者。

1.1建立阶段

(1) IDC选择两个大素数p, q,且q|p-1,g为GF(p)中阶为q的元素;选择单向Hash函数H(x);再选择一个t-1次的多项式f(x)=a0+a1x+…+at-1xt-1(modq),其中ai∈[1,q-1],对于i=1,2,…,t-1。IDC计算Y=gf(0)modp。

(2) 成员Pi(i=1,2,…,n)随机选择li∈[1,q-1],计算xi=glimodp,然后保密li,将xi秘密地送给IDC。

(3) IDC随机地选取zi∈[1,q-1],计算idi=gziximodp(注意idi要两两不同),yi=gf(idi)modp,ui=(xizi+f(idi))modq,然后IDC将{idi,yi,ui}发送给成员Pi,其中idi为成员Pi身份代码,yi、ui分别为Pi的公开密钥和秘密密钥,IDC公开{H(x),p,q,g,Y},保密zi。

1.2签名

对一个消息m,任意t个成员组成的小组按如下过程对m签名(为简化符号,不妨设参加签名的t个成员为P1,P2,…,Pt)。

(1) 部分签名任一组内成Pi随机选择ki∈[1,q-1],计算:

ri=gkimod $p s_{i} = g^{\frac{k_{i} Η (m) - u_{i} h_{i}}{2}} m o d p$

其中 $h_{i} = \prod_{j = 1, j \neq i} \frac{- i d_{j}}{i d_{i} - i d_{j}} m o d q$ ,然后Pi把{i,di,yi,ri,si}发送给签名合成者DC。

(2) 部分签名的验证及门限签名的生成

DC收到这t个成员的部分签名后,对各成员验证下式是否成立:(idiyi)hisi2 = riH(m)modp。若成立,DC再计算: $R = \prod_{i = 1}^{t} r_{i} m o d p ‚ S = \prod_{i = 1}^{t} s_{i} m o d p ‚ Ι D = \prod_{i = 1}^{t} i d_{i}^{h_{i}} m o d p ‚ g (x) = \prod_{i = 1}^{t} (x - i d_{i}) m o d p$ 。

DC将对消息m的签名(ID,g(x),R,S)发送给签名验证者。

1.3签名的验证

签名验证者验证下式是否成立:ID·Y·S2=RH(m)modp。若成立,则说明此签名为真。另外当事后发生纠纷时,可借助IDC判断式g(idi)≡0modp是否成立,找出idi,再由idi与x的对应关系可查出参加这次签名的具体成员。

2对文献[5]方案的伪造攻击

对于任意的消息M,任何人都可以按下面步骤生成有效签名:

(1) 选择随机数S∈[1,p-1],计算T=(Y·S2)-1modp;

(2) 选择随机数R∈[1,p-1],计算ID=T·RH(M)modp;

(3) 可以随便选择一个t次多项式作为g(x),或用以前从DC那里得到的DC生成的对其它消息签名中的g(x)。

(ID,g(x),R,S)就是伪造的对M的门限签名。

伪造方案的正确性:

ID·Y·S2=(T·RH(M))·Y·S2=(Y·S2)-1RH(M)·Y·S2=RH(M)modp

3文献[6]方案

3.1初始化阶段

(1) IDC选择两个大素数p, q,且q|p-1,g为GF(p)中阶为q的元素;选择单向Hash函数H(x);再选择一个t-1次的多项式f(x)=a0+a1x+…+at-1xt-1(modq),其中ai∈[1,q-1]对于i=1,2,…,t-1。

(2) IDC计算Y=gf(0)modp;选择xi∈[1,q-1],i=1,2,…,n,计算ui=gximodp(注意这里ui要两两不同),yi=gf(ui)mod $p ‚ z_{i} = (x_{i} + f (u_{i})) m o d q ‚ F (x) = \prod_{i = 1}^{t} (x - i d_{i}) m o d q$ 。

IDC保密xi,公开{H(x),p,q,g,Y},将{ui,yi,zi}发送给成员Pi(i=1,2,…,n),并且将f(x)和F(x)发送给DC。这里的ui为Pi的身份代码。

3.2签名

(1) 若t个成员构成的小组B同意对某个消息m进行签名,则每个成员Pi∈B(i=1,2,…, t)首先将自己的身份代码ui发送给DC。

(2) DC收到ui后,验证下式是否成立来判断Pi是否为一个合法的成员:F(ui)=0modq。当DC验证了t个ui有效后,然后计算 $g (x) = \prod_{u_{i} \in B} (x - u_{i}) m o d q$ 并在组内广播g(x)。

(3) Pi通过验证下式是否成立可以确定自己的身份是否已被DC合法登记:

g(ui)=0modq;然后Pi随机选择ki∈[1,q-1],计算:

ri=gkimodp Gi(0)=-(uig′(ui))-1g(0)modq

si=(ziGi(0)+kiH(m))modq

其中g′(x)为g(x)的导函数。Pi保密Gi(0),将个人签名{ui,yi,ri,si}发送给DC。

(4) DC计算Gi(0),验证下式是否成立来判定Pi签名是否有效:gsi=((uiyi)Gi(0)r $_{i}^{Η (m)}$ )modp;然后DC计算 $R = \prod_{i = 1}^{t} r_{i} m o d p ‚ S = \sum_{i = 1}^{t} s_{i} m o d q ‚ U = \prod_{i = 1}^{t} u_{i}^{G_{i} (0)} m o d p$ 。

{R,S,U,g(x),m}即为对m的门限群签名。

3.3签名的验证

验证者验证下式是否成立:gS=YURH(m)modp。若成立,则说明签名为真。另外当事后发生纠纷时,DC可以通过判断式g(ui)≡0modq是否成立,找出签名者的具体身份。

4对文献[6]方案的伪造攻击

对于任意的消息M,任何人都可以按下面步骤生成有效签名:

(1)选择随机数S∈[1,q-1],计算T=gSmodp;

(2)选择随机数R∈[1,p-1],计算L=(YRH(M))-1modp,计算U=T·Lmodp;

(3)可以随便选择一个t次多项式作为g(x),或用以前从DC那里得到的DC生成的对其它消息签名中的g(x)。

{R,S,U,g(x),M}就是伪造的对M的门限签名。

伪造方案的正确性:

gS=YgS(YRH(M))-1RH(M)=YT·LRH(M)=YURH(M)modp

5结束语

门限签名是数字签名研究的热点领域,有着广泛的应用前景。本文在对门限签名研究的基础上,针对文献[5,6]提出的两个门限签名的漏洞,分别提出了一种行之有效的伪造方案。考虑到进一步的研究工作,希望同行在设计新的门限签名时有效避免此类攻击。

摘要：为克服合谋攻击,文献[5,6]通过引入成员身份代码参数分别设计了一个门限签名方案。通过对这两个方案进行分析,针对其漏洞提出了一个伪造攻击方法。任何人对于任意消息都可用该攻击方式产生有效签名,从而说明其方案是不安全的。该伪造攻击的提出,为新的门限签名方案的设计提供了有效借鉴。

关键词：门限签名,合谋攻击,伪造攻击

参考文献

[1]Desmedt Y,Frnkel Y.Shared Generation of Authenticators and Signa-tures[C]//Proc.of Advances in Cryptology-CRYPTO’91.Berlin,Germany:Springer,1992:457-469.

[2]Li Chuanming,Hwang T,Lee N Y.Remark on the Threshold RSA Signature Scheme[C]//Proc.of Advances in Cryptology-CRYPRO’93.Berlin,Germany:Springer,1994:413-420.

[3]Wang C T,Lin C H,Chang C C.Threshold signature schemes with traceable signers in group communications[J].Computer communica-tions,1998,21(8):771-776.

[4]Kne J Jan,Tseng YM,Chien H Y.A threshold signature scheme with-standing the conspiracy attack[J].Communications of institute of in formation and Computing Machinery,1999,2(3):31-38.

[5]黄梅娟,张建中.一个安全有效的门限签名方案[J].计算机工程与应用,2005,41(36):125-126.

[6]黄梅娟,张建中.一种安全的门限群签名方案[J].计算机应用研究,2006,23(6):116-117.

基于椭圆曲线的门限数字签名研究篇2

关键词：门限签名,认证,可信中心

0前言

随着网络的迅速发展和普遍使用,网络信息安全已成为国家安全的战略性问题。WebGIS是以网络为基础的GIS技术,因此如何保证WebGIS的信息安全是WebGIS应用的一个重要技术问题。

基于椭圆曲线(ECC)的门限密码数字签名体制是近年信息安全领域中的研究热点之一。它主要是利用椭圆曲线上有理点组成的代数系统中离散对数问题的难解性来实现对非法入侵的防卫,从而达到信息安全。它的安全性不仅依赖于ECC的选取和它的体制,而且也依赖于ECC上的有理点组成的代数系统中离散对数问题的难解性,这与有限域上的离散对数或整数分解问题的情形不同。目前对ECC已知最好的离散对数算法需要指数时间,这就意味着ECC实现密码算法可以用较小的数来达到使用更大的有限域所获得的安全性。另一方面,ECC密码体制比RSA等有限域的公钥体制要快得多,这无疑提高ECC密码体制的吸引力[1]。随着大整数分解和并行处理技术的发展,当前采用的公钥体制必须进一步加长密钥,这将使其速度更慢、实现更复杂,而ECC则可用较小的开销(所需的计算量、存储量、带宽等)实现较高的安全性。预期能够在WebGIS,电子商务、电子政务等重要信息的加密存储及加密传输,以及决策者的数字签名与验证中提供很好的应用。

本文首先对秘密共享与群体密码学及相关知识进行概述,在此基础上对几种典型的基于椭圆曲线的门限数字签名机制进行深入研究,并对它们的有效性及安全性进行系统分析。

1 秘密共享与群体密码学概述

秘密共享[2,3]是由A.Shamir和G.R.Blakley于1979年各自独立提出的一个重要的密码学概念,在密钥管理、多方安全计算、密钥托管等方面有重要作用。所谓秘密共享,是指将一个秘密S以某种方式划分成若干个子秘密S1,S2,…,Sn,这n个子等密称作秘密S的部分份额(Share),分别由n个参与者P1,P2…,Pn掌管,参与者集合P={P1,P2,…,Pn}的某些指定子集可以通过出示其掌握的子秘密重构秘密S;而P的其他任何子集都不能得到秘密S的任何有用信息。对于一个秘密共享方案,参与者集合P的可重构秘密的所有子集的集合称作该方案的“访问结构(access structure)”,P的其他子集(即这些子集不可重构秘密,也不能得到有关秘密的任何有用信息)的集合称作该方案的“禁止结构(forbidden structure)”[4]。对一个具有n个参与者的秘密共享方案,如果其访问结构为其参与者集合P的所有元素大于等于t(1≤t≤n)的子集的全体,即任何大于或等于t个子秘密拥有者可重构秘密S,而任何小于或等于t-1个子秘密拥有者不能得到秘密S的任何信息,则称秘密共享方案为(t,n)门限方案,它是门限密码学中最简单、常用的秘密共享方案。

群体密码学[5]由Desmedt于1987年提出,是面向社团或群体的密码体制。在群体密码中,群体外的人可以使用群体的唯一群公钥,向群体发送加密信息,而只有群体中的某些子集成员合作才能解密这些信息。同样,群体密码学中也有群体签名问题,群体外的用户只需知道群体的唯一公开密钥就可以验证该签名。门限数字签名是群体密码学的一个重要分支,特别适用电子政务的某些安全要求。其方法是将一个群体的签名密钥颁发给群体中的每个成员,使得任何成员个数大于或等于门限值的子集可以产生签名;而任何成员个数小于门限值的子集都无法产生签名。

2 基于ECC的EIGamal数字签名方案

2.1 ECC的基本知识

给定任一有限域Fq,q为大素数,定义了Fq上的ECC,在密码学中使用的是曲线上的整数离散点,所有这些整数点都包含在某一个区域内部,区域越大,曲线的安全性越高;区域越小,计算速度越快,但安全性降低。

以有限域F(p)上的ECC:y2=x3+ax+b为例,p和q是两个大素数,P是ECC上的基点,其阶数为q。p、q、ECC和P都是公开的,Zq为有限域。

2.2 基于ECC的ElGamal数字签名方案

ElGamal签名体制由T.ElGamal在1985年提出[6],其修正形式已被美国NIST作为数字签名标准(DSS)。设待签名的消息为m,用户A、B分别为签名者和验证者,其数字签名方案如下:

(1)密钥产生。

用户A产生密钥对,①随机选取密钥d,d∈Zq。②计算点Q=d×P。③A的公钥是(ECC,P,q,Q),私钥为d。

(2)签名产生。

用户A对消息m进行签名,①随机选取整数k,k∈[1,q-1]。②计算k×P=(x,y),令r=x(mod q),若r=0,则转步骤①。③计算s=dr+kh(m)(modq),若s=0,则转步骤①。④(r,s)为用户A对消息m的数字签名。

(3)签名验证。

用户B验证用户A的数字签名(r,s),①获得A的公钥(ECC、P、q、Q),验证r和s都是区间[1,q-1]上的整数。②计算(x',y,)=s×h(m)-1P-rh(m)-1 Q。③若x'=r(mod q),则接受签名;否则拒绝。

3 基于ECC的门限数字签名方案

建立在ECC上门限数字签名方案[7],密钥需要n个参与者一起秘密生成。设D表示秘密处理者,G={P1,...,Pn}表示签名者群体,此门限签名由密钥产生协议和签名发布协议组成。密钥产生协议由D执行。在签名发布协议里,若签名者子集T是G的子集,并且T中包含t或t个以上诚实的签名者,则能够发布签名(r,s)。而任何小于等于(t-1)个不诚实的签名者不能伪造有效签名。

3.1 密钥产生协议

D产生随机整数d(1≤d≤q-1)作为签名者群体G共享的密钥,公钥为Q=dG。D按密钥共享方案将密钥d分割成多种组合,d的每种组合都与包含t个不同的签名者子集相对应。

3.2 签名发布协议

(1)从G中选择t个签名者P1,P2,…,Pt,设这t个签名者根据对应的组合各自决定使用的影子分别为d1,…,dt,有。

(2)每个签名者Pi(1≤i≤t)计算并广播Qi=tiP。

(3)每个签名者Pi(1≤i≤t)产生一随机数ki(1≤ki≤q-1),计算并广播Ri=kiP。

(4)每个签名者Pi(l≤i≤t)计算(每个Pi计算出来的(x,y)值都相同)。

(5)每个签名者Pi(1≤i≤t)计算r=x(mod q),si=dir+kih(m)(mod q),并广播si。

(6)对于1≤j(≠i)≤t,每个签名者Pi(1≤i≤t)验证Rj=sj h(m)-1P-r(m)-1Qj是否成立。如果不成立,则拒绝Pj并停止。

(7)每个签名者Pi(i∈S)计算,然后输出(r,s)作为签名者群体的数字签名。

3.3 签名协议的有效性分析

设,对上述协议的数字签名(r,s)分析如下:

(1)由第(5)步可得r=x(mod q);由第(4)步、第(5)步可得。所以x是点kP的x坐标。

(2)由于h(m))(由第(5)步)=dr+kh(m)(由第(1)步)。所以,s=dr+kh(m)(mod q)。

可见,上述签名协议产生的签名(r,s)同基于ECC的ElGamal数字签名方案生成的签名形式完全相同,签名(r,s)的验证也同基于ECC的ElGamal签名验证的方法相同,因此本方案是有效的。

4 基于ECC的可验证门限签名方案

基于ECC的可验证(t,n)门限签名方案包含两个过程[1],秘密共享过程和门限签名过程。秘密共享过程利用可信中心的可验证秘密共享方案,门限签名以ElGamal签名为基础,并设有一名非签名的群服务员A,负责收集和验证签名成员的签名,把消息m和最终的签名(r,s)发送给接收方。令P1,P2,…,Pn为n个秘密共享者。

4.1 基于ECC的可验证门限签名机制

可验证签名过程如下:

第(1)步由签名者Pi1,Pi2,…,Pit对消息m进行门限签名,B={i1 i2,…,it}。同时对每位签名者Pi(i∈B)计算ei,B=ai,B ti,Qi=ei,BP,其中,并向群服务员A公开Qi其中

第(2)步每位签名者Pi(i∈B)任选一随机数ki≤ki≤q-1),计算Ri=kiP并向B中的成员公开Ri。并计算。

第(3)步,每位签名者Pi(i∈B)计算r=x-h(m)(modq),si=ei,Br+ki(modq),并把(r,si)发送给服务员A。

第(4)步,群服务员A对所有的j∈B验证Rj=sjP-rQj。若成立,计算,然后把消息m连同群签名(r,s)发送给接收方。若不成立,拒绝Pi,并停止。

4.2 可验证签名协议的有效性分析

由上述门限签名过程的第(2)步知,又由第(3)步知r=x-h(m)(nod q)显然成立。

另一方面,

(由拉格朗日公式知)。即上述签名(r,s)满足r=x-h(m)(mod g)和s=dr+k(mod q)。其中x满足(x,y)=kP,d是系统密钥(公钥Q=dP),。

4.3 安全性分析

我们对上述可验证签名方案的安全性进行了以下几方面的分析:

(1)成员身份和子密钥分发的验证

为了保证签名成员身份的正确性,防止伪造签名。在签名过程中,群服务员A负责收集和验证签名成员的签名,由签名的第(4)步可知,如果有伪造签名者Pj(j∈B),验证Rj=sjP-rQj不成立,则计算签名也不成立,拒绝Pj的签名,这样保证了成员身份的正确性。子密钥是每个签名成员Pj(j∈B)的密钥,如果在可信中心分发了错误的子密钥,则可在第(1)步被共享者检验出子密钥是否有误。

(2)签名的有效性

每位签名成员Pj(j∈B)进行签名时,都任选自己的随机数ki(1≤ki≤q-1),由第(2)步计算得到Ri并向B中的成员公开,同时得到(x,y),第(3)步计算r=x-h(m)(mod q),si=ei,B r+ki(mod q),并把(r,si)发送给服务员A。如果有假冒签名,第(4)步就可以由群服务员A检验出来。

(3)可靠性与防欺骗性

群服务员A在签名过程中,只负责收集和验证签名成员的签名保证了此方案的可靠性;若参与签名的签名者在第(3)步有欺骗行为,则可由第(4)步检验出来。

(4)防止明文攻击

对(t,n)门限签名方案,选择明文攻击是不可伪造性,攻击者要想得到签名,必须得到t个参与的签名,这通常比较困难。如果某些参与者丢失了签名子秘钥,攻击者利用这些子秘钥仿造签名,由第(3)步和第(4)步可知,群服务员A能验证是否是伪造签名。

结果表明,建立在可信中心的ECC可验证门限签名方案是切实可行和安全的。

5 结论

(1)建立在ECC上门限数字签名方案产生的签名(r,s)及基于ECC的可验证(t,n)门限签名方案同基于ECC的ElGamal数字签名方案生成的签名形式完全相同,签名(r,s)的验证同基于ECC的ElGamal签名验证的方法也相同,上述两种方法有效。

(2)由椭圆曲线的特点决定椭圆曲线门限签名具有门限签名的正确、安全、可检验、防欺骗等特点,建立在可信中心的ECC可验证门限签名方案是切实可行和安全的。

(3)有关方法在WebGIS、电子政务等领域中的应用还需进一步研究。基于椭圆曲线的数字签名机制的相关算法也可进一步优化,从而提高门限数字签名的效率。

参考文献

[1]韩锦荣，吕继强．王新梅．基于椭圆曲线的可验证门限签名方案[J]．西安电子科技大学学报(自然科学版)，2003．30(1)：26～28．

[2]Blakley G R.Safeguarding Cryptographic Keys[Z].In:Proc.Nat.Cpmputer Conf,AFIPS Conf;Proc.Vol.48,1979,pages:313～317.

[3]Shamir A.How to Share a Secret[A].Comm_unications of the ACM[C],1979,22(11):612～613.

[4]张鹏．门限数字签名相关特性研究[D]．济南：山东大学，2004．

[5]Desmedt Y,Frandkel Y.Shared generation of authenticators and signatures[A].In: Advances in Cryptology-CRYPTO'91[C]. 1991:457～469.

[6] Kazuo Takaragi,Kunihiko Miyazaki,Masashi Takahashi,et al.A threshold digital signature issuing scheme without secret communication [EB/OL].http://grouper.Ieee.org/groups/1363/Study -Group/contributions/th-sche.pdf.

[7]张险峰，刘锦德．一种基于门限ECC的入侵容忍CA方案[J]．计算机应用，2004，24(2)：5～8．

实用的前向安全门限重签名方案篇3

1 前向安全的门限数字签名方案

1.1 初始化阶段

1.1.1 选择循环子群

密钥分发中心首先选择n=P1P2=(2qp1'+1)(2qp2'+1)和一个阶为q的循环子群,g∈QRn(即gq=1mod n),QRn为模n的平方剩余集合,且p1=p2=3mod 4,其中p1,p2,p1',p2',q都为安全的大素数,然后选择一对整数(e,d),分别作为基于合数n的RSA公私钥,h()为一个安全的单向散列函数。

1.1.2 系统选择t-1阶秘密多项式

最后,公布(n,q,g,h,Y)。

1.1.3 秘密分量的分发

设A={u1,u2,…,ul}是群组t个成员,其身份标示IDi。对每个群组成员,密钥分发中心通过秘密信道把σi发送给每个ui作为成员秘密分量。

1.1.4 密钥的更新

将群组签名整个有效期分为T个时间段,从第一个时间段开始,群组成员根据前一时间段的密钥计算出目前时间段的密钥。

式(1)中,σi,j表示成员ui的第j时间段密钥,σi,j-1表示成员ui的第j-1时间段密钥,初始密钥σi,j=σi;j=1,2,…,T。更新完成后,销毁前一周期密钥σi,j-1。

1.2门限重签名的产生

1.2.1 部分签名产生

设群组集合A中t各成员B={u1,u2,…,ut}相对消息M产生代表群组的门限重签名,B中成员一起执行下列操作:

每个ui(i=1,2,3,…,t)选择一个随机数βi,计算:

然后,每个ui把{P,si,zi}发送给群签名合成者。

1.2.2 门限重签名的产生

群组签名合成者计算:

最后,{j,P,Z,S}为消息M的门限签名,j为第j个签名时间段。

1.2.3 门限签名的验证

任何验证者都能通过计算下式验证{j,P,Z,S}就是消息M的门限重签名。

2 方案安全性分析

2.1{j,P,Z,S}是有效的前向安全门限签名

证明:为了证明{j,P,Z,S}是有效的前向安全门限签名,则需要证明式(6)成立。

根据式(3)、式(4)和式(5)得:

根据式(5)和上式得:

则{j,p,Z,S}是有效的前向安全门限签名。

2.2 方案具有前向安全的特性

方案的前向安全是基于强RSA假定。

强RSA假定已知n和,n为两个大素数的乘积,则找出一个,且满足y=xβmod n(β>1)是一个非常困难的问题。

如果攻击者已获得群组签名者ui的第j时间段密钥σi,j,企图通过n计算第j时间段密钥σi,j-1,这是一个强RSA假定问题,所以攻击者无法通过σij计算出σi,j-1,也就无法伪造第k周期签名(k

2.3 方案能抵抗伪造攻击

非法用户企图通过式(4)和式(5)求S',这将面临大整数分解和单向散列函数求逆的问题。少于t个合法的参与者不能代表群组进行有效签名,t个成员无法获得系统秘密参数,任何一组成员不可以假冒另一组成员对消息生成有效的门限签名,而事后不负任何责任。这是由Shamir的秘密共享方案的安全性来保证的。

2.4 方案具有实用性

方案将求(Lagrange相关系数)通过计完成,在不知道RSA秘密参数(p-1)(q-1)的情况系不用求逆计算,因为整除P,这样的设计将方案具有实用性。

3 结束语

就日前已有的前向安全门限数字签名存在理论错误的缺陷,提出一种新的实用的前向安全门限重数字签名方案。降低门限签名者密钥泄漏造成的损失,将群组成员密钥按时间段进行更新,群组公钥保持不变。即使第k时间段的签名密钥被泄露,攻击者无法推出第k-1时间段的签名密钥,也无法伪造第k时间段之前的签名。前向安全的门限签名为签名密钥提供了强大的保护,使签名密钥被泄露所造成的损失降到最小。基于强RSA的假设,证明方案可抵抗非法签名者的伪造攻击和具有前向安全性和实用性。

参考文献

[1] Desmedt Y,Frankel Y.Threshold cryptosystems.In:Brassard G,ed. Advances in Cryptology——CRYPTO' 89 Proceedings Lecture Notes in Computer Science 435 Berlin:Springer Verlag,1990:307-315

[2] Anderson R..Invited lecture.In:Proceedings of the 4th ACM Conference on Computer and Communications Security,Zurich,Switzerland, 1997:1-7

[3]于佳.标准模型下的前向安全多重签名:安全模型和构造.软件学报,2010;21(11):2910-2923

[4]张明武.密文匿名的高效前向安全短签密方案,北京邮电大学学报,2010;33(4):131-135

[5]米军利,张建中.前向安全的门限签名方案.计算机工程与应用,2009;45(1):124-125

[6]程曦,戚文峰.一种向前安全的门限代理签名方案.信息工程大学学报,2006;4(7):314-318

门限签名篇4

关键词：数字签名,代理签名,门限多代理多签名,内部攻击

0引言

自1976年Diffie和Hellman首次提出数字签名概念以来[1], 数字签名在一些特殊行业, 如金融、商业、军事等领域得到广泛的应用, 尤其在数据完整性检验、身份鉴别、防否认性等方面具有独特的功能[2]。随着社会的发展, 普通的数字签名方案已经不能满足实际需求, 为了适应实际需要, 许多具有特殊功能的数字签名方案相继提出, 如门限签名[3]、代理签名[4]等。

2003年, Li等提出了一种同时具有多种特殊功能的数字签名即门限多代理多签名[5]。在 (t1, n1;t2, n2) 门限多代理多签名方案中, 只有n1个原始签名者中的任意t1个或多于t1个共同合作才能将代理权授给代理签名者, 同时, 只有n2个代理签名者中的任意t2个或多于t2个共同合作才能生成有效的签名。门限多代理多签名是门限签名和多重代理多重签名的有机结合, 克服了多重代理多重签名需要所有的原始签名者合作才能授权及所有的代理签名者合作才能签名这个弱点, 与普通的多重代理多重签名相比, 门限多代理多签名具有更大的灵活性和实用性。但是, 2004年Hwang等指出Li方案存在缺陷并进行了改进[6]。

2004年, Tzeng等提出了一个具有共享验证性质的门限多代理多签名方案[7], 即在该方案中, 不仅原始签名者和代理签名者是由群体组成, 而且验证者也是由群体组成。但是, Tzeng方案存在一些缺陷[8,9,10], 其中Kang等指出Tzeng方案具有这样一个缺陷:n1个原始签名者中的任意t′1个都能代表原始组将签名权委托给代理组, 并进行了相应的改进[9]。为了方便叙述, 我们把Kang等提出的方案称为KHW 方案。本文指出, KHW 方案仍存在缺陷, 即如果存在一定数量的恶意内部成员, 则当他们截获到一个有效的签名后, 可以实施合谋攻击, 最终伪造出另一个有效的签名。最后, 本文对攻击存在的原因及后果作了详细的分析, 并提出了改进措施。

1KHW方案简介

设GO={UO1, UO2, …, UOn1}表示有n1个原始签名者的组, GP={UP1, UP2, …, UPn2}表示有n2个代理签名者的组, GV={UV1, UV2, …, UVn3}表示有n3个验证者的组。系统中心SC负责产生系统参数、个人私钥和群私钥及相应的公钥。

1.1参数产生过程

SC按照如下过程选择和计算系统参数及密钥:

(1) 选择两个大素数p和q, 满足q|p-1, g是GF (p) 中的一个q阶生成元;选择hash函数h。

(2) 选择三个秘密多项式:

fO (x) =Ot1-1xt1-1+Ot1-2xt1-2+…+O1x+O0 (mod q)

fP (x) =Pt2-1xt2-1+Pt2-2xt2-2+…+P1x+P0 (mod q)

fV (x) =Vt3-1xt3-1+Vt3-2xt3-2+…+V1x+V0 (mod q)

其中Ol, Pi, Vj∈Zq*, l=0, 1, 2, …, t1-1, i=0, 1, 2, …, t2-1, j=0, 1, 2, …, t3-1。

(3) fO (0) = O0为群GO的私钥, fP (0) = P0为群GP的私钥, fV (0) =V0为群GV的私钥。YO=gfO (0) (mod p) , YP=gfP (0) (mod p) 及YV=gfV (0) (mod p) 为相应的公钥。

(4) 每个原始签名者UOl的私钥为ηOl, 分享私钥为fO (xOl) , 相应的公钥为βOl = gηOl (mod p) 和yOl=gfO (xOl) (mod p) , l=1, 2, …, n1。每个代理签名者UPi的私钥为λPi, 分享私钥为fP (xPi) , 相应的公钥为γPi=gλPi (mod p) 和yPi=gfP (xPi) (mod p) , i=1, 2, …, n2。每个验证者UVj的分享私钥为fV (xvj) , 相应的公钥为yVi=gfV (xVj) (mod p) , j=1, 2, …, n3。其中xOl、xPi、xvj分别为UOl、UPi、UVj的唯一身份标志符。

最后, SC公开系统参数 (p, q, g) , h, 及所有的公钥YO, YP, YV, βOl, yOl, γPi, yPi, yVi。

1.2代理份额产生阶段

方案中要求任意t1个原始签名者都能代表原始群授权给代理群。不失一般性, 设DO={UO1, UO2, …, UOt1}为实际参与的原始签名者, 在DO中选择一个合成者。DO按照如下过程将代理权授给GP:

(1) 每个UOi选择一个随机数ai∈Zq*, 广播ki=gai (mod p) 。

(2) 每个UOi计算:

K=∏ $_{i = 1}^{t_{1}}$ ki (mod p)

σOi= (ai+ηOi) K+fO (xOi) LOi (mod q)

其中LOi=∏ $_{j = 1, j \neq i}^{t_{1}}$ (-xOj) (xOi-xOj) -1 (mod q) 。

(3) 每个UOi在公开信道上发送σOi给指定的合成者。

(4) 指定的合成者收到σOi后, 通过下式检查σOi是否有效。

gσOi = (kiβOi) KyOiLOi (mod p)

若成立, 则计算σ = t2 -1∑ $_{i = 1}^{t_{1}}$ σOi, 向GP广播 (σ, K, ∏ $_{i = 1}^{t_{1}}$ βOi) 。

最后, 每个代理签名者UPi (i=1, 2, …, n2) 验证:

gσ = ( (K∏ $_{i = 1}^{t_{1}}$ βOi) KYO) t2 -1 (mod p)

是否成立, 若成立, 则将σ作为代理份额。

1.3代理签名产生阶段

方案中要求任意t2个代理签名者都能代表代理群对消息m签名。不失一般性, 设DP={UP1, UP2, …, UPt2}为实际参与签名的代理签名者, 在DP中选择一个合成者。DP按照如下过程产生签名:

(1) 每个UPi选择一个随机数bi∈Zq*, 广播rpi=gbi (mod p) 。

(2) 每个UPi计算:

r′pi=YVfP (xPi) LPi + bi (mod p)

其中LOi=∏ $_{j = 1, j \neq i}^{t_{1}}$ (-xOj) (xOi-xOj) -1 (mod q) , 经安全信道发送r′pi给DP中的其它代理签名者。

(3) 每个UPi计算:

R′=∏ $_{i = 1}^{t_{2}}$ r′pi (mod p) , R=∏ $_{i = 1}^{t_{2}}$ rpi (mod p) ,

si=R′fP (xPi) LPi+Rbi- (λPi+σ) h (m) (mod q) (1)

发送部分签名si给合成者。

(4) 合成者验证:

yPiR′LPirpiR = gsi (γPi ( (K∏i = 1t1 βOi) KYO) t2 -1) h (m) (mod p) (2)

是否成立, 若成立, 则计算s=∑ $_{i = 1}^{t_{2}}$ si (mod q) 。最后将 (R, K, ∏ $_{i = 1}^{t_{2}}$ γPi, s) 作为消息m的签名发送给GV。

1.4代理签名的验证过程

方案中要求任意t3个验证者都能代表验证群对代理签名进行验证。不失一般性, 设DV={UV1, UV2, …, UVt3}为实际参与的验证者。DV按照如下过程进行验证:

(1) 每个UVj计算:

rVj= (YPR) fV (xVj) LVj (mod p)

其中LVj=∏ $_{i = 1, i \neq j}^{t_{3}}$ (-xVi) (xVj-xVi) -1 (mod q) , 经安全信道将rVj发送给DV中的其它验证者。

(2) UVj计算:R′=∏ $_{i = 1}^{t_{3}}$ rVi (mod p) , 最后验证

YPR′RR = gs (∏ $_{i = 1}^{t_{2}}$ γPi (K∏ $_{i = 1}^{t_{1}}$ βOi) KYO) h (m) (mod p) (3)

是否成立, 若成立, 则 (R, K, ∏ $_{i = 1}^{t_{2}}$ γPi, s) 是消息m的有效签名。

2KHW方案的攻击

设GO中有t1个恶意的内部成员, 不失一般性, 可设为A= D′O={U′O1, U′O2, …, U′Ot1}, U′Oi∈GO, i=1, 2, …, t1, 选取其中一人为合成者。由KHW方案可知, 攻击者A容易获得方案中的 σ, 这时他们只要截获到消息m的有效签名 (R, K, ∏ $_{i = 1}^{t_{2}}$ γPi, s) , 则他们可按如下过程实施攻击。

(1) 每个U′Oi随机选择a′i∈Zq*, 广播k′i=ga′i (mod p) 。

(2) 每个U′Oi收到k′i后, 计算:

K′=∏ $_{i = 1}^{t_{1}}$ k′i (mod p)

σ′Oi= (a′i+η′Oi) K′+fO (x′Oi) L′Oi (mod q)

其中L′Oi=∏ $_{j = 1, j \neq i}^{t_{1}}$ (-x′Oj) (x′Oi-x′Oj) -1 (mod q) 。

(3) 每个U′Oi将σ′Oi发送给指定的合成者。

(4) 指定的合成者收到σ′Oi后, 可以通过gσ′Oi = (ki′β′Oi) K′y′OiL′Oi (mod p) 验证σ′Oi的有效性。若成立, 指定的合成者计算σ′ = t2 -1∑ $_{i = 1}^{t_{1}}$ σ′Oi (mod q) 。

(5) 此时, 攻击者A可以计算s′=t2 (σ-σ′) h (m) +s (mod q) 。

最后, 攻击者利用 (R, K′, ∏ $_{i = 1}^{t_{2}}$ γPi, s′) 代替 (R, K, ∏ $_{i = 1}^{t_{2}}$ γPi, s) 作为消息m的签名, 并将其发送给验证组GV。

3KHW方案的攻击分析及改进

3.1攻击的正确性

由KHW方案中的代理份额产生过程可知:

gσ = ( (K∏ $_{i = 1}^{t_{1}}$ βOi ) KYO ) t2 -1 (mod p)

由验证过程可知:

YP R′RR = gs (∏ $_{i = 1}^{t_{2}}$ γPi (K∏i = 1t1 βOi ) KYO ) h (m) (mod p)

由攻击过程可知:

gσ′ = ( (K′∏ $_{i = 1}^{t_{1}}$ β′Oi ) K′YO ) t2 -1 (mod p)

进一步有:

gs′ (∏ $_{i = 1}^{t_{2}}$ γPi (K′∏ $_{i = 1}^{t_{1}}$ β′Oi) K′YO) h (m)

= gt2 (σ-σ′) h (m) gs (∏ $_{i = 1}^{t_{2}}$ γPi ) h (m) gt2 σ′h (m)

=gt2σh (m) gs (∏ $_{i = 1}^{t_{2}}$ γPi) h (m)

=gs (∏ $_{i = 1}^{t_{2}}$ γPigt2σ) h (m)

=gs (∏ $_{i = 1}^{t_{2}}$ γPi (K∏ $_{i = 1}^{t_{1}}$ βOi) KYO) h (m)

= YP R′RR

所以验证者可以验证 (R, K′, ∏ $_{i = 1}^{t_{2}}$ γPi, s′) 是消息m的有效签名, 即攻击者取得了成功的攻击。

3.2攻击的后果

由攻击过程及正确性分析可知, 在攻击者A截获了KHW方案中的 σ和消息m的有效签名 (R, K, ∏ $_{i = 1}^{t_{2}}$ γPi, s) 后, 攻击者A可以伪造一个签名 (R, K′, ∏ $_{i = 1}^{t_{2}}$ γPi, s′) , 并能通过验证组GV的验证。攻击者A通过伪造有效签名 (R, K′, ∏ $_{i = 1}^{t_{2}}$ γPi, s′) 可以达到这样的目的:本来攻击者A不同意消息m中的内容, 但是他们通过伪造有效签名后, 可以使得验证者认为攻击者同意m中的内容。这样的攻击后果是相当严重的, 例如, 某公司董事会对提升一些员工的福利待遇进行表决, 表决结果为:有达到规定数量的董事同意此决议, 即可以授权给代理签名组对此决议签名, 不妨设DO={UO1, UO2, …, UOt1}是同意决议的董事且代表董事会将签名权委托给代理签名组, D′O={U′O1, U′O2, …, U′Ot1}不同意此项决议。此时, D′O={U′O1, U′O2, …, U′Ot1}可以伪造有效签名让验证者相信自己也是同意该决议, 从而可以向验证者索取好处。

3.3攻击的原因

攻击成功的关键原因不是攻击者能获取σ和截获有效签名 (R, K, ∏ $_{i = 1}^{t_{2}}$ γPi, s) , 而是由于方案设计过程中授权过程和代理过程相分离, 即在求s的过程中没有把消息m、原始签名者的身份和代理签名者的身份联系起来, 使得攻击者可以用自己的身份代替合法身份。

3.4改进的方案及分析

由上面的攻击原因, 我们可以将原方案进行改进。在原方案的基础上, 将式 (1) -式 (3) 分别改为:

si=R′fP (xPi) LPi+Rbi- (λPi+σ) h (m‖R‖R′‖K‖APSID‖AOSID)

yPi R′LPi rpi R = gsi (γPi ( (K∏ $_{i = 1}^{t_{1}}$ βOi ) KYO ) t2 -1) h (m‖R‖R′‖K‖APSID‖AOSID)

YP R′RR = gs (∏ $_{i = 1}^{t_{2}}$ γPi (K∏ $_{i = 1}^{t_{1}}$ βOi ) KYO ) h (m‖R‖R′‖K‖APSID‖AOSID)

其中APSID和AOSID分别表示实际参与签名的代理签名者和实际参与授权的原始签名者。此时, 攻击者要想伪造签名, 就必须计算:

s′=t2 (σ-σ′) h (m‖R‖R′‖K′‖APSID‖AOSID′) +s (mod q)

但是由于攻击者无法知道R′, 所以攻击不能成功。

4结束语

本文给出了KHW方案中内部成员实施的一个伪造攻击, 并详细阐述了攻击造成的严重后果, 最后在分析攻击原因的基础上提出了改进方案。

参考文献

[1]Diffie M, Hellman M E.New directions in cryptography[J].IEEE Trans-actions on Information Theory, 1976, 22 (6) :644-654.

[2]赵泽茂.数字签名理论[M].北京:科学出版社, 2007:4-7.

[3]Mambo M, Usuda K, Okamoto E.Proxy signatures:delegation of the power to sign messages[J].IEICE Trans.Fundamentals, 1996, E79-A (9) :1338-1354.

[4]Desmedt Y, Frandel Y.Shared generation of authenticator and signature[C].//Proc of Advances in Cryptology-Crypto’91.Berlin:Springer-Verlag, c1991:457-469.

[5]Li L H, Tzeng S F, Hwang MS.Generalization of proxy signature based on discrete logarithms[J].Computers&Security, 2003, 22 (3) :245-255.

[6]Hwang S J, Chan C C.Improvement on Li et al.’s generalization of proxy signature schemes[J].Computers&Security, 2004, 23 (7) :615-619.

[7]Tzeng S F, Yang C Y, Hwang M S.A nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J].Future Gen-era-tion Computer Systems, 2004, 20 (5) :887-893.

[8]Kang Baoyuan, Han Jingguang, Wang Qinju.A new threshold multi-proxy multi-signature scheme[J].Journal of Electronics (China) , 2006, 23 (4) :560-563.

[9]Bao Haiyong, Cao Zhenfu, Wang Shengbao.Improvement on Tzeng et al.’s nonrepudiable threshold multi-proxy multi-signature scheme with shared verification[J].Applied Mathematics and Computation, 2005, 169 (2) :1419-1430.

门限签名篇5

门限代理重签名不仅能有效分散单个代理者的重签名权力, 还可保证重签名密钥的安全性和完整性。在一个 (t, n) 门限代理重签名方案中, 重签名密钥被分成个n个子密钥, 然后分发给n个半可信的代理者持有。即使攻击者攻陷了t-1个代理者, 门限代理重签名方案仍是安全的。在现有的大部分门限代理重签名方案中, 只有一个固定的门限值[1,2,3]。然而, 在许多实际应用中, 参加重签名的代理者数目往往取决于重签名消息的重要性, 这就要求签名方案的门限值是可变的。

近年来, 代理重签名是密码学的一个热点研究方向, 国内外学者在代理重签名和门限代理重签名方面已进行了一些出色的工作[4,5,6,7,8,9,10];但可变门限代理重签名的研究才刚刚起步, 关于可变门限代理重签名的公开文献非常少。文献[11]提出了可变门限代理重签名的思想, 并构造了一个可证明安全的单向可变门限代理重签名方案, 但该方案的部分重签名算法和签名验证算法的效率比较低。当用具体的密码学哈希函数替换随机预言机时, 在随机预言模型下可证安全的签名方案不一定是安全的。因为单向代理重签名能实现双向代理重签名的功能, 所以研究无随机预言机的单向可变门限代理重签名方案就显得很有吸引力。本文在Sherman等人[5]提出的代理重签名方案的基础上, 提出一个在标准模型下可证明安全的单向可变门限代理重签名方案, 并利用文献[11]的安全性证明思想, 给出了新方案的安全性证明。在门限重签名密钥生成算法中, 分发者和每个代理者之间仅通信一次。根据可变的门限值, 每个代理者都能非交互地生成相应的重签名子密钥和验证公钥。与文献[11]的单向可变门限代理重签名方案相比, 新方案的部分重签名算法和重签名验证算法具有较高的计算效率, 同时具有更短的重签名长度。

1 准备知识

定义1 (CDH问题) 设p是一个大素数, G是一个阶为p的循环群, g是G的一个生成元, 群G上的计算性Diffie-Hellman (CDH) 问题是:已知 (g, ga, gb) ∈G3, 计算gab, 这里a, b∈Zp。

定义2 (CDH假设) 如果没有一个概率多项式时间算法在时间t内以至少ε的概率解决群G上的CDH问题, 则称群G上的 (t, ε) -CDH假设成立。

定理1 (中国剩余定理) 设q1, q2, …, qk是两两彼此互素的k个正整数, Q=q1, q2, …, qk, 则一次同余方程组x=ai (modqi) (i=1, 2, …, k) , 对模Q有唯一解:

这里Qi=Q/qi, Qiei=1 (modqi) (i=1, 2, …, k) 。

定义3一个单向可变门限代理重签名方案是一个由概率多项式时间算法构成的七元组 (Setup, Key Gen, Rekey Share, Sign, Resign Share, Combine, Ver) 。

1) Setup是系统参数生成算法:输入一个安全参数1λ, 输出系统参数cp。

2) Key Gen、Sign和Ver算法与标准数字签名体制中的密钥生成算法、签名算法和签名验证算法相同。

3) Rekey Share是门限重签名密钥生成算法:给定一个受托者的公钥pkA和一个委托者的公钥/私钥对 (pkB, skB) , 生成一个重签名密钥rkA→B, 然后将rkA→B分割成n个子密钥rkiA→B分发给n个代理者秘密保管。根据可变的门限值k, 每个代理者Pi均能生成相对应的重签名子密钥rkk, iA→B和验证公钥vkk, i。

4) Resign Share是部分重签名生成算法:给定一个门限值k, 一个重签名子密钥rkk, iA→B, 一个公钥pkA, 一个消息m和一个签名σA, 该算法首先验证σA的合法性, 如果Ver (pkA, m, σA) =1, 输出一个对应于公钥pkB的m的部分重签名σB, i;否则, 输出⊥。

5) Combine是门限重签名生成算法:给定k个诚实代理者对消息m的部分重签名输出一个对应于公钥pkB的消息m的门限重签名σB。

2 一个新的单向可变门限代理重签名方案

在Sherman等人[5]提出的代理重签名方案的基础上, 提出了一个新的单向可变门限代理重签名方案。假定签名消息m的和用户公钥pk的长度分别是nm和nη长的比特串, 可用两个个抗碰撞的哈希函数H1:{0, 1}*→{0, 1}nm和H2:{0, 1}*→{0, 1}nη来实现。新方案由受托者、委托者和n个半可信的代理者{P1, …, Pn}组成。新方案具体描述如下:

1) Setup:给定一个安全参数1λ, 选择一个大素数p和两个阶为p的循环群G1和G2, 定义一个双线性映射e:G1×G1→G2。在G1中随机选取nη+1个元素和nm+1个元素选择G1的一个生成元g, 并随机选取n个两两互素的正整数q0

2) Key Gen:选择一个随机数x∈Zp*, 输出公钥pk=gx和私钥sk=x。

3) Rekey Share:给定一个受托者的公钥pkA=gα和一个委托者的公钥/私钥对 (skB, pkB) = (β, gβ) , 该算法执行如下操作:

(1) 在Zp*中选取两个随机数bi和ci, 计算根据中国剩余定理计算a0∈ZQ, 使得a0=β (modqj) , j=0, …, n-1。构造一个n-1次秘密多项式对于任意的门限值k (1≤k≤n) , 一定存在一个k-1次秘密多项式

(2) 在Zp*中选取两个随机数ei和di, 计算随机选择一个数t∈Zp, 根据中国剩余定理计算t0∈ZQ, 使得t0=t (modqj) , 0≤j≤n-1。构造一个n-1次秘密多项式对于任意的门限值k (1≤k≤n) , 一定存在一个k-1次秘密多项式

(3) 广播Aj=gaj, Bj=gtj, j=0, 1, …, n-1, 其中B0=gt, A0=pkB。

(4) 根据中国剩余定理, 计算秘密份额 (f (i) , g (i) ) ∈ZQ2, 满足f (i) =fk (i) (modqk-1) , g (i) =gk (i) (modqk-1) , k=1, 2, …, n。通过一个秘密渠道将秘密份额 (i, f (i) , g (i) ) 发送给代理者Pi, i=1, 2, …, n。

(5) Pi收到 (f (i) , g (i) ) 后, 首先计算f (i) (modqn-1) =fn (i) , g (i) (modqn-1) =gn (i) , 然后通过下式验证收到的秘密份额的合法性:

如果上面两个等式都成立, 则说明秘密份额 (f (i) , g (i) ) 是合法的。

对于任意的门限值k (1≤k≤n) , 每个代理者Pi在本地计算 (fk (i) , gk (i) ) = (f (i) (modqk-1) , g (i) (modqk-1) ) , 然后广播验证公钥vkk, i=gfk (i) , 并计算相应的重签名子密钥:

4) Sign:给定一个私钥sk=α和一个消息输出一个m的签名这里r是Zp中的一个随机数

7) Ver:输入一个nm比特长的消息m, 一个nη比特长的公钥pk和一个待验证的签名σ, 如果σ= (σ1, σ2, σ3) 且输出1;如果输出1;否则, 输出0。

3 安全性分析与证明

3.1 正确性分析

本方案的正确性可以通过以下方程得到验证:

(1) 秘密份额 (i, f (i) , g (i) ) 的正确性验证

代理者Pi收到秘密份额 (i, f (i) , g (i) ) 后, 可通过下式验证其合法性:

(2) 门限值为k时的部分重签名σB, i= (σi, 1, σi, 2, σi, 3) 的正确性验证:

(3) 门限值为k时的门限重签名σB= (σB, 1, σB, 2, σB, 3) ) 的正确性验证:

3.2 安全性分析

利用文献[11]可模拟性的安全性证明方法, 证明本文提出的新方案的安全性。

定理2门限重签名密钥生成算法Rekey Share是可模拟的。

证明:给定一个门限值k, 一个受托者和一个委托者的公钥 (pkA, pkB) , 构造一个门限重签名密钥生成算法Rekey Share的模拟器SIMRekey。SIMRekey知道已被攻陷代理者的验证公钥vkk, i和重签名子密钥rkAk, i→B, i=1, 2, …, k-1;然后计算未被攻陷代理者的验证公钥。

这里λj, i是Lagrange插值多项式的系数。由于从而可计算Ai和Bi, i=1, 2, …, k-1。从攻击者的角度来看, 模拟器SIMRekey的模拟过程与Rekey Share算法的执行过程是不可区分的, 所以Rekey Share算法是可模拟的。

定理3部分重签名生成算法Resign Share是可模拟的。

这里λj, i是Lagrange插值多项式的系数。因此, SIMResign能模拟攻击者在算法Resign Share中输出消息的部分重签名的视图。综上所述, 本文提出的可变门限代理重签名方案是可模拟的。

即使恶意的攻击者攻陷了k-1个代理者, 我们的方案只要有k个诚实的代理者仍能生成一个合法的重签名, 所以当n≥k+k-1=2k-1时, 我们的单向门限代理重签名方案是强壮的。

定理4如果一个单向可变门限代理重签名方案是可模拟的, 且关联于该门限方案的代理重签名方案是安全的, 则单向可变门限代理重签名方案也是安全的[11]。

定理5在标准模型下, Sherman等人提出的代理重签名方案在适应性选择消息攻击下是安全的, 其安全性可归约到计算性Diffie-Hellman (CDH) 假设[5]。

结合定理2、定理3、定理4、定理5和单向门限代理重签名方案的强壮性, 可得如下定理:

定理6在标准模型下, 本文所提出的单向可变门限代理重签名方案在CDH假设下是安全的;对于某个门限值k, 如果n≥2k-1, 则新方案也是强壮的。

3.3 性能比较

下面将本文提出的新方案与文献[11]的单向可变门限代理重签名方案进行计算开销和重签名长度的比较。假定所有方案选择相同长度的素数|p|=160比特。记P表示双线性对运算, E表示指数运算。相对于双线性对和指数运算而言, 模乘法运算、模加法运算和普通哈希函数的计算量都比较小, 因此这些运算操作将不再进行讨论。所有方案的比较结果如表1所示。

从表1可以看出, 与文献[11]的单向可变门限代理重签名方案相比, 本文提出的新方案在部分重签名算法中少4次指数运算、重签名验证算法少1次双线性对运算、重签名的长度少160比特, 所以本文提出的新方案比文献[11]的方案具有较高的计算效率、更短的重签名长度。

4 结语

单向可变门限代理重签名可实现双向可变门限代理重签名的性能, 所以单向可变门限代理重签名更具有研究价值。基于Sherman等人[5]提出的代理重签名方案, 提出了一个单向可变门限代理重签名方案, 并在标准模型下给出了该方案的安全性证明。然而, 双线性对是已知最复杂的密码操作, 如何设计没有双线性对的可变门限代理重签名是我们下一步的研究方向。

参考文献

[1]Yang Piyi, Cao Zhenfu, Dong Xiaolei.Threshold proxy re-signature[J].Journal of Systems Science and Complexity, 2011, 24 (4) :816-824.

[2]Yang Xiaodong, Wang Caifen.Threshold proxy re-signature schemes in the standard model[J].Chinese Journal of Electronics, 2010, 19 (2E) :345-350.

[3]Yang Xiaodong, Wang Caifen, Zhang Yulei, et al.A new forward-secure threshold proxy re-signature scheme[C]//Proceedings of IC-NIDC2009, 2009:566-569.

[4]Benoit L, Damien V.Multi-use unidirectional proxy re-signatures[C]//Proceedings of the 15th ACM Conference on Computer and Communications Security.Alexandria, USA, 2008:511-520.

[5]Sherman C, Raphael P.Proxy re-signatures in the standard model[C]//Proceedings of the 11th International Conference on Information Security, Taibei, China, 2008:260-276.

[6]Ateniese G, Hohenberger S.Proxy re-signatures:new definitions, algorithms, and applications[C]//Proceedings of the 12th ACM CCS, Alexandria, USA, 2005:310-319.

[7]Shao Jun, Wei Guiyi, Ling Yun, et al.Unidirectional identity-based proxy re-signature[C]//Proceedings of 2011 IEEE ICC, 2011:1-5.

[8]Guo Duntao, Wei Ping, Yu Dan, et al.A certificateless proxy re-signature scheme[C]//Proceedings of IEEE ICCSIT 2010, 2010:157-161.

[9]Yang Xiaodong, Wang Caifen.Efficient on-line/off-line proxy re-signature schemes[J].Journal of Electronics&Information Technology, 2011, 33 (12) :2916-2921.

[10]Hong Xuan, Chen Kefei, Wan Zhongmei.Simplified universally composable proxy re-signature[J].Journal of Software, 2010, 21 (8) :2079-2088.

门限签名篇6

网络全球化已经加快了人们的电子信息交流,电子商务、电子政务、电子银行等都是网络全球化的重要应用领域。如何保证网络通信的安全已成为人们密切关注的问题之一,其中建立在RSA和ELGamal上的许多数字签名机制,其安全性依赖于因数分解和离散对数问题。然而,RSA的加解密钥要求比较大,ELGamal的签名认证花的时间太长,使得它们不适合某些系统的应用。现在,椭圆曲线密码体制的研究已经成为密码学的热点之一,由于在相同的条件下,椭圆曲线(EC)比其它公钥密码体制具有更强的安全性和效率,使得它在信息安全和密码系统的应用越来越引起了人们的重视。在某些应用领域ECC可以代替RSA、DSS和其它密码系统的使用[1,2]。一般来说,160位的ECC与1024位的RSA的安全性相当,这意味着ECC只需要更窄的带宽和更小的存储空间,这是网络应用的关键。

本文利用ECC短密钥和(t,n)门限方法建立一种多人同时签名的机制[3],这个方案的显著特点是群签名的成员个数t不能小于门限n的值,消息的接收者都能够验证签名。

1 有效群签名方案

群体密码学[4]由Desmedt于1987年提出,是面向社团或群体的密码体制。在群体密码中,群体外的人可以使用群体的唯一群公钥,向群体发送加密信息,而只有群体中的某些子集成员合作才能解密这些信息。同样,群体密码学中也有群体签名问题,群体外的用户只需知道群体的唯一公开密钥就可以验证该签名。门限数字签名是群体密码学的一个重要分支,特别适用电子政务的某些安全要求。其方法是将一个群体的签名密钥颁发给群体中的每个成员,使得任何成员个数大于或等于门限值的子集可以产生签名,而任何成员个数小于门限值的子集都无法产生签名。

群数字签名方案的安全性是建立在椭圆曲线离散对数的难解性上。当有n个成员的群想公开发布一个消息时,t(1≤t≤n)或者t个以上的成员能够代表群的签名,t个以下的成员不能代表群的签名。签名过程分为三个阶段:密钥产生、门限数字签名、门限数字签名的验证。验证中心CA(Center Authority)负责生成系统参数,验证每个成员的签名并公开群签名。

1.1 密钥产生[5]

CA产生和公开系统参数、群公钥,每个成员公钥和门限函数的其它部分。系统参数生成如下:

(1)CA产生和公开的参数

ECC:y2=x3+ax+b mod p,a、b∈Zp,4a3+27b2≠0 mod p,p是大素数,GF(p)={0,1,…,p-1},椭圆曲线的阶N也是一个大素数,且p+1-2≤#E(GF(p))≤p+1+2,单向哈希函数h(·),椭圆曲线的基点G,其阶为n,群成员Ui的公开身份Xi。

(2)CA产生和保留的参数

(t,n)门限函数f(x)=at-1xt-1+…+a1x+a0mod n,其中{i=0,…,t-1},ai∈[1,n-1],群密钥f(0)=a0,群成员Ui的密钥为f(xi)。

(3)CA计算并公开群公钥N

(4)CA计算并公开每个成员公钥Ni

1.2 门限数字签名产生[6]

假设群需要对消息m进行签名,群成员U1,U2,…,Ut能代表群签名。这一阶段需要产生每个人的数字签名、验证每个人的数字签名以及产生(t,n)门限签名。步骤如下:

(1)每个成员Ui使用密钥f(xi)和随机整数ki(ki∈[1,n-1]),计算对消息m的签名(ri,si)。Ri=kiG,公开Ri,

其中h(m)为消息m的单向哈希函数,有利于提高系统的安全性,成员Ui把自己的数字签名(ri,si)发送给CA中心。

(2)CA中心收到每个成员Ui的数字签名(ri,si)后,CA利用以下方程验证签名:检查di=ri是否满足,如果满足,则(ri,si)是成员Ui对m的有效签名;否则,成员Ui的签名无效。

(3)收到所有成员的签名(ri,si)后,CA计算并公开对消息m的群签名(r,s)。CA首先获得所有成员的公钥Ri=(XRi,YRi),然后计算R。

1.3 群数字签名的验证

任意一个接收到(r,s)的接收者能够验证对消息m的群签名:

(1)接收者首先计算判断S=s是否成立,如果成立则执行(2),否则群签名无效。

(2)计算Q=(xQ,yQ)=s G+h(m)N,q=xQmod n,如果q=r,则(r,s)是群对消息m的签名,否则签名无效。

证明2:由方程

2 安全性和可行性分析

我们从不同的角度来分析方案的安全性和可行性。从可能潜在的攻击来分析它的安全性,这也是通过对这个系统的缺陷研究来证明系统的安全性。通过目前的签名机制和提出的方案来比较分析系统的可行性,包括密钥长度、签名长度、签名时间等方面来证明方案的优越性。

2.1 安全性分析

使用(t,n)门限签名方案,要有t或t个以上的成员才能建立有效的群签名并获得群密钥,使攻击不可行。如果攻击者企图从群公钥N=-f(0)G获得群密钥f(0),攻击者首先必须解决椭圆曲线离散对数问题(ECDLP),这比离散对数问题还困难,因此攻击不可行。

如果攻击者想通过改变成员签名进行攻击,由方程要从Di获得Di'伪造有效的签名si',他仍然要解决ECDLP问题。

如果攻击者获得了Q、s、G、h(m)、N,想通过(t,n)门限群签名验证方程伪造有效签名:Q=(xQ,yQ)mod n=s G+h(m)N,则攻击者还是必须解决ECDLP问题,并且对消息m使用了单向哈希函数,这样不仅提高了消息m的安全性,而且也避免了消息m受到的攻击。

2.2 可行性分析

在签名和验证过程中,所进行的计算用加法代替了乘法和指数运算,运算速度比传统的ELGamal签名方案和DSA系统要快。在个人签名和群签名使用相同的协议,减少了系统设计代价。

在方案中,群成员可以同时进行签名,另外(t,n)门限方案在任何时候验证签名人的身份提供了灵活性。然而许多目前建立在RSA、ELGamal上的签名机制的安全性不如建立在椭圆曲线离散对数问题的(t,n)门限签名方案。这个方案只使用160bits与RSA使用1024bits的安全性相同,相同的安全级别只需更短的密钥,可以减少内存空间;另外也加快了消息的传输。参数n只要160bits可以与RSA的1024bits的安全性相同,因此消息只要320bits。

可见,上述签名协议产生的签名(r,s)同基于ECC的ElGamal数字签名方案生成的签名形式完全相同,签名(r,s)的验证也同基于ECC的El Gamal签名验证的方法相同,因此本方案是有效的。

3 结束语

建立在椭圆曲线上的公钥系统不仅使用的钥匙短,而且它的安全性更高。优越的可行性和较窄的带宽是未来公钥系统的主流。不管在内网还是在外网的商业事务中都能利用这种有效的门限群签名系统发送签名的消息。而且,系统还能够在没有改变和伪造的情况下进行群成员签名的验证。

在未来的应用中,建立在椭圆曲线上的(t,n)门限数字签名能够有效地改善签名机制,这样不仅缩短了签名密钥,也缩短了产生和验证消息的时间。在安全的网络环境下,对电子政务和电子商务的未来发展也有很重要的意义。

摘要：本文结合椭圆曲线密钥短和(t,n)门限方案的特点,研究了一种基于椭圆曲线的多人同时签名并可验证的门限群数字签名算法,并分析了这个算法的安全性、可行性。

关键词：门限,群数字签名,椭圆曲线密码系统

参考文献

[1]M.Robshaw,Y.Yin,Elliptic curve cryptosystems,An RSA Laboratories Technical Note,1997,Revised June27.

[2]G.J.Lay,H.G.Zimmer,Constructing elliptic curves with given group order over large finite fields,in:Algorithmic Number Theory Proceedings LCNS877,Springer-Verlag,Berlin,1994:.250-263.

[3]C.Blundo,A.De Santis,D.Stinson,Graph decompositions and secret sharing schemes,in:Proceeding of EUROCRYPT_92,Springer-Verlag,Berlin,1992:1-20.

[4]Desmedt Y,Frandkel Y.Shared generation of authentica-tors and signatures[A].In:Advances in Cryptology-CRYPTO'91[C].1991:457-469.

[5]Tzer-Shyong Chen,Jen-Yan Huang,Tzer-long Chen.An efficient undeniable group-oriented signature scheme.Applied Mathematics and Computation165,2005:95-102.

【门限签名】推荐阅读：

门限效应05-19

门限检测08-25

门限面板模型05-25

签名励志向上的签名05-18

承诺个性签名承诺个性签名06-07

经典语句个性签名 - 经典语句个性签名06-07

在线签名08-30

伤心签名08-30

冷酷签名07-06

淘宝签名07-24

>> 查看更多相关文档