简介

生日攻打其实是一个概率论的问题，也就是说一个看起来很难产生的事件，事实上它产生的概率却很大。这种主观上和事实上的概率差距，让随机攻打胜利的几率变的更高，这样的攻打就叫做生日攻打。

生日问题的由来

生日问题也叫做生日悖论，它是这样这样形容的。

如果随机抉择 n 集体，那么这个 n 集体中有两个人的生日雷同的概率是多少。如果要想概率是 100%，那么只须要抉择 367 集体就够了。因为只有 366 个生日日期（包含 2 月 29 日）。

如果想要概率达到 99.9%，那么只须要 70 集体就够了。50% 的概率只须要 23 集体。

对于当初的幼儿园小朋友来说，一个班上差不多有 30 人，那么将会有大于 50% 的几率，班上有两个人的生日是一样的。

听起来是不是很神奇？跟咱们第一映像中的基数是不是要少很多。

咱们看一张概率图：

在理论利用中，能够利用生日问题中的概率模型，从而缩小碰撞攻打的复杂度，或者来评估一个 hash 函数中可能呈现碰撞攻打的几率。

怎么计算呢？

如果 P(A) 是生日雷同的概率，那么 P(A) = 1 – P(A<super>’</super>)，其中 P(A<super>’</super>) 是生日不同的概率。

一个人生日不同的概率是 365/365, 两个人生日不同的概率就是 365/365 * 364/365 , 顺次类推。

咱们能够失去 23 集体生日不同的概率大略就是 0.492703。

也就是说 23 集体中有两个人生日雷同的概率能够大于 50%。

再看一张表来个更加直观的形容：

生日问题的衍生

生日问题的取值范畴是在一年的 365 天之内，也就是说生日只可能有 365 种可能性。

咱们将这个问题扩大一下到个别的状况，假如有一个函数 f，它的输入范畴是 H，那么咱们的攻打就是找到两个不同的 x，y，让 f(x)=f(y)。

这时候，咱们能够称 x 和 y 产生了碰撞。

依据概率论的公式，咱们想要达到 50% 的几率，那么须要尝试的次数是:

如果以 bits 位来示意可能计算出的后果的话，咱们能够参考上面的概率表：

生日攻打的利用

生日攻打个别利用在数字签名中。一般来说为了对机密消息进行签名，因为加密的限度，如果音讯很大的状况下，不可能对所有的音讯进行签名，通常会对音讯计算 hash 值，而后对这个 hash 值进行签名。

比方有人想做一个欺诈性的合同，那么会在原合同的根底上进行批改，一直的进行尝试，从而找到一个批改后的合同，让合同和之前合同的 hash 是一样的，从而导致两者的签名也是一样的。

怎么抵挡这种攻打呢？依据咱们生日攻打的公式，当然是将签名计划应用的哈希函数的输入长度抉择得足够大，以使生日攻打在计算上变得不可行。

本文已收录于 http://www.flydean.com/birthday-attack/

最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！

欢送关注我的公众号:「程序那些事」, 懂技术，更懂你！