你真的了解MD5吗？
导语 | 日常开发中，在用到签名的地方我们基本上总是可以看到MD5的身影。但是你真的了解它吗？本文将以探索的思路带你走进MD5。
引言
在日常开发中，在用到签名的地方，我们经常可以看到会有一个token，一般而言这个token是经过约定的MD5规则生成的，生成的php代码一般如下（其中salt是约定的一个盐值，提高签名token的安全性）：
$token = md5(salt . code)可以发现token都是一个长字符串，由数字和字母构成的，例如：365e3982a117a192f5d7c9882b3d1df1。仔细研究token，我们就会发现token中的英文字母只有a~f，大胆猜想一下：token中的每个字母或者数字是不是一个十六进制的数呢？还有一点，每次md5生成的值的长度好像都是那么长，仔细一数发现是32位，那是不是：每个MD5生成的值都是一个长度为32位，每一位都是一个十六进制数字而组成的字符串呢？
二、猜想
经过我们的“研究”，我们有了以下两个大胆的猜想：
MD5生成的值长度是固定的。
如果设置为十六进制输出，那么MD5的结果长度是32。如果按照一位十六进制占4位来算，MD5的结果长度固定为128bits。
三、原理
没有什么问题是看源码或者官方API文档不能解决的！为了验证我们的猜想，经过研究MD5的官方原稿，总结原理如下：
MD5原稿：
https://datatracker.ietf.org/doc/html/rfc1321
MD5算法的整体流程如上图所示，主要分为4步：处理原文、设置初始值、循环加工、拼接结果。
（一）处理原文
处理原文就是一个关键词：补位，此处的补位有两个地方需要补。那具体怎么补位呢？
补填充位
首先需要对原文补填充位，使得带填充位后的长度对512取余为448。填充位怎么补呢？首位是1其余的各位都是0，如下图所示：
到这里，我们就会有两个问题：
为什么是对512取余，而且为什么补位要补到对512取余后为448？
如果原文的长度本来就是对512取余是448呢，是不是就不需要进行填充位的填补了？
首先我们来解决第2个问题：假设原文长度为len，且mod(len, 512) = 448，则需要再补充512位的填充位。假设填充位长度为appendLen，则有伪代码：
if(mod(len, 512) < 448) {appendLen = 448 - mod(len, 512);} else {appendLen = 448 + 512 - mod(len, 512);}
至于第1个问题，我们接着往下看：
补数据长度
这里需要补64位的原文长度，我们会发现，补充齐64位后，整体的长度就是512的整数倍了。这里就可以回答上面的第一个问题了：MD5是一种基于block的算法，要求每次处理的block都是512bits。64位的数据长度，即最长可以是2^64 。那如果原文的长度len > 2^64呢？则取len的低阶64位进行填充。
此时的数据是16字（32位）的整数倍，用M[0，...，N-1]表示此时的数据，其中N为16的倍数。如下图所示：
（二）设置初始值
MD5的结果是是由4个初始值A、B、C、D经过不断演变得到。MD5的官方实现中，A、B、C、D的初始值如下（16进制）：
A=0x01234567
B=0x89abcdef
C=0xfedcba98
D=0x76543210
到这里，其实我们就会发现我们一开始的猜想基本上就被验证了。MD5的结果长度确实是固定的，并且长度是128位。那具体是怎么演变得到的呢？
（三）循环加工
这一步是整个算法最重要的一步。话不多说，先上图：
图中，ABCD就是哈希值的四个分组，每一次循环都会让旧的ABCD产生新的ABCD。一共进行多少次循环呢？由处理后的原文长度决定。
假设经过第一步处理原文之后的长度为M，则主循环次数L=M÷512，每个主循环中包含512÷32*4=64次子循环，分为4组16次。上面这张图表达的是一次子循环的流程。
其中F是一个非线性函数。MD5用到的非线性函数有下面四种，4组循环中依次使用FGHI。
F(X，Y，Z) =(X&Y) | ((~X) & Z)
G(X，Y，Z) =(X&Z) | (Y & (~Z))
H(X，Y，Z) =X^Y^Z
I(X，Y，Z)=Y^(X|(~Z))
其中Mi为原文的一个分组，长度为32bits，每次循环所用到的分组编号不同，会交替使用到M0到M15中的数据。
而Ki则是一个32bits的常量，具体的计算公式如下：
Ki=floor(2^64*sin(i)) i的范围是1~64，单位是弧度
而<<
[7，12，17，22 ]
[5，9，14，20]
[4，11，16，23]
[6，10，15，21]
第一组16次循环中依次使用【7，12，17，22】，使用4次，以此类推。所以经过一次循环后可以发现(其中=左边为新，等号右边全部使用旧的abcd)：
a=d
b=(F(b，c，d)+Mi+Ki)<<
d=c
而一次主循环的4组16次子循环依次如下：
第一轮
FF(a，b，c，d，M0，7，0xd76aa478)
FF(d，a，b，c，M1，12，0xe8c7b756)
FF(c，d，a，b，M2，17，0x242070db)
FF(b，c，d，a，M3，22，0xc1bdceee)
FF(a，b，c，d，M4，7，0xf57c0faf)
FF(d，a，b，c，M5，12，0x4787c62a)
FF(c，d，a，b，M6，17，0xa8304613)
FF(b，c，d，a，M7，22，0xfd469501)
FF(a，b，c，d，M8，7，0x698098d8)
FF(d，a，b，c，M9，12，0x8b44f7af)
FF(c，d，a，b，M10，17，0xffff5bb1)
FF(b，c，d，a，M11，22，0x895cd7be)
FF(a，b，c，d，M12，7，0x6b901122)
FF(d，a，b，c，M13，12，0xfd987193)
FF(c，d，a，b，M14，17，0xa679438e)
FF(b，c，d，a，M15，22，0x49b40821)
第二轮
GG(a，b，c，d，M1，5，0xf61e2562)
GG(d，a，b，c，M6，9，0xc040b340)
GG(c，d，a，b，M11，14，0x265e5a51)
GG(b，c，d，a，M0，20，0xe9b6c7aa )
GG(a，b，c，d，M5，5，0xd62f105d)
GG(d，a，b，c，M10，9，0x02441453)
GG(c，d，a，b，M15，14，0xd8a1e681)
GG(b，c，d，a，M4，20，0xe7d3fbc8)
GG(a，b，c，d，M9，5，0x21e1cde6)
GG(d，a，b，c，M14，9，0xc33707d6)
GG(c，d，a，b，M3，14，0xf4d50d87)
GG(b，c，d，a，M8，20，0x455a14ed)
GG(a，b，c，d，M13，5，0xa9e3e905)
GG(d，a，b，c，M2，9，0xfcefa3f8)
GG(c，d，a，b，M7，14，0x676f02d9)
GG(b，c，d，a，M12，20，0x8d2a4c8a)
第三轮
HH(a，b，c，d，M5，4，0xfffa3942)
HH(d，a，b，c，M8，11，0x8771f681)
HH(c，d，a，b，M11，16，0x6d9d6122)
HH(b，c，d，a，M14，23，0xfde5380c)
HH(a，b，c，d，M1，4，0xa4beea44)
HH(d，a，b，c，M4，11，0x4bdecfa9)
HH(c，d，a，b，M7，16，0xf6bb4b60)
HH(b，c，d，a，M10，23，0xbebfbc70)
HH(a，b，c，d，M13，4，0x289b7ec6)
HH(d，a，b，c，M0，11，0xeaa127fa)
HH(c，d，a，b，M3，16，0xd4ef3085)
HH(b，c，d，a，M6，23，0x04881d05)
HH(a，b，c，d，M9，4，0xd9d4d039)
HH(d，a，b，c，M12，11，0xe6db99e5)
HH(c，d，a，b，M15，16，0x1fa27cf8)
HH(b，c，d，a，M2，23，0xc4ac5665)
第四轮
II(a，b，c，d，M0，6，0xf4292244)
II(d，a，b，c，M7，10，0x432aff97)
II(c，d，a，b，M14，15，0xab9423a7)
II(b，c，d，a，M5，21，0xfc93a039)
II(a，b，c，d，M12，6，0x655b59c3)
II(d，a，b，c，M3，10，0x8f0ccc92)
II(c，d，a，b，M10，15，0xffeff47d)
II(b，c，d，a，M1，21，0x85845dd1)
II(a，b，c，d，M8，6，0x6fa87e4f)
II(d，a，b，c，M15，10，0xfe2ce6e0)
II(c，d，a，b，M6，15，0xa3014314)
II(b，c，d，a，M13，21，0x4e0811a1)
II(a，b，c，d，M4，6，0xf7537e82)
II(d，a，b，c，M11，10，0xbd3af235)
II(c，d，a，b，M2，15，0x2ad7d2bb)
II(b，c，d，a，M9，21，0xeb86d391)
其中FF(a，b，c，d，Mi，s，Ki)表示a=b+((F(b，c，d)+Mi+Ki)<<
（四）拼接结果
最终经过L次主循环之后，将每次主循环之后的结果拼接在一起便得到了MD5的最终结果。
四、特性
研究完原理之后，我们会发现，MD5有一个非常重要的特性：不可逆。因为在上述FGHI操作中，是有部分信息丢失的，没有办法通过结果反推得到原文。而其实这样也给MD5带来一个好处：即使在原文中稍微改动一点，得到的MD5结果也会截然不同，所以很适合用于签名中，伪造篡改的成本很高。
所以进而引发了一个争论：MD5是加密算法吗？如果从加解密角度看，加密之后没有办法通过一定手段解密得到原文，MD5不属于加密算法。
其次，由于MD5的结果长度是固定的，所以MD5的结果是有限的，但是原文是无限的。所以MD5算法不是严格意义上的一对一的，是多对一。即：存在原文A和B，且A≠B，但是MD5(A)=MD5(B)的可能。
既然如此，就引出了MD5的破解方法：找到一个原文B，使得原文B的MD5值和原文A的MD5值相同（其中找到的B可能就是A，也可能不是A，但是“殊途同归”）
五、破解
（一）暴力破解
暴力破解有两个极端：一个是时间复杂度极高的穷举法；另一个是空间复杂度极高的字典法。
穷举法
穷举法的思路十分简单，就是不断穷举尝试，直到找到一个原文B使得MD5值与原本A的MD5值相同。就以6位明文为例（字母和数字组成），一共就有62^6=56800235584种组合。可想而知如果明文长度加长，这种方法的时间复杂度有多高。
字典法
既然每个原文的MD5值都是固定的，那把所有的MD5值记下来，然后通过匹配去定位到原文。这就是字典法。同理可见，该方法的空间复杂度极高。
（二）哈希列表&彩虹表
暴力破解法走了两个极端的路，那有没有折中的方法呢？有！接下来介绍一下哈希列表及其优化彩虹表。
哈希列表
哈希列表其实是暴力破解两个方法的一个折中，即考虑用链表将一系列有关联的原文和MD5值串联起来，仅存储“头”和“尾”。
构造这样的链表前，我们先介绍两个函数：哈希函数H(x)和衰减函数R(x)。其中H(x)是生成信息摘要的哈希函数，可以是MD5，也可以是其他信息摘要算法。R(x)是从信息摘要转换成字符串的衰减函数。
注意：H(x)的值域是R(x)的定义域，R(x)的值域是H(x)的定义域。但是注意R(x)不是H(x)的反函数。
哈希链表的原理就是：将原文不停的使用H(x)和R(x)交替进行k次运算，然后再将原文和运算结果以链表的形式存储起来，得到节点个数为2K+1的链表。实际存放时，只存放最开始的原文和最后生成的字符串。具体如下(图中数据仅为说明原理)：
假设我们现在要破解的值为2c5e1873，经过R(x)计算得到了lknegc，说明我们寻找的原文就在以abcdef为首，lknegc为尾的链表中。那么我们从abcdef开始经过一系列计算发现opyntf的H(x)值为2c5e1873，那么我们便找到了2c5e1873的原文是opyntf。
简单来说，哈希链表代表了一组映射关系，其中每组包含K对映射，但只存储了首尾两个字符串。这样存储空间只是字典法的K分之一，代价就是破解时运算次数提高了K倍，这就是空间和时间之间的取舍。
但是！哈希链表有一个致命的缺陷：衰减函数R(x)的可靠性。尽管R(x)在设计时已经尽可能的使其结果均匀分布了，但是仍然无法避免碰撞的情况发生。如下图示例：
现在我们拿到5c38d215，想要得到它的原文，经过一系列运算之后得到结果lknegc，但是我们会发现5c38d215并不在abcdef，lknegc的链表中。这样我们就没办法通过对abcdef进行一系列运算得到5c38d215的原文。
有人会说，那就再记录一个链表，存放有5c38d215值的，假设首尾分别为burnlf和lknegc。但是我们会发现，这样就导致了冗余存储，本身两个链表可以存2K个映射，但是由于重复的存在，实际上不足2K。
那有没有避免碰撞的方法呢？由此便诞生了彩虹表。注意：彩虹表也仅是降低碰撞的概率，不能完全避免。
彩虹表
彩虹表是在哈希链表上进行改进得来的，将R(x)改进，用R1(x)到Rk(x)一共k个衰减函数替代。这样一来虽然仍然可能碰撞，但是碰撞只会发生在链表中的一节，大大减小了重复存储的几率。
（三）差分攻击
还有更厉害的破解方法就是差分攻击，王小云教授当初使用查分攻击算法连续攻破MD5和SHA-1等，该方法的关键是如何寻找差分和差分路径，此处不做过多介绍，想要深入了解的可以由参考文献入门开始探究。
参考文献
1.MD5算法原理及其实现
2.漫画：什么是MD5算法？
3.MD5算法
4.维基百科 MD5
5.张裔智，赵毅，汤小斌，《MD5算法研究》，计算机科学，2008,Vol.35 No.7
6.MD5算法如何破解
7.MD5破解的几种方法
8.周林，韩文报，王政，《Hash差分攻击算法研究》，计算机科学，2010，Vol.37 No.9
9.差分攻击
作者简介
韩雄飞
腾讯运营开发工程师
腾讯运营开发工程师，毕业于同济大学。目前负责腾讯天美部分游戏业务的营销活动开发工作，有丰富的游戏运营活动开发经验。
推荐阅读
超实用教程！一探Golang怎样践行Clean Architecture？
颠覆Kafka的统治，新一代云原生消息系统Pulsar震撼来袭！
