密码学｜ 5.4.2 碰撞定理

密码学 2年前 (2023) admin

485 0 0

碰撞算法在密码学中的应用通常基于以下场景。假设 Bob 有一个包含个数字的盒子。他从盒子选择个不同的数字，并将它们放入列表中。然后，他从盒子中再选择个（不一定不同）数字，构造出第二个列表。值得注意的是，如果和都稍大于，那么这两个列表很可能包含一个共同的元素。

我们从一个基本结论开始，该结论用于量化碰撞算法成功的概率。

定理 5.38（碰撞定理）

一个盒子中有个球，其中个是红色的，个是蓝色的。Bob 从盒子中有放回的随机选择颗球，那么

1. Bob 至少选到一次红色球的概率为

密码学｜ 5.4.2 碰撞定理

2. 式 5.28 的下界为

密码学｜ 5.4.2 碰撞定理

如果很大，并且略大于，（比如，，那么不等式则十分接近于等式。

证明：

Bob每次取球取到红色球的概率为，因此你会想，由于 Bob 要取次，那么他取到一次红色球的概率为，然后再仔细想一想就可以知道这样的想法是不对的。因为，如果足够大，那么这个概率公式的值肯定会大于 1。为什么呢？就像我们在前一节中介绍生日悖论时的情况相似，我们重复计算了取到多个红色球的概率。正确的计算方式应该是计算 Bob 全部取到蓝色球的概率，然后用 1 减去这个事件的概率。因此

定理（1）证毕。

对于定理（2），我们使用基本不等式，我们设，并且等式两边升次，得到

进而得到

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

（PS：为什么当都略大于时不等式接近取等的证明就留给读者了）

为了将定理5.38与我们前面在两个数字列表中找匹配的问题联系起来，我们可以将数字列表视为包含个编号蓝色球的盒子。在选取个不同编号的球记为第一个列表后，我们用红色油漆重新绘制这个球，并将它们放回盒子。第二个列表是一次从盒子中抽出个球，记下它们的编号和颜色，然后放回。那么这里至少选取到一个红球的概率与两个列表中有匹配数字的概率则是相同的。

例 5.39

洗一副牌，随机选择八张牌面朝上。然后 Bob 拿起第二副牌，有放回地随机选择八张牌。两次选牌选中相同的牌的概率是多少？

我们将第一副牌中的八张牌视为对第二副牌中相同的牌的“标记”。所以我们的“盒子”是第二副牌，“红球”是第二副牌中的八张标记牌，而“蓝球”则是第二副牌中的其他44张牌。定理 5.38（a）告诉我们

定理 5.38 (b) 中的近似给出了的下限。相反，假设 Bob 从第一副牌中发十张牌，而从第二副牌中只选五张牌。那么则有

例 5.40

一个盒子包含100亿个标记对象。Bob 从盒中随机选择 100,000 个不同的对象，列出他选择的对象，并将它们放回到盒中。如果他接下来随机选择另外 100,000 万个对象，并制作第二个列表。那么这两个列表包含匹配项的概率是多少？使用定理5.38（a）中的公式（5.28），我们有

定理 5.38(b) 中的近似给出了 0.632121，可见近似值是相当准确。有趣的是，如果 Bob 将列表中的对象数量增加一倍，达到 200000，那么他获得匹配的概率将大幅增加到。如果他将每个列表中的元素数增加三倍，达到300000，那么匹配的概率为。这种快速增加反映了这样一个事实，即一旦大于，(5.29) 中的指数函数就会非常迅速地减小。

例 5.41

设一个集合中包含个对象。Bob 随机选择其中的个，标记他的选择，然后放回。然后从中再次有放回的选择个对象。他应该选择多大的才能让自己有的机会使得两次能够选取到同样的对象；如果他想获得的机会呢？

对于第一个问题，Bob 使用公式 (5.29) 来设置下限

于是我们解出

略小于即可。

第二个问题也是同样的，只不过式子变为

解得

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

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