• 单向——给定任意值y，要想找到一个值x，使得h(x) = y，将是计算不可行的 。换一种不同的说法，即对于哈希运算，没有行之有效的逆运算。
• 抗弱碰撞性——给定x和h(x)，要想找到任意y，满足y≠x，并且h(y) = h(x)，这 是不可能的。
• 抗强碰撞性——要想找到任意的x和y，使得x≠y，并且h(x) = h(y)，这是不可 能的。也就是说，我们不能够找到任何两个输入，使得它们经过哈希后会产 生相同的输出值。
6
5.3 生日问题
假如你和其他N个人同在一个房间里。那么，N必须多大，你才有指望找 到至少一个人和你有相同的生日呢？或者说：N必须多大，才会使得“有 某个人与你生日相同”的概率大于1/2呢？
你的生日是在一年中特定的一天。如果一个人和你的生日不同，那么他 或她的生日必定是在其他364天中的一天。假设所有的生日都是概率相等 的，那么“一个随机选择的人不与你的生日相同”的概率就是364/365。 这样，所有的N个人都跟你的生日不同的概率就是(364/365)N，于是，至 少有一个人与你的生日相同的概率就是：
5
签名的正确方法
• 假设没有碰撞，那么对h(M)签名和对消息M实施签名的效果一样好。 事实上，对哈希值实施签名比起仅仅对消息本身实施签名，实际上会 更加安全。
• 现在数字签名的安全性不仅依赖于公钥系统的安全性，而且也依赖于 哈希函数本身的安全性——如果二者中有任何一个比较弱，签名体制 就可能会被破解。
4
哈希函数在数字签名上的应用 • 以前
Alice对一条消息M实施签名，是通过使用她自己的私钥进行“加密”计算得到的，即要计 算S = [M]Alice。如果Alice发送消息M和签名S给Bob，Bob就能够通过执行验证过程M = {S}Alice来验证该签名的有效性。但是，如果消息M很大，[M]Alice就是一个成本很高的计算， 更不用提发送消息M和签名S的带宽需求了，这两者都会很大。相比之下，在计算一个MAC 时，加密的速度会很快，而且在发送时，我们也仅仅需要伴随着消息发送少量附加的校验 位(比如MAC)而已。
Information Security: Principles and Practice, 2nd Edition [美]Mark Stamp 著 张戈 译
1
第5章 哈希函数及其他
2
5.1 引言
本章内容 • 加密哈希函数 • 加密哈希函数的标准应用 • 哈希函数的高级应用 • 加密相关的副作用问题
相比较而言，对于一个密钥长度为N位二进制数的安全对称密钥加密 方案来说，对其强力破解的计算开销的因子是2N-l。
所以，安全哈希函数的输出必须是对称加密密钥二进制位数的大约两 倍长，才能够获得与后者基本相当的安全水平。
9
5.4 生日攻击
假设哈希函数h生成一个n位二进制长的输出。Trudy原则上能够发起一次 生日攻击，具体如下：
1 (364 / 365)N
设置这个表达式等于1/2，并解出N，得到N = 253。
7
• 真正的生日问题
我们给房间里的N个人分别编上号码1，2，3，…，N。编号为1的人的生 日是一年365天中的一天。如果所有人的生日各不相同，那么编号为2的 人必须与编号为1的人的生日不相同，也就是说，编号为2的人的生日只 能是剩余的364天中的任意一天。同样，编号为3的人的生日只能是再剩 余的363天中的任意一天，依此类推。假设所有的生日都是概率相等的， 考虑上述情况的补集，其最后的概 365363/ 365(365 N 1) / 365
设置这个表达式等于1/2，并解出N，我们得到N = 23
生日 悖论
8
• 延伸
对于一个生成N位二进制长度输出的安全哈希函数来说，一个计算开 销大约以2N /2为因子的强力破解方式，就能够对其发起有效的攻击。
3
5.2 什么是加密哈希函数
一个加密哈希函数h(x)，必须满足下列所有条件：
• 压缩——对于任何长度的输入值x，输出值y = h(x)的长度都比较小。在实际使 用中，通常输出值是固定长度的(比如160位长度的二进制值)，而无论输入值 的长度是多少。
• 高效——对于任何的输入值x，必须能够很容易地计算出h(x)。当然，伴随着 输入值x的长度增加，计算h(x)所需要的计算量也会随之增加，但是，这不能 增长得太快。
• Trudy选择一条“恶意”消息E，这是她想让Alice签名的消息，但是Alice并不想对其签 名。
• Trudy也创建了一条无害的消息I，她有信心Alice愿意对这条消息签名。 • 然后，Trudy通过对消息实施较小的编辑性修改，生成2n/2条该无害消息I的变体。这些
无害的消息，我们分别标识为Ii，其中i = 0,1, ... ,2n/2 – 1，所有消息都与I的含义相同， 但是既然消息本身不同，那么它们的哈希值也不一样。 • 同样，Trudy创建出2n/2个恶意消息E的变体，分别标识为Ei，其中i = 0,1, ... ,2n/2 – 1。 这些消息也都与原始的恶意消息E表达同样的含义，但是它们的哈希值不一样。 • Trudy对所有的恶意消息Ei以及所有的无害消息Ii实施哈希运算。根据上述生日问题的讨 论，她就有希望找到一个碰撞，比方说，h(Ej) = h(Ik)。基于这样的一个碰撞，Trudy将Ik 发送给Alice，并请Alice对其进行签名。既然这条消息看起来没有问题，Alice就对其进 行签名，并将Ik和[h(Ik)]Alice返回给Trudy。既然h(Ej) = h(Ik)，那么由此可以得出[h(Ej)]Alice = [h(Ik)]Alice，于是，Trudy实际上就已经获得了Alice对恶意消息Ej的签名。
• 使用哈希函数之后
假设Alice有一个加密哈希函数h。那么，h(M)可以被看做文档M的一个“指纹”，也就是说， h(M)比M小得多，但是它能够标识出M。如果M'不同于M，那么即使仅仅相差一个单独的二 进制位，哈希函数执行的结果也几乎肯定会不同。而且，哈希函数的抗碰撞特性意味着， 想要将消息M替换为任何不同的消息M'，使得h(M) = h(M')是不可能的 1. 一旦哈希值发生相 同的情况，该怎么办呢？好的，这说明你已经发现了一个碰撞，也就意味着你已经攻破了 这个哈希函数，于是你就成为一个著名的密码破解专家了。所以，这是个双赢的好事。