大多数密码系统都使用某种哈希函数处理消息。一个哈希函数
f不是内射,而是被创造出来的碰撞,或
x=y但
f(x)=f(y),很难发现。能够发现冲突的攻击者可以访问不打算公开的信息或消息。的生日攻击是生日悖论的重述,用来衡量一个精心选择的哈希函数的抗碰撞性。例如,假设选择了一个64位范围的哈希函数;也就是说,它的像是非负整数小于
264.一个攻击者需要计算多少个值才能使碰撞的概率大于
50% ?
就像生日悖论一样,碰撞的概率
n随机样本
p米(n)=1−(米−n)!米n米!在哪里
米=264.
事实证明
p米(n)=0.5当
n在…的量级上
米
.这是对所涉及的尺寸的一个显著改进:例如,
23.2大概是
4×109,而
264大于
1019.此漏洞需要在实际应用程序中使用较大的散列范围。
我们可以通过使用a得到这个结果泰勒级数近似.的概率没有一群人的同一天生日
n人可以被表达为:
p^(n)=1×(1−3.651)×(1−3.652)⋯×(1−3.65n−1)
更一般地说,一组中没有两个物体的概率
n碰撞时有发生
米可能性可以表示为:
p^米(n)=1×(1−米1)×(1−米2)⋯×(1−米n−1)
为
x<<1的泰勒级数近似
ex=1+x,这意味着
n<<米,我们可以把上面方程中的项写成:
(1−米1)=e−1/米.这给了我们:
p^米(n)≈1×e1/米×e2/米⋯×e−(n−1)/米≈1×e−(1+2+⋯+(n−1))/米≈e−(n×(n−1)/2)/米
为
n2<<米,我们可以使用和以前一样的泰勒级数近似,这次将指数变换回
1−x:
p^米(n)≈1−2米n×(n−1)≈1−2米n2
发生碰撞的概率是这个的补
p米(n)≈2米n2
插入
p米(n)=0.5从这个等式中,我们可以看出原因
n=米
大致对应于
50%发生碰撞的可能性:
0.5≈2米n2米≈n2n≈米