现代密码学第10讲：密码协议

1密码协议《现代密码学》第十讲上讲内容回顾密钥管理简介密钥分配密钥协商PKI及数字证书秘密共享技术3本章主要内容密码协议概念零知识证明比特承诺公平抛币协议安全多方计算。。。。。。密码协议概念协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。一般包含了三个方面的含义：⑴协议需要二个或二个以上的主体参与。⑵参与者按照一定的次序交替地执行一系列的步骤，在前一步尚未完成之前，后面的步骤不能被执行。⑶参与者必须能够协同地完成某项任务，或达成某种意向。密码协议概念密码协议的目的是参与协议的各方根据协议中采用的密码算法，执行一系列规定的步骤和操作，最终完成某项任务或达成一致的意向。零知识证明例1：假设A告诉B：我知道哥德巴赫猜想的证明？如果A把证明过程写下来给B看，B记住了证明然后以自己的名义发表，A将蒙受损失；如果A不把证明给B看，B如何证实A确实知道？例2：A告诉B：我知道近期有支股票要涨，我们两个合作，你出资，我提供信息？合作协议达成之前，A显然不能透露股票的任何信息；但是如果B不能确信他是正确的，肯定不会投资零知识证明零知识证明ZKP(ZeroKnowledgeProof)是由S.Goldwasser等人在20世纪80年代引入该协议的一方称为证明者(Prover)，通常用P表示，协议的另一方是验证者(Verifier)，一般用V表示。零知识证明是指P试图使V相信某个论断是正确的，但却不向V提供任何有用的信息，或者说在P论证的过程中V得不到任何有用的信息。透露秘密利用秘密做一些事零知识证明1990年，L.C.Guillou和J.J.Quisquater提出的例子ABCD零知识证明一个迷宫，C与D之间有一道门，需要知道秘密口令才能打开。现在，证明者P希望向验证者V证明他拥有这道门的秘密口令，但是P不愿意向V泄露该口令。协议开始，为什么验证者不呆在B口，而要站在A口零知识证明验证者V开始停留在位置A。证明者P一直走到迷宫的深处，随机选择到位置C或位置D。V看不到P后，走到位置B，然后命令P从某个出口返回B。P服从V的命令，要么原路返回至位置B，要么使用秘密口令打开门后到达位置B。P和V重复上述步骤次。零知识证明若P不知道秘密口令，就只能原路返回，而P第一次猜对V要求他哪一条路径的概率为0.5，因此，第一轮协议P能够欺骗V的概率为0.5。执行轮协议次后，P成功欺骗V的概率为1/2n。反例：足球比赛赌博一个人收到一份邮件，说他有一个先进的数学工具可以正确猜测足球比赛的结果，如果感兴趣可以购买他们的产品。并连续10次在赛前给此人寄来了正确的预测，于是这个人信以为真并汇款购买，结果发现是一个骗局。n必须很大零知识证明用途：身份识别协议一个安全的身份识别协议至少应满足以下两个条件：证明者P能够向验证者V证明他的确是P。在证明者P向验证者V证明他的身份后，验证者V不能获得关于P的任何有用信息，使得V能冒充P向第三方证明V是P。也就是说，P即能向V证明他的身份，又没有向V泄露P的识别信息，安全的身份识别协议应满足零知识证明。零知识证明身份认证实现公开参数：，，；证明者知道对的离散对数。1)证明者任选随机数，计算，并将送给验证者；2)验证者任选随机数，并将b送给证明者.3)证明者计算y=r+bxmod(p-1)，把y送给验证者;4)验证者验证是否成立，若成立，则继续5)，否则停止；5)重复1)至4)步t次.{1,2,,1}Rrpp*pZxmodrp{0,1}Rbmodybp零知识证明不泄露秘密mod(1)mod(2)mod(1)(3)xrppyrbxp解等式（1）（2），即为求离散对数r为随机数，故已知b、y，不知道x的值零知识证明欺骗过程：1)欺骗者猜测证明者选取的随机数，随机选取，计算2)将和y按协议分别传送送给验证者；若欺骗者猜测b正确，那么，。即验证者相信欺骗者知道x，认为与自己交互的是证明者。重复1)至4)步t次，将欺骗的概率降到2^{-t}{1,2,,1}Rypmodybp{0,1}Rbmodybp欺骗:欺骗者不知道离散对数x,却冒充证明者零知识证明Shnorr身份认证协议融合了ELGamal协议、Fiat-Shamir协议、和Chaum-Evertse-VandeGraff交互协议等协议的思想，是一种计算量、通信量均少，特别适合智能卡上用户身份识别的方案。其安全性建立在计算离散对数问题的困难性上。零知识证明Shnorr身份认证协议需要一个可信中心TA。TA为协议选择下列参数：(1)p及q是两个大素数，且q|(p-1);的生成元。）为，阶元（如可取为pqppggqZZ)2(/)1(*(3)选择安全参数t零知识证明每个用户自己选定个人秘钥s，并计算公钥v。其中每位用户必须到TA注册其公开密钥v。TA验明用户身份后，对每位用户指定一识别名I。I中包括用户的姓名、性别、生日、职业、电话号码、指纹信息等识别信息。TA对(I,v)的签名为ST(I,v)。在身份认证过程中，不需要TA介入。pvqssmod],1,1[零知识证明证明者A向验证者B证明他身份（Schnorr认证协议）)),(,,(1ATAvISvI、AB用TA的数字签名来验证A的公开密钥pZr*任选pXrmod2、]2,1[te任选整数3、eqserymod4、pvXeymod.5验证零知识证明从v求s就是求离散对数，在计算上是不可行的。r和s都是用户的秘密，假冒者Eve是无法从y中得到用户的秘密，当然也就无法假冒证明者A。pvqssmod],1,1[比特承诺生活实例股市预测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值，并与第②步收到的值做比较以检验消息的有效性。公平掷币协议分蛋糕问题：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安全多方计算安全多方计算就是指在无可信第三方的情况下，安全地计算一个约定的函数的值。在一个安全多方计算协议中，参与方之间一般是互不信任的，他们各自都有一个不想让其它任何人了解的秘密数，但是他们要利用这些秘密数来求得大家都信任的值或答案。确切地讲，安全多方计算就是满足下述三个条件的密码协议：安全多方计算一群参与者要利用他们每个人的秘密输入来计算某个多变量复合函数的值。参与者希望保持某种安全性，如机密性与正确性。协议即要保持在发生非协议参与者攻击行为下的安全性，也要保持在发生协议参与者攻击行为下的安全性，但不包括协议参与者的主动欺骗行为，即故意输入错误的秘密数据的情况。安全多方计算百万富翁问题平均薪水问题安全多方计算安全多方计算本章要点小结密码协议零知识证明比特承诺公平抛币协议37THEEND！