参考原文：彩虹表 - 知乎

哈希链

• 预计算的哈希链集Precomputed hash chains
• 破解的哈希函数 H，约简函数 R
• 哈希函数 H 是不可逆的，所以对于密文进行 R 运算几乎不可能得到明文原文
• 约简函数 R 的要求
  • 能将值域限定在固定的范围 因此可以将 R 理解成一种hash函数
  • R 必须同哈希函数一样，尽量保证输出值在值域中的均匀分布，减少碰撞的概率

构造哈希链

• 对明文进行H运算得到密文，对此密文进行R运算，得到下一次进行H运算的明文
• 对一个随机的起始明文进行k次的“H运算，R运算”后，得到一条哈希链 如下图
• 哈希链只需要保存起节点（第一个随机明文）和末节点，从而节省了存储空间

k = 2的哈希链

哈希链集

• 大量的随机明文作为起节点，得到多条哈希链作为哈希链集

• 破解流程：目标密文 C，目标明文 P，哈希链集 S

  • 对C进行一次R运算，如果运算结果的明文在S的任意一末节点上，即可猜测P极大可能在此哈希链上
  • 如果不存在这样一条哈希链，则先进行一次H运算后，再R运算得到新的结果明文进行判断
  • 如此往复，直到尝试了K次R运算后，所需的P并不在S里（每一条哈希链都是经过了K次的H，和K次的R，所以K次即为上限）
  • 如果找到这样的一条哈希链，则从其的起节点起，按照构造哈希链的顺序查找，P在找到C的那一次H运算中

彩虹表

哈希链集的不足之处

出现碰撞的哈希链

• 如果约简函数 R 出现了哈希碰撞，碰撞处往后的链条节点完全相同，造成了冗余
• 为了减小此情况带来的影响，出现了彩虹表

彩虹表的改进之处

• 一条运算K次的哈希链，将使用K个不同的约简函数，R₁ ... R_k
• 即便在某一处出现了哈希碰撞，也会因后续使用的 R_i 的不同从而避免了冗余（极大概率）

彩虹表的防御

• 加盐salt
• 提高单次H运算的计算耗时