有人能为我澄清生日效应吗？ [英] Can someone please clarify the Birthday Effect for me?

问题描述

请帮助解释维基百科中描述的生日效应：

生日攻击的工作原理如下：

1. 选择任何消息m并计算h（m）。


2. 更新列表L.检查h（m）是否在列表L.


3. 如果（h（m），m）已经在L，找到了一个冲突消息对。
   else将该对（h（m），m）保存在
   列表L中，然后返回步骤1.
   

从生日悖论中我们知道，在执行大约
2 ^（n / 2）散列评估之后，我们可以期望找到一个
匹配项。

以上是否意味着通过上述整个循环的2 ^（n / 2）迭代（即2 ^（n / 2）返回到步骤1），还是意味着2 ^（n / 2）比较已经在L中的单个项目？

解决方案

它意味着2 ^（n / 2）通过循环。但请注意， L 在这里不是一个普通列表，而是一个将 h（m）映射到米。因此，每次迭代平均只需要一个常数（O（1））的比较，总共会有O（2 ^（n / 2））个比较。

如果L是一个正常数组或链表，那么比较次数会更多，因为每次迭代都需要搜索整个列表。这将是一个不好的方法来实现这个算法。

Please help interpret the Birthday effect as described in Wikipedia:

A birthday attack works as follows:

1. Pick any message m and compute h(m).
2. Update list L. Check if h(m) is in the list L.
3. if (h(m),m) is already in L, a colliding message pair has been found. else save the pair (h(m),m) in the list L and go back to step 1.

From the birthday paradox we know that we can expect to find a matching entry, after performing about 2^(n/2) hash evaluations.

Does the above mean 2^(n/2) iterations through the above entire loop (i.e. 2^(n/2) returns to step 1), OR does it mean 2^(n/2) comparisons to individual items already in L?

解决方案

It means 2^(n/2) iterations through the loop. But note that L would not be a normal list here, but a hash table mapping h(m) to m. So each iteration would only need a constant number (O(1)) of comparisons in average, and there would be O(2^(n/2)) comparisons in total.

If L had been a normal array or a linked list, then the number of comparisons would be much larger since you would need to search through the whole list each iteration. This would be a bad way to implement this algorithm though.

这篇关于有人能为我澄清生日效应吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！