[证券考试]生日悖论与生日攻击：50个人中相同生日的缘分是多少？

admin

作者

每个人都有生日，偶然会遇到与自己同一天过生日的人，但在日子中，这种缘分好像并不常有。咱们猜猜看，在50个人傍边，呈现这种缘分的概率有多大，是10%，20%，仍是50%？

有人告诉我，在文章最初刺进公式十分倒胃，所以我就不写核算进程，直接给出成果（除了传统的排列组合方法外，Pa 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]

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

所以生日悖论的实质便是，跟着元素增多，呈现重复元素的概率会以惊人速度增加，而咱们轻视了它的速度。（对核算感到头疼的读者，可以挑选在此停下脚步。别忧虑，国际仍然夸姣。）这个问题不容忽视，由于它意味着，在密码学中，咱们轻视了散列值呈现磕碰的概率。这一定论应用于对散列函数的进犯中，称为“生日进犯(Birthday Attack)”[2]。

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

下面考虑一个64位散列函数，它有2^64种或许的散列值，要想100%地找到一组磕碰，就需求2^64+1≈10^19次进犯。可是根据生日进犯的原理，咱们只需求2^32≈10^9次进犯，就有约50%的概率可以进犯成功。下面给出一种证明（符号沿袭上面公式的）：