彩虹表的改进

R的问题
在构造哈希链的时候，一个优秀的函数R功不可没。首先R需要能将值域限定在固定的范围——例如给定的长度范围、给定的字符取值范围等等——之内，否则的话，哈希链中大量的计算结果并不在可接受的取值范围内，一条链条无法对应多个明文，链条就失去了意义；其次R必须同哈希函数一样，尽量保证输出值在值域中的均匀分布，减少碰撞的概率。
然而实际上，很难找到能满足这些需求的完美的R函数。当计算中发生碰撞时，就会出现如下的情况：

图中加粗的部分，所涉及到的明文是完全重复的，因此这两条哈希链能解密的明文数量就远小于理论上的明文数2×k。不幸的是，由于集合只保存链条的首末节点，因此这样的重复链条并不能被迅速地发现。随着碰撞的增加，这样的重复链条会逐渐造成严重的冗余和浪费。
改进
对于这个问题，2003年提出的彩虹表算法进行了针对性的改进。它在各步的运算中，并不使用统一的R函数，而是分别使用R1…Rk共k个不同的R函数（下划线表示下标）。这样生成的哈希链集即被称为彩虹表。（在不同的运算位置使用不同的R函数，就像彩虹由内而外的不同位置上显示出不同的颜色一样。）这样一来，如果发生碰撞，通常会是下图的情况：

不难发现，当两个链条发生碰撞的位置并非相同的序列位置时，后续的R函数的不一致使得链条的后续部分也不相同，从而最大程度地减小了链条中的重复节点，保证了链条的有效性。
同时，如果在极端情况下，两个链条有1/k的概率在同一序列位置上发生碰撞，导致后续链条完全一致，这样的链条也会因为末节点相同而检测出来，可以丢弃其中一条而不浪费存储空间。
彩虹表的使用比哈希链集稍微麻烦一些。首先，假设要破解的密文位于任一链条的k-1位置处，对其进行Rk运算，看是否能够在末节点中找到对应的值。如果找到，则可以如前所述，使用起节点验证其正确性。否则，需要继续假设密文位于k-2位置处，这时就需要进行Rk-1、H、Rk两步运算，然后在末节点中查找结果。如是反复，最不利条件下需要将密文进行完整的R1、H、…Rk运算后，才能得知密文是否存在于彩虹表之中。