在各种介绍密码学与协议的教材里都有关于零知识证明的话题——如何让你相信我已经找到了一个解，但又不告诉你这个解是什么。最经典的例子便是关于Hamilton回路的问题——存在这样一种巧妙的协议，可以让你相信我已经找到了某个图的Hamilton回路，而你却完全得不到关于这个Hamilton回路本身的任何信息。今天我又看到了一个非常不错的零知识证明实例。给定一个平面图，你需要给每个区域染一种颜色，使得任两个相邻的区域颜色不同。如果你仅用三种颜色就能做到这一点，我们就说这个图是可以三染色的。目前我们还没有一个判断平面图可否三染色的好办法，寻找一个平面图的三染色方案并不是一件容易的事。现在，假如你已经找到了某个给定平面图的三染色方案，你想向别人炫耀自己的成果，但又不想透露关于你的染色方案的任何信息。你能否设计一种协议使得对方能够相信你确实找到了一种三染色方案而又不告诉他这种方案是什么呢？
md5
密码学协议举例（一）：带有防欺骗的承诺
我们常常在电视上看到这样的一幕：一位老太太兴冲冲地走上台去，翻过三个商标牌，发现上面尽是5块钱、10块钱的小奖，垂头丧气地回到观众席；然后马脸李咏会跑出来，边翻着另外几个牌子边说，1000块的大奖在这个后面，800块的在这里，之类的。或许有人会纳闷了，为什么主持人要演出“事后揭大奖”这一幕呢？道理很简单，节目组想通过这一个“验证过程”告诉观众，这个环节不是骗人的，大奖真的就在这后面，只是刚才那家伙运气背了没摸到而已。摸奖前宣称有大奖，摸完奖之后还能证实大奖真的存在，这就是带有防欺骗的承诺。
但是，同样的事情在网络上似乎是办不到的。一个典型的例子就是QQ原来弄的那个恶心的砸金蛋砸银蛋。屏幕左边那个是银蛋，屏幕右边那个是金蛋，你鼠标选一个敲下去，看能否砸出QQ宠物来。大量测试表明砸出宠物的概率远远低于50%，让人质疑游戏的真实性。鬼知道它那个程序是不是真的预先指定了一个有宠物的蛋蛋，很可能不管你点了哪个蛋蛋结果都一样，系统按照概率直接显示出抽奖结果来。当然，怀疑游戏的公平性也没办法，要想在网络上实现带防欺骗的承诺是比较困难的，毕竟让你看一段从另一个蛋蛋里跳出一个宠物的Flash动画不能让你相信刚才你是真的“选错”了吧。
我们的问题就是：如何设计一个协议，用以保证一个二选一的网络互动抽奖游戏的真实性？换句话说，假如你选择了金蛋，结果没有中奖，那么系统如何能够令你相信奖品刚才真的在银蛋里？
身份验证、中间人攻击和数字签名：浅谈密码学（上）
说到“密码学”，大多数人的第一念头或许是Morse电码、Ceasar移位密码、同音替换密码之类的东西。这些东西在各类小说中都已是老面孔了，“字母e在英文中出现频率最高”这一最基本的破密码方法已经是耳熟能详了。几天前和网易的云风聊了一下，突然体会到了密码学的真谛。密码学关注更多的并不是加密解密的各种数学算法，而是在已有数学算法上如何实现各种安全需求。防止消息泄露只是众多安全问题中的冰山一角，而这个问题本身又有很多复杂的变化。
当我们谈到“消息泄露”时，我们头脑中想到的往往是，在信息传输过程中如何防止第三方截获。当然，小偷防是防不住的，不过我能保证他偷到东西也没用。双方只需要事先约定一套加密函数和解密函数，以密文的方式进行传输，这样便能很好地防止消息泄露。但有时候，“消息泄露”的内涵复杂得多，加密解密的传统方法并不适用。考虑这么一个问题：10个人坐在一起谈天，突然他们想知道他们的平均年薪，但又都不愿意透露自己的工资数额。有没有什么办法让他们能够得出答案，并且不用担心自己的年薪被曝光？事实上，最简单的解决办法不需要依赖任何密码学知识：第一个人随便想一个大数，比如880516。然后他在纸条上写下这个数与自己的年薪之和，传给第二个人；第二个人再在这个数上加上他的年薪数额，写在另一张纸条上传给第三个人；直到最后一个人把纸条传回第一个人后，第一个人把纸条上的数减去只有自己知道的那个880516，便得到了全部10个人的工资和。
标题党 之 密码学家用PS3成功预测美国2008大选结果
昨天，一帮密码学家在网上宣称，他们通过一台PS3成功预测出了2008年大选的结果。但为了不干预事件的进程，他们将放出描述大选结果的文档的md5值。大选结束后，密码学家们会放出该文档，证实他们之前确实成功预测到了这个结果。这份电子文档的md5值为：
3D515DEAD7AA16560ABA3E9DF05CBC80
你能猜出这背后有什么阴谋诡计吗？
在字谜界有一个非常有趣的故事。美国大选结果出炉的前一天，某报纸上刊登了一则纵横字谜，正中间的那个最长的单词的提示是：美国新一任总统的名字。字谜爱好者纷纷给报社打电话，说大选结果还没出来，我他妈的咋知道新总统是谁，这背后到底隐藏了什么秘密。第二天，报纸上刊登了字谜的答案，中间那个单词果然就是新总统的名字。这家报社“预测”出了大选的结果。你可能已经想到了，这是一个设计得非常巧妙的字谜。这则纵横字谜有两个答案，每个答案都完全符合所有的提示，只是中间的那个人名字不同。纵横字谜中任一个字母的改变都会引起连锁反应导致很大一片字母的改变，因此要想设计出这样一个字谜是非常困难的。但是，就有这么牛的人设计出来了。
你相信吗？就有那么牛的人，他居然可以构造出两篇文档，hash出来的md5是完全一样的！比起纵横字谜来，这似乎变得更不可思议，因为一篇文档中任何一处微小的改变都会使原来的md5值面目全非。但是，就有这样一种算法，它可以在短时间内构造出md5发生“碰撞”的情况。这就是前几年炒得沸沸扬扬的“山东大学王小云教授成功破解md5”一事。
当时的新闻很不负责任，没有几个是说清楚了的。和大多数人想的不同，md5被破解并不是真的md5被破解了，你无法把md5还原为原来的信息（因为md5是多对一、不可逆的），也几乎不可能构造一个字符串具有指定的md5值。但是，王小云教授发现，作为一种验证码，md5已经不再可靠了，因为利用他的发现可以很轻易地构造出md5发生冲突的情况。考虑这样一种情况，你需要在未来的某个时间公开一份秘密文档，但到时候你必须证明这份文档确实就是之前说要公开的那一份。比如，你参加CCTV的垃圾娱乐节目，主持人叫你猜一个充气娃娃的价格，你猜是1000元，然后被干冰吓跑，主持人阴笑着宣布这个充气娃娃的真实价格是998。但制作单位如何证明这个价格确实就是998呢？即使是把真实价格藏在一块遮板后面，也有作假的可能。一种不错的方式就是，预先算出998的md5值，由于md5值是不可逆转的，因此即使公开md5别人也拿它没办法；但这个md5可以起一个验证作用，我在报出998的同时你可以验证998的md5值和刚才给的是不是一样，这样才能确保制作单位没有作假。这就需要md5算法具有很低的碰撞概率。现在看来，这种验证方法也不能相信了，因为人为构造md5冲突的两个原始信息变得越来越容易，你猜价格是A我就说是B，你说是B我就说是A，而A和B的md5是一样的。这样的话，我可以做很多坏事，比如说些什么我能预测股票的走向，我五年前就知道我会和你在一起之类的屁话。从这个意义上说，md5不再安全，它已经被破解了。
消息来源：http://blog.wired.com/27bstroke6/2007/11/cryptographers.html
查看更多：http://www.win.tue.nl/hashclash/Nostradamus/
做人要厚道，转贴请注明出处