密码学 ｜ 5.4.2 碰撞定理

定理 5.38（碰撞定理）

进而得到

于是我们完成了 （2） 的证明。

例 5.39

例 5.40

例 5.41

注 5.42 依赖于从一个或多个列表中查找匹配元素的算法有多种名称，包括碰撞算法、中间相遇算法、生日悖论算法和平方根算法。最后一个是指碰撞算法的运行时间通常是穷举搜索所需运行时间的平方根的小倍数。当这些算法中的一种被用来破解密码系统时，“算法”一词通常被“攻击”一词所取代，因此密码分析时常称为中间相遇攻击、平方根攻击等。

注 5.43 碰撞算法倾向于采取大约  个步骤来找到  个对象之间的碰撞。这些算法的一个缺点是，它们需要创建一个或多个大小约为  的列表。当  较大时，为  个数字提供存储可能比进行计算更为困难。在第 5.5 节中我们将描述一种 Pollard’s  的碰撞方法，该方法以少量额外计算为代价来减小存储开销，实际上基本上不需要存储。