密码学中的生日攻击详细介绍

先决条件-生日悖论
生日攻击
生日攻击是一种密码攻击，属于蛮力攻击的一类。它利用了概率论中生日问题背后的数学原理。这种攻击的成功很大程度上取决于在随机攻击尝试和固定排列程度之间发现碰撞的较高可能性，如生日悖论问题所描述的那样。
生日悖论问题–
让我们考虑一个有30名学生和一名老师的教室的例子。老师希望找到几对同一天生日的学生。于是老师要求每个人的生日来找这样的一对。直觉上，这个值可能看起来很小。例如，如果老师确定了一个特定的日期，比如10月10日，那么至少有一个学生在那一天出生的概率是1 -(364/365)^30，大约是7.9%。然而，根据下面的公式，至少有一个学生和其他学生的生日相同的概率是70%左右:
使用以下公式：

1 - 365!/((365 - n!) * (365n))(substituting n = 70 here)

上述术语的推导：
假设–
1.假定为非leap年(因此365天)。
2.假设一个人在一年中的任何一天都有相同的机会出生。
让我们考虑n = 2。
P(两个人有相同的生日)= 1 – P(两个人有不同的生日)
= 1 –(365 * 365)*(364 * 365)
= 1 – 1 *(364/365)
= 1 – 364/365
= 1/365。
因此, 对于n个人来说, 他们所有人生日不同的概率为：
P(N个生日不同的人)=(365/365)*(365-1/365)*(365-2/365)* ....(365-n + 1)/ 365。
= 365！/((365-n)！* 365^n)
哈希函数–
哈希函数H是一个转换，它接受大小可变的输入m，并返回一个固定大小的字符串作为哈希值(H = H(m))。密码学中选择的哈希函数必须满足以下要求:

输入是可变长度的
输出具有固定长度,
对于任何给定的x, H(x)相对容易计算,
H(x)是单向的
H(x)无碰撞。

如果难以反转, 则哈希函数H被认为是单向函数, 其中"难于反转"意味着给定哈希值h, 在计算上找不到某些输入x使得H(x)= h.
如果在给定消息x的情况下, 找到不等于x的消息y在计算上不可行, 则使得H(x)= H(y)那么H被称为弱碰撞散列函数。
一个无强烈冲突的哈希函数H是一种在计算上不可行的方法, 无法找到任何两个消息x和yH(x)= H(y).
让H：M => {0, 1}?是一个哈希函数(| M | > > 2^n)
以下是及时发现碰撞的通用算法O(2n/2)哈希。
算法：

选择2^(n/2)中的随机讯息：m1, m2, …。, m(n/2)
对于i = 1, 2, …, 2^(n/2)计算ti=H(mi)=> {0, 1}^n
寻找碰撞(ti = tj)。如果找不到, 请返回步骤1

我们考虑以下实验。从一组H值中, 我们随机地均匀选择n个值, 从而允许重复。让p(n; H)是在此实验中至少一个值被多次选择的概率。该概率可以近似为：

p(n; H) = 1 - ( (365-1)/365) * (365-2)/365) * ...(365-n+1/365)) p(n; H) = e-n(n-1)/(2H) = e-n2/(2H)

【密码学中的生日攻击详细介绍】数字签名敏感性
数字签名很容易受到生日攻击。消息m的签名通常首先计算H(m)，其中H是加密哈希函数，然后使用某个密钥对H(m)签名。假设爱丽丝想骗鲍勃签一份欺诈性合同。爱丽丝准备了一份公平的合同和一份欺诈的合同。然后她发现了一些可以在不改变意思的情况下改变m的位置，比如插入逗号、空行、句子后的一个空格和两个空格、替换同义词等。通过结合这些变化，她可以在m上创造大量的变化，这些都是公平的合同。
同样, 爱丽丝也可以在m’使它更接近米, 那是H(m)= H(m’)。因此, 爱丽丝现在可以展示公平的版本米给鲍勃签名。鲍勃(Bob)签名后, 爱丽丝(Alice)签名并附上欺诈性合同。此签名证明鲍勃已经签署了欺诈性合同。
为了避免此类攻击, 散列函数的输出应为非常长的位序列, 以使生日攻击现在在计算上变得不可行。