密码学之哈希碰撞和生日悖论

哈希碰撞

哈希碰撞是指找到两个不一样的值，它们的哈希值却相同

假设哈希函数的取值空间大小为k ，计算次数为n

先算每个值不一样的概率P’

 

所以至少两个值相同(即存在哈希碰撞)的概率P为 

生日悖论

假设班里有50个人，求班里至少两个人相同生日的概率

可以看成取值空间大小为365，计算次数为50的哈希碰撞问题

用python编程计算

import mathn = 50
k = 365print(1 - math.factorial(k) / (k ** n * math.factorial(k - n)))  # 精确计算
print(1 - pow(math.e, -n * (n - 1) / (2 * k)))  # 近似计算

这里虽然k太小，但是实际值和估计值不会差很多

 

班里只有50个人，两个人相同生日的概率竟高达0.9704，与我们的惯性思维差很多，这就是著名的生日悖论问题