彩虹表是如何解决碰撞的？

Question

我明白其中的要点。它就像蛮力攻击和查找表之间的中间地带，它存储由约简和哈希组成的每个链的起始明文和结束散列。

我不明白的是：

1. 据说彩虹表能解决碰撞，但为什么碰撞一开始就这么重要呢？
2. 据说彩虹表通过对链中的每一列使用不同的约简函数来解决碰撞，但是这如何防止碰撞呢？约简函数不是只是从散列中提取的随机字符吗？那么，如果你使用前8个字符而不是最后8个字符，会有什么不同呢？

Answer 1

目前投票最多的答案似乎并没有对你的问题作出适当的回答。我会试着同时回答你的两个问题。

在每列

中的相同约简函数

比方说，您对每一列都使用相同的约简函数，并且有一个有2行和3列的基本表。

P1  --R-->  P1'  --R-->  P1'' --R-->  P1'''
P2  --R-->  P2'  --R-->  P1'  --R-->  P1''

在这里，一个--R-->表示一个散列，然后是一个缩减。P1, P2, P1', ...代表密码。正如你所看到的，在第二条链中发生了碰撞。在第一个链中已经遇到了值P1'。

注意之后会发生什么。

由于散列和P1'的约简完全相同，所以我们得到了一个已经计算过的值。如果我们继续下去，从P1'开始的第二链的部分将成为从P1'开始的第一链部分的精确副本。

所以实际上，这就是为什么碰撞是坏的。第二条链合并成第一条。我们的表中有重复的结果，造成存储空间和计算时间的浪费。

各列

的不同约简函数

这一次，让我们看看如果我们对每一列使用不同的缩减会发生什么。约简用--RX-->表示，其中X是列号。

P1  --R1-->  P1'  --R2-->  P1'' --R3-->  P1'''
P2  --R1-->  P2'  --R2-->  P1'  --R3-->  P2''

同样，在这两个链中都遇到了P1'。但是，由于还原函数不同，在第二链中P1'之后计算的值不会像在第一链中那样产生P1''。这有效地解决了第一个示例中的合并问题。

请注意，这并不能解决所有的链合并。注意在下面的示例中发生了什么：

P1  --R1-->  P1'  --R2-->  P1''  --R3-->  P1'''
P2  --R1-->  P1'  --R2-->  P1''  --R3-->  P1'''

这一次，两条链的第一列发生碰撞。因为它发生在同一列中，所以每个下一个约简函数都将是相同的，并且这些链将再次合并。不过，这种情况发生的可能性较低。

Answer 2

碰撞是彩虹桌唯一的问题。具有讽刺意味的是，碰撞被认为是哈希算法的一件坏事，但是对于彩虹表来说，一种比较有规律地产生碰撞的散列算法将更安全。

据说彩虹表能解决碰撞，但为什么碰撞一开始就这么重要呢？

给定的散列可能由多个明文(这称为冲突)生成，这对于链来说是一个很大的问题，因为它会导致开始不同的链收敛到一个。此外，您还会得到循环，当哈希被简化为在链中的前一点被散列的明文时，循环就会产生。

据说彩虹表通过对链中的每一列使用不同的约简函数来解决碰撞，但是这如何防止碰撞呢？约简函数不是只是从散列中提取的随机字符吗？那么，如果你使用前8个字符而不是最后8个字符，会有什么不同呢？处理碰撞的方式使彩虹桌有别于1980年开发的它的前身。

前人通过使用许多小表格解决了某些明文永远不会减少的问题。每个小表使用不同的约简函数。这并不能完全解决问题，但确实有帮助。

为了解决链合并和循环，每条链都以“不同的点”结束；在某种程度上是唯一的散列，例如前4个字符为0的散列。铁链一直往前走，直到到达一个明显的点为止。如果两条链在同一点结束，那么在链中的某个地方发生了碰撞，其中一条链被丢弃。如果一个链生成了非常长的时间而没有到达一个不同的点，那么就会怀疑一个循环(其中一个哈希链最终会减少并散列到该链中的前一个散列)。问题是，如果发生碰撞，可能会有整个分支被切断，不能进入链中，而循环会导致链中所有在循环之前出现的散列被丢弃。而且，所有的时间花在产生这条链上都会被浪费掉，并且只有在不同的点结束，你就有了可变长度的链。这意味着您可能必须在其他链结束后很长的时间内继续检查其中的散列。

我从这里得到了正确的灵感：http://kestas.kuliukas.com/RainbowTables/