彩虹表原理

以前一直以为彩虹表就是一个大的数据库，破解的时候直接通过查表获得明文。今天发现我错了，彩虹表的原理还是挺有趣的。

如果直接暴力破解 Hash 的明文太费时，如果通过查表的方法则太耗存储。彩虹表则是暴力破解与查表破解的折中。

原理

假设有这么一个函数R，可以将 Hash 值转化与字符串（非明文，而是另一个字符串），称其为衰减函数。假设p为明文，h为明文的 Hash 值，H为 Hash 函数。彩虹表在建表时，先选一个p[0]，做如下计算：

h[0] = H(p[0]) p[1] = R(h[0]) h[1] = H(p[1]) ... h[k]  = H(p[k]) ... h[n - 1] = H(p[n - 1]) p[n] = R(h[n - 1])

其中n为迭代的次数。

经过，这种运算之后，会形成一条 Hash 链：

p[0]--->h[0]--->p[1]--->...--->p[k]--->h[k]--->...--->p[n]

这条链上已经有n对明文到 Hash 值的对应关系了，但我们只保存首尾p[0]和p[n]，因为中间的值可以用p[0]重新通过上述的计算运算出来。

彩虹表中有好多条这样的链p[0]-->p[n]，n值取足够大。这样就可以用p[0]和p[n]的存储空间，存储n对的明文到 Hash 值的对应关系。

破解

假设待破解的 Hash 值为h'，那么我们可以反复地迭代运算 p' = R(h'), h‘= H(p')，直到p'与彩虹表中的某个p[n]相等。

该链为p[0]-->p[n]，那么h'的明文很有可能在这条链中，因为这条链是通过p[0]反复迭代得到p[n]的，h'也是通过反复迭代得到p[n]。

我们只要知道h'迭代到p[n]的次数，只在找到链中迭代到p[n]相同次数的h[k]，就可以获得其明文p[k]（在链中，h[k] = H(p[k])）。