1 365/ 365 364 / 365 363/ 365 (365 N 1) / 365
设置这个表达式等于1/2，并解出N，我们得到N = 23
生日 悖论
8
• 延伸
对于一个生成N位二进制长度输出的安全哈希函数来说，一个计算开 销大约以2N /2为因子的强力破解方式，就能够对其发起有效的攻击。 相比较而言，对于一个密钥长度为N位二进制数的安全对称密钥加密 方案来说，对其强力破解的计算开销的因子是2N-l。 所以，安全哈希函数的输出必须是对称加密密钥二进制位数的大约两 倍长，才能够获得与后者基本相当的安全水平。
•
• • •
4
哈希函数在数字签名上的应用 • 以前
Alice对一条消息M实施签名，是通过使用她自己的私钥进行“加密”计算得到的，即要计 算S = [M]Alice。如果Alice发送消息M和签名S给Bob，Bob就能够通过执行验证过程M = {S}Alice来验证该签名的有效性。但是，如果消息M很大，[M]Alice就是一个成本很高的计算， 更不用提发送消息M和签名S的带宽需求了，这两者都会很大。相比之下，在计算一个MAC 时，加密的速度会很快，而且在发送时，我们也仅仅需要伴随着消息发送少量附加的校验 位(比如MAC)而已。
• •
• •
10
• 在这个攻击中，Trudy获得了Alice对于一条Trudy自选消息的签名，但 是并没有以任何方式攻击潜在的公开密钥加密系统。 • 这个攻击是一个针对哈希函数h的强力攻击，而哈希函数h是用于计算 数字签名的。 • 为了防止此类攻击，我们可以选择一个哈希函数，使得该哈希函数的 输出值的长度n足够大，以至于Trudy无法完成2n/2个哈希值的计算。
3
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)，这是不可 能的。也就是说，我们不能够找到任何两个输入，使得它们经过哈希后会产 生相同的输出值。
5
签名的正确方法
• 假设没有碰撞，那么对h(M)签名和对消息M实施签名的效果一样好。 事实上，对哈希值实施签名比起仅仅对消息本身实施签名，实际上会 更加安全。 • 现在数字签名的安全性不仅依赖于公钥系统的安全性，而且也依赖于 哈希函数本身的安全性——如果二者中有任何一个比较弱，签名体制 就可能会被破解。
1 (364 / 365) N
设置这个表达式等于1/2，并解出N，得到N = 253。
7
• 真正的生日问题
我们给房间里的N个人分别编上号码1，2，3，…，N。编号为1的人的生 日是一年365天中的一天。如果所有人的生日各不相同，那么编号为2的 人必须与编号为1的人的生日不相同，也就是说，编号为2的人的生日只 能是剩余的364天中的任意一天。同样，编号为3的人的生日只能是再剩 余的363天中的任意一天，依此类推。假设所有的生日都是概率相等的， 考虑上述情况的补集，其最后的概率计算如下式所示
6
5.3 生日问题
假如你和其他N个人同在一个房间里。那么，N必须多大，你才有指望找 到至少一个人和你有相同的生日呢？或者说：N必须多大，才会使得“有 某个人与你生日相同”的概率大于1/2呢？
你的生日是在一年中特定的一天。如果一个人和你的生日不同，那么他 或她的生日必定是在其他364天中的一天。假设所有的生日都是概率相等 的，那么“一个随机选择的人不与你的生日相同”的概率就是364/365。 这样，所有的N个人都跟你的生日不同的概率就是(364/365)N，于是，至 少有一个人与你的生日相同的概率就是：
15
Tiger算法的过程 • 首先对输入值X进行附加填充位，使其长度满足512位二进制长的倍数， 表示为： X=(X ,X ,...,X ) ，其中每一个Xi都是一个512位二进制长的分组。 • 对每一个Xi使用一个外层的轮运算。假设a，b和c都是64位二进制长的 值。对于第一轮运算，(a, b, c)的初始值以16进制形式表示如下：
19
• 小结
fm,i由下式给定：
•
每一个Si都是一个S-box(即查找表)，将8位二进制映射为64位二进制。
18
密钥调度算法 • 假设令W为密钥调度算法的512位二进制输入值。同上，我们将W写作 W= (w0, w1,…, w7)，其中每一个wi都是一个64位二进制值，我们再令 为wi的二进制补数。 • 密钥调度算法如下，其中最后的计算结果W= (w0, w1,…, w7)给出了该 算法的输出值。Βιβλιοθήκη 115.5 非加密哈希
非加密哈希运算的例子
X ( X 0 , X1, X 2 ,..., X n 1 )
（1）其中，每个Xi是一个字节，定义哈希函数h(X)为：
h X ( X 0 X1 X 2 ... X n 1 ) mod 256
这毫无疑问提供了压缩功能，因为任何长度的输入都被压缩为8位二进制的输出。但是，这 个哈希很容易被破解，因为生日问题的结论告诉我们，只需对24 = 16个随机选择的输入执 行哈希运算，我们就有望找到一个碰撞。 对两个字节进行互换，就总是能够产生一个碰撞，类似如下这种情况：
• 使用哈希函数之后
假设Alice有一个加密哈希函数h。那么，h(M)可以被看做文档M的一个“指纹”，也就是说， h(M)比M小得多，但是它能够标识出M。如果M'不同于M，那么即使仅仅相差一个单独的二 进制位，哈希函数执行的结果也几乎肯定会不同。而且，哈希函数的抗碰撞特性意味着， 想要将消息M替换为任何不同的消息M'，使得h(M) = h(M')是不可能的 1. 一旦哈希值发生相 同的情况，该怎么办呢？好的，这说明你已经发现了一个碰撞，也就意味着你已经攻破了 这个哈希函数，于是你就成为一个著名的密码破解专家了。所以，这是个双赢的好事。
例子 假设给定的除数是10011，而有趣的是数据恰好是10101011。那么，我们先对数 据附加上4个0(附加的位数要比除数的二进制位数少1)，然后执行如下长除法运算：
CRC校验和就是长除法运算的余数——在这个例子中，就是1010。
13
5.6 Tiger Hash
• MD5
MD指的是消息摘要(Message Digest)，它的前身是MD4，而MD4本身又 继承自MD2。 所有的MD系列算法都是由加密领域的大师级人物Ron Rivest所发明。 MD5算法生成128位的输出值。
W=(w0 ,w1,...,w7 )
17
• 对于函数fm,i，当i = 0,1,2, ... ,7时，其各自的输入值分别如下
其中各自对应的函数fm,i-1的输出标记为(a, b, c)。每一个fm,i都依赖于a，b，c， wi和m，其中wi是512位二进制输入值W的第i个64位子分组。
• c写作： c (c0 ,c1,...,c7 ) ，其中每一个ci都是一个单独的字节。
Information Security: Principles and Practice, 2nd Edition [美]Mark Stamp 张 戈 著 译
1
第5章 哈希函数及其他
2
5.1 引言
本章内容 • 加密哈希函数 • 加密哈希函数的标准应用 • 哈希函数的高级应用 • 加密相关的副作用问题
14
Tiger算法特点
算法的输入先被分成512位二进制长度的分组，如果需要的话，就对输入 值进行附加填充位，以补足成512的倍数位的长度。 算法输出192位二进制长度的哈希值。 算法实现中使用了4个S-box，这4个S-box的每一个都将8位二进制位映射 为64位。 算法还使用了一个“密钥调度”的算法，不过由于这里没有密钥的概念， 该算法实际是施加到了输入分组上。
h(00000001, 00001111) h(00000000,00010001) 00010001
12
循环冗余校验，或简称为CRC
• • 循环冗余校验码的计算本质上是长除法，将余数作为CRC计算的“哈希”值。 与常规的长除法不同，CRC在计算中使用XOR运算替代了减法。 在一个CRC的计算过程中，除数被指定作为算法的一部分，数据作为被除数。
• SHA-1算法
SHA表示安全哈希算法(Secure Hash Algorithm)，是美国政府的一个标准。 SHA-1算法实际上非常类似于MD5算法。两个算法在实践中的主要不同在 于SHA-1生成160位二进制长的输出值，比MD5提供了更可观的安全边际。 所谓雪崩效应，是所有加密哈希函数都会追求的一个理想特性。其目标是：在 输入值中任何小的变化，都应该级联传递并导致输出结果较大的变化——就像 雪崩一样。理想情况下，任何输入值的变化引发的输出值变化都是不相关的， 这样，攻击者将不得不实施穷举式检索来寻找碰撞。
h(10101010,00001111) = h(00001111,10101010) = 10111001
（2）我们将哈希函数h(X)定义为：
h X (nX 0 (n 1) X1 (n 2) X 2 ... 2X n 2 X n 1 ) mod 256
虽然该函数在交换输入字节顺序的情况下能够输出不同的结果，但是仍然逃不过生日问题 带来的麻烦。