好久没见小明了，今天我们继续来聊小明的故事。小明最近十分勤奋好学，看了很多数学书籍，数学成绩上升很快，于是被老师提拔为新任班长。刚好，小红最近快过生日了，于是小红就来问小明自己班上，或者隔壁班有没有和她生日相同的同学。小明知道自己班上有41个同学，而隔壁班上的人稍微少一点只有23个，但是小明手上现在没有花名册。于是他对小红说，我们班上一定有两个生日相同的人，隔壁班上有一半的可能有两个生日相同的人，但是我不太确定是不是你。

小红十分疑惑，问他：你怎么这么确定我们班上有生日相同的人，隔壁班上有一半可能有生日相同的人？

小明故作神秘的笑而不语，然后问小红： “你觉一个有23个同学的班上，有生日相同的同学的概率是多少？”

“23/365吧，这个概率应该很小吧”，小红说。

“但是，你的答案正确的概率更小。”，小明说。

Why？  OK，right now！我们来回答这个问题吧，首先需要提出一个概念：生日悖论。什么是生日悖论？其实就是上文中小明向小红提的那个问题；在一个23个人的人群中，有两人生日相同的概率是多少？我们直觉的答案是23/365，但是实际上，答案应该是0.5。同样，在一个41人的人群中，有两人生日相同的概率是0.9而不是40/365。这就是所谓的生日悖论！

是不是感觉到很奇怪？

但是，why？  要回答这一个问题，我们只需要做一个简单的计算：依次考虑每个人的生日，

第一个人：365/365；

第二个人；364/365；

第三个人：363/365；

……

第n个人：（365-n+1）/365

那么，在一个n人的群体中，有至少两人生日相同的概率为1-（365/365 * 364/365 * 363/365……（365-n+1）-365）

从上面的等式我们可以得知：

当n=23时，概率为0.5；

当n=41时，概率为0.9。

所以，小明才有把握说隔壁班上一定有生日相同的人 而自己班上有百分之五十的可能性有生日相同的人。

知道了什么是生日悖论，我们来接着讨论生日攻击，也就是本文的重点内容。

什么是生日攻击？

生日攻击是指在网络安全中利用生日现象，找到冲突的密码学哈希函数值，伪造报文，攻击报文身份验证算法的模式。（以上解释来源于Wiki）

举例说明生日攻击的形式（同样来源于Wiki）。

艾丽斯要通过某种签名方案对文档的散列值签名来签署一个电子文档，假设散列函数产生一个50比特的输出，她担心佛瑞德(Fred)哄骗她签署另外一个合同，也许是关于佛罗里达的沼泽地。由于欺骗性的合同和正确的文档有相同散列值的概率是1 / 250，这大概是1 / 1015，因此艾丽斯感觉是安全的。佛瑞德可以尝试许多欺骗性的合同，但是他找到有相同散列值的合同的可能性非常小，但是佛瑞德研究了生日问题并且照着下面的方法去做，他找到了能够对文档进行细微改变的30个位置：在一行的末尾增加一个空格，略微改变一个词的拼写，等等。在每一个位置他有两个选择，要么做一个细微的改变要么保留原状，因此他能够产生230个本质上与原始文档相同的文档，同样他得到230个欺骗性的合同并且存储它们的散列值。考虑最初的生日问题，其中r = 230并且n = 250，我们有).其中λ = 210 = 1024。因此一个好文档的版本和一个欺骗性的合同有相同散列值的概率是。佛瑞德找到这一对匹配的文档，并且让艾丽斯签署其中好的文档版本，他计划将她的签名附加在欺骗性的合同之上，由于它们有相同的散列值，因此签名对于欺骗性的合同将会有效，所以佛瑞德会声称艾丽斯同意购买沼泽地。然而艾丽斯是一个英语教师，她坚持从一个句子中删除一个逗号，这样就和佛瑞德要求她签名的文档有着完全不同的散列值，佛瑞德又被挫败了，这时他面临的问题是找到一个欺骗性的合同和新的正确文档具有相同的散列值，这根本是不可能的。

佛瑞德的行为被称为生日攻击，由于生日攻击有效地将比特数对分，在实际应用中只要你认为有必要，就可以对输出使用两次散列函数。对于签名方案的生日攻击，艾丽斯所做的是一种可取的方法，在签名电子文档时要做一个小的改动。

看过上文之后相信大家都对生日攻击有极大的兴趣 下面详细解释生日攻击的原理。

设h：X->Y是一个Hash函数，X和Y都是有限的，并且|X|>=2|Y|，记|X|=m，|Y|=n。显然至少有n个碰撞，问题是如何去找到这些碰撞。因为我们关心的是碰撞概率的下界，所以可以假定对所有y∈Y，有|h-1(y)|≈m/n。这个假定是合理的，这是因为如果原像集h-1(y)( y∈Y)不是近似相等的，那么找到一个碰撞的概率将增大。

因为原像集h-1(y)( y∈Y)的个数都近似相等，并且xI(1<=i<=k)是随机选择的，所以可将yI=h(xi)，1<=i<=k视作Y中的随机元素（yi(1<=i<=k)未必不同）。但计算k个随机元素y1,y2, .....yk∈Y是不同的概率是一件容易的事情。依次考虑y1,y2, .....yk。y1可任意地选择；y2 ≠y1的概率为1-1/n；y3 ≠y1 ,y2的概率为1-2/n；.....；yk ≠y1,y2, .....,yk-1的概率为1-(k-1)/n。

因此，没有碰撞的概率是（1-1/n）(1-2/n）.....(1-(k-1)/n）。如果x是一个比较小的实数，那么1-x≈e-x，这个估计可由下式推出：e-x=1-x+x2/2!-x3/3!+ .....。现在估计没有碰撞的概率（1-1/n）(1-2/n）.....(1-(k-1)/n）约为1-e-k(k-1)/2n。我们设ε是至少有一个碰撞的概率，则ε≈1-e-k(k-1)/2n，从而有k2-k≈nln(1/(1-ε)2)。去掉-k这一项，我们有k2≈nln(1/(1-ε)2)，即k≈sqrt(2nln(1/(1-ε)2))。

如果我们取ε=0.5，那么k≈1.17 sqrt(n)。这表明，仅sqrt(n)个X的随机的元素就能以50%的概率产生一个碰撞。注意ε的不同选择将导致一个不同的常数因子，但k与sqrt(n)仍成正比例。

来源于生日攻击，有另外两种密码攻击方法将其改进后而应用广泛：中间偶遇攻击和修正分组攻击。

中间相遇攻击是生日攻击的一种变形，它不比较Hash值，而是比较链中的中间变量。这种攻击主要适用于攻击具有分组链结构的Hash方案。中间相遇攻击的基本原理为：将消息分成两部分，对伪造消息的第一部分从初试值开始逐步向中间阶段产生r1个变量；对伪造消息的第二部分从Hash结果开始逐步退回中间阶段产生r2个变量。在中间阶段有一个匹配的概率与生日攻击成功的概率一样。

在修正分组攻击中，为了修正Hash结果并获得期望的值，伪造消息和一个分组级联。这种攻击通常应用于最后一个组，因此也称为修正最后分组攻击。差分分析是攻击分组密码的一种方法。这种攻击也可用来攻击某些Hash算法。