信息安全原理与实践-第二版05 哈希函数及其他.ppt

《信息安全原理与实践-第二版05 哈希函数及其他.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1信息安全原理与实践InformationSecurity:PrinciplesandPractice,2ndEdition[美]MarkStamp著张戈译第5章哈希函数及其他25.1引言本章内容加密哈希函数加密哈希函数的标准应用哈希函数的高级应用加密相关的副作用问题35.2什么是加密哈希函数一个加密哈希函数h(x)，必须满足下列所有条件：压缩——对于任何长度的输入值x，输出值y=h(x)的长度都比较小。在实际使用中，通常输出值是固定长度的(比如160位长度的二进制值)，而无论输入值的长度是多少。高效——对于任何的输入值x，必须能够很容易地计

2、算出h(x)。当然，伴随着输入值x的长度增加，计算h(x)所需要的计算量也会随之增加，但是，这不能增长得太快。单向——给定任意值y，要想找到一个值x，使得h(x)=y，将是计算不可行的。换一种不同的说法，即对于哈希运算，没有行之有效的逆运算。抗弱碰撞性——给定x和h(x)，要想找到任意y，满足y≠x，并且h(y)=h(x)，这是不可能的。抗强碰撞性——要想找到任意的x和y，使得x≠y，并且h(x)=h(y)，这是不可能的。也就是说，我们不能够找到任何两个输入，使得它们经过哈希后会产生相同的输出值。4哈希函数在数字签名上的应用以前Alice对一

3、条消息M实施签名，是通过使用她自己的私钥进行“加密”计算得到的，即要计算S=[M]Alice。如果Alice发送消息M和签名S给Bob，Bob就能够通过执行验证过程M={S}Alice来验证该签名的有效性。但是，如果消息M很大，[M]Alice就是一个成本很高的计算，更不用提发送消息M和签名S的带宽需求了，这两者都会很大。相比之下，在计算一个MAC时，加密的速度会很快，而且在发送时，我们也仅仅需要伴随着消息发送少量附加的校验位(比如MAC)而已。使用哈希函数之后假设Alice有一个加密哈希函数h。那么，h(M)可以被看做文档M的一个“指纹”，

4、也就是说，h(M)比M小得多，但是它能够标识出M。如果M'不同于M，那么即使仅仅相差一个单独的二进制位，哈希函数执行的结果也几乎肯定会不同。而且，哈希函数的抗碰撞特性意味着，想要将消息M替换为任何不同的消息M'，使得h(M)=h(M')是不可能的1.一旦哈希值发生相同的情况，该怎么办呢？好的，这说明你已经发现了一个碰撞，也就意味着你已经攻破了这个哈希函数，于是你就成为一个著名的密码破解专家了。所以，这是个双赢的好事。5签名的正确方法假设没有碰撞，那么对h(M)签名和对消息M实施签名的效果一样好。事实上，对哈希值实施签名比起仅仅对消息本身实施签

5、名，实际上会更加安全。现在数字签名的安全性不仅依赖于公钥系统的安全性，而且也依赖于哈希函数本身的安全性——如果二者中有任何一个比较弱，签名体制就可能会被破解。65.3生日问题假如你和其他N个人同在一个房间里。那么，N必须多大，你才有指望找到至少一个人和你有相同的生日呢？或者说：N必须多大，才会使得“有某个人与你生日相同”的概率大于1/2呢？你的生日是在一年中特定的一天。如果一个人和你的生日不同，那么他或她的生日必定是在其他364天中的一天。假设所有的生日都是概率相等的，那么“一个随机选择的人不与你的生日相同”的概率就是364/365。这样，所

6、有的N个人都跟你的生日不同的概率就是(364/365)N，于是，至少有一个人与你的生日相同的概率就是：设置这个表达式等于1/2，并解出N，得到N=253。7真正的生日问题我们给房间里的N个人分别编上号码1，2，3，…，N。编号为1的人的生日是一年365天中的一天。如果所有人的生日各不相同，那么编号为2的人必须与编号为1的人的生日不相同，也就是说，编号为2的人的生日只能是剩余的364天中的任意一天。同样，编号为3的人的生日只能是再剩余的363天中的任意一天，依此类推。假设所有的生日都是概率相等的，考虑上述情况的补集，其最后的概率计算如下式所示设

7、置这个表达式等于1/2，并解出N，我们得到N=238生日悖论延伸对于一个生成N位二进制长度输出的安全哈希函数来说，一个计算开销大约以2N/2为因子的强力破解方式，就能够对其发起有效的攻击。相比较而言，对于一个密钥长度为N位二进制数的安全对称密钥加密方案来说，对其强力破解的计算开销的因子是2N-l。所以，安全哈希函数的输出必须是对称加密密钥二进制位数的大约两倍长，才能够获得与后者基本相当的安全水平。95.4生日攻击假设哈希函数h生成一个n位二进制长的输出。Trudy原则上能够发起一次生日攻击，具体如下：Trudy选择一条“恶意”消息E，这是她想

8、让Alice签名的消息，但是Alice并不想对其签名。Trudy也创建了一条无害的消息I，她有信心Alice愿意对这条消息签名。然后，Trudy通过对消息实施较小的