数字签名Read课件

*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2020/9/14,#,第10章 数字签名,数字签名特点：,签名不可伪造；,签名是可靠的；,签名不可重用；,签名不可改变；,签名不可抵赖。,定义10.0.1：一个签名方案是一个5元组（M,A,K,S,V）,满足如下的条件：,（1）M是一个可能消息的有限集；,（2）A是一个可能签名的有限集；,（3）密钥空间K是一个可能密钥的有限集；,（4）对每一个k=（k1，k2）K，都对应一个签名算法Sig S和验证算法Ver V。每一个Sig:MA和Ver:M ATRUE,FALSE是一个对每一个消息x M和每一个签名y A满足下列方程的函数：,Ver(x,y)=,（5）对每一个k，函数Sig和Ver都是多项式时间可计算的函数。Ver是一个公开函数，k1称作公钥；而Sig是一个秘密函数，k2称作私钥，由用户秘密地保存。,10.1基于RSA和离散对数的签名体制,10.1.1RSA签名方案,系统参数：设n=pq,且p和q是两个大素数，则 M=A=Z,n,定义=（n,d,p,q,e）这里e和d 满足ed,1(mod(n)(是欧拉函数),公开密钥 n,e.,私有密钥 p,q,d.,签名算法:Sig,k2,(x)=y=x,d,mod n,验证算法：Ver(x,y)=TRUE,y,e,x,(mod n).(x,y),ZnZn.,带加密的签名,先签名再加密,先加密再签名,10.1.2 EIGAMAL签名方案及其一般化的模型,系统参数：设p是一大素数，g是Z的一个生成元，定义=（p,g,y,x）:y=g,x,mod p其中x,Z。,公开密钥 y,p,g,私有密钥 x,签名算法：对于=（p,g,y,x）、随机数k,Z和待签消息m,定义Sig(x,k)=(r,s).这里的r=g,k,mod p;s=(m-xr)k,-1,mod(p-1).,（r,s）即为生成的签名。,验证算法：Ver(m,r,s)=TRUE,y,r,r,s,=g,m,mod p,EIGAMAL签名方案的安全性分析,（1）本方案是基于离散对数问题的。,（2）对于随机数k应注意两方面的情况.首先，k不能泄露，其次，随机数不能重复使用。,（3）伪造签名攻击。,一般ELGAMAL签名方案,（1）系统初始化,（2）签名方程,Ax=Bk+Cmod(p-1),（3）验证方程,y,A,=r,B,g,C,mod p,10.1.3 DSS,系统参数：设p是一512位到1024位的大素数，它满足Zp中的离散对数问题是难解决的，q是160位长的素数，且q|p-1，g,Zp是Zp域中的q次单位根。定义=（p,q,g,y,x）：y=g,x,mod p,公开密钥：p,q,g,y,私有密钥：x,签名算法：对于随机数k,Z和待签消息m,Z,计算r=(g,k,mod p)mod q,s=(h(m)+xr)k,-1,mod q,消息对（r,s）即为生成的签名。,验证算法：Ver(m,r,s)=TRUE,(y,e2,g,e1,mod p)modq=r,其中 e1=h(m)s,-1,modq，e2=r s,-1,modq,10.1.4Lamport签名方案,系统参数：设k是一个正整数，P=0,1,k,，假设f:Y,Z是一单向Hash函数，A=Y,k,，随机选择y,ij,Y这里1,i,k,j=0,1且z,ij,=f(y,ij,),1,i,k,j=0,1.,私有密钥:y,ij,，1i k,j=0,1,公开密钥:,z,ij，,1,i,k,j=0,1,签名算法：Sig(x,1,x,k,)=(y,1x1,y,kxk,),验证算法：,Ver(x,1,x,k,a,1,a,k,)=TRUE,f(a,i,)=z,ixi,1,i,k,10.1.5不可否认签名方案,系统参数：设p=2q+1是一个素数，这里的q是素数且Zp中的离散对数问题是难解决的，,是 Z域中的q次单位根，,a,q-1,设G表示阶为q的Z的乘法,子群,M=A=G，且定义,=（p,a）:,a,mod p,私有密钥a，,公开密钥 p,。,签名算法：设待签消息为x,G,y=Sig(x)=x,a,modp，这里y,G。,验证协议：.A随机选取e1，e2,Z。,.A计算c=y,e1,e2,mod p且把它传给B,.B计算d=c modp，并将其传给A,.A接受y，并将它作为一有效签名当且仅当,d=x,e1,e1,mod p,否认协议如下：,A随机选取e1，e2 Z.,A计算c=y,e1,e2,mod p且把它传给B,B计算d=c modp，并将其传给A,A证实d,x,e1,e2,modp,A随机选取f1,f2 Z.,A计算c=y,f1,f2,modp且把它传给B,B计算d=c modp，并将其传给A,A验证d,x,f1,f2,modp,A推出y是伪造的当且仅当,(d,-e2,),f1,=(d,-f2,),e1,mod p,不可否认签名方案的安全性分析,定理10.1.1：当y,x,a,mod p时，则A接受y作为x的真正签名的概率为1/q。,定理10.1.2：若y,x,a,mod p 且A和B都遵守否认协议，则,(d,-e2,),f1,=(d,-f2,),e1,mod p,定理10.1.3：若y=x,a,mod p且A遵守否认协议，又 dx,e1,e2,mod p,d,x,f1,f2,modp,则,(d,-e2,),f1,=(d,-f2,),e1,mod p,成立的概率为1-1/q,。,10.1.6故障停止式签名方案,系统参数,签名算法,：对于k=（1,2,a1,a2,b1,b2）和待签消息x Z,定义Sig(x)=(y1,y2),y1=a1+xb1 modq y2=a2+xb2 modq 消息对(y1,y2)即为生成的签名。,验证算法,：对y=(y1,y2)ZZ,我们有,Ver(x,y)=TRUE,12,x,=,y1,y2,modp,伪造证明算法,10.1.7 Schnorr数字签名方案,系统参数,签名算法 对于待签消息m,Z，选择随机数k(1k2,160,)，在此阶下，基于离散对数问题的体制是否安全有待进一步研究。,（2）Schnorr系统的签名文较短，e的长度由函数h决定。s的长度小于|q|。若h的输出长度为128位，|q|为160位，则其签名长度为288位，比EIGAMAL系统的1024位小.,（3）Schnorr首先提出r=g,k,mod p可以事先计算，由于k是与m无关的随机数，故Schnorr系统在签名中只需一次乘法及减法(模运算)，比EIGAMAL系统快很多。因此，Schnorr数字签名方案特别适合于智能卡的应用。,10.2 群签名,一般说来，群签名方案由组、组成员（签名者）、签名接受者（签名验证者）和权威(Authority)或GC(Group Center)组成，具有如下特点：,(1)只有组中的合法用户才能对消息签名，并产生群签名；,（2）签名的接收者能验证群签名的有效性；,（3）签名的接收者不能辨认是谁的签名；,(4)一旦发生争论，群签名的权威或组中所有成员的联合可以辨别出签名者。,K-P-W可变群签名方案,系统参数；选择,n=pq=(2fp+1)(2fq+1),，这里的,p,q,f,p和q,为相异的大素数，g的阶为f,和d为整数，且,d=1mod,(n),gcd(,(n)=1，h为安全的hash函数，ID,G,为GC的身份消息。,签名组的公钥：(n,g,f,h,ID,G,)，,签名组的私钥：(d,p,q)。,设ID,A,为组成员A的身份消息，A随机选取s,A,(0,f)并将消息(ID,A,g,sA,mod n)发送给GC。GC计算x,A,=(ID,G,),-d,mod n，并将x,A,秘密地传送给成员A。则A的私有密钥：(x,A,s,A,)。,签名算法：对于待签消息m：组中成员A随机选择整数(r1,r2)，计算,V=g,r1,r2,mod n,e=h(V,m)则群签名为（e,z1,z2），,其中z1=r1+s,A,e(mod f),z2=r2x,A,e,mod n,签名验证算法：e=h(V,m),这里的V=(ID,G,),e,g,z1,z2,(mod n).,身份验证算法：g,z1,=(Vr2,-,)(g,sA,),e,mod n，其中 r2=z2x,A,-e,(mod n),K-P-W可变群签名方案的安全性分析,（1）当p和q具有相同的比特位时，攻击者可以采用对参数n进行因子分解的方法。分解n=pq=(2fp+1)(2fq+1)只需要 2 次整数乘法，这里的x为x的比特位数。,（2）在组中成员诚实的情况下，虽说权威能辨别出签名者签名。可是当组中的成员伪造或共谋伪造时，仍能生成有效的签名。设组中成员A随机选取整数a和b,计算 sA=ab mod f 和 sA=sA+b mod f，将(sA,sA)作为A的私钥,公钥为yA=g,sA,mod n,yA=g,sA,mod n,从GC处秘密地收到私钥 xA和xA，则有g,bd,=xA(xA),-1,mod n,ID,G,-d,=xA(g,bd,),a,mod n，于是可以得到g,d,=(g,bd,),b,-1,mod n。对于任意的sA,由于A知道ID,G,-d,和g,d,，故可算出私钥（xA,sA）.对任意的消息，都可以产生有效的群签名，而权威无法辨认签名用户。如果组中两成员共谋，利用上述方法同样可产生有效的群签名,而权威无法辨认签名用户。,10.3 多重数字签名方案,广播多重数字签名方案,（Broadcasting Multisignature）,消息发送者,U,U,U,签名收集者,签名验证 者,有序多重数字签名方案,(Sequential Multisignature),EIGAMAL有序多重数字签名方案,（1）系统初始化,（2）签名算法,签名者Ui(i=2,n)收到上一签名者发送的待签消息（m，（s,i-1,r,i-1,）（s=0）后做如下的工作：首先随机选取k,i,1,p-1，计算r,i,=g,k,i,modp，si=s,i-1,+mxi-rikimod,(p)这里的 m=h(m)，最后将签名消息(m,(si,ri)发给下一个签名者Ui+1，并将ri发给Ui以后的签名者和签名验证者。,（3）验证算法,验证包括两方面的要求：签名者Ui(i=2,n)要对U1,U2,Ui-1的签名的有效性进行验证；验证者Uv要对所有签名者U1,U2,Un的签名进行验证.,对于Ui(i=2,n)通过验证等式g =modp是否成立，来判断U1,U2,Ui-1的签名是否有效。若等式成立则有效，反之无效。,对于验证者Uv通过验证等式是否成立来判断U1,U2,Un的签名是否有效。若等式成立则有效，反之无效。,HARN广播多重数字签名方案,（1）系统初始化,（2）单用户签名的产生,（3）单用户签名的验证,（4）多重签名的产生,（5）多重签名的验证,10.4代理数字签名体制,定义10.4.1：设A,B是某个数字签名体制（M,A,K,S,V）的两个用户，他们的私钥和公钥对分别是（x,y),（x,y）.如果满足下列条件：,（1）A利用它的秘密密钥x计算出一个数，并将秘密交给B;,（2）任何人（包括B）在试图求出x时，不会对他有任何帮助；,（3）B可以用和x生成一新的签名密钥；,（4）存在一个公开的验证算法Ver，使得对任何s和mM都有Ver(y,s,m)=TRUEs=Sig(,m);,（5）任何人在试图求出x,x,或时，任何数字签名Sig(,m)都不会对他产生帮助。,代理签名体制具有下面的特定的安全特性：,可区别性。任何人都可区别代理签名和正常的签名。,不可伪造性。只有原始签名者和指定的代理签名者能够产生有效的代理签名。,代理签名者的不符合性。代理签名者必须创建一个能检测到是代理签名的有效代理签名。,可验证性。从代理签名中，验证者能够相信原始的签名者认同了这份签名消息。