首页 >> 数学 >> 文章

生日悖论与生日攻击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. 选择性的条件理解把背景改动了，变成习惯经验主导——“我平时最常遇到生日不同的人，所以找相同更困难。”
    这样就把自己的生日当成相同的唯一判断标准，忘记了自己只占有366个可用标准的其中之一。
    而且在其他日期发生重叠的可能被排除了。
    于是乎，用自己做检测器，在人海中过筛，随机遇到生日相同的人，总概率必然接近1/365.25。

    以上是理论概率，不是可知情况的暴露信息。
    因为平时不是碰面都询问生日的，绝大部分相同事件被遗漏了，被错误以为属于不相同的事件之一。
    假设一个人只在自己过生日的当时、被询问生日的当时、闲聊生日问题的当时，等等，才进行生日是否相同的信息采集，这些有效采样时间每年只有估计大概约莫可能似乎接近1天上下左右不离谱，就把遇到的人生日正好相同的真实事件遗漏了绝大部分，只得到~1/300，
    于是乎此人每年得知遇到生日相同的人的事件，占遇到别人的事件的~1/10000，属于小概率水平。
    所以，一般会形成取伪+弃真因素联合作用的经验式理解，即很难遇到生日相同的人，当交流确认发现和别人生日相同时，经常觉得很稀奇，就是因为在用实际经历的规律来判断，认为是用可知的事实证明少有的偶然现象。
    而实际上，任意选择的一个人，平均算，他/她的活动几乎都是在一个很小的交流范围内，遇到的人只占全世界人口的极少数，很难作到询问确认所有人的生日，检测工作就是没有遍历，遗漏很多样本，会被误解成世界上的人就是自己真正遇到的那些家伙，他们的可知情况就是绝少和自己的生日相同，把误解的经验强化了；又偏偏通过间接的信息知道和相信世界上有非常多的人，再把不可知的生日特征默认是生日不同，忽略了实际检测没有包括所有人，会理解成生日相同的机会更少，概率的故意压低程度不好量化计算，但是估计也不小。

    多种因素联合作用，一个人的经验式理解自然是生日相同的事件非常罕见。
    ---------
    换个理解角度更容易发现亲历经验的错误
    ---------

    设想有366个座位，让所有的人按实际的距离远近、交通难度、旅行花费时间来抢坐，每个座位对应一个生日，想象一下跑来多少个人就会发生生日重叠，出现不止一个人争一个座位。
    再想象不断有人跑来的叠罗汉过程，看看每个座位上逐渐叠上1000多万人的情景。
    用讨厌生日相同的心理来算，就会注意到搭人梯的可能性实际有多大——如果很难发生，只有366个座位是远远不够分的，上千万次的重叠事件在每个座位上都会频频出现，而随机跑来的人很难保证是预先避免重叠的，来人的总数还没达到366个，开始发生重叠的情况就非常非常可能出现了，先各坐一个位置占满了才出现重叠是极小概率的事件。
    所以更快就几乎肯定要遇到重叠是真实的规律，只是信息来源不足的每个人难以得知而已。

    • 我没有公式，啦啦啦。。。。
      但是字多，啦啦啦。。。。。
      没有人画画，啦啦啦。。。。

    • 硬出一个经验公式

      相信有现场生日相同的概率 = 知道的相同事件次数/（有记忆以来遇到别人的人次+听说别人相遇事件的人次）

      =很少很少/多得不得了

    • 其实用那个多项式的根的集合图的方法，画个实际情况发生机会的正态分布图，可能更容易理解。

      366个座位，先跑来的百来人当中，都不同和都相同的情况都极端特殊，可能性都非常小，最可能的是很多座位只有一人占，又有少数座位已经重叠了，还有一些座位还空着。

      会场、电影院、酒席、教室、火车、市场摊位、体育馆的座位填充过程就比较随机，把相邻几个、十几个、百几个座位看成一块，整体分成366块，观察实际的重叠过程就是变形的生日问题了。
      公交车、地铁、食堂窗口、厕所的情况不算，那是通票乱抢的。

    • 有点恼，本来有一个生猛的验证材料可以用，但是显示内容不完整，失去利用价值了。

      到现在为止，松鼠会博客上、论坛上发的帖子，剔除可能在无意中干扰的沙发党、广告机器人的痕迹，剩下的帖子基本上都没注意选择发布时间。

      这很有意思，把每个小时的3600秒分成360个部分，每部分长10秒，假设是一个生日标记，那么这些帖子的“生日”非常类似人的生日。

      从提醒这个情况截止，过去已经发布的帖子几乎都是在“生日”上随机出现的（以后就难说了，估计总有一些故意捣蛋的同学）。
      从这篇博文的楼顶开始，去掉很可能故意抢时间的沙发类，以及发作时间的规律可能不随机的机器类，连续向过去选定50贴，不管是博文还是回复，可以组成较好的实验样本，检查其中“生日”重叠的情况，就可以发现可能性是否大了。

      但是，发布时间只显示到分钟，秒级精度的特征被隐掉了（后台记录应该有吧？），无法细分，可惜可惜。如果方便，希望后台给个按时间顺序的“生日”记录来，就能现玩了。
      -------------
      街头生日调查也可以进行。

      设计一张表格，366个位置，带很多张表格去询问调查。

      街上的行人还没有被规定按照生日限行，也基本不被生日因素干扰平常的活动，同时很少暴露生日信息。
      那么，在街上随机选择行人，或者凭空猜测故意选择行人，或者遇到不愿接受调查的行人，都不能避免按照随机规律收集样本。

      所以拿着表格选择行人询问，把生日记到对应位置，再去询问下一个。
      不断询问正好遇到的不同行人，记录生日，直到开始出现重叠，这张表格就算完工了。

      启用下一张表格，同样的调查记录，有重复就终止。

      回家就可以整理数据，看看平均每张能记录多少人的生日、有没有366个位置都填满了才重复的。

  3. 其实楼主开头的一段文字对读者有误导

    ——偶尔会遇到与自己同一天过生日的人，但在生活中，这种缘分似乎并不常有。我们猜猜看，在50个人当中，出现“这种缘分”的概率有多大……

    这里的“这种缘分”是指和自己同一天过生日？还是有任意两个人同一天过生日呢？从语文角度严格地讲应该是前者。但论述过程发现“这种缘分”的概念被偷换成了后者，因而出现这么大的落差也就不奇怪了。

    可见—— 人无完人，数学高手语文不一定很强啊。

    开个玩笑，别介意。

  4. 你写的内容这里全部都有：http://en.wikipedia.org/wiki/Birthday_Paradox
    你想把别人的东西直接拿过来吗。

  5. 是否意味着买彩票时，机选（相当于第一条曲线）要比固定买一组号（第二条曲线）中奖的几率要大吗？

    • 差点儿想去买彩票...有二个人买了一样的号码(第一条曲线),有一个人买了头奖号码(第二条曲线)

    • 对，我也觉得应该考虑年份，若只是同月同日生的话就没什么意思了 ，比如我和一位老爷爷或大叔说话就基本不会因为是同月同日生的而越过代沟成为忘年……

  8. 一个浅显易懂的生日攻击的介绍，苏椰写科技短文有一定实力。

  9. 2009-12-13于9:46
    你写的内容这里全部都有：http://en.wikipedia.org/wiki/Birthday_Paradox

    发个申明嘛，即使是翻译，也是很有味道，是非常值得尊重的事业和工作。
    有点不厚道了。

  10. 我貌似就是那个到公式就停止的人...不过记住结论了..

  12. 高中都学过?小学奥数？
    上面的评论看到后来让我真想撞墙~

  13. 文中所说的“攻击”的含义到底是什么？

    就一般人的理解，对一个64位的密码（二进制位，也就是由64个0和1组成的序列），需要破解掉这个密码，就要找到一个和它每一位都相同的64位序列，只有这样才算“攻击”成功。

    而这篇文章里所说的“攻击”，我觉得是这个意思：
    管他真正的密码是什么，只要我自己的这一大堆密码里有相同的，我就认为攻击成功了。例如我自己生成了10^10个64位密码，其中这里面存在两个相同密码的概率超过99.9%，那么我就认为有99.9%以上的概率“攻击成功”。这个99.9%，并不是与真正的密码相同的概率。

    如果不知道敌人是谁，就根本谈不上战争。同样，如果连攻击的对象都没搞清楚，后面的计算又有什么意义呢？

    以上是我的一点疑惑，还请众高人指点。

    • 是的，你可以这样理解，这个“攻击”不是指破解一个密码，而是攻击一个单向散列函数（比如说MD5）。
      对于函数来说，只要找到任意一对相同的输出（在不同输入的情况下），就算攻击成功。

      • 原来如此。那麻烦再问一个问题：
        “对于函数来说，只要找到任意一对相同的输出（在不同输入的情况下），就算攻击成功。”
        我举一个例子：
        比如有一个函数的功能是“把两个数相加”。那么用不同的两组输入：
        1+1
        2+0
        显然，针对两组不同的输入，输出都是等于2，（问题1）这就是你所讲的对函数的成功攻击吗？

        对于散列函数来讲，不同输入得到同一个输出叫做“哈希碰撞”，但没听说过有叫“哈希攻击”，或任何带有“攻击”含义的术语。
        我想文章中所说的“攻击”一定是出自某个应用场景。我想知道，（问题2）这种对函数的攻击一般都使用在什么场合？谢谢。

        • 从某种意义上来说，你举的加法函数的例子，的确也是一种碰撞。

          单向散列函数一般用于对信息进行验证，比如MD5就是很常用的一种。比如我给你一个文件，同时给你这个文件的MD5值。你收到文件后，再重新计算一次MD5，如果散列值相同，就说明这个文件在中途没有被纂改

          因此，我们要保证这个函数有两个性质：

          第一，它是不可逆的，否则的话，通过散列值直接能解出原文，那么验证就没有意义了。
          加法满足这个性质，我们知道1+2=3，但不把3分解成确定的几加几

          第二，要保证不同原文的散列值也不同，否则的话，纂改的假文件也能得到相同的散列。
          加法就不具有这个性质了，它的碰撞极多。MD5函数相对来说就好很多。
          检测一个散列函数是否具有良好的这种性质，也就是去找它的碰撞，这个过程习惯上就称作“攻击”。
          山东大学的王小云教授就因为曾经找到了MD5的一个碰撞，在国内计算机业一夜成名。

          • 原来“攻击”是这个意思啊，明白了。
            理解这个攻击的含义还是蛮曲折的，如果在原文中解释一下就更好了:) Thanks

          • 其实这篇文章是分成两半的，前面那半是科普，后面密码学的内容就算是扩展资料了，是给有密码学基础的人看。
            不过你说的也很对，把这块加上去更好~

  14. 参考文献对理解相关公式意义大有帮助，尤其是参考文献2。
    这份严谨应该赞一下，嗯，也许我喜欢有参考文献。

  15. 说的很好。我刚好正读社会心理学一书。上面就有很多关于人的心理认知与行为的错误判断。能够对自己不假思索的判断说等等这就是我读后的所获。谢谢作者呵呵

    • 能够对自己不假思索的判断说等等这就是我读后的所获。

      到公式停步的人，真的可以发觉世界的美好啊——美好在公式外~

  16. 下次人家跟我说，我和你同一天生日。然后我特倒胃口的来一句，这一点都不惊奇，平均25个人中就能遇见一个。

      • 是不是应该这样说：25个人中基本能有同一天生日的一对人。

  18. 数学没学好，第一个公式就没看懂，不过还是想让作者写更细一些，弄些演算过程或者公式说明啥的。

  19. 真的好有趣。数学很美好。
    “对计算感到头疼的读者，可以选择在此停下脚步。别担心，世界依然美好。”看到这句话我就真的停住了。世界真的还很美好……

    • 我是好奇了看了下后面，然后发现世界还是很美好，自认数学白痴的人飘过

  20. 老实说，我觉得同月同日生日的还算比较普遍了。

    我认识四对人是同年同月同日生日（同年同月同日哦，还不仅仅是同月同日）。我自己和我的儿子也在其中。结果，我对结果并不意外。

  21. 我觉得楼主写的很好啊。看不懂公式的可以选择不看吗，楼主已经说了，世界依然美好。

  22. 应该强调一下，碰撞与攻击是两个相近但不同的概念。
    攻击是针对特定Hash值的密文，生造出具有相同Hash值的一段文字。前几年轰动密码界的山东大学的女教授就达到了这个程度。
    碰撞是两段随机抽取的文字，Hash值相同，这对于一个数字签名系统当然很糟糕。比如eMule等，会发现两个文件内容不同，但Hash值相同，究竟采取哪个文件呢？

  23. 很久以前就听闻过这个生日问题了，没想到这里面还有这么大的文章。
    对文中提到的不均匀情况下相同生日概率更高的结论，不知道怎样证明？楼主可以介绍一下吗？如果可以给点资料就更好了，嘻嘻！

  24. 去自己的QQ空间的个人中心看一下，你到底加了多少个QQ好友，但是里面基本都会有二个人以上的好友生日是同一天，而且出现的概率很高！

  25. Lewind的解释言简意赅，苏椰的不够科普。

  26. 12.12是我的生日，看到有关生日的话题，觉得很开心，然。。。看了文章，我就杯具了。。。

  27. 我觉得这种悖论只是由于把命题理解为50个人中有人与你同一天生日的概率。只是语文的问题而多过于数学的问题:)

    • 也不完全是，早在几年前我就问过别人，详细特别说明过，是任意2个人。。。但别人给出答案还是差十万八千里。。。。。

  29. 作者好，我是2月29号，不好意思，我可能会对你的计算带来一些小小的麻烦，因为我这个成员比较特殊，不是每年都归队。但是请不要忽视我，因为那样会对人们的生活带来更大的麻烦。给你一个将功补过的机会，我想知道我平均要见多少人才能遇见一次我的同党呢？

  30. 据说世界上有三分之一的人是左撇子，但是周围左撇子的人很少，也可以用本文的结论来解释~~~