数字签名与认证协议.ppt

《数字签名与认证协议.ppt》由会员分享，可在线阅读，更多相关《数字签名与认证协议.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数字签名与认证协议现在学习的是第1页，共21页M进行签名：SigK(x,k)=(,),其中，=k(modp),=(x-)k-1(modp-1)对x,Fp*和Zp-1,验证签名定义为 Ver(x,)=真（true)x(modp)对EIGamal签名方案安全性的讨论：若Oscar在不知道a的情况下企图伪造一个给定消息x的签名：Sigoscar(x,k)=(,)(1)Oscar先选定一个，然后企图找，这样，他就必须解一个关于未知数的方程：x(modp)这个方程是一个已知无可行解法的难处理问题！现在学习的是第2页，共21页(2)Oscar先选定一个，使其满足：x(modp)，于是，-x(modp)，这

2、样，他就必须计算离散对数 log(-x)=?,这自然是难处理的问题！(3)若两者,都被 Oscar首先选定,然后企图解出一个随机消息x,使得x(modp)，于是Oscar利用这种方式也不能伪造随机消息的签名。(4)Oscar同时选择,和x来伪造签名问题:假设i和j是整数,0=I=p-2,0=j=p-2,且(j,p-1)=1,先完成下列计算:ij(modp)-j-1(modp-1)x=-ij-1(modp-1)(其中j-1是用模p-1来计算的)现在学习的是第3页，共21页 可以证实(,)是一个消息x的有效签名:例子:假设p=467,=2和=132,它们为Bob公开的签名方案中的参数。Oscar利

3、用这些参数伪造对一随机信息x的签名：选择i=99和j=179，那么j-1(modp-1)=151，计算出下列的x,:)(mod)(mod)(mod)(mod)(mod)(1111pppppxijijijjjijijijijijiji117)467(mod132217999ji现在学习的是第4页，共21页那么（117，41）是消息331的一个有效签名。验证：因此，这个伪造的签名有效！（5）其他类型的伪造签名：Oscar依据Bob已签名的消息来做伪签名。假设(,)是一个消息x的有效签名，那么Oscar可以用此来伪签其它消息：设h,i,j为整数,0=h,i,j=p-2且 ,计算331)466(mod

4、419941)466(mod151117x)467(mod30322)467(mod30311713233141117x1)1,(pjh现在学习的是第5页，共21页（其中 是模p-1算出）然后可验证出因此，为假消息 的一个有效签名讨论两个问题：（1）用EIGamal方案计算一个签名时，使用的随机数k为什么不能泄露？（2）若Bob用相同的值来签名不同的两份消息，Oscar能否攻破这个体制？)1(mod)()1(mod)()(mod11pjhihxxpjhpjih1)(jh)(mod px),(x现在学习的是第6页，共21页2 数字签名标准数字签名标准 公布于1994年5月19日的联邦记录上，并于

5、1994年12月1日采纳为标准DSS。DSS为EIGamal签名方案的改进。DSS：p为512bit的素数，q为160比特的素数，且q|p-1,Fp*,且为模p的q次单位根。消息集合P=Fp*，签名集合A=FqFq,定义K=（p,a,)|=a(modp),值p,q,和是公开的，a是保密的。取xP,对K=(p,q,a,)和一个（秘密）随机数k(1=k=q-1),定义 SigK(x,k)=(,),其中，=k(modp)（modq),=(x+)k-1(modq)对xFp*和,Fq来说,按下述计算来验证签名的真伪：现在学习的是第7页，共21页 注：1*.DSS的使用涉及到Smart卡的使用,要求短的签

6、名。DSS以一个巧妙的方法修改了EIGamal方案，使得签名160bits消息产生一个320bit的签名，但是计算使用了512比特的模p.2*.要求 在整个签名算法中，如果计算了一个值 ,程序自动拒绝，并且产生一个新的随机值计算新的签名，事实上，的发生概率大约为2-160.)(mod)(mod1211qeqxe)(mod)(mod),(21qpxVeeerK真)(mod(mod)(mod,)()(mod21111pqpkaxqaxee事实上)(mod0p)(mod0p)(mod0p现在学习的是第8页，共21页3*.DSS是一个产生签名比验证签名快得多的方案，验证签名太慢！4*.Smart卡的应

7、用！Smart卡有有限的处理能力，但是能与计算机进行通信。人们企图设计一种让Smart卡仅作小量运算的签名方案。该方案必须完成签名、验证签名两部分，而且方便安全。用DSS签名的例子：假设取q=101，p=78*9+1=7879，3为F7879的一个本原元，所以能取=378（mod7879)=170为模p的q次单位根。假设a=75，那么a(mod7879)=4567.现在,假设Bob想签名一个消息x=1234，且他选择了随机值k=50，可算得k-1(mod101)=99,签名算出:=(17050(mod7879)(mod101)=2518(mod101)=94现在学习的是第9页，共21页=(12

8、34+75*94)99(mod101)=97签名为（1234，94，97）。验证：-1=97-1（mod101)=25,e1=1234*25(mod101)=45,e2=94*25(mod101)=27(17045*456727(mod7879)(mod101)=2518(mod101)=94因此，该签名是有效的。现在学习的是第10页，共21页3 一次签名一次签名 任何单向函数都可用来构造一次签名方案。该签名对一个消息来说，唯一对应着一个确定的签名。这样的签名可验证任意多次。Lamport方案：设k为一个正整数，P=0,1K,设f:YZ是一个单向函数，签名集合A=YK，对于1=i=k,j=0,

9、1来说，yijY可随机地选择。选后，可算得 Zij=f(yij)1=i=k,j=0,1 密钥K由2k个y值和2k个Z值组成，y值保密而Z值公开.消息x=x1x2.xk(kbit串）。对于K=（yij,Zij|1=i=k,j=0,1)现在学习的是第11页，共21页定义其中，yixi=ai,f(ai)=Zixi验证：注：1*.待签名的消息为一个二进制 元组,每一个都单独签名.这个特征决定了“一次签名”2*.验证是简单的检查:签名结果的每一个元素是相应公开钥元素的愿象.例子:取单向函数f(x)=x(modp),设p=7879(素数),3为F7879的本原元,定义f(x)=3x(mod7879)假设B

10、ob想签名3比特消息,他选择了6个(秘密的)随机数:),.,(),.,(221121kxkxxkKyyyxxxSigKiZafaaaxxxVixiikkerK1)(),.,;,.,(2121真现在学习的是第12页，共21页y10=5831,y11=735,y20=803,y21=2467,y30=4285,y31=6449在f的作用下计算y的像:z10=2009,z11=3810,z20=4672,z21=4721,z30=268,z31=5732将这些Z值公开。现在Bob打算签名消息x=(1,1,0),那么对的签名为(y11,y21,y30)=(735,2467,4285).验证签名:373

11、5(mod7879)=3810 32467(mod7879)=4721 34285(mod7879)=268 因此,该签名有效。注：该方案，仅能用于签一个消息！一次，无法伪造。现在学习的是第13页，共21页4 不可否认的签名不可否认的签名（Chaum和Van Antwerprn 1989年提出）该签名的特征是：验证签名者必须与签名者合作。验证签名是通过询问-应答协议来完成。这个协议可防止签名者Bob否认他以前做的签名。一个不可否认的签名方案有三个部分组成：设p=2q+1是一个素数，它满足q为素数，且Fp中的对数问题是难解的。,且阶为q,取1=a=q-1,定义 ,G表示阶为q的FP*的子群。易见

12、G=,（事实上G由模p的二次剩余组成）设P=A=G，且定义K=（p,a,)|=a(modp),值p,和是公开的，a是保密的。*pF)(modpa现在学习的是第14页，共21页对K=（p,a,)和消息xG,定义y=SigK(x)=xa(modp)易见y G。按如下协议完成验证：（1）.Alice 随机选择（2）Alice计算 ,且将C送给Bob.（3）Bob计算 ,且d将送给Alice.（4）Alice接受y作为一个有效签名,当且仅当 对上述这个签名方案，要证明以下两点：1）Alice将回接受按如上方案的有效签名2）Bob几乎不可否认经Alice 验证过的自己的签名。证明(1)：(alice接受

13、Bob的签名)。下面计算的所有指数都已做到模q约简.*21,qFee)(mod21pyCee)(mod)(mod1pCdqa)(mod21pxdee现在学习的是第15页，共21页知代入上式得刚好与协议（4）相符，故Alice接受Bob的签名。对于（2）Bob几乎不可否认经Alice验证过的自己的签名。相当于证明下述定 理。：若 ,那么Alice以概率1/(q-1)接受y作 为x的有效签名.证明:Bob对x做了签名y(=xa)给Alice后。Bob接受了Alice的一个询问 ,这个询问对应于q-1个有序对(e1,e2)。(原因是 一旦固定，e2=f(e1)。然而，Bob不知Alice选择了哪一对

14、(e1,e2)来构造出C。)(mod)(mod12111pypCdaeaea)(mod),(modppxyaa)(mod21pxdee)(mod pxya)(mod21pyCeeCGy,现在学习的是第16页，共21页如果 ,那么Bob能做的任何可能回答 ，刚好与q-1个可能的有序对(e1,e2)中的一个相对应。由 G=,所以对C,d,x,y来说，可设C=i,d=j,x=k,y=l,i,j,k,l ,考虑同余式：写出关于 的指数表示：等价于下述方程组：y)(mod pxyaGpCdqa)(mod()(mod1*qF)(mod)(mod)(),(mod2112121)(modpxdpydpyCee

15、qaeeee)(mod)(mod2121ppekejaelei现在学习的是第17页，共21页既然假设 而 y=2l，xa=(k)a=ak,所以lak,相当于说上述方程的系数行列式：知该方程组仅有唯一一组解。即对每一个dG,对于q-1个可能的有序对中（e1,e2），刚好有一个是正确的回答，Bob给Alice的一个回答d，将被验证的概率刚好为1/（q-1）。定理得证！)(mod)(mod2121qekejqaelei)(mod pxya)(mod01qaklkal现在学习的是第18页，共21页 下面讨论否认协议：目的：（1）Bob能使Alice相信一个无效的签名是伪造的.（2）Bob签名有效，而导

16、致Alice判决错误的概率为小概率事件。否认协议：(y?=xa)暂视为对的签名1）Alice 随机选取2）Alice计算 且将送给Bob,3）Bob计算 ,且将他回送Alice4）Alice验证5）Alice再随机选取6）Alice计算 ，且将他送给Bob7）Bob计算 ，且将他回送给Alice8）Alice验证*21,qFee)(mod21pyCee)(mod)(mod1pCdqa)(mod21pxdee)(mod21pyCff*21,qFff)(mod)(mod1pCDqa)(mod21pxDff现在学习的是第19页，共21页9)Alice推出 y是伪造的：如果 yxa(modp),且Al

17、ice和Bob都遵守否认协议，那么证明：注意,，而 又 ，从而有进一步有)(mod)()(1221pDfdefe)(mod)()(1212pDdeffe)(mod1pCda)(mod21pyCee)(mod pa)(mod)()(1212112pydfeaeefe)(mod)(mod)(mod)(mod)(1111212111121121111211211112pypypypydfaefefefaefefaaefaefefaefaefe现在学习的是第20页，共21页类似地，按如上方式推出 证毕。注注：我们不能假设遵守了否认协议，他可以想方设法构造d,D,来达到否认自己签过名的目的。然而，只要Alice严格遵守协议，Bob是无法否认的。可证。，假设yxa(modp)且Alice遵守否认协议，如果那么成立的概率为1-1/(q-1)。)(mod)(11112pyDfaeef)(mod)(mod2121pxDpxdffee)(mod)()(1212pDdeffe现在学习的是第21页，共21页