MD5和MD5破解的一些事 MD5破解的介绍

看到网上一些对于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却是很困难的，这里就不展开说了，大家有个大体的认识就可以了。

（图来自维基百科）

刚才说过了由于MD5是多对一的，所以肯定会出现变换后的值是一样的情况，这种情况叫做冲突，或者叫碰撞。为了保证安全性，定义了两种，一种叫无弱碰撞，一种叫无强碰撞。
无弱碰撞是
已知函数M和一段数据H
找到一个H'
使得M(H)=M(H')
是难的
无强碰撞是
已知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))，所以说找到强碰撞更简单，也就是说满足无强碰撞更难！
王小云的贡献呢就是找到了比生日攻击复杂度低得多算法来快速找到一对强碰撞，弱碰撞吗依旧是不行的。这里有她的论文，有兴趣的可以看一下。那么也就是说通过密文找到明文依旧是不可能的，并且弱碰撞依旧是很难的。