现代密码学之密码协议资料

国家级精品课程现代密码学灾备技术国家工程实验室北京邮电大学信息安全中心上一讲内容回顾有特殊性质的签名方案盲签名群签名与环签名多重签名聚合签名代理签名不可否认签名一次签名失败即停签名……3密码协议《现代密码学》第十讲4本章主要内容密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议5本章主要内容密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议密码协议概念协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。一般包含了三个方面的含义：⑴协议需要二个或二个以上的主体参与。⑵参与者按照一定的次序交替地执行一系列的步骤，在前一步尚未完成之前，后面的步骤不能被执行。⑶参与者必须能够协同地完成某项任务，或达成某种意向。密码协议概念密码协议的目的是参与协议的各方根据协议中采用的密码算法，执行一系列规定的步骤和操作，最终完成某项任务或达成一致的意向。8本章主要内容密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议比特承诺生活实例股市预测Alice想对Bob承诺一个比特(也可以是一个比特序列)，但不告诉Bob她的承诺，也就是不向Bob泄露她承诺的比特值，直到某个时间以后才提示(或公开)她的承诺；另一方面，Bob可证实在Alice承诺后，她没有改变她的承诺。比特承诺实例Alice把消息（承诺）放在一个箱子里并将它(只有Alice有钥匙)锁住送给Bob等到Alice决定向Bob证实消息时，Alice把消息及钥匙给BobBob能够打开箱子并验证箱子里的消息同Alice出示的消息相同，且Bob确信箱子里的消息在他保管期间没有被篡改。比特承诺基于对称密码算法的比特承诺方案如下：Alice和Bob共同选定某种对称加密算法。Bob产生一个随机比特串并发送给Alice。Alice随机选择一个密钥，同时生成一个她欲承诺的比特串(也可以是一个比特)，然后利用对称加密算法对“和”加密，最后将加密后的结果发送给验证者Bob。当需要Alice承诺时，她将密钥和承诺的比特发送给Bob。Bob利用密钥解密，并利用他的随机串检验比特的有效性。比特承诺利用基于单向函数的比特承诺方案如下：Alice和Bob共同选定一个单向函数，如Hash函数Alice生成两个随机数和承诺比特串，计算单向函数值并将结果（哈希值）和其中一个随机数发送给Bob。当Alice向Bob出示消息时，她把承诺比特串与另一个随机数一起发送给Bob。Bob计算hash值，并与第②步收到的值做比较以检验消息的有效性。13本章主要内容密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议公平掷币协议分蛋糕问题：Alice切蛋糕，Bob优先选，所以Alice要把蛋糕分得尽量均匀抛币：Alice抛币Bob猜测是花还是字如果由一个人来完成，他可以作弊公平掷币协议不能见面的两个人通过网络或者电话完成⑴Alice和Bob各有50%的机会获胜；⑵任何一方欺骗则认为其在博弈中失败；⑶协议执行结束后，Alice和Bob都知道结果公平掷币协议1)Alice发送一对大素数p,q的乘积n=p*q给Bob.2)Bob在中随机选取一个小于n/2的x,然后发送给Alice.3)Alice校验是否是模n的二次剩余，即是否满足勒让德符号和，若满足则计算的四个根：，其中。然后Alice随机猜测Bob选取的是中的哪一个，并把猜测结果0或1发送给Bob（事先规定大的用1表示，小的用0表示）.N应该为Blum数nZnxamod2a1pa1qa)(mod2nax2211,,,xnxxnx221nxx21,xx公平掷币协议4)Bob收到后0或1后将第2)步中选择的发送给Alice.5)Alice检验是否属于，是否属于，现在Alice根据第3)步和接收到x的可以知道她的猜测是否正确，然后将p,q值传送给Bob.6)Bob检验p,q是否是两个不同的素数，且验证n=p*q是否成立。然后根据和计算出，现在Bob也知道他和Alice的博弈最终是谁赢了.x*nZx},{21xx)(mod2pax)(mod2qax21,xx公平掷币协议例：1)Alice选择p=11,q=19,然后把n=11*19=209发送给Bob.2)Bob在中随机选取x=31(209/2),计算并把a=125发送给Alice.3)因为和，所以a是模p的二次剩余，同时也是模q的二次剩余，所以Alice验证得出a是模n的二次剩余；求出的四个根是假设Alice猜测Bob选取的是，则把1发送给Bob.*209Z22mod31mod209125axn125119aq125111ap2125mod209x112231,178,64,145xnxxnx2x公平掷币协议4)Bob收到1后将第2）步中选择的发送给Alice.5)Alice检验x属于，且，现在Alice知道她的猜测是错误的，也就是说在博弈当中Alice失败了，然后Alice将p=11,q=19传送给Bob.6)Bob检验p,q是两个不同的素数，且满足n=p*q=11*19=219.Bob根据3）步Alice传给他的数值1知道Alice猜测错了.131xx*209Z131xx20本章主要内容密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议安全多方计算安全多方计算就是指在无可信第三方的情况下，安全地计算一个约定的函数的值。在一个安全多方计算协议中，参与方之间一般是互不信任的，他们各自都有一个不想让其它任何人了解的秘密数，但是他们要利用这些秘密数来求得大家都信任的值或答案。确切地讲，安全多方计算就是满足下述三个条件的密码协议：安全多方计算一群参与者要利用他们每个人的秘密输入来计算某个多变量复合函数的值。参与者希望保持某种安全性，如机密性与正确性等。协议即要保持在发生非协议参与者攻击行为下的安全性，也要保持在发生协议参与者攻击行为下的安全性，但不包括协议参与者的主动欺骗行为，即故意输入错误的秘密数据的情况。安全多方计算典型例百万富翁问题：每个人都不想告诉对方自己的财富，但希望知道谁更富有。平均薪水问题：每个员工都不想让其他人知道自己的薪水，但希望知道他们的平均薪水。共同兴趣问题：Alice喜欢XXX，Bob则喜欢YYY，他们想找到一个有共同喜好的伙伴，但并不愿意招惹推销商。加密数据计算：Alice希望Bob替她计算f(x)，但是不想让Bob知道x。不经意传输——不可思议的读写：Alice读取Bob拥有的秘密中的一个且不知其余，而Bob并不知道Alice买走了哪一个。……百万富翁问题假设A拥有i百万，B拥有j百万，且即1≤i,j≤N。两人执行如下协议：①A和B共同协商一种公钥加密体制。不妨设B的公钥和私钥分别为KUB和KRB。②A随机选择一个大随机数x,用B的公钥加密c=EKUB(x),然后将c-i发送给B。③B首先计算N个数：yu=DKRB(c-i+u),u=1,2,…,N。然后随机选择一个大素数p,再计算N个数：zu=yumodp,u=1,2,…,N。接着验证对于所有的0≤a≠b≤N-1,是否都满足|za-zb|≥2？若不满足，则重新选择大素数p重新验证。最后，B将以下的N+1个数串发送给A:z1,z2,…,zj,zj+1+1,zj+2+1,…,zN+1和p。④设A收到N+1个数串m的第i个数是mi，若满足mi≡xmodp，则结论是i≤j;否则ij。⑤A将最终的结论告诉B。平均薪水问题平均薪水问题共同兴趣问题假设Alice与Bob已协商好各种嗜好编码和某个单向函数：1)Alice使用一个单向函数，将自己的嗜好编码映射为7位数字2)Alice用这7位数字作为电话号，拨号。若有人接听，则Alice给Bob留下一条消息；若无人接听，则Alice将这7位数代入单向函数再找下去，直到有人接听。3)Alice告诉Bob她进行了几次单向函数迭代4)Bob从自己的嗜好出发，进行同样次数的单向函数迭代，将结果的7位数作为电话号，拨号，询问是否有人给他留言分析：Bob可以进行穷举攻击加密数据计算问题对某些f(x)而言，是有办法的，例如盲签名。离散对数函数：有大素数p，生成元g，f(x)=loggx(modp)协议如下：1)Alice随机选择rp2)Alice计算x'=xgrmodp，并将x'提交给Bob3)Bob计算e'=f(x')，并将e'发送给Alice4)Alice计算f(x)=(e'-r)mod(p-1)不经意传输情景1：Alice有一个秘密，想用100元的价格卖给Bob。而Bob只有50元，秘密又不能分为两半。两人协商的结果是：Bob付50元并以50%的几率得到消息，而Alice对Bob是否得到消息并不知情。Rabin的ObliviousTransfer(1)A：取两个素数p,q，计算n=pq，n→B(2)B：取x，0xn，gcd(x,n)=1，计算a=x2modn，a→A(3)A：因为知道p和q，可以计算x2modn=a的四个根：x,n-x,y,n-y,从中随机挑选一个送给B(4)B：若收到y或n-y，则可计算p和q：gcd(x+y,n)=p或q；若收到x或n-x，则B什么也得不到。分析：Bob获得p和q的概率是50%Alice不知道Bob是否解得p和q国家级精品课程现代密码学王励成副教授灾备技术国家工程实验室北京邮电大学信息安全中心上节课内容回顾密码协议比特承诺公平抛币安全多方计算百万富翁问题平均薪水问题共同兴趣问题不经意传输不经意传输情景2：Alice有两个秘密，想用100元的价格卖给Bob。而Bob只有50元，只能买一个秘密。两人协商的结果是，Bob付50元并能得到其中任意一个秘密，而Alice对Bob得到的是哪个消息并不知情。扩展：Alice传送一组消息给Bob，Bob收到其中一个子集，Alice不知道Bob收到的是哪个子集。不经意传输解决情形2的协议：1)Alice产生两对公钥/私钥，将两个公钥送给Bob2)Bob选择一个对称密码算法（如DES）密钥，并用Alice的某一个公钥加密，将加密密钥发给Alice3)Alice分别用两个私钥解密Bob的加密密钥，分别用两个解密结果加密她的两份消息，将加密结果送给Bob4)Bob用密钥解密两份密文，得到两份消息之一分析：考虑到Alice可以用解密结果加密同一份消息，而欺骗Bob；Bob如何知道Alice没有欺诈？解决办法：Alice将两份私钥发给Bob，以便验证她没有欺诈。但此时Bob将有能力获得第二份消息，怎么办？使用仲裁可以解决这个问题。（注意：协议结束后引入的仲裁不同于协议当中引入的可信第三方，是可以接受的。）34本章主要内容密码协议概念比特承诺公平抛币协议安全多方计算电子货币电子选举匿名协议电子货币电子货币是指用一定的现金或存款从银行兑换出代表相同金额的数据，并以可读写的电子形式存储起来。当使用者需要消费时，通过电子方式将该数据直接转移给支付对象，这种数据就称为电子货币。电子货币电子现金系统由三个协议组成：(1)取款协议：用户从银行自己的帐户上提取电子货币(2)支付款协议：用户向商店支付电子货币(3)存款协议：商店向银行提交用户支付的电子货币要求银行把相应的款存到商店的帐户上电子货币电子货币协议满足的性质：1991年，Okamoto和Ohta提出理想的电子现金方案应满足以下六个标准：独立性不可伪造性和不可重用性离线性可转移性可分性不可跟踪性和不可联系性目前的技术还很难高效实现上述所有功能电子货币1982年，Chaum最早提出一个在线的、基于RSA盲签名的完全电子货币方案；1988年，Chaum，Fait和Naor利用切割-选择和RSA盲签名技术提