看了一些密码学的书籍，都是老外的，才发现歪果仁还真是喜欢alice和bob，这二位霸占了密码学的故事的主角。今天我们也邀请二位来参与我们的故事。今天介绍的是比较简单的零知识证明，交互式零知识证明——Fiat-Shamir，不过这就是为了把大家领上道，实际应用是比这个要复杂的；
Fiat-Shamir要进行Fiat-Shamir，首先进行准备工作，由可信第三方，随机选择两个大的素数p和q，计算n = p*q的值（n的值是公开的，p和q的值要保密）。
Alice选择s属于（1～n-1），并计算出，其中s作为Alice的私钥，v则为Alice的公钥。
（三个横线是同余，v mod n 等于 s^2 mod n，两边平方可以将mod n移出）
现在需要Bob出场了，Alice希望向Bob证明她知道s，但是又不希望Bob知道s是多少。准备工作到此结束，开会证明。
1）Alice随机选择r（0～n-1），然后计算，将x发给Bob；x称之为证据；
2）Bob随机选择c = 0 or 1 发送给Alice，c称之为挑战；
3）Alice根据收到Bob的挑战，发送给Bob，y称之为应答；
4）Bob则进行验证，
如果c=0，则，所以c=0时，Bob只需要根据验证
即可，而这些数据并不会透露s的任何消息；
当c=1时，则 ，所以c=1时，Bob只需要根据验证
即可，而这些数据也不会透露s的任何消息；
这就是一次完整的验证过程，整个验证过重，Bob没有得到s的任何信息，而且也验证了，Alice是否知道s，如果s不知道s，则当c=1的时候，Alice是无法发送正确的值的。所以只要我们重复这个验证过程，则Alice就不能欺骗Bob；
Alice真的无法欺骗Bob？？？ 下面我们假装自己是Alice，而且Alice不知道s，看看是否真的咩有办法欺骗Bob，说不定咱们更聪明呢。
我是alice，我不知掉s；我们先正向思考一下这个问题，因为我们不知道s，所以，一旦Bob的c=1，我们肯定是无法验证通过的，这条路肯定是不行的；
我们在反向思考一下，无论c=0 or 1，Bob最终要验证的公式就是,其中x是我们可控的，v呢，是公开的，c呢是Bob控制的，所以如果我们能够提前预测每次Bob每次c的值，则我们就完全可以控制Bob最后验证公式的结果；例如，如果我们知道Bob要发送c=0，则我们只需要在第三步，给Bob发送
即可；如果提前预测Bob发送c=1，则只需在第三步发送
；
实际上，我们是无法预测Bob要发送c的值，当这个验证重复n次后，则我们猜对的概率变为，n=16大概是60000分之一的概率，已经很低了；这足够证明这个算法的可行性；
----------------------------------- ©著作权归作者所有：来自51CTO博客作者xq310的原创作品，如需转载，请注明出处，否则将追究法律责任 零知识证明四——Fiat-Shamir，三分钟零知识证明入门 https://blog.51cto.com/u_1334935/2862812
