首页 >> 数学 >> 文章

Chinese (Simplified) flagItalian flagKorean flagEnglish flagGerman flagFrench flagSpanish flagJapanese flagArabic flagRussian flag

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

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

每个人都有生日，偶尔会遇到与自己同一天过生日的人，但在生活中，这种缘分似乎并不常有。我们猜猜看，在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

 

上一篇：
下一篇：

131 Responses to “生日悖论与生日攻击”

回到顶部
  1. Ent 说：
    2009-12-12于11:05

    沙发&挑错~“为了让矛盾更突出，我把人数换成了57”->50

    回复
    • Ent 说：
      2009-12-12于11:08

      PS 可不可以把图转存到群博服务器上啊……苏椰你的博客似乎属于国外ip……很多高校里不开代理看不到……

      回复
    • 杨 说：
      2010-01-05于11:48

      这个好象是高中，知识就能解决吧，作者给出的结果是好，不过我想有没有更简单写的过程了

      回复
  2. ARTHUR 说：
    2009-12-12于11:53

    两端整理得：
    N*N < N*(N-1) ???
    这是为什么？

    回复
  3. woodenman 说：
    2009-12-12于12:03

    我猜，我们觉得同生日的很少是因为我们总是将目光集中在自己身上，因为存在和自己同生日的概率正是（n-1）/365。如果有人将注意力集中在整个群体中的话，他的感觉肯定会不一样的

    回复
    • nemo 说：
      2009-12-12于20:53

      我觉得这种问题使用概率的思维方式本身就是一个问题。
      在一群人中，个人一般考虑“是否有人和我的生日相同”，而不会将“有没有人生日相同”作为第一考虑的问题。
      所以这本身就不是一个单纯的数学问题。

      回复
      • 眉毛 说：
        2009-12-14于12:11

        嗯…我也是看到一半了才发现问题原来是有2个相同的人 而不是找到于自己相同的人…

        回复
  4. 莽轩 说：
    2009-12-12于12:15

    好吧，我承认我看到97%的数字大吃了一惊，然后对于数学迷茫的我继续看了下那些公式发现还是老老实实按照作者的话“（对计算感到头疼的读者，可以选择在此停下脚步。别担心，世界依然美好。）”其实我好奇的是有没计算出多少个人里会出现两人生日会在≤15天的，不知道我们这层宿舍楼的内大约10多间寝室，一间寝室按6人算会不会有出现跟我同月同日的

    回复
  5. deepblue 说：
    2009-12-12于12:32

    呃~ “两端整理得:” 后面有点问题吧， n^2 0) ?

    回复
  6. BSG75 说：
    2009-12-12于12:56

    想到了福利彩票不只一次出现两个相同号码的中奖者，难道不是造假而是有科学根据？

    回复
    • yuye 说：
      2010-03-18于17:30

      其实这个概率也不是很大，因为首先要满足一个条件：这个号码中奖，然后才是与这个号码相同的人数。

      回复
  7. adu 说：
    2009-12-12于13:19

    用在攻击上倒是有些难。它不是在[1,n]中找两个相同的数，而是在[1,n]中找一个与X（1≤X≤n）相同的数，所以难度并不会减少。

    回复
    • 苏椰 说：
      2009-12-12于21:12

      这里的“攻击”是指对散列函数进行攻击，而不是破解某个特定的散列值
      只要能够找到该函数的一对碰撞，就认为攻击是成功的。

      回复
  8. 不是魔芋丝 说：
    2009-12-12于13:24

    看到公式就失去了继续往下看的冲动。。。主啊，赐予我数学及格的能力吧

    回复
  9. 不是魔芋丝 说：
    2009-12-12于14:28

    我真的不认为这是一个科普文章，倒是可以收入教材的论文。到处都是引文和公式，缺少科普应有的趣味和低门槛。当然，我仅针对这篇文章，这篇文章是我最近在松鼠会读到的最无趣的文章。。。。

    回复
    • wealk 说：
      2009-12-12于16:12

      这也没办法啊 这个问题写到后来 不是只能写成这样吗

      回复
    • 莽轩 说：
      2009-12-12于16:53

      前半部分挺好的，起码我知道57个人里面有一对是同月同日生的人几率有97%，还有个通俗易懂的人越多里面有一对同月同日生的人概率越高，但是特定到某个日期的就比较符合人们通俗的认知了

      回复
    • 苏椰 说：
      2009-12-12于18:53

      后面那段我都说了，不喜欢计算的读者可以跳过去么……
      这篇确实不是大众科普，不是写给所有人看的。

      回复
  10. 朝雲 说：
    2009-12-12于15:24

    雖然我一樣看不懂數式,但我覺得很有趣.

    我想試用文字解釋.是不是因為地球人口很多(超過70億),即使分佈在365天,同一天生日的平均數仍然很高(約一千九百萬人),人們思考時忽略此因素,只想到自己每次遇到同一天生日的人應該只有365分之一,想不到人愈多機會就會極速攀升.

    回复
  11. t 说：
    2009-12-12于15:26

    一看97%就不想看下去了，想想看如果遇到100个人问一问，会不会有97个同天生日。

    回复
    • 苏椰 说：
      2009-12-12于21:46

      既然把97%理解成了这个意思，那就别看了，是我害了你……

      回复
    • 有个人 说：
      2009-12-13于13:05

      原来是说我们猜“100人中一定有人生日同日”这个问题 回答“是”，答对几率为97%

      回复
      • 又有个人 说：
        2009-12-18于20:47

        怎么可以回答“是”呢？那样答错的概率是100%，要看清题目再回答滴

        回复
        • 有个人 说：
          2009-12-19于19:40

          错在哪啊，随机调100人，里面有人生日相同的几率不是97%吗
          如果不能说“100人中一定有人生日同日”这个问题 回答“是”，答对几率为97%
          那该咋说呢

          回复
    • 一双绣花鞋 说：
      2009-12-13于17:28

      哈哈，终于碰到一个数学比我还差的人了，提升了我不少信心啊。

      回复
  12. 铁蛋骑士 说：
    2009-12-12于15:35

    哈，我想起了我们概率课的一道题，
    原题就是，50个人中，有两人生日相同（仅月日）的概率为多大，
    当时算完我也是震惊了…

    回复
  13. maokk 说：
    2009-12-12于15:56

    让它有点实际意义，就是人数到了一定程度，人云亦云就多起来了？

    回复
  14. sheldon.li 说：
    2009-12-12于16:37

    汗，是不是latexrender做的？

    回复
  15. Mycroft 说：
    2009-12-12于17:08

    计算完全看不懂。。。。

    回复
  16. 白左 说：
    2009-12-12于17:47

    貌似人们普遍认为高中数学极其困难～

    回复
  17. 一叔 说：
    2009-12-12于18:35

    今天生日的人进来看看,有和我一天生日的吗?

    回复
  18. deoxys 说：
    2009-12-12于18:44

    貌似高数更困难

    回复
  19. xuby 说：
    2009-12-12于19:00

    我感觉出现悖论的原因是，每个人只会关心有没有人跟自己生日撞车，至于是不是有另外两个家伙生日撞车，潜意识里面根本不在考虑范围内。
    50人的团体中，具体到某个人，跟其他人生日撞车的可能性还是比较低的(14%)。

    回复
  20. hbchendl 说：
    2009-12-12于19:19

    这样考虑也许能好理解一点：
    50个人先排个队。
    先考虑第一个人：其他49人有一个与他同时出生的概率是49/365.这其实已经是一个比较大的概率了。
    再考虑第二个人：剩下的48人有一个与他同时出生的概率还有48/364。
    再去考虑第三个，第四人，概率累加起来（当然不是简单地相加的）就相当可观了。

    回复
    • xuby 说：
      2009-12-12于19:44

      大学肯定没学好概率论与统计～～

      回复
      • 莽轩 说：
        2009-12-12于22:15

        不是每个专业都有这个课的，像我所学的“生物技术”所学的与数学有关的就是大一的高数，还有大二的线性代数，大学物理，好吧还有门生物的计算与统计方法。

        回复
        • 温和蜕变 说：
          2010-02-11于15:13

          我们连线性代数都没了，生物统计学是选修，不喜欢数学的大都不会去选

          回复
    • Lewind 说：
      2009-12-12于20:16

      49/365完全没有道理……

      回复
  21. 少言 说：
    2009-12-12于19:56

    今天我20咯

    回复
  22. Lewind 说：
    2009-12-12于20:15

    记得小学数学奥校讲排列组合时，老师是这样帮大家理解这个问题的：

    虽然正着理解时，感觉悖离了常识，但我们不妨反过来理解。
    “50个人中至少有两人同一天生日”，意思反过来就是“50个人中没有任何两个人同一天生日”。
    如果前者的概率很大，就意味着后者的概率很小，因为这两者互为反命题，概率之合为1。

    50个人生日全不同的概率很好算。
    第一个人的生日在某一天，在365天中有365个可能，所以概率是365/365=1。
    第二个人的生日在某一天，但不能跟第一个人的生日重复，也就是只能出现在剩下的364天中，所以概率是364/365。但还要联合上第一个人的选择，所以总概率是(365/365)*(364/365)。
    以此类推，后面的人可选的日子越来越少，这个式子会随人数增加而变长：
    (365/365)*(364/365)*(363/365)*(362/365)*……*(317/365)*(316/365)
    有50个人，上面这个式子就有50项。

    一开始这几项都很接近1，相乘结果也接近1，所以符合常识：人少时，没有任何人同一天生日的可能性很大；反之，有两人同天生日的概率就很少。
    但只要在计算器上按按这个数你就会发现，这个式子越往后乘，虽然每项都还远大于0.5，但总的积已经越来越小，最后小到了0.03，也就是3%。
    反过来，50人中任两人同天生日的概率就大到了97%。

    回复
  23. laoma 说：
    2009-12-12于21:10

    用抽屉原则应该有366个抽屉，2月29日也是一个抽屉。

    回复
    • 苏椰 说：
      2009-12-12于21:17

      在前面的例子中，我们是把一年当作365天的～ 如果要考虑366天或火星的年度啥的，可以用后面的公式算～

      回复
  24. 每天一锅 | 2009-12-12 | PlayTrue 说：
    2009-12-12于21:47

    [...] Posted 生日悖论与生日攻击. [...]

    回复
  25. 默默 说：
    2009-12-12于21:55

    我们班40个人，怎么就没人跟我生日一样呢？我高中班上也四十个人，也没人跟我生日一样，从小到大的所有班级都没有人跟我生日一样。

    回复
    • Lewind 说：
      2009-12-14于4:34

      “很可能有两个人的生日在同一天”并不意味着“你”一定是那“两个人”中的一个……

      回复
  26. 莽轩 说：
    2009-12-12于22:10

    C2（365） （364/365）364次方*（1/365）2次方 这个计算方法不知道行不行，本人没计算，因为数看起来太大了

    回复
  27. 磊 说：
    2009-12-12于22:47

    一直引以为自豪的和老婆同月同日（差一年），看来只是在加上性别，感情因素，概率不是想象中那么小啊！

    回复
  28. 小丑鱼 说：
    2009-12-12于23:12

    文章写得挺好的，此现象也很有趣，如果公式再简化一下就更好了

    回复
  29. 菠菜 说：
    2009-12-12于23:28

    楼主不知道写些什么最后也没得出个97%
    Lewind的算法通俗易懂
    楼主你不会科普不是你的错
    但写一堆超过9年制教育的公式出来吓人是不是太无聊了？

    我不知道喜欢吓别人的人是不是自己还没搞清楚
    就喜欢出来卖弄
    没研究就想写博客干吗不写点爱情或者鬼怪呢？
    把科普弄成跳大神有意思吗

    就算你小时候没看过科幻世界
    对数学也没有兴趣
    拜托现在多学学怎么用google和百度

    回复
    • 苏椰 说：
      2009-12-13于3:09

      您怪我前一个问题没有给出计算过程，又怪我后一个问题给出了计算过程，那我到底应不应该给啊？

      第二段我明明已经说了，“在文章开头插入公式十分倒胃，所以我就不写计算过程，直接给出结果（除了传统的排列组合方法外，Paul Halmos[1]还给出了一个巧妙的解法）。”

      回复
      • 菠菜 说：
        2009-12-13于9:56

        是。
        因为我觉得先不把简单公式说清楚
        就急匆匆写比较晦涩的公式
        违背科普的本性
        就跟跳大神地说不出基本的事物规律却强调自己会抓鬼一样
        当然也有可能你我对科普的定义不同
        您觉得前一个太简单了不屑说
        但就我看评论的大部分
        基本都在玩味97%的结论

        另外我本人觉得多用晦涩的公式会打击许多人对简单规律的理解和追求
        或者会让别人觉得这些玩意没有趣味

        正确+易懂+趣味=优秀的科普作品
        当然这只是我个人观点
        您怎么想没关系
        我姑且一说，您姑且一看
        看的不爽么。。。或删或骂随您高兴
        希望没打击你继续写博客的信心

        回复
  30. Mike 说：
    2009-12-12于23:32

    其实那个概率的算法公式只要简化一下上过高中都都能看懂。。。再说了。。。通过概率计算的生日悖论上过高中的都应该早就学过了。。。

    主要是后面的生日攻击太。。。笼统了点。。。稍微解释下着篇就是科普精品了。。。

    个人认为。

    回复
  31. suizui 说：
    2009-12-13于0:38

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

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

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

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

    回复
    • suizui 说：
      2009-12-13于0:42

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

      回复
    • suizui 说：
      2009-12-13于0:53

      硬出一个经验公式

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

      =很少很少/多得不得了

      回复
    • suizui 说：
      2009-12-13于1:13

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

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

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

      回复
    • suizui 说：
      2009-12-13于19:13

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

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

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

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

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

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

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

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

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

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

      回复
  32. 里斯本 说：
    2009-12-13于5:16

    作者的意思是，其实“我”也是“人”

    回复
  33. 江南尖头曼 说：
    2009-12-13于9:33

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

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

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

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

    开个玩笑，别介意。

    回复
  34. 陈镜全 说：
    2009-12-13于9:46

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

    回复
  35. BizAsia 说：
    2009-12-13于10:54

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

    回复
    • 好玩 说：
      2009-12-13于12:25

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

      回复
  36. ygd 说：
    2009-12-13于11:57

    不可思议

    回复
  37. ygd 说：
    2009-12-13于12:03

    年份不要考虑吗?

    回复
    • Coke 说：
      2009-12-13于19:53

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

      回复
  38. BountyHunter 说：
    2009-12-13于12:51

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

    回复
  39. re.jet 说：
    2009-12-13于12:52

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

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

    回复
  40. 小A 说：
    2009-12-13于13:48

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

    回复
  41. PS 说：
    2009-12-13于14:44

    即使在文末插入公式也很倒人胃口

    回复
  42. xiaopu 说：
    2009-12-13于14:47

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

    回复
  43. 史蒂芬 说：
    2009-12-13于14:50

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

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

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

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

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

    回复
    • Schuyler 说：
      2009-12-14于7:03

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

      回复
      • 史蒂芬 说：
        2009-12-14于8:41

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

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

        回复
        • Schuyler 说：
          2009-12-14于9:28

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

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

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

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

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

          回复
          • 史蒂芬 说：
            2009-12-14于12:49

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

          • Schuyler 说：
            2009-12-14于15:58

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

  44. Explorer 说：
    2009-12-13于15:43

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

    回复
  45. 迷雾 说：
    2009-12-13于15:55

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

    回复
    • 温和蜕变 说：
      2010-02-11于15:20

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

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

      回复
  46. 虾然蛙然 说：
    2009-12-13于16:47

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

    回复
  47. Coke 说：
    2009-12-13于19:54

    鸽巢原理就是抽屉原理吧？

    回复
  48. 另一条八爪鱼 说：
    2009-12-13于23:14

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

    回复
  49. 小姬 说：
    2009-12-14于8:37

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

    回复
  50. Big_ken 说：
    2009-12-14于12:27

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

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

    回复
  51. conwood 说：
    2009-12-14于12:56

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

    回复
  52. whale 说：
    2009-12-14于22:13

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

    回复
  53. exreed 说：
    2009-12-15于8:47

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

    回复
  54. 行者如思 说：
    2009-12-15于15:26

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

    回复
  55. 绿萝花 说：
    2009-12-15于16:04

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

    回复
  56. Elaine 说：
    2009-12-16于22:56

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

    回复
  57. wan 说：
    2009-12-17于13:56

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

    回复
    • williamjen 说：
      2009-12-18于10:35

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

      回复
  58. V 说：
    2009-12-18于12:04

    这篇文章很有Matrix大大的韵味^_^

    回复
  59. 那一天 说：
    2009-12-18于21:41

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

    回复
  60. kid 说：
    2009-12-20于21:06

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

    回复
  61. a-dai 说：
    2009-12-21于22:06

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

    回复
  62. guanenhao 说：
    2010-01-03于15:38

    真的很神奇呀！

    回复
  63. suizui 说：
    2010-01-11于0:59

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

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

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

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

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

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

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

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

    回复
  64. iceblast 说：
    2010-02-11于15:50

    终于知道HASH表的原理了，叹

    回复

Leave a Reply

必填

必填，不会公开

选填