密码学 / 什么是彩虹表？

彩虹表的出现是为了解决破解 Hash 算法成本过高的问题（时间过长、所需硬盘空间过大）。

以前我也跟其他很多人一样，认为彩虹表就是描述“明文 & 密文”对应关系的一个大型数据库，破解时通过密文直接反查明文。

今天因某些需要而详细了解了彩虹表的一些细节，才发现其原理比之前想象的更值得称赞。它所谓的 time-memory trade-off，并不是简单地“以空间换时间”，而是双向的“交易”，在二者之间达到平衡。在此分享一些心得。本部分内容本答案主要参考资料为英文维基的 Rainbow table 词条。答案末尾分隔线后附上一个简化的比喻，希望能给更多的人说清楚这个问题。

在彩虹表之前，已经出现了对哈希函数的破解算法，被称为“预计算的哈希链集”（Precomputed hash chains）。

当面对要破解的哈希函数 H，首先要定义一个约简函数（reduction function）R，该函数的定义域和值域需要和哈希函数相反，通过该函数可以将哈希值约简为一个与原文相同格式的值（plain text value）。

需要强调的是，由于哈希函数 H 是不可逆的，所以对于密文进行 R 运算几乎不可能得到明文原文。例如，五位字母明文“zhihu”进行 H 运算后得到了“D2A82C9A”，而对“D2A82C9A”进行 R 运算后得到另一个五位字母格式的值“vfkkd”。因为这个值落在 H 的定义域中，因此可以对它继续进行 H 运算。就这样，将 H 运算、R 运算、H 运算……这个过程反复地重复下去，重复一个特定的次数 k 以后，就得到一条哈希链，例如 k 为 2 时得到：

这条链条并不需要完整地保存下来，只需要保存其起节点和末节点即可，例如上例中只需要保存起节点“zhihu”和末节点“crepa”。以大量的随机明文作为起节点，通过上述步骤计算出哈希链并将终节点进行储存，即可得到一张哈希链集。

这张集合需要如何使用呢？例如，我们知道哈希运算后的密文为“0CAFC376”，则先对其进行一次 R 运算，得到“crepa”。

正巧在本例中，它等于集合中的一个末节点，因此我们可以猜测，明文有极大的可能存在于以起节点“zhihu”开头、末节点“crepa”结尾的这条哈希链中。（注意可能性并不是100%，因为函数 H 和 R 均有可能发生碰撞，从不同的输入值得到相同的输出值。）为了验证我们的猜测，可以从起节点“zhihu”开始重复哈希链的计算过程：

算到这里我们发现，“vfkkd”进行哈希运算的结果正是密文“0CAFC376”，这样就找到了所需的明文。

如果密文不是“0CAFC376”而是“D2A82C9A”，第一次 R 运算后的结果并未在末节点中找到，则再重复一次 H 运算 + R 运算，这时又得到了末节点中的值“crepa”，则我们还是从起节点“zhihu”开始计算，这次可得到“D2A82C9A”对应的明文为“zhihu”。