信息摘要算法之MD5( 二 ) _MD5

原理就是记录尽可能多的原文和对应的hash值，破解的时候，拿到摘要去找查找对应的原文，即可快速的碰撞摘要信息从而达到破解的目的。
那么，对应的8位密码，按照Base64可打印字符排列组合，大概需要多大的空间呢？
即（128+64）*64^8=6PB的空间，假设一台计算器的内存为1TB ，则需要6144台计算机存储所有的数据。而这对应的只是一个8位数的密码，越长，存储的成本也就成指数增长。
3.彩虹表法（比较烧脑，不感兴趣的可以绕开）
了解彩虹表之前，先了解两个函数：H(X),R(X)
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次为止
其实，每个hash链表维护了一组映射关系，每组包括k个映射，但只需存储首位两个字符串。假设K=10 ，那么其需要的存储空间则为全量字典的1/10 ，效率也就提高了10倍。
即使如此，彩虹表的衰减函数R(X)依然存在致命弱点，即使R(X)设计的hash分布再均衡，依然存在hash碰撞的可能。
示例：
给定信息摘要：FB107E70
经过多次R（X）， H（X）运算，得到结果kiebgt
【信息摘要算法之MD5】通过哈希表查找末端kiebgt ，可以找出首端aaaaaa
但是， FB107E70并不在aaaaaa到kiebgt的哈希链条当中，这就是R（X）的碰撞造成的。

文章插图

这个问题看似没什么影响，既然找不到就重新生成一组首尾映射即可。但是想象一下，当K值较大的时候，哈希链很长，一旦两条不同的哈希链在某个节点出现碰撞，后面所有的明文和哈希值全都变成了一毛一样的值。
这样造成的后果就是冗余存储。原本两条哈希链可以存储 2K个映射，由于重复，真正存储的映射数量不足2K 。
这个时候，彩虹表出现了，嗯，现在才是真正的彩虹表原理部分：
彩虹表对链表进行了改进，把原来的R(X)分割成R(1)....R(K)个衰减函数，这样也可能发生碰撞，但最多同一级的碰撞，即R1和R1 ， R2和R2碰撞，大大避免了数据重复存储的可能。