哈希函数2.PPT

6.2 生日攻击与强抗碰撞强度 6.2.1 生日悖论 问题：假定每个人的生日是等概率的，每年有365天（不考虑闰年）。在k个人中至少有两个人的生日相同的概率大于1/2。问k的最小值。 我们把每个人的生日看成在[1，365]中的随机变量。有基本组合数学知识知个人的生日不重复的概率为 当k=23时， 。从而23个人的生日至少有一个重复的概率为 = 0.5073。这个结果似乎和人们的直觉不太一致，这就是所谓的生日悖论。 6.2.2 两个相交的集合 6.2.3 强抗碰撞强度 “两个集合相交”问题可以转述为：假设哈希函数h输出长度为m，全部可能的输出有 个。现哈希函数h接收k个随机输入产生X，接受另外k个随机输入产生Y。根据前面的讨论知，当取 时才使X与Y至少存在一对匹配的概率大于1/2。 由此看出 将决定输出长度m为哈希函数h强抗碰撞的强度。 如果我们采用传输加密的消息摘要和不加密的消息，那么对手需要寻找另一个消息使得这两个消息的摘要相同，以便代替原消息来欺骗接收者。一种基于生日悖论的攻击有可能做到这一点。G.Yuval在1979年提出如下策略： 发送者准备通过在消息x后面附加 来对消息x进行签名，其中 是m位； 对手对消息x产生 个变形的消息（表达同样的意思），再拟定表示另一个意思的 个假消息（准备去替换消息x）。计算所有消息的哈希值； 根据生日悖论，“两个相交集合”问题成功的概率大于1/2。比较两个哈希值集合，以便发现具有相同哈希值（匹配）的消息。如果没发现，则再产生其他一批有效消息和假消息。直到出现一个匹配为止。 用找到匹配的假消息代替消息x后面仍然附加 送给接受方。 * * 给定一个取整数的随机变量，它服从[1，n]的 均匀分布。两个有个随机变量的集合 ， 。取定 ， （称与匹配）的概率 为1 / n， 的概率为1-1/n。Y中所有k个随机变量 都不等于 的概率为 。假设X中k个随机变量两两 互不相同，则Y中所有k个随机变量与X中k个随机变量都 不相等的概率为 。从而Y与X至少有一个匹 配的概率为 。我们希望知道多大的k能使这 个概率大于1 / 2。为此，利用不等式 有 。令不等式右边等于1/2，求 出 。