昨天微信群里又热闹了起来，我一看消息，原来是有人在讨论：“如果突然有一天 MD5 算法被破解了，可逆了怎么办？”

其中有些网友表示，这题我会。

“如果它被破解了，我 35 岁之后就有事干了”

“如果可逆了，全宇宙最强的压缩算法就诞生了，任意字节数据都可以压缩到128bits”

“根据摘要就能把论文全文推导出来，碉堡了”

...

群消息刷了很多，都在带薪摸鱼，却没人讨论，具体怎么破解。所以，今天我就来献丑一下，浅谈一下 MD5 怎么样“破解”，大家轻喷！

在正式介绍 MD5 “破解”的方法前，先说明一点：目前我们没办法把 MD5 字符串还原回对应的原文。道理很简单，任意长度的数据经过 MD5 处理后，所包含的信息量已经大大减少。要是可以还原的话，那 MD5 岂不是成为最强的压缩算法了？？

所以，目前所谓的“破解”指的就是“碰撞”。即找到一个原文，算出来的 MD5 码和已知的 MD5 码一样。接下来介绍一些常见的破解方法。

小标题上写了两种方法：穷举法和字典法。但是我认为它们的本质是一样的，都是利用计算机的资源尝试碰撞已知的 MD5 码。这里就放在一起了。

穷举法非常简单，就是不停地尝试各种字符的排列组合，看哪一个组合的 MD5 码能对上。可惜缺点是太耗费时间了。我们举个栗子，假设我们要破解一个 6 位大小写字母和数字混合的密码，那么一共有 种组合。这个数的大小超过 500 亿。

只考虑大小写字母和数字，每一位有 62 种可能，那么 8 位密码的排列组合就是 62 的 8 次方，218340105584800，约等于二百万亿！

既然计算如此费时，能不能考虑「把计算结果以映射表的形式存放起来，一个萝卜一个坑」，一个原文对应着一个 MD5 码呢？可以呀！这就是传说中的“字典法”。将已知的 MD5 码查表，直接反查出原文。

字典法体现了算法设计的“以空间换时间”的思想。「缺点是比较耗费空间。不过现在硬盘的价格变得白菜价了，空间开销不算什么。」

所以，简单且常见的密码，如果用了 MD5 加密，会被暴力的很快。况且现在量子计算机要来了，等量子计算机发展到和我们现在的普通笔记本大小，MD5 被暴力的就更快了，说不定就是分分钟的事。

给大家推荐一个用字典法破解 MD5 的网站：https://www.cmd5.com/password.aspx

如果说穷举法太耗费时间，字典法太耗费存储空间的话，我们能不能考虑在时间消耗和空间消耗之间折中呢？我们可以考虑用链表将一系列有意义的原文和 MD5 码串起来。

要构造这样的链表，我们需要两个函数：哈希函数 H(x)和衰减函数（reduction function）R(x)。哈希函数可以是 MD5，也可以是其他的消息摘要算法。H(x) 的值域是 R(x) 的定义域，R(x) 的值域是 H(x)的定义域。「R(x)不是H(x)的反函数。」

将一个原文不停地使用 H(x) 和 R(x) 交替进行运算 k次，再将原文本身和运算结果以链表的形式串接起来，就可以得到结点个数为 2k+1 的链表。实际存放的时候只存放首端和末端两个原文即可。「这种链表叫做“哈希链表”，体现了算法设计的“时空权衡”（Space and Time Tradeoffs）。」

举个栗子，假设原文s=abcabc，经过 2 次交替运算，得到以下的链表：

❝ abcabc->H(x)->3C8B0D7A->R(x)->eopmca->H(x)->7E9F216C->R(x)->rapper ❞

以上数据均为举例编造的，仅为说明原理使用。那我们存放这个链表的时候，只需要记录 abcabc 和 rapper 两个原文即可。

假设我们要破解的摘要值（哈希链表的 H(x) 不一定是 MD5 算法，这里用更准确的说法代替 MD5 码）是 7E9F216C，经过 R(x) 运算得到 rapper，说明我们要寻找的原文就在以 rapper 为末端的哈希链表中。从首端开始经过多次运算，我们发现 eopmca 的摘要值就是 7E9F216C。于是就反查出 7E9F216C 对应的原文是 eopmca。

「如果在生成哈希链表的时候依次使用多个不一样的 R(x)，此时的哈希链表就是“彩虹表”。」

文字描述起来太过复杂，还是用图列举一个 demo。

彩虹表法

这里再给大家推荐一个已经计算好的彩虹表：http://project-rainbowcrack.com/table.htm

上面介绍的穷举法、字典法和彩虹表法都是暴力破解，适用于任何的消息摘要算法。真正意义上 MD5 算法的破解，是 2004 年山东大学王小云教授提出的 MD5 碰撞方法。她所用到的方法正是差分攻击。

这种方法概括起来说是这样的：给定一个 1024 位的原文 M1，加上一个特定的常数得到的新的明文 M2。M1 和 M2 的 MD5 码是一样的。（这里大家可以去找具体的论文）这个特定的常数到底是怎么找出来的？笔者当时在查阅原始文献的时候也不清楚。因此后来的研究者开始对怎么样差分进行了各种各样的研究。具体的方法比较复杂，我就这里就不再赘述，班门弄斧了。

其实还有一种破解 MD5 的方法——长度扩展攻击。不过这种方法是在一定条件下（破解加盐之后产生的 MD5 码）才能用的。这种方法由 MD5 分块计算的特性而来。

如果，我是说如果。你能逆转破解成功，你一定会获得图灵等计算机大奖。大大的解放数据存储能力，任何数据都可以用一段字符串表示。