HASH GAME - Online Skill Game GET 300

　　第六章．哈希函数 6.1.哈希函数 当我们对长的文件使用DSS签名时，需要把文件切成160 位的块并逐块分别签名，最后拼接起来构成整个文件的签名。这样做存在问题是： 文件的签名太长. 使用安全性好的签名算法，计算签名的时间花费太多. 将所有签名段的重新排序或删除其中一些段，最后仍然能够通过验证。需要保证的是整个消息的完整性 . 密码学哈希函数(Cryptography Hash Function)的基本思想是把哈希函数值 看成 的压缩代表（称为Imprint, Message Digest），即 中任意一位发生变化都将引起函数值的变化。这样我们可以用对 的签名代替对 的签名。哈希函数 ， ， 把任意有限长的输入行映射到固定长的行。哈希函数的值域与定义域相比规模要小得多，它是“多对一”的映射。所谓碰撞(Collision)是指定义域的两个不同元素 映射到同一个象 上。哈希函数存在碰撞是必然的。我们把 和 从计算意义上唯一地联系在一起，而找到碰撞在计算上是困难的。 例如： ， 满足基本要求但不 满足单向性3）。 ， 是大素数， ，不满足1）和4）5）。 为什么要提出性质3）4）和5）呢？ 如果哈希函数不满足3），则对手有可能用特定签名方案伪造随机消息摘要z 上的签名。例如对手掌握随机消息摘要z 上的签名y，他可以找到消息x 使 ，则 ( x, y ) 就是合格的伪造品。为此我们希望哈希函数满足单向性质。 如果我们不是对消息本身签名而是对消息摘要签名，那么就希望哈希函数满足性质4）。否则对手看到A在上的签名 后去找 使 ，而且声称A是对 签名。 如果让对手能自己选送消息请A签名，则要求哈希函数满足性质5）。否则对手找一对 使得 ，对手先让A对 签名，而后声称A是对 签名。 不难看出由性质5）可以推出性质4）。但是由性质5）不能推出性质3）。例如：g是满足性质5）的哈希函数，定义 。那么取以1打头长度为n+1的y，它的原象就是y的后面n位。 6.1.2 哈希函数的用法 哈希函数是一种消息认证码(Message Authentication Code)，它对消息产生一个短小的值。哈希函数是整个消息x的函数，消息中任意一位改变都将引起哈希函数值的改变。所谓认证是指一个证实收到的消息源可信且未被篡改的过程。有多种使用哈希函数方式来提供消息认证。已知A和B共享密钥K，如果A发送给B 1) 提供保密（仅双方共享K）和认证（加密保护哈希值）. 2) 提供认证（加密保护哈希值）. 提供认证和数字签名（加密保护 哈希值，仅发送方能生成签名）. 提供保密（仅双方共享K）、认证 和数字签名. 5) 提供保密、认证和数字签名（仅双方共享S） . 提供保密、认证和数字签名（仅双方共享K,S） . 对于不需要消息保密的应用中使用2）3）可以降低计算量。由于加密软件慢、硬件费用高、加密算法专利保护、出口限制等等因素，人们倾向不使用带有加密的方法，而采用5）。 6.1.3 哈希函数的构造方法 大多数重要的哈希函数设计成迭代过程。 为初值， 是第 阶段与 +1阶段间的链接变量。 是哈希函数的压缩函数， 是 位， 是 位， 是输出变换. 哈希函数 的输入是 。首先对 进行预处理使之长度是 的整倍数， ， 是 位， 。再令 ，对 做 。最后令函数值 。 以下两点提供了简单有效的构造方法。 1)任何强抗碰撞的压缩函数都可以扩展成一个强抗碰撞的哈希函数。 2)若 或 是强抗碰撞哈希函数，则 强抗碰撞的哈希函数。 由此可知，设计安全的哈希函数的难题变成设计一固定长输入的抗碰撞压缩函数。 * * 6.1.1哈希函数的性质 哈希函数应满足的要求是： 1) 压缩—— 任意长， 固定长； 2) 容易从 计算出 。 单向性(one-way)——基本上对所有事先指定的 ，找到 使 在计算上是困难的； 弱抗碰撞(Weak Collision Resistance) ——已知 ，找 使 在计算上是困难的； 5) 强抗碰撞(Strong Collision Resistance)——找任 两个不同的输入 ，使 在计算上 是困难的. 其中1）2）是对哈希函数的基本要求。