第10章数字签名-Read.ppt

1、第10章数字签名,数字签名特点：签名不可伪造；签名是可靠的；签名不可重用；签名不可改变；签名不可抵赖。,定义10.0.1：一个签名方案是一个5元组（M,A,K,S,V）,满足如下的条件：（1）M是一个可能消息的有限集；（2）A是一个可能签名的有限集；（3）密钥空间K是一个可能密钥的有限集；（4）对每一个k=（k1，k2）K，都对应一个签名算法SigS和验证算法VerV。每一个Sig:MA和Ver:MATRUE,FALSE是一个对每一个消息xM和每一个签名yA满足下列方程的函数：Ver(x,y)=（5）对每一个k，函数Sig和Ver都是多项式时间可计算的函数。Ver是一个公开函数，k1称作公钥；

2、而Sig是一个秘密函数，k2称作私钥，由用户秘密地保存。,10.1基于RSA和离散对数的签名体制,10.1.1RSA签名方案,系统参数：设n=pq,且p和q是两个大素数，则M=A=Zn,定义=（n,d,p,q,e）这里e和d满足ed1(mod(n)(是欧拉函数)公开密钥n,e.私有密钥p,q,d.签名算法:Sigk2(x)=y=xdmodn验证算法：Ver(x,y)=TRUEyex(modn).(x,y)ZnZn.,带加密的签名先签名再加密先加密再签名,10.1.2EIGAMAL签名方案及其一般化的模型,系统参数：设p是一大素数，g是Z的一个生成元，定义=（p,g,y,x）:y=gxmodp其

3、中xZ。公开密钥y,p,g私有密钥x签名算法：对于=（p,g,y,x）、随机数kZ和待签消息m,定义Sig(x,k)=(r,s).这里的r=gkmodp;s=(m-xr)k-1mod(p-1).（r,s）即为生成的签名。验证算法：Ver(m,r,s)=TRUEyrrs=gmmodp,EIGAMAL签名方案的安全性分析（1）本方案是基于离散对数问题的。（2）对于随机数k应注意两方面的情况.首先，k不能泄露，其次，随机数不能重复使用。（3）伪造签名攻击。一般ELGAMAL签名方案（1）系统初始化（2）签名方程Ax=Bk+Cmod(p-1)（3）验证方程yA=rBgCmodp,10.1.3DSS,系

4、统参数：设p是一512位到1024位的大素数，它满足Zp中的离散对数问题是难解决的，q是160位长的素数，且q|p-1，gZp是Zp域中的q次单位根。定义=（p,q,g,y,x）：y=gxmodp公开密钥：p,q,g,y私有密钥：x签名算法：对于随机数kZ和待签消息mZ,计算r=(gkmodp)modqs=(h(m)+xr)k-1modq,消息对（r,s）即为生成的签名。验证算法：Ver(m,r,s)=TRUE(ye2ge1modp)modq=r其中e1=h(m)s-1modq，e2=rs-1modq,10.1.4Lamport签名方案,系统参数：设k是一个正整数，P=0,1k，假设f:YZ是

5、一单向Hash函数，A=Yk，随机选择yijY这里1ik,j=0,1且zij=f(yij),1ik,j=0,1.私有密钥:yij，1ik,j=0,1公开密钥:zij，1ik,j=0,1签名算法：Sig(x1,xk)=(y1x1,ykxk)验证算法：Ver(x1,xk,a1,ak)=TRUEf(ai)=zixi,1ik,10.1.5不可否认签名方案,系统参数：设p=2q+1是一个素数，这里的q是素数且Zp中的离散对数问题是难解决的，是Z域中的q次单位根，aq-1,设G表示阶为q的Z的乘法子群,M=A=G，且定义=（p,a）:amodp私有密钥a，公开密钥p,。签名算法：设待签消息为xG,y=Si

6、g(x)=xamodp，这里yG。验证协议：.A随机选取e1，e2Z。.A计算c=ye1e2modp且把它传给B.B计算d=cmodp，并将其传给A.A接受y，并将它作为一有效签名当且仅当d=xe1e1modp,否认协议如下：A随机选取e1，e2Z.A计算c=ye1e2modp且把它传给BB计算d=cmodp，并将其传给AA证实dxe1e2modpA随机选取f1,f2Z.A计算c=yf1f2modp且把它传给BB计算d=cmodp，并将其传给AA验证dxf1f2modpA推出y是伪造的当且仅当(d-e2)f1=(d-f2)e1modp,不可否认签名方案的安全性分析定理10.1.1：当yxamo

7、dp时，则A接受y作为x的真正签名的概率为1/q。定理10.1.2：若yxamodp且A和B都遵守否认协议，则(d-e2)f1=(d-f2)e1modp定理10.1.3：若y=xamodp且A遵守否认协议，又dxe1e2modp,dxf1f2modp则(d-e2)f1=(d-f2)e1modp成立的概率为1-1/q。,10.1.6故障停止式签名方案,系统参数签名算法：对于k=（1,2,a1,a2,b1,b2）和待签消息xZ,定义Sig(x)=(y1,y2),y1=a1+xb1modqy2=a2+xb2modq消息对(y1,y2)即为生成的签名。验证算法：对y=(y1,y2)ZZ,我们有Ver(

8、x,y)=TRUE12x=y1y2modp,伪造证明算法,10.1.7Schnorr数字签名方案,系统参数签名算法对于待签消息mZ，选择随机数k(1t,则要求用户重发签名，当E=0时，正确译码得到C和E.Ver(M,C)=TRUEM=CJ+EW,安全性分析与改进Harn攻击Alabhadi-Wieker攻击,10.6批验证协议,安全的批验证协议需满足如下的条件：签名者在签名过程中一次产生多个消息的签名；多个签名的有效性由签名验证者一次验证完成；多个有效的签名一定满足批验证协议中的批验证原则；在批验证协议中有效的多个签名一定是有效的签名。,HARN非交互式批验证协议系统参数：设p是一512位到1

9、024位的大素数，它满足Z中的离散对数问题是难解决的，q是160位长的素数，且q，gZ是Z域中的q次单位根。定义=（p,q,g,y,x）:y=gmodp,公开密钥p,q,g,y,私有密钥x。签名算法：对于待签的消息m(i=1,2,t)，签名者i随机选取kZ，计算r=gmodp,s=rk-h(m)xmodq,r,s(i=1,2,t)即为生成的签名。批验证算法：验证者收到消息的签名r,s,r,s,r,s后，验证Ver(m,s,r)=TRUE=gymodpmodq,N-M-R-V交互式批验证协议系统参数：设p是一512位到1024位的大素数，它满足Z中的离散对数问题是难解决的，q是160位长的素数，且q，gZ是Z域中的q次单位根。定义=（p,q,g,y,x）:y=gmodp公开密钥p,q,g,y，私有密钥x。签名算法：对于消息m(i=1,2,t)，签名者i随机