05 哈希函数及其他.ppt

* 一条直线是一个一次多项式，它可以由两点唯一确定。 一条抛物线是一个二次多项式，它可以由三个点唯一确定。 一般而言，一个次数为m – 1的多项式可以由m个点唯一确定。 对于任意的m≤n，正是上述基本事实使得我们能够构造出一个“m out of n”型的秘密共享机制。 * 5.9.1.1密钥托管 如何解决密钥托管机构的信任问题？ 通过拥有多个托管机构，并允许用户将其密钥在这些托管机构中的n个之间进行分割，使得必须得有n个托管机构中的m个协同合作才能恢复出密钥。 Shamir的秘密共享机制可以用于实现这样的一个密钥托管方案。 假设N = 3 和 m = 2，Alice的密钥是S。使用 “2 out of 3”方案即可。 比如，Alice可能会选择让司法部持有点(X0, Y0)，让商务部持有点(X1, Y1)，再让Fred的密钥托管公司持有点(X2, Y2),。于是，这三个托管机构中必须至少有两个协同合作才能确定Alice的密钥S。 * 第5章 哈希函数及其他 TWELVE BUSINESS ACTIVITY MARKETING PLAN TEMPLATE * 5.1 引言 本章内容 加密哈希函数 加密哈希函数的标准应用 哈希函数的高级应用 加密相关的副作用问题 * 5.2 什么是加密哈希函数 一个加密哈希函数h(x)，必须满足下列所有条件： 压缩——对于任何长度的输入值x，输出值y = h(x)的长度都比较小。在实际使用中，通常输出值是固定长度的(比如160位长度的二进制值)，而无论输入值的长度是多少。 高效——对于任何的输入值x，必须能够很容易地计算出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)，这是不可能的。也就是说，我们不能够找到任何两个输入，使得它们经过哈希后会产生相同的输出值。 * 哈希函数在数字签名上的应用 以前 Alice对一条消息M实施签名，是通过使用她自己的私钥进行“加密”计算得到的，即要计算S = [M]Alice。如果Alice发送消息M和签名S给Bob，Bob就能够通过执行验证过程M = {S}Alice来验证该签名的有效性。但是，如果消息M很大，[M]Alice就是一个成本很高的计算，更不用提发送消息M和签名S的带宽需求了，这两者都会很大。相比之下，在计算一个MAC时，加密的速度会很快，而且在发送时，我们也仅仅需要伴随着消息发送少量附加的校验位(比如MAC)而已。 使用哈希函数之后 假设Alice有一个加密哈希函数h。那么，h(M)可以被看做文档M的一个“指纹”，也就是说，h(M)比M小得多，但是它能够标识出M。如果M不同于M，那么即使仅仅相差一个单独的二进制位，哈希函数执行的结果也几乎肯定会不同。而且，哈希函数的抗碰撞特性意味着，想要将消息M替换为任何不同的消息M，使得h(M) = h(M)是不可能的 1. 一旦哈希值发生相同的情况，该怎么办呢？好的，这说明你已经发现了一个碰撞，也就意味着你已经攻破了这个哈希函数，于是你就成为一个著名的密码破解专家了。所以，这是个双赢的好事。 签名的正确方法 假设没有碰撞，那么对h(M)签名和对消息M实施签名的效果一样好。事实上，对哈希值实施签名比起仅仅对消息本身实施签名，实际上会更加安全。 现在数字签名的安全性不仅依赖于公钥系统的安全性，而且也依赖于哈希函数本身的安全性——如果二者中有任何一个比较弱，签名体制就可能会被破解。 * 5.3 生日问题 假如你和其他N个人同在一个房间里。那么，N必须多大，你才有指望找到至少一个人和你有相同的生日呢？或者说：N必须多大，才会使得“有某个人与你生日相同”的概率大于1/2呢？ 你的生日是在一年中特定的一天。如果一个人和你的生日不同，那么他或她的生日必定是在其他364天中的一天。假设所有的生日都是概率相等的，那么“一个随机选择的人不与你的生日相同”的概率就是364/365。这样，所有的N个人都跟你的生日不同的概率就是(364/365)N，于是，至少有一个人与你的生日相同的概率就是： 设置这个表达式等于1/2，并解出N，得到N = 253。 * 真正的生日问题 我们给房间里的N个人分别编上号码1，2，3，…，N。编号为1的人的生日是一年365天中的一天。如果所有人的生日各不相同，那么编号为2的人必须与编号为1的人的生日不相同，也就是