首页 >> 数学 >> 文章

生日悖论与生日攻击Comments>>

发表于 2009-12-12 10:39 | Tags 标签：

每个人都有生日，偶尔会遇到与自己同一天过生日的人，但在生活中，这种缘分似乎并不常有。我们猜猜看，在50个人当中，出现这种缘分的概率有多大，是10%，20%，还是50%？

有人告诉我，在文章开头插入公式十分倒胃，所以我就不写计算过程，直接给出结果（除了传统的排列组合方法外，Paul Halmos[1]还给出了一个巧妙的解法）。在50个人中有相同生日的概率，高达97%，这个数字，恐怕高出了绝大多数人的意料。

我们没有算错，是我们的直觉错了，科学与生活，又开了个玩笑。正因为计算结果与日常经验产生了如此明显的矛盾，该问题被称为“生日悖论(Birthday Paradox)”[2]。它体现的，是理性计算与感性认识的矛盾，并不引起逻辑矛盾，所以倒也算不上严格意义上的悖论。它的原始表述是：在23个人当中出现相同生日的概率大于50%[2]。为了让矛盾更突出，我把人数换成了50，如果事先不知道答案，猜测的结果一般远远小于97%。也许有人质疑，我们在计算时，假定人们的生日均匀而随机地分布，但生活中却未必如此——别担心，不平均分布的情形也已解决[3]，而且更进一步的证明是，不平均分布时，概率只会更高[4]。此外，Knuth在TAOCPv3中还计算了，平均在多少人中才能找到一对相同生日，答案是25人[5]，这看起来实在不可思议。

对于为何出现这种矛盾，我没有看到专门的研究。我的想法是，首先，当只有1个人时，概率为0%，当人数大于365时，根据鸽巢原理，概率是 100%。于是，在1到365这个区间内，我们直觉地认为，对应的概率是线性地从0％增长到100%，哪怕不线性，也不会陡峭得太离谱，所以对于57人来 说，该概率应该在57/365，即七分之一左右。但事实上，这条曲线的增长劲头却是十分可怕：[6]

2139__400x_575px-birthday_paradoxsvg

绿色的曲线，就是在不同的人数时，对应的存在相同生日的概率，它就像坐了直升机一样迅猛窜升，在50人时就已相当接近100%，与我们幻想的线性曲 线有天壤之别。那么问题就是：为啥我们会误以为它是线性的？别急，我们把问题稍作改动，就能得到启发。新的问题是，在一群人当中，有人与你同一天生日，这个概率有多大？同样地，我们把概率曲线描出来（即上图蓝色线），可以看到，它是十分平缓的。我认为，就是因为当我们看到“有人生日相同”时，下意识地用“与我生日相同”去推测，以致于把火箭发射当成了平稳增长，造成了生日悖论。

所以生日悖论的本质就是，随着元素增多，出现重复元素的概率会以惊人速度增长，而我们低估了它的速度。（对计算感到头疼的读者，可以选择在此停下脚步。别担心，世界依然美好。）这个问题不容忽视，因为它意味着，在密码学中，我们低估了散列值出现碰撞的概率。这一结论应用于对散列函数的攻击中，称为“生日攻击(Birthday Attack)”[2]。

我们先把这个问题与生日脱钩，写成一般形式。从离散均匀分布的区间[1,d]中取出n个整数，至少两个数字相同的概率[2]

P(d,n) = \left\{\begin{matrix} 1-\prod_{i=1}^{n-1}(1-\frac{i}{d}), & n\le d \\ & \\<br /> 1, & n > d \end{matrix} \right. ” /><img src=

下面考虑一个64位散列函数，它有2^{64}种可能的散列值，要想100%地找到一组碰撞，就需要2^{64}+1\approx 10^{19}次攻击。但是基于生日攻击的原理，我们只需要 2^{32}\approx 10^9次攻击，就有约50%的概率能够攻击成功。下面给出一种证明（符号沿用上面公式的）：

\begin{matrix} P & = & 1-\prod_{i=1}^{n-1}(1-\frac{i}{d}) & < & 1- \prod_{i=1}^{n-1}e^{-\frac{i}{d}}\\<br /> \\<br /> \ & = & 1- e^{-\sum_{i=1}^{n-1}\frac{i}{d}} & = & 1- e^{-\frac{n(n-1)}{2d}}\\<br /> \end{matrix}<br />

两端整理得：

\begin{matrix} n^2 & > & n(n-1) & > & -2dln(1-P)\\<br /> \\<br /> \ & \ & n & > & \sqrt{-2ln(1-P)} \sqrt{d} \\<br /> \end{matrix}<br /> ” /><img src=

当P=0.5时

n > 1.17\sqrt{d} \sim \sqrt{d} ” /><img src=

在\sqrt{d} = 2^{32}次攻击中，就有约50%的概率发生碰撞，收益降低一半，成本却开了根号，对于这些大数字来说，开根号是件不得了的事。为了提高碰撞率，我们以2^{32}个散列作为一组，用独立的10组分别进行攻击，则一共需要约10^{10}次攻击，出现碰撞的概率高于99.9%——这是一个非常理想的成功率，需要的攻击次数却仅是原来的1/1,000,000,000。

参考文献：
[1] Paul Halmos. Wikipedia. http://en.wikipedia.org/wiki/Paul_Halmos
[2] Birthday Problem. Wikipedia. http://en.wikipedia.org/wiki/Birthday_Paradox
[3] M. Klamkin and D. Newman Extensions of the Birthday Surprise, Journal of Combinatorial Theory 3, 279–282. 1967
[4] D. Bloom. A Birthday Problem, American Mathematical Monthly 80, 1141–1142. 1973
[5] D. E. Knuth; The Art of Computer Programming. Vol. 3, Addison-Wesley, 1973
[6] Toobaz. Image. http://zh.wikipedia.org/wiki/File:Birthday_paradox.svg

相关文章
如何预测伦敦奥运会中国金牌数？ Riemann 猜想漫谈 (十二) Riemann 猜想漫谈 (十一) Riemann 猜想漫谈 (十) Riemann 猜想漫谈 (九)
上一篇：
下一篇：

  1. “生日悖论”，翻译成“生日佯谬”更合适吧？

  3. 啊，我想到一个闪客活动来检验生日的相同概率。

    开一家商店，生日大优惠。

    活动方法：
    顾客拿自己的身份证件来，如果是某个生日的第一次出现，就可以免费进场掏宝366秒，掏到的商品全部免费。
    如果某个生日已经被人先占了，对不起，你没有免费资格，照价付钱。

    想象现场会是什么样的——

    大家都不知道自己的机会消失了没有，都想抢到免费资格，远远超过366人跑来，样本量足够大，而且互相没有按照生日特征事先商量谁来谁不来（其实都想排斥别人，但又管不了，只好各自行动，靠赶时间来抢，行为无序），跑来的人接近随机分布规律。

    最先到的一个人绝对有机会免费，不管生日是哪天，都有空位配套；
    第二个跑来的人如果又是同一天生日，就没有资格了，但是这种概率应该很小，还有365/366的机会免费；
    再后面跑来，被占的空位越少，免费概率下降（所以大家要跑快点，越晚越没有便宜占）

    真正的过程记录下来，就是生日重复的规律，看看谁第一个失去资格跺脚。

    这个游戏在几百上千人的学校里就可以玩，比如早上进校门的生日位次、进饭堂的生日位次，用点小甜头临时引诱一下，规律就出来了。

  7. 经oracle 与mysql 自身随机算法计算50人中有两人生日相同概率为96%~97%间（计算10000次）

    • select count(9) from (
      select a.day1,count(9) from (select ceil(rand()*365) as day1 from `table`/*某表，记录大于50，这是俺能想到的最快的取出五十条记录的办法了，寒一个*/ limit 0,50) a group by a.day1 having count(9) > 1) b
      mysql 的语句，循环10000次，有96%以上的可能结果大于0

  8. Pingback: 七彩盒 » 数学魔术系列之Kruskal的魔力

  9. Pingback: 科学松鼠会 » 数学魔术系列之Kruskal的魔力

  10. 所以现在干脆直接把几百位长度的密码写入U盘里面...恐怕连变形金刚都不能破解.

  11. 高中生算法：1-（50人2人同日的可能性/各不相同的可能性），即1-（（365！/315！）/365^50），即1-364/365x……x316/365，364/365约等0.997，316/365约等0.866，二数平均0.931，1-（0.931）^50，得97%左右。当然，很粗略。我文科生，如果2B了大家别太意外，真的。

  12. Pingback: 《概率知多少》（million 2 one）【国语中字】 | Gabriel'Blog