(现代密码学课件)07数字签名.ppt_163文库

资源描述

1、第第七七章章数字签字和密码协议数字签字和密码协议一一数字签字的基本概念数字签字的基本概念二二数字签字标准数字签字标准三三其他签字方案其他签字方案四四认证协议认证协议五五身份证明技术身份证明技术六六其他密码协议其他密码协议1一、一、数字签字的基本概念数字签字的基本概念2数字签字应具有的性质数字签字应具有的性质n能够验证签字产生者的身份，以及产生能够验证签字产生者的身份，以及产生签字的日期和时间签字的日期和时间n能用于证实被签消息的内容能用于证实被签消息的内容n数字签字可由第三方验证，从而能够解数字签字可由第三方验证，从而能够解决通信双方的争议决通信双方的争议3数字签字的产生方式数字签字的产生方

2、式n由加密算法产生数字签字由加密算法产生数字签字n由签字算法产生数字签字由签字算法产生数字签字6由加密算法产生数字签字由加密算法产生数字签字n单钥加密单钥加密MMEKMEKDK无法实现无法实现数字签名数字签名n 向向B保证收到的消息确实来自保证收到的消息确实来自An B恢复恢复M后，可相信后，可相信B未被窜改，否则未被窜改，否则B将得到无将得到无意义的比特序列意义的比特序列7由加密算法产生数字签字由加密算法产生数字签字n公钥加密公钥加密MMESKAMEASKDPKA只有A才能用SKA加密，可使B相信消息来自A,不提供保密性MMESKAMEASKDPKAEPKBMEEABSKPKDSKBMEAS

3、K提供保密性和认证性8由加密算法产生数字签字由加密算法产生数字签字nRSARSA签字体制签字体制n体制参数体制参数n大素数大素数p,qp,q，n=pn=pq,y(n)=(p-1)(q-1)q,y(n)=(p-1)(q-1)。选整数。选整数1e y(n),1e y(n),且且gcd(e,y(n)=1;gcd(e,y(n)=1;计算计算d d满足满足de1 de1 mod y(n).e,nmod y(n).e,n为公开密钥，为公开密钥，d,nd,n为秘密密钥。为秘密密钥。n签字过程签字过程nS=MS=Md d mod n mod nn验证过程验证过程nM=SM=Se e mod n mod nn实

4、际应用中加密是对实际应用中加密是对H(M)H(M)进行的。进行的。9由加密算法产生数字签字由加密算法产生数字签字n外部保密外部保密n数字签字直接对需要签字的消息生成数字签字直接对需要签字的消息生成n内部保密内部保密n数字签字对已加密的消息产生数字签字对已加密的消息产生n外部保密有利于争议的解决。外部保密有利于争议的解决。10由签字算法产生数字签字由签字算法产生数字签字签字体制签字体制=(M,S,K,V)M:明文空间，明文空间，S:签字的集合，签字的集合，K:密钥空间，密钥空间，V:证实函数的值域，证实函数的值域，由真和伪组成。由真和伪组成。(1)签字算法：签字算法：对每一对每一m M和和每一每

5、一k K，易于计算对，易于计算对m的签字的签字 s=Sigk(m)S 签字密钥是秘密的，只有签字人掌握；签字密钥是秘密的，只有签字人掌握；(2)验证算法：验证算法：true,()(,)false,()kkksSigmVer s msSigm11由签字算法产生数字签字由签字算法产生数字签字体制的安全性体制的安全性：从：从M和其签字和其签字S难于推出难于推出K或或伪造一个伪造一个M使使M和和S可被证实为真。可被证实为真。与消息加密不同点与消息加密不同点：消息加密和解密可能是一：消息加密和解密可能是一次性的，它要求在解密之前是安全的；而一次性的，它要求在解密之前是安全的；而一个签字的消息可能作为一个

6、法律上的文件，个签字的消息可能作为一个法律上的文件，如合同等，很可能在对消息签署多年之后才如合同等，很可能在对消息签署多年之后才验证其签字，且可能需要多次验证此签字。验证其签字，且可能需要多次验证此签字。12数字签字的执行方式数字签字的执行方式n直接方式直接方式数字签字的执行过程只有通信的双方参数字签字的执行过程只有通信的双方参与，并假定双方有共享的秘密密钥或者与，并假定双方有共享的秘密密钥或者接收一方知道发送方的公开钥。接收一方知道发送方的公开钥。n缺点：方案的有效性取决于发方密钥的缺点：方案的有效性取决于发方密钥的安全性。安全性。n发方可声称秘密钥丢失或被窃发方可声称秘密钥丢失或被窃13

7、数字签字的执行方式数字签字的执行方式n直接方式直接方式数字签字的执行过程只有通信的双方参与，数字签字的执行过程只有通信的双方参与，并假定双方有共享的秘密密钥或者接收一并假定双方有共享的秘密密钥或者接收一方知道发送方的公开钥。方知道发送方的公开钥。n缺点：方案的有效性取决于发方密钥的安缺点：方案的有效性取决于发方密钥的安全性。全性。n发方可声称秘密钥丢失或被窃发方可声称秘密钥丢失或被窃14数字签字的执行方式数字签字的执行方式n具有仲裁方式的数字签字具有仲裁方式的数字签字1.发方发方X对发往收方对发往收方Y的消息签字的消息签字2.将消息和签字先发往仲裁者将消息和签字先发往仲裁者A3.A对消息和签

8、字验证完后，再连同一个表示对消息和签字验证完后，再连同一个表示已通过验证的指令一起发给已通过验证的指令一起发给Y.15具有仲裁方式的数字签字具有仲裁方式的数字签字n例例1：1.XA:M|2.AY:)(|MHIDEXKXA|)(|TMHIDEMIDEXKXKXAAYE：单钥加密算法：单钥加密算法KXA,KAY:A与与X和和Y的共享密钥的共享密钥M：消息：消息T：时戳：时戳IDX：X的身份的身份H(M)：M的杂凑值的杂凑值A必须获得X和Y的高度信任X相信A不会泄漏KXA，并且不会X的签字Y相信A只有对中的杂凑值及X签字验证无误后才将其发给YX，Y都相信A可公正的解决争议|)(|TMHIDEMID

9、EXKXKXAAY16具有仲裁方式的数字签字具有仲裁方式的数字签字n例例21.XA:IDX|2.AY:|)(|TMEHIDEMEIDEXYXAXYAYKXKKXK)(|MEHIDEMEXYXAXYKXKKX对M的签字X和Y的共享密钥此方案提供了对此方案提供了对M M的保密性的保密性和前一方案相同，仲裁者可和发方共谋否认发方曾发过和前一方案相同，仲裁者可和发方共谋否认发方曾发过的消息，也可和收方共谋产生发方的签字的消息，也可和收方共谋产生发方的签字17具有仲裁方式的数字签字具有仲裁方式的数字签字n例例3|:.2|:.1TMEEIDEYAMEEIDEIDAXXYAXYXSKPKXSKSKPKXSK

10、XX的私钥Y的公钥18二、二、数字签名标准数字签名标准Digital Signature Standard(DSS)19概况概况n由由NIST1991年公布年公布n1993年公布修改版年公布修改版n美国联邦信息处理标准美国联邦信息处理标准FIPS PUB 186n签名长度签名长度320比特比特n只能用于数字签字，不能用于加密只能用于数字签字，不能用于加密20DSS的基本方式的基本方式M|HESKAM)(MHEASKHDPKA比较RSARSA签字签字DSSDSS签字签字M|HSKAMsHPKG比较VerPKGk随机数rPKASig全局公开钥21数字签字算法数字签字算法DSAn在在Elgamal和

11、和Schnorr两个方案基础上设计的两个方案基础上设计的n算法描述算法描述:(a)全局公钥全局公钥(p,q,g)p：是：是2L-1 p 2L中的大素数，中的大素数，512 L 1024，L是是64的倍数的倍数；q：p-1的素因子，且的素因子，且2159 q 2160，即字长，即字长160比特；比特；g：g=h(p-1)/q mod p，且，且1 h 1。(b)用户秘密钥用户秘密钥 x：x为在为在0 xq内的随机数。内的随机数。(c)用户公钥用户公钥 y：y=gx mod p。(d)用户每个消息用的秘密随机数用户每个消息用的秘密随机数k：在：在0kq内的随机数内的随机数22数字签字算法数字签字算

12、法DSA(e)签字过程：对消息签字过程：对消息M，其签字为，其签字为S=Sigk(M,k)=(r,s)，r (gk mod p)mod q s k-1(H(M)xr)mod q(f)验证过程：计算验证过程：计算 w =s-1 mod q;u1=H(M)w mod q;u2=rw mod q;v=(gu1yu2)mod p mod q。Ver(M,r,s)=真真 v=rrqpgqpgqpggvksxrMHxrwwMHmod)mod(modmodmodmod)(1)()(23三、三、其他签字方案其他签字方案24离散对数签字体制离散对数签字体制n体制参数体制参数 p p：大素数：大素数 q q：(p

13、 p1)1)或或p p-1-1的大素因子的大素因子 g g：ggR RZ Zp p*,g,gq q=1 mod p=1 mod p。x x：用户秘密钥：用户秘密钥,x x为在为在1 1xqxq内的随机数。内的随机数。y y：用户公钥：用户公钥 g gx x=mod=mod p p。25离散对数签字体制离散对数签字体制n签字产生过程签字产生过程1.1.计算计算m m的杂凑值的杂凑值2.2.选择随机数选择随机数k:1kqk:1kq，计算，计算r rg gk k mod p mod p3.3.从签字方程从签字方程akak=b+cxb+cx mod q mod q中解出中解出s.s.（r,sr,s)为

14、数字签字。为数字签字。abcrrH(m)rH(m)H(m)rH(m)ss s H(m)srsrsH(m)111126离散对数签字体制离散对数签字体制n签字验证过程签字验证过程)(mod),(,(pygrTuremsryVercba27Elgamal签字体制签字体制n离散对数签字体制的特例离散对数签字体制的特例n体制参数体制参数 p p：一个大素数；：一个大素数；g g：是：是Z Zp p中乘群中乘群Z Zp p*的一个生成元或本原元素；的一个生成元或本原元素；M M：消息空间，为：消息空间，为Z Zp p*；S S：签字空间，为：签字空间，为Z Zp p*Z Zp p1 1；x x：用户秘密钥

15、：用户秘密钥x x Z Zp p*；y y：用户公钥用户公钥，y y g gx x modmod p p p p，g g，y y为公钥，为公钥，x x为秘密钥。为秘密钥。28Elgamal签字体制签字体制n签字过程：给定消息签字过程：给定消息M M，进行下述工作。，进行下述工作。(a)(a)选择秘密随机数选择秘密随机数k k Z Zp p*；(b)(b)计算计算 H H(M M)；(c)(c)计算计算 r=gr=gk k mod mod p ps=s=(H H(M M)xrxr)k k-1-1 mod(mod(p p1)1)(r,sr,s)作为签字作为签字.29Elgamal签字体制签字体制n

16、验证过程：验证过程：收信人收到收信人收到M M，(r,sr,s)，先计算，先计算H H(M M)，并按下，并按下式验证式验证 VerVerk k(H H(M M),r,s,r,s)=)=真真 y yr rr rs s g gH(M)H(M)mod mod p p 因为因为y yr rr rs s g grxrxg gs sk k g g(rx+sk)(rx+sk)mod mod p p，(rx+skrx+sk)H H(M M)mod(p)mod(p1)1)故有故有y yr rr rs s g gH(M)H(M)mod mod p p30Schnorr签字体制签字体制n 体制参数体制参数 p,q

17、p,q：大素数，：大素数，q|p-q|p-1 1。q q是大于等于是大于等于160 bits160 bits的整的整数，数，p p是大于等于是大于等于512 bits512 bits的整数，保证的整数，保证Z Zp p中求解离中求解离散对数困难；散对数困难；g g：Z Zp p*中元素，且中元素，且g gq q 1 mod1 mod p p；x x：用户密钥：用户密钥1 1 x x q q；y y：用户公钥：用户公钥y y g gx x mod mod p p。消息空间消息空间M M=Z=Zp p*，签字空间，签字空间S S=Z=Zp p*Z Zq q；密钥空间；密钥空间K K=(p,q,g,

18、x,yp,q,g,x,y):y:y g gx x mod mod p p 31Schnorr签字体制签字体制n签字过程：令待签消息为签字过程：令待签消息为M M，对给定的，对给定的M M做做下述运算：下述运算：(a)(a)发用户任选一秘密随机数发用户任选一秘密随机数k k Z Zq q (b)(b)计算计算 r r g gk k mod mod p p s s k kxexe mod mod p p 式中式中 e=H(re=H(r|M)M)(c)(c)签字签字S=SigS=Sigk k(M M)=(e,se,s)32Schnorr签字体制签字体制验证过程验证过程：收信人收到消息：收信人收到消息

19、M M及签字及签字S=S=(e,se,s)后后(a)(a)计算计算r r g gs sy ye e mod mod p p 而后计算而后计算H H(r r|M M)。(b)(b)验证验证 VerVer(M,r,sM,r,s)H H(r r|M M)=e=e 因为，若因为，若(e|s)(e|s)是是M M的合法签字，则有的合法签字，则有g g s sy y-e e g gk-xek-xeg gxexe g gk k r r mod mod p p。33Schnorr签字体制签字体制SchnorrSchnorr签字与签字与ElGamalElGamal签字的不同点：签字的不同点：在在ElGamalE

20、lGamal体制中，体制中，g g为为Z Z*p p的本原元素；而在的本原元素；而在SchnorrSchnorr体制中，体制中，g g为为Z Zp p*中子集中子集Z Zq q*的本原元素，它的本原元素，它不是不是Z Zp p*的本原元素。显然的本原元素。显然ElGamalElGamal的安全性要高于的安全性要高于SchnorrSchnorr。SchnorrSchnorr的签字较短，由的签字较短，由|q q|及及|H H(M M)|)|决定。决定。在在SchnorrSchnorr签字中，签字中，r=gr=gk k mod mod p p可以预先计算，可以预先计算，k k与与M M无关，因而签字

21、只需一次无关，因而签字只需一次mod mod q q乘法及减法。乘法及减法。所需计算量少，速度快。所需计算量少，速度快。34四、四、认证协议认证协议Authentication Protocols35相互认证相互认证nA，B双方在建立共享密钥时需要考虑保双方在建立共享密钥时需要考虑保密性和实时性。密性和实时性。n保密性：会话密钥应以密文传送，因此保密性：会话密钥应以密文传送，因此双方应事先共享密钥或者使用公钥双方应事先共享密钥或者使用公钥n实时性实时性:防止重放防止重放n序列号方法序列号方法n时戳时戳n询问应答询问应答36序列号方法序列号方法n对交换的每一条消息加上序列号，序列对交换的每一条消

22、息加上序列号，序列号正确才被接收号正确才被接收n要求每个用户分别记录与其他每一用户要求每个用户分别记录与其他每一用户交互的序列号，增加用户负担，因而很交互的序列号，增加用户负担，因而很少使用少使用37时戳法时戳法nA收到消息中包含时戳，且收到消息中包含时戳，且A看来这一时看来这一时戳充分接近自己的当前时刻，戳充分接近自己的当前时刻，A才认为收才认为收到的消息是新的并接收到的消息是新的并接收n要求各方时间同步要求各方时间同步38询问应答询问应答n用户用户A向向B发出一个一次性随机数作为询发出一个一次性随机数作为询问，如果收到问，如果收到B发来的应答消息也包含一发来的应答消息也包含一正确的一次性随

23、机数，正确的一次性随机数，A就认为消息是新就认为消息是新的并接受之。的并接受之。39各种方法的比较各种方法的比较n时戳法不适用于面向连接的应用过程时戳法不适用于面向连接的应用过程n要求不同的处理器之间时间同步，所用的协要求不同的处理器之间时间同步，所用的协议必须是容错的以处理网络错误议必须是容错的以处理网络错误n协议中任何一方时钟出现错误失去同步，则协议中任何一方时钟出现错误失去同步，则敌手攻击的可能性增加敌手攻击的可能性增加n网络中存在延迟，不能期待保持精确同步，网络中存在延迟，不能期待保持精确同步，必须允许误差范围必须允许误差范围40各种方法的比较各种方法的比较n询问应答不适合于无连接的应

24、用过程询问应答不适合于无连接的应用过程n在传输前需要经过询问应答这一额外的握在传输前需要经过询问应答这一额外的握手过程，与无连接应用过程的本质特性不符。手过程，与无连接应用过程的本质特性不符。n无连接应用最好使用安全时间服务器提供同无连接应用最好使用安全时间服务器提供同步步41Needham-Schroeder协议协议2.4.)|(|1AsKBsKIDKENIDKEBAKDCAB1.IDA|IDB|N13.|AsKIDKEB2NESK5.)(2NfESK如果敌手获得了旧会话如果敌手获得了旧会话密钥，则可以冒充密钥，则可以冒充A A重重放放3 3，并且可回答，并且可回答5 5，成，成功的欺骗功的

27、B4.|APKABNEIDIDAS6|BBSASKPKNIDKNEEASA7BKNES47单向认证单向认证n不需要双方同时在线（电子邮件）不需要双方同时在线（电子邮件）n邮件接收者希望认证邮件的来源以防假冒邮件接收者希望认证邮件的来源以防假冒n分为单钥加密方法和公钥加密方法分为单钥加密方法和公钥加密方法48单钥加密单钥加密2.)|(|1AsKBsKIDKENIDKEBAKDCAB1.IDA|IDB|N13.|MEIDKESBKAsK不要求不要求B B同时在线，保同时在线，保证只有证只有B B能解读消息，能解读消息，提供对提供对A A的认证。不能的认证。不能防止重放攻击。防止重放攻击。49公钥加

28、密公钥加密AB|MEKEsBKsPK对发送消息提供保密性对发送消息提供保密性对发送消息提供认证性对发送消息提供认证性AB|)(|AASKSKPKIDTEMHEMASA对发送消息提供保密和认证性对发送消息提供保密和认证性AB|)(|AASKSKPKPKIDTEMHEMEASABA的证书50五、五、身份证明技术身份证明技术51身份证明技术身份证明技术传统的身份证明：传统的身份证明：一般是通过检验一般是通过检验“物物”的有效性来确认持该的有效性来确认持该物的的身份。徽章、工作证、信用卡、驾物的的身份。徽章、工作证、信用卡、驾驶执照、身份证、护照等，卡上含有个人驶执照、身份证、护照等，卡上含有个人照

29、片照片(易于换成指纹、视网膜图样、牙齿的易于换成指纹、视网膜图样、牙齿的X适用的射像等适用的射像等)。信息系统常用方式：信息系统常用方式：用户名和口令用户名和口令52交互式证明交互式证明两方参与两方参与示证者示证者P(Prover)，知道某一秘密，使，知道某一秘密，使V相信相信自己掌握这一秘密；自己掌握这一秘密；验证者验证者V(Verifier)，验证，验证P掌握秘密；每轮掌握秘密；每轮V向向P发出一询问，发出一询问，P向向V做应答。做应答。V检查检查P是是否每一轮都能正确应答。否每一轮都能正确应答。53交互证明与数学证明的区别交互证明与数学证明的区别n数学证明的证明者可自己独立的完成证数学

30、证明的证明者可自己独立的完成证明明n交互证明由交互证明由P产生证明，产生证明，V验证证明的有验证证明的有效性来实现，双方之间要有通信效性来实现，双方之间要有通信n交互系统应满足交互系统应满足n完备性：如果完备性：如果P知道某一秘密，知道某一秘密，V将接收将接收P的的证明证明n正确性：如果正确性：如果P能以一定的概率使能以一定的概率使V相信相信P的的证明，则证明，则P知道相应的秘密知道相应的秘密54Fiat-Shamir身份识别方案身份识别方案参数：参数：选定一个随机模选定一个随机模m=pq。产生随机数。产生随机数v，且使且使s2=v，即，即v为模为模m的平方剩余。的平方剩余。m和和v是公开的，

31、是公开的，s作为作为P的秘密的秘密55Fiat-Shamir身份识别方案身份识别方案(1)P(1)P取随机数取随机数r r(m m)，计算，计算x x=r r 2 2 mod m mod m，送给，送给V V；(2)V(2)V将一随机将一随机bit bit b b送给送给P P；(3)(3)若若b b=0=0，则，则P P将将r r送给送给V V；若；若b b=1=1，则，则P P将将y y=rsrs送给送给V V；(4)(4)若若b b=0=0，则，则V V证实证实x x=r r 2 2 mod mod m m，从而证明，从而证明P P知道，若知道，若b b=1=1，则，则B B证实证实 x

32、vxv=y y2 2 mod mod m m，从而证明，从而证明A A知道。知道。这是一次证明，这是一次证明，A A和和B B可将此协议重复可将此协议重复t t次，直到次，直到B B相信相信A A知道知道s s为止。为止。56Fiat-Shamir身份识别方案身份识别方案n完备性完备性n如果如果P P和和V V遵守协议，且遵守协议，且P P知道知道s s，则应答，则应答rsrs是应是模是应是模m m下下xvxv的平方根，的平方根，V V接收接收P P的证明，所以协议是完备的。的证明，所以协议是完备的。n正确性正确性nP P不知道不知道s s，他也可取，他也可取r r，送，送x x=r r2 2

33、 mod mod m m给给V V，V V送送b b给给P P。P P可将可将r r送出，当送出，当b b=0=0时则时则V V可通过检验而受骗，当可通过检验而受骗，当b b=1=1时，时，则则V V可发现可发现P P不知不知s s，B B受骗概率为受骗概率为1/21/2，但连续，但连续t t次受骗的次受骗的概率将仅为概率将仅为2 2-t-tnV V无法知道无法知道P P的秘密，因为的秘密，因为V V没有机会产生没有机会产生(0,1(0,1）以外的）以外的信息，信息，P P送给送给V V的消息中仅为的消息中仅为P P知道知道v v的平方根这一事实。的平方根这一事实。57零知识证明零知识证明最小

34、泄露证明和零知识证明：最小泄露证明和零知识证明：以一种有效的数学方法，使以一种有效的数学方法，使V可以检验可以检验每一步成立，最终确信每一步成立，最终确信P知道其秘密，而知道其秘密，而又能保证不泄露又能保证不泄露P所知道的信息。所知道的信息。58零知识证明的基本协议零知识证明的基本协议例Quisquater等等1989。设设P P知道咒语，知道咒语，可打可打开开C C和和D D之间的秘密门，之间的秘密门，不知道者不知道者都将走向死胡同中。都将走向死胡同中。ABCD59零知识证明的基本协议零知识证明的基本协议 (1)V(1)V站在站在A A点；点；(2)P(2)P进入洞中任一点进入洞中任一点C

35、C或或D D；(3)(3)当当P P进洞之后，进洞之后，V V走到走到B B点；点；(4)V(4)V叫叫P P：(a)(a)从左边出来，或从左边出来，或(b)(b)从右边出来；从右边出来；(5)P(5)P按要求实现按要求实现(以咒语，即解数学难题帮助以咒语，即解数学难题帮助)；(6)P(6)P和和V V重复执行重复执行 (1)(1)(5)(5)共共n n次。次。若若A A不知咒语，则在不知咒语，则在B B点，只有点，只有50%50%的机会猜中的机会猜中B B的要求，协议执行的要求，协议执行n n次，则只有次，则只有2 2-n-n的机会完全猜中，的机会完全猜中，若若n n=16=16，则若每次均

36、通过，则若每次均通过B B的检验，的检验，B B受骗机会仅为受骗机会仅为1/65 5361/65 53660零知识证明的基本协议零知识证明的基本协议哈米尔顿回路哈米尔顿回路图论中有一个著名问题，对有图论中有一个著名问题，对有n个顶点个顶点的全连通图的全连通图G，若有一条通路可通过且，若有一条通路可通过且仅通过各顶点一次，则称其为哈米尔顿仅通过各顶点一次，则称其为哈米尔顿回路。回路。Blum1986 最早将其用于零知识最早将其用于零知识证明。当证明。当n大时，要想找到一条大时，要想找到一条Hamilton回路，用计算机做也要好多年，它是一回路，用计算机做也要好多年，它是一种单向函数问题。若种单

37、向函数问题。若A知道一条回路，如知道一条回路，如何使何使B相信他知道，且不告诉他具体回路？相信他知道，且不告诉他具体回路？61零知识证明的基本协议零知识证明的基本协议1.1.A A将将G G进行随机置换，对其顶点进行移动，并改变其标号得进行随机置换，对其顶点进行移动，并改变其标号得到一个新的有限图到一个新的有限图H H。因。因，故，故G G上的上的HamiltonHamilton回路回路与与H H上的上的HamiltonHamilton回路一一对应。已知回路一一对应。已知G G上的上的HamiltonHamilton回路回路易于找出易于找出H H上的相应回路；上的相应回路；2.2.A A将将

38、H H的复本给的复本给B B；3.3.B B向向A A提出下述问题之一：提出下述问题之一：(a)(a)出示证明出示证明G G和和H H同构，同构，(b)(b)出出示示H H上的上的HamiltonHamilton回路；回路；4.4.A A执行下述任务之一：执行下述任务之一：(a)(a)证明证明G G和和H H同构，但不出示同构，但不出示H H上的上的HamiltonHamilton回路，回路，(b)(b)出示出示H H上的上的HamiltonHamilton回路但不证明回路但不证明G G和和H H同构；同构；5.5.A A和和B B重复执行重复执行 (1)(1)(4)(4)共共n n次。次。H

39、G 62六、六、其他密码协议其他密码协议63智力扑克智力扑克nA A和和B B通过网络进行智力扑克比赛，不用第三方做裁通过网络进行智力扑克比赛，不用第三方做裁判，发牌者由任一方担任，要求发牌过程满足判，发牌者由任一方担任，要求发牌过程满足1.1.任一副牌是等可能的任一副牌是等可能的2.2.发给发给A A，B B的牌没有重复的牌没有重复3.3.每人知道自己手中的牌，不知道别人的牌每人知道自己手中的牌，不知道别人的牌4.4.比赛结束后，每一方都能发现对方的欺骗行为比赛结束后，每一方都能发现对方的欺骗行为n为满足要求，为满足要求，A,BA,B方需要加密一些信息，比赛结束前，方需要加密一些信息，比赛结

40、束前，这些机密算法都是保密的。这些机密算法都是保密的。64智力扑克智力扑克nA A和和B B的加密解密算法记为的加密解密算法记为E EA A，E EB B，D DA A，D DB B，满足满足E EA A(E EB B(m)=E(m)=EB B(E EA A(m)(m)nA,BA,B协商好用以表示协商好用以表示5252张牌的张牌的w w1 1,w,w52522.随机选5个EB(wi)3.另选5个EB(wi)，以EA加密以DA解密1.洗牌，用EB对52个wi加密解密，作为发给自己的牌以DB解密52个EB（wi）5个随机的EB（wi）5个的EA(EB(wi)5个的EA(wi)完后公开所有加密变换A

41、B65掷硬币协议掷硬币协议n某些密码协议中要求通信双方在无第三某些密码协议中要求通信双方在无第三方协助情况下，产生一个随机序列，因方协助情况下，产生一个随机序列，因为为A，B之间不存在信任关系，因此不能之间不存在信任关系，因此不能由一方产生在通过网络或电话告诉另一由一方产生在通过网络或电话告诉另一方方66掷硬币协议掷硬币协议n利用单向函数掷硬币利用单向函数掷硬币nA A，B B都知道某一单向函数都知道某一单向函数f(x)f(x)，但都不知道逆函数，但都不知道逆函数1.1.B B选择一个随机数选择一个随机数x x，求，求y yf(xf(x)并发给并发给A A2.2.A A猜测猜测x x的奇偶性，

42、并将结果告诉的奇偶性，并将结果告诉B B3.3.B B告诉告诉A A猜测正确不正确，并将猜测正确不正确，并将x x发给发给A An安全性安全性nA A不知道不知道f(xf(x)的逆函数，无法由的逆函数，无法由y y求求x x，只能猜，只能猜nB B若在若在A A猜测后改变猜测后改变x x，A A可以通过可以通过y=y=f(xf(x)?)?检查出来检查出来67不经意传输不经意传输n设设A有一个秘密，想以有一个秘密，想以1/2的概率传递给的概率传递给B，即即B有有50概率收到该秘密概率收到该秘密n协议执行完后，协议执行完后，A不知道不知道B是否收到这个是否收到这个秘密秘密68基于大数分解的不经意传

43、输协议基于大数分解的不经意传输协议nA A想通过不经意传输协议传给想通过不经意传输协议传给B B大数大数n n的因子分子的因子分子n如果已知某数在模如果已知某数在模n n下的两个不同的平方根，就可下的两个不同的平方根，就可以分解以分解n n1.1.B B随机选一数随机选一数x x，将发给，将发给A A2.2.A A（掌握（掌握n n的分解）计算的分解）计算x x2 2 mod n mod n 的四个平方根的四个平方根x,x,y,y,将其中之一发给将其中之一发给B B3.3.B B检查收到的数是否与检查收到的数是否与x x 在模在模n n下同余，如果是，下同余，如果是，B B没有没有得到任何新的信息，否则得到任何新的信息，否则B B掌握了掌握了x x2 2mod n mod n 的两个不同的的两个不同的平方根，从而可以分解平方根，从而可以分解n n，而，而A A确不知道究竟是哪种情况确不知道究竟是哪种情况69总结：数字签名和密码协议总结：数字签名和密码协议一一数字签字的基本概念数字签字的基本概念二二数字签字标准数字签字标准三三其他签字方案其他签字方案四四认证协议认证协议五五身份证明技术身份证明技术六六其他密码协议其他密码协议70

展开阅读全文