标题党 之 密码学家用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/