密码学 | 5.4.2 碰撞定理

admin 2023年1月13日22:00:54CTF专场评论6 views1855字阅读6分11秒阅读模式

碰撞算法在密码学中的应用通常基于以下场景。假设 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  的碰撞方法,该方法以少量额外计算为代价来减小存储开销,实际上基本上不需要存储。

原文始发于微信公众号(山石网科安全技术研究院):密码学 | 5.4.2 碰撞定理

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年1月13日22:00:54
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  密码学 | 5.4.2 碰撞定理 http://cn-sec.com/archives/1515234.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: