MD5和MD5破解的一些事

本文由@isnowfy 的投稿于伯乐在线，也欢迎其他朋友投稿。提示：投稿时记得留下微博账号哦。

看到网上一些对于MD5的介绍，还有对于当初王小云所做的破解有很多的误解，或者说不理解，然后觉得对于这些事情只要说明白，还是比较好理解的说。

首先MD5其实就是一种hash，或者叫散列函数，有的地方叫杂凑函数，都是一个东西，其实它就是一种映射，而平常最常见的就是说MD5是不可逆的，为什么不可逆呢？有人就说就是像有些函数没有反函数那样了，其实还是有点抽象，考虑MD5是多对一的映射，也就是说很多不同的经过MD5变换之后可能会是相同的，那么既然多对一，自然是不可逆啦，你怎么会知道他到底是由哪个变换过来的呢。在密码学的应用里，说是单向函数，或者说单向变换，一种是这种多对一不可逆，还有一种是说逆工程会非常困难，举个例子吧，假设f(x)=x^6-x-1，然后你知道f(1)=-1，在知道x=1和f的情况下计算f(1)是很简单的，而知道f(x)=-1和f去求x却是很困难的，这里就不展开说了，大家有个大体的认识就可以了。

[/url]

刚才说过了由于MD5是多对一的，所以肯定会出现变换后的值是一样的情况，这种情况叫做冲突，或者叫碰撞。为了保证安全性，定义了两种，一种叫无弱碰撞，一种叫无强碰撞。

无弱碰撞是

1 2 3 4

已知函数M和一段数据H 找到一个H' 使得M(H)=M(H') 是难的

无强碰撞是

1 2 3 4

已知M 找到一对H和H' 使得M(H)=M(H') 是难的

很明显满足无强碰撞比满足无弱碰撞更难，真的吗？好吧，就不说明显了，为什么说无强碰撞更难呢，换句话说为什么找到强碰撞更简单呢，恩，这就涉及到生日悖论了，或者叫生日攻击了。

来想想以前的概率吧，假设一年365天，那么，至少有多少人使得有两人是同样生日的概率会超过1/2呢，直觉上应该是365/2个人吧，其实答案是23，少的夸张是吧，不然不会叫做悖论了啊，如何计算呢，其实我们是在求一个最小的n，使得1-(1-1/365)*(1-2/365)*…(1-(n-1)*365)>=1/2，随便写个程序验证下就知道是23了，什么你不知道这个式子怎么得来的，考虑第二个人不要和第一个人生日冲突的概率是(1-1/365)然后第三个人不和前两个人生日相同的概率是(1-2/365)后面就知道了吧。然后这个人数其实是O(sqrt(365))。那么回到前面的问题，假设映射空间，就是说最后能够得到的值的个数是m，那么弱碰撞的复杂度是O(m)，而强碰撞呢是O(sqrt(m))，所以说找到强碰撞更简单，也就是说满足无强碰撞更难！

王小云的贡献呢就是找到了比生日攻击复杂度低得多算法来快速找到一对强碰撞，弱碰撞吗依旧是不行的。[url=http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf]这里有她的论文，有兴趣的可以看一下。那么也就是说通过密文找到明文依旧是不可能的，并且弱碰撞依旧是很难的。

不过后来又有外国的nb人受到了王小云的启发，得到了一种很快的算法能够在已知前缀x1,x2的情况下构造一对后缀y1,y2使得M(x1y1)=M(x2y2)，不过有两点需要注意，一个是他其实还是一种寻找强碰撞，另一个就是他的复杂度比王小云的直接构造高的多，然后这里有论文，然后利用这个搞了个预测2008年美国大选结果的东西，为啥叫预测呢，因为可以这样

因为我说我知道大选结果，但是必须事后公布，为了保证我没有说谎，我先给出一段MD5的值，之后给出我的结果，只要结果和MD5相同不就是我预测成功了吗

这个东西是基于我很难构造两个东西使得他们的MD5相同的基础上的，不过有了上面的算法，这个事情的复杂度大大降低，使得变为了可能。

那么这些破解对于我们有什么影响呢，首先需要认识到MD5有什么用，现在很多网站都用MD5来验证文件的完整性，但是你从非官方的地方下载了文件发现MD5相同，那么你依然不能掉以轻心，因为可能是通过上述算法而在程序里加入了某段病毒代码，但是MD5还是相同的而已，所以下文件还是从官方地址下吧，还一个就是经常在数字签名里使用了，至于不知道数字签名的这里先不说了，然后这个可以伪造数字签名啥的，不过传说现在貌似没谁用MD5来弄数字签名了，也不必太过担心了，基本就是这样子了。

本文由@isnowfy 的投稿于伯乐在线，也欢迎其他朋友投稿。提示：投稿时记得留下微博账号哦。

【如需转载，请标注并保留原文链接、译文链接和译者/作者等信息，谢谢合作！】

来自：http://blog.jobbole.com/22105/