现代密码学09---安全协议.pptVIP

*零知识洞穴问题可以转化为数学问题，Peter知道解决某个难题的秘密（相当于咒语），而Victor通过与Peter交互以验证其真实性。*结论如果单向函数是存在的，任何一个NP问题都存在零知识证明相关论文Goldwasser,Micali,Rackoff.Theknowledgecomplexityofinteractive-proofsystems.Proc.of17thACMSym.onTheoryofComputation,pp.291-304,1985.NP与零知识证明G0NP与零知识证明举例—图同构证明两个图G0和G1是同构的（置换为δ）Alice向Bob证明：他知道两个图是如何同构的也即证明自己知道δG1δG0基本原理G1δGπG与G1的置换？πoδG与G0的置换为πG0G1πGC=0or1δ证明过程如下G0G1C=0or1GπδG0G1GC’C=0or1C’=0or1πδG0G1GC=0or1C’=0or1x=πifc=c’x=πoδifc≠c’xπC’δG0G1GC=0or1C’=0or1x=πifc=c’x=πoδifc≠c’xπC’δ检查x是否是G与Gc’的同构关系n轮G0G1*协议描述：Alice如下执行：Alice随机选择图G0或G1(c=0or1)Alice构造其同构图G(置换为π)，并发给BobBob随机让Alice证明G与G0或G1同构(c’=0or1)Alice产生x，将x发送给Bobx=πifc=c’x=πoδifc≠c’Bob校验Gc’是否能在置换x的变换下等于G重复执行1-4共n次*分析：完备性如果G0与G1确实同构，且Alice知道同构置换δ，她总能正确回答Bob的提问。正确性如果Alice不知道δ,或者G0与G1不同构，她只能以1/2概率正确回答Bob的提问，n轮成功欺骗的概率是1/2n,是可以忽略的。零知识Bob能从交互中获得δ的知识吗？*分析（续）：其实，即使不与Alice交互，Bob也可以自己产生交互数据。Bob可以这么做：随机选择一个c’=0or1构造图Gc’的同构图G，设同构置换为x生成交互数据（G,c’,x）这就说明，“产生交互数据”这件事，即使不与Alice交互，Bob自己也可以干，所以他没从Alice处获得任何知识。*扩展阅读其他协议比特承诺公平抛硬币智力扑克阈下信道安全多方计算不经意传输*掌握安全协议的相关概念、Dolev-Yao攻击者模型掌握实体认证的分类方法掌握Needham口令认证协议、Lamport的一次性口令机制掌握秘密共享的基本概念、Shamir的方案掌握零知识证明的基本概念本章小结*原理利用Hash函数存储口令，防范攻击者偷取数据库后得到口令简单有效，广泛应用于各种系统中UNIX：使用DES代替Hash函数Discuz！……实体认证knowsth:Needham口令认证协议*用户名口令散列值zhangxtR$^42@Alice6tT$^2%%……数据库passwordH6tT$^2%%比较usernameAlice缺点无法防范攻击者在线窃听口令无法防范离线字典攻击*为防范在线窃听口令，可使用一次性口令机制每次认证使用不同的口令要求用户和系统共享很多口令但管理和保护大量的口令在技术上很困难为克服这一缺点，Lamport提出利用多次Hash的方法实现一次性口令机制实体认证knowsth:一次性口令机制*方法举例系统保存P100用户保存P99、P98、P97……认证过程用户提交P99系统计算if（P100==Hash(P99)）{验证通过;保存P99;}用户丢弃P99初始秘密值wP1=H(w)P2=H(P1)P100=H(P99)系统保存计算完销毁用户保存实体认证knowsth:Lamport的一次性口令机制*Lamport方案的缺点必须保持同步但可能因为不可靠信道或死机出现丢失同步的情况(有可能是攻击者的破坏所致)*在