有人可以帮我解释一下生日效应吗？
请帮助解释维基百科中描述的生日效应：
生日攻击的工作原理如下：
- 选择任意消息 m 并计算 h(m)。
- 更新列表L。检查h(m)是否在列表L中。
- 如果 (h(m),m) 已在 L 中，则已发现冲突消息对。 否则将 (h(m),m) 对保存在 列出 L 并返回步骤 1。
从生日悖论我们知道我们可以期望找到一个 执行 about 后匹配条目 2^(n/2) 次哈希评估。
上述是否意味着通过上述整个循环进行 2^(n/2) 次迭代（即 2^(n/2) 返回到步骤 1），或者是否意味着与 L 中已有的单个项目进行 2^(n/2) 次比较？
Please help interpret the Birthday effect as described in Wikipedia:
A birthday attack works as follows:
- Pick any message m and compute h(m).
- Update list L. Check if h(m) is in the list L.
- 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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这意味着循环进行 2^(n/2) 次迭代。但请注意，这里的
L并不是一个普通的列表，而是一个将h(m)映射到m的哈希表。因此每次迭代平均只需要常数 (O(1)) 次比较，总共会有 O(2^(n/2)) 次比较。如果 L 是普通数组或链表，则比较次数会大得多，因为每次迭代都需要搜索整个列表。但这将是实现该算法的一个糟糕方法。
It means 2^(n/2) iterations through the loop. But note that
Lwould not be a normal list here, but a hash table mappingh(m)tom. 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.