问题：假设有n个人参加一个集会，且每个人的生日均是相互独立的；那这n个人的生日全不同的概率p是多少？ 解析：假设一年为365日，且这n个人的生日是均匀分布的。记第一个人的生日为r1，要使第二个人与第一个人生日不同，则第二个人只能选择365天中除掉r1剩下的，同理，要使第三个人与前两个人生日不同，他只能从剩下的363天中选择……以此类推，n个人的生日全不同的概率p为： P=（1-1/365）×（1-2/365）×……×［1-（n-1）/365］ 借助计算机可以计算出，当n=23时，p≈0.5，即在一个屋子里只需要23个人，找到两个或两个以上相同生日的人的概率就有50%。而当n=70时，p≈0.99。这样的结果与我们的直觉不符，所以称之为生日悖论。 生日悖论在密码学中有着广泛的应用。为了保证信息传输的保密性、数据交换的完整性，我们采用数字签名技术确保安全。形象地说：A要给B发送一段报文。A发送时用哈希函数从报文中生成报文摘要，再用密钥对摘要进行加密。加密后的摘要将作为报文的数字签名和报文一起发送给B。B用同样的方法对报文进行加工，若得到的摘要与A发送的相同，则B得到的报文在A发送的期间没有被改动过。 我们将生日悖论拓展开来：在该计算过程中，我们是将人（输入）转换成生日（输出）。也就是说，我们将千万种不同的人映射成365种人。在密码学中，哈希算法就是将一个大的集合（输入）映射到小的集合（哈希值），必然会造成多个输入映射到一个哈希值上，这就是哈希碰撞。根据生日悖论，如果哈希值的位数过短，很容易可以找到一组（两个）哈希值相同的输入，这就是一种最常用的生日攻击的应用。 如果产生每个哈希值的可能性是相同的，根据生日悖论，n位的哈希值预计产生一次碰撞需要2^（n/2）次尝试。如果找到哈希碰撞，那么两个报文可以产生相同的报文摘要。这意味着，当你在网络上使用电子签名签署一份合同后，还可能存在另外一份具有相同签名但内容迥异的合同。在神不知鬼不觉的情况下，你们的信息就被掉包了。 |
|
|
