第7章数字签字和密码协议.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 由E≠F可设ej≠fj，ej和fj是第j次执行协议时V的两个不同的询问（为向量），简记为e=ej和f=fj，这一轮对应的aj简记为a。所以E能计算两个不同的值， 即 ，所以E可由 求得 的平方根，矛盾。 (3) 安全性 Fiat-Shamir身份识别方案是对简化的FiatShamir身份识别方案的推广，首先将V的询问由一个比特推广到由t个比特构成的向量，再者基本协议被执行k次。假冒的证明者只有能正确猜测V的每次询问，才可使V相信自己的证明，成功的概率是2-kt。 假设两个人A和B通过计算机网络进行智力扑克比赛，比赛中不用第三方做裁判。发牌者可由任一方担任，发牌过程应满足以下要求： ① 任一副牌（即发给参赛人员手中的牌）是等可能的。 ② 发给A、B手中的牌没有重复的。 ③ 每人都知道自己手中的牌，但却不知对方手中的牌。 ④ 比赛结束后，每一方都能发现对方的欺骗行为（如果有的话）。 7.6 其他密码协议 7.6.1 智力扑克 为满足这些要求，A、B之间必须以加密形式交换一些信息。在下面的协议中，加密体制可以是单钥密码也可以是公钥密码，设EA和EB、DA和DB分别表示A和B的加密变换和解密变换，在比赛结束之前，这些变换都是必威体育官网网址的，比赛结束后予以公布用以证明比赛的公正性。要求加密变换满足交换律，即对任意消息M有： EA(EB(M))=EB(EA(M)) 比赛开始前A、B协商好用以表示52张牌的消息w1,w2,…,w52，协议中设A为发牌人，并设给每人发5张牌。协议如下： ① B先洗牌，然后用EB对52个消息分别加密，将加密结果EB(wi)发送给A。 ② A从收到的52个加密的消息中随机选5个EB(wi)，并发送给B，B用自己的解密变换DB对这5个值解密，解密后的值作为发给自己的一副牌。因为B的加密变换EB和解密变换DB都是必威体育官网网址的，所以A无法知道B手中的牌。 ③ A另选5个EB(wi)，用EA加密后发送给B。 ④ B用DB对收到的值解密后再发送给A，A用DA对收到的值解密后作为发给自己的一副牌，这是因为B发送给A的值是 DB(EA(EB(wi)))=DB(EB(EA(wi)))=EA(wi) 其中用到加密变换的交换律。 下面考虑该协议是否满足发牌过程的4个要求。 对第②个要求，B可在协议的第③步检查A发来的5个值是否和第②步发来的5个值有重复。为满足第4个要求，可在比赛结束后公开所有的加密变换和解密变换，双方都可检查对方的牌看是否有欺诈。对第①个和第③个要求来说，关键在于加密变换EB的强度，由EB(wi)可能得不出wi，但有可能得出wi的部分信息。例如，wi是一个比特串，则有可能从EB(wi)得出wi的最后一个比特，因此A可将52个值EB(w1),EB(w2),…,EB(w52)分成两个子集，A在发牌时可将发给B的牌集中在某一子集中，因此使得第①个和第③个要求无法满足。 在某些密码协议中要求通信双方在无第三方协助的情况下，产生一个随机序列，因为A、B之间可能存在不信任关系，因此随机序列不能由一方产生再通过电话或网络告诉另一方。这一问题可通过掷硬币协议来实现，掷硬币协议有多种实现方式，下面介绍其中的3种。 7.6.2 掷硬币协议 1. 采用平方根掷硬币 协议如下： ① A选择两个大素数p、q，将乘积n=pq发送给B。 ② B在1和n/2之间，随机选择一个整数u，计算z≡u2 mod n，并将z发送给A。 ③ A计算模n下z的4个平方根±x和±y（因A知道n的分解，所以可做到），设x’是x mod n和-x mod n中较小者，y’是y mod n和-y mod n中较小者，则由于1un/2，所以u为x’和y’之一。 ④ A猜测u=x’或u=y’，或者A找出最小的i使得x’的第i个比特与y’的第i个比特不同，A猜测u的第i个比特是0还是1。A将猜测发送给B。 ⑤ B告诉A猜测正确或不正确，并将u的值发送给A。 ⑥ A公开n的因子。 因