每个人都有生日,偶尔会遇到与自己同一天过生日的人,但在生活中,这种缘分似乎并不常有。我们猜猜看,在50个人当中,出现这种缘分的概率有多大,是10%,20%,还是50%?
有人告诉我,在文章开头插入公式十分倒胃,所以我就不写计算过程,直接给出结果(除了传统的排列组合方法外,Paul Halmos[1]还给出了一个巧妙的解法)。在50个人中有相同生日的概率,高达97%,这个数字,恐怕高出了绝大多数人的意料。1 x" ~* J8 `* A) w
& f7 Q/ v' |" f2 a, ]( T! I1 I
我们没有算错,是我们的直觉错了,科学与生活,又开了个玩笑。正因为计算结果与日常经验产生了如此明显的矛盾,该问题被称为“生日悖论(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位散列函数,它有
种可能的散列值,要想100%地找到一组碰撞,就需要
次攻击。但是基于生日攻击的原理,我们只需要
次攻击,就有约50%的概率能够攻击成功。下面给出一种证明(符号沿用上面公式的):
两端整理得:
当P=0.5时
在
次攻击中,就有约50%的概率发生碰撞,收益降低一半,成本却开了根号,对于这些大数字来说,开根号是件不得了的事。为了提高碰撞率,我们以
个散列作为一组,用独立的10组分别进行攻击,则一共需要约
次攻击,出现碰撞的概率高于
99.9%——这是一个非常理想的成功率,
需要的攻击次数却仅是原来的