零知识身份认证.doc

4零知识身份认证零知识证明（zero-knowledge proof）的思想是：证明者Peggy拥有某些知识（如某些长期没有解决的难问题的解决方法），零知识证明就是在不将该知识的内容泄露给验证者Victor的前提下，Peggy向Victor证明自己拥有该知识。首先，我们看下面Peggy和Victor之间的一段对话：Peggy：“我可以对密文为C的消息进行解密。”Victor：“我不相信。请证明。”Peggy（糟糕的回答）：“密钥是K，您可以看到消息解密成了M。”Victor：“哈哈！现在我也知道了密钥和消息。”这里，Peggy虽然证明了自己拥有某些知识（密钥K及明文M），却向Victor泄露了这些知识。一个更好的对话是：Peggy：“我可以对加密为C的消息进行解密。”Victor：“我不相信。请证明。”Peggy（好的回答）：“让我们使用一个零知识协议，我将以任意高的概率证明我的知识（但是不会将关于消息的任何情况泄露给您）。”Victor：“好”。Peggy 和 Victor 通过该协议可以使用洞穴例子来解释零知识，C和D之间存在一个密门，并且只有知道咒语的人才能打开。Peggy知道咒语并想对Victor证明，但证明过程中不想泄露咒语。图7.13 零知识洞穴步骤如下：（1）Victor站在A点；（2）Peggy一直走进洞穴，到达C点或者D点；（3）在Peggy消失在洞穴中之后，Victor走到B点；（4）Victor随机选择左通道或者右通道，要求Peggy从该通道出来；（5）Peggy从Victor要求的通道出来，如果有必要就用咒语打开密门；（6）Peggy和Victor重复步骤（1）至（5）n次。如果Peggy不知道这个咒语，那么只能从进去的路出来，如果在协议的每一轮中Peggy都能按Victor要求的通道出来，那么Peggy所有n次都猜中的概率是1/2n。经过16轮后，Peggy只有65536分之一的机会猜中。于是Victor可以假定，如果所有16次Peggy的证明都是有效的，那么她一定知道开启C点和D点间的密门的咒语。我们来看一个零知识证明的例子。图是否同构是NP完全问题，对于一个非常大的图，判断两个图是否同构是非常困难的。对于图G1和G2，如果存在一个一一对应的函数F：F的定义域是G1的顶点集。F的值域是G2的顶点集。当且仅当g1,g2是G1中的一条边，F(g1),F(g2)才是G2中的一条边，称G1和G2同构的。假设Peggy知道图G1和G2之间同构，Peggy使用下面的协议将使Victor相信G1和G2同构：（1）Peggy随机置换G1产生另一个图H，并且H和G1同构。因为Peggy知道G1和H同构，也就知道了H和G2同构。（2）Peggy把H送给Victor。（3）对如下两个问题Victor选择其中的一个，要求Peggy证明。但是，Victor不要求两者都证明。证明G1和H同构，或者证明G2和H同构。（4）Peggy按Victor的要求证明。（5）Peggy和Victor重复步骤（1）至（4）n次。如果Peggy不知道G1和G2之间的同构性，Peggy就只能创造一个图或者与G1同构或者与G2同构。每一轮中Peggy只有50%的机会猜中Victor的选择。又因为Peggy在协议的每一轮都产生一个新图H，故不管经过多少轮协议Victor也得不到任何信息，他不能从Peggy的答案中了解G1和G2的同构性。图同构的零知识证明只具有理论意义，从实现来看，是不实用的。这里我们介绍著名的Feige-Fiat-shamir零知识身份认证协议的一个简化方案。可信赖仲裁选定一个随机模数n，n为两个大素数乘积，实际中至少为为512位或长达1024位。仲裁方产生随机数v，使x2=v mod n，即v为模n的平方剩余，且有v-1mod n存在。以v作为Peggy的公钥，而后计算最小的整数s：s=sqrt(v-1) mod n作为Peggy的私钥。实施身份证明的协议如下：（1）用户Peggy取随机数r，这里rm，计算x= r2 mod m，把x送给Victor；（2）Victor把一个随机位b送给Peggy；（3）若b=0，则Peggy将r送给Victor；若b=1，则Peggy将y=rs 送给Victor；（4）若b=0，则Victor验证x=r2 mod m ，从而证实Peggy知道sqrt