现代密码学第十讲：密码协议(一)new.ppt

上讲内容回顾 密钥管理简介 密钥分配 密钥协商 PKI及数字证书 秘密共享技术 密码协议概念 协议是一系列步骤，它包括两方或多方，设计它的目的是要完成一项任务。一般包含了三个方面的含义： ⑴ 协议需要二个或二个以上的主体参与。 ⑵ 参与者按照一定的次序交替地执行一系列的步骤，在前一步尚未完成之前，后面的步骤不能被执行。 ⑶ 参与者必须能够协同地完成某项任务，或达成某种意向。 密码协议概念 密码协议的目的是参与协议的各方根据协议中采用的密码算法，执行一系列规定的步骤和操作，最终完成某项任务或达成一致的意向。 零知识证明 例1：假设A告诉B：我知道哥德巴赫猜想的证明？ 如果A把证明过程写下来给B看，B记住了证明然后以自己的名义发表，A将蒙受损失； 如果A不把证明给B看， B如何证实A确实知道？ 例2：A告诉B：我知道近期有支股票要涨，我们两个合作，你出资，我提供信息？ 合作协议达成之前，A显然不能透露股票的任何信息；但是如果B不能确信他是正确的，肯定不会投资 零知识证明 零知识证明ZKP(Zero Knowledge Proof)是由S. Goldwasser等人在20世纪80年代引入 该协议的一方称为证明者(Prover)，通常用P表示，协议的另一方是验证者(Verifier)，一般用V表示。零知识证明是指P试图使V相信某个论断是正确的，但却不向V提供任何有用的信息，或者说在P论证的过程中V得不到任何有用的信息。 透露秘密 利用秘密做一些事 零知识证明 1990年，L. C. Guillou和J. J. Quisquater提出的例子 零知识证明 一个迷宫，C与D之间有一道门，需要知道秘密口令才能打开。现在，证明者P希望向验证者V证明他拥有这道门的秘密口令，但是P不愿意向V泄露该口令。 零知识证明 验证者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次在赛前给此人寄来了正确的预测，于是这个人信以为真并汇款购买，结果发现是一个骗局。 零知识证明 用途：身份识别协议 一个安全的身份识别协议至少应满足以下两个条件： 证明者P能够向验证者V证明他的确是P。 在证明者P向验证者V证明他的身份后，验证者V不能获得关于P的任何有用信息，使得V能冒充P向第三方证明V是P。 也就是说，P即能向V证明他的身份，又没有向V泄露P的识别信息，安全的身份识别协议应满足零知识证明。 零知识证明 身份认证实现 公开参数： ， ， ；证明者知道 对 的离散对数 。 1) 证明者任选随机数 ，计算 ，并将 送给验证者； 2) 验证者任选随机数 ，并将b送给证明者. 3) 证明者计算y=r+bx mod(p-1) ，把y送给验证者; 4) 验证者验证 是否成立，若成立，则继续5)，否则停止； 5) 重复1)至4)步t次. 零知识证明 解等式（1）（2），即为求离散对数 r为随机数，故已知b、y，不知道x的值 零知识证明 欺骗过程： 1) 欺骗者猜测证明者选取的随机数 ，随机选取 ， 计算 2) 将 和y按协议分别传送送给验证者； 若欺骗者猜测b正确，那么， 。即验证者相信欺骗者知道x，认为与自己交互的是证明者。 重复1)至4)步t次，将欺骗的概率降到2^{-t} 零知识证明 Shnorr 身份认证协议融合了ELGamal协议、Fiat-Shamir协议、和Chaum-Evertse-Van de Graff交互协议等协议的思想，是一种计算量、通信量均少，特别适