彩虹表 信息摘要算法之MD5

单次子循环过程

图中，A，B，C，D就是哈希值的四个分组。每一次循环都会让旧的ABCD产生新的ABCD。一共进行多少次循环呢？由处理后的原文长度决定。

假设处理后的原文长度是M

主循环次数 = M / 512

每个主循环中包含 512 / 32 * 4 = 64 次 子循环。

1.绿色F

图中的绿色F，代表非线性函数。官方MD5所用到的函数有四种：

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))

在主循环下面64次子循环中，F、G、H、I 交替使用，第一个16次使用F，第二个16次使用G，第三个16次使用H，第四个16次使用I。

2.红色“田”字

很简单，红色的田字代表相加的意思。

3.Mi

Mi是第一步处理后的原文。在第一步中，处理后原文的长度是512的整数倍。把原文的每512位再分成16等份，命名为M0~M15，每一等份长度32。在64次子循环中，每16次循环，都会交替用到M1~M16（命名+1）之一。

4.Ki

一个常量，在64次子循环中，每一次用到的常量都是不同的。

5.黄色的<<

循环左移S位，S的值也是常量。

“流水线”的最后，让计算的结果和B相加，取代原先的B。新ABCD的产生可以归纳为：

新A = 原d

新B = b+((a+F(b,c,d)+Mj+Ki)<<

新C = 原b

新D = 原c

总结一下主循环中的64次子循环，可以归纳为下面的四部分：

拼接结果

一步就很简单了，把循环加工最终产生的A，B，C，D四个值拼接在一起，转换成字符串即可

整个过程及其复杂和繁琐，也促使它在一定程度上保证了hash值的均匀分布和安全性。

即使MD5的加密如此复杂，但也并非不可破解的。但总体来说，所有的破解方法都采用“碰撞”方式，类似于不同字符的hash值可能相同的原理，即hash(A)==hash(B),尽管大多数的时候在内存中A!=B，但是MD5加密后的值是相同的。

那么怎么实现MD5的摘要碰撞呢？

MD5的破解方法及其多，像暴力枚举，字典，彩虹表等方法。

1.暴力枚举法

简单暴力的枚举出原文，并计算他们的hash值，看是否与摘要信息一致来达到破解目的。此方法时间复杂度极高，仅仅8位的密码，只考虑Base64中的字符，就会有64^8中可能，如果只是单机破解，可能需要几十年。当然，也可以取巧，例如考虑生日或者电话号码等等，缩小穷举范围。

2.字典法

既然暴力破解这么费时，典型的以时间换空间，那么就有人采用了相反的方式，即字典法，拿空间换时间。

原理就是记录尽可能多的原文和对应的hash值，破解的时候，拿到摘要去找查找对应的原文，即可快速的碰撞摘要信息从而达到破解的目的。

那么，对应的8位密码，按照Base64可打印字符排列组合，大概需要多大的空间呢？

即（128+64）*64^8=6PB的空间，假设一台计算器的内存为1TB，则需要6144台计算机存储所有的数据。而这对应的只是一个8位数的密码，越长，存储的成本也就成指数增长。

3.彩虹表法（比较烧脑，不感兴趣的可以绕开）

了解彩虹表之前，先了解两个函数：H(X),R(X)

H（X）

R（X）

通过交替运算H和R若干次，可以形成一个原文和哈希值的链条。假设原文是aaaaaa，哈希值长度32bit，那么哈希链表就是下面的样子