在之前的漫画中，我们介绍了MD5算法的基本概念和底层原理，没看过的小伙伴们可以点击下面的链接：
这一次，我们来讲解如何破解MD5算法。
设MD5的哈希函数是H（X），那么：
H(A) = M
H(B) = M
任意一个B即为破解结果。
B有可能等于A，也可能不等于A。
用一个形象的说法，A和B的MD5结果“殊途同归”。
MD5碰撞通常用于登陆密码的破解。应用系统的数据库中存储的用户密码通常都是原密码的MD5哈希值，每当用户登录时，验签过程如下：
如果我们得到了用户ABC的密码哈希值E10ADC3949BA59ABBE56E057F20F883E，并不需要还原出原密码123456，只需要“碰撞”出另一个原文654321（只是举例）即可。登录时，完全可以使用654321作为登陆密码，欺骗过应用系统的验签。
暴力枚举法
字典法
彩虹表法
H（X）：生成信息摘要的哈希函数，比如MD5，比如SHA256。
R（X）：从信息摘要转换成另一个字符串的衰减函数（Reduce）。其中R（X）的定义域是H（X）的值域，R（X）的值域是H（X）的定义域。但要注意的是，R（X）并非H（X）的反函数。
通过交替运算H和R若干次，可以形成一个原文和哈希值的链条。假设原文是aaaaaa，哈希值长度32bit，那么哈希链表就是下面的样子：
这个链条有多长呢？假设H（X）和R（X）的交替重复K次，那么链条长度就是2K+1。同时，我们只需把链表的首段和末端存入哈希表中：
给定信息摘要：920ECF10
如何得到原文呢？只需进行R（X）运算：
R（920ECF10） = kiebgt
查询哈希表可以找到末端kiebgt对应的首端是aaaaaa，因此摘要920ECF10的原文“极有可能”在aaaaaa到kiebgt的这个链条当中。
接下来从aaaaaa开始，重新交替运算R（X）与H（X），看一看摘要值920ECF10是否是其中一次H（X）的结果。从链条看来，答案是肯定的，因此920ECF10的原文就是920ECF10的前置节点sgfnyd。
需要补充的是，如果给定的摘要值经过一次R（X）运算，结果在哈希表中找不到，可以继续交替H（X）R（X）直到第K次为止。
给定信息摘要：FB107E70
经过多次R（X），H（X）运算，得到结果kiebgt
通过哈希表查找末端kiebgt，可以找出首端aaaaaa
但是，FB107E70并不在aaaaaa到kiebgt的哈希链条当中，这就是R（X）的碰撞造成的。
这个问题看似没什么影响，既然找不到就重新生成一组首尾映射即可。但是想象一下，当K值较大的时候，哈希链很长，一旦两条不同的哈希链在某个节点出现碰撞，后面所有的明文和哈希值全都变成了一毛一样的值。
这样造成的后果就是冗余存储。原本两条哈希链可以存储 2K个映射，由于重复，真正存储的映射数量不足2K。
2004年，王小云教授提出了非常高效的MD5碰撞方法。
2009年，冯登国、谢涛利用差分攻击，将MD5的碰撞算法复杂度进一步降低。
几点补充：
对于单机来说，暴力枚举法的时间成本很高，字典法的空间成本很高。但是利用分布式计算和分布式存储，仍然可以有效破解MD5算法。因此这两种方法同样被黑客们广泛使用。
最后推荐一篇不错的文章，有关Linux的干货：
—————END—————
喜欢本文的朋友们，欢迎长按下图关注订阅号梦见，收看更多精彩内容
原文始发于微信公众号（程序员小灰）：漫画：如何破解MD5算法？
