现代密码学第6讲：单向函数和散列函数1

《现代密码学》第六讲

HASH函数和MAC(一)

上讲内容回顾

流密码(序列密码)的思想起源 流密码的分类 基于移位寄存器的流密码算法 RC4算法 ESTREAM推荐算法介绍

本章主要内容

单向函数 Hash函数的定义及发展现状 hash函数的用途 MD5算法 SHA-256算法 SHA-512和SHA-384算法 消息鉴别码简介 CBC-MAC算法 HMAC算法

单向函数定义. 函数 f :{0,1}* {0,1}*若满足 下列两个条件，则称之为强单向函数： 1 计算 f ( x) 是容易的，即 f ( x) 是多项 式时间可计算的； f 1 ( x) 是困难的， 即 2 计算 f 函数的逆 对每一多项式时间概率算法 M,每一多 项式 p (n) 和充分大的 n(n n0 ) 有Pr{M ( f (U n )) f 1

( f (U n ))} 1/ p( n)4

单向函数注. 1 可能有少量x给出的f(x)可用多项式时间概 率算法求逆； 2 单向函数的存在性没有理论上的证明，但 是有些函数，经过实践检验，至今没有发 现多项式时间的求逆算法，仍在使用.

例1 伪随机数生成器(种子密钥—密钥流) 例2 因子分解问题(因子—合数)

f ( x, y) x * y, | x | | y |

Hash函数定义

消息是任意有限长度，哈希值是固定长度.

Hash的概念起源于1956年，Dumey用它来解决symbol table question(符号表问题)。使得数This is an input to a cryptographic hash function. The input is a very long string, that is reduced by the hash function to a string of fixed length. There are additional security conditions: it should be very hard to find an input hashing to a given value (a preimage) or to find two colliding inputs (a collision).

据表的插入、删除、查询操作可以在平均常数时间完成。

奇偶校验码新版身份证

h

1A3FD4128A198FB3CA345932

Hash函数的定义

单向性(抗原像):对干任意给定的消息，计算其哈希值

容易. 但是，对于给定的哈希值h,要找到M使得H(M)=h在计算上是不可行的.

弱抗碰撞(抗二次原像):对于给定的消息M1,要发现 另一个消息M2,满足H( M1 )=H(M2)在计算上是不可行 的.

强抗碰撞：找任意一对不同的消息M1,M2 ,使H(M1)=H(M2 )在计算上是不可行的. 随机性.7

Hash函数的定义Hash函数的安全性需求

格子

生日

Hash函数的定义Hash函数的分类

改动检测码MDC (Manipulation Detection Code)不带密钥的哈希函数 主要用于消息完整性

消息认证码 MAC (Message Authentication Code)带密钥的哈希函数 主要用于消息源认证和消息完整性9

Hash函数的用途消息完整性检测 Hash链用于口令认证 数字签名(速度快；防止消息伪造) 消息完整性和消息源认证(MAC) 。。。。。。

Hash函数的用途消息完整性

检测“网站卫士”是一个网络安全软件产品。它的主要功能是 通过网络扫描网站的网页，监测网页是否被修改，当发现 网页被修改后，系统能够自动报警和恢复。

初始化过程 (1)对监视网站的文件备份到监控主机上。 (2)对每个备份的文件生成一个结构：文件位置、文件的哈希值。 监控过程 监控主机对监控网站进行轮回扫描，对扫描的文件进行如下操作： (1)计算文件的哈希值，并与备份的文件哈希值进行比较，如果相 同，转(4)步。 (2)如果不同，上载备份文件替换网站现有文件，转(4)步。 (3)如果备份文件不存在，则删除网站上这个文件，转(4)步。 (4)监控程序扫描下一文件。11

Hash函数的用途消息完整性检测

Hash函数的用途输入终端

口令认证

常见的Unix系统 明文口令 口令以及多数论 坛/社区系统口 令都是经MD5处 理后保存其摘要 信息串；

认证系统

口令哈希值

口令哈希运算

口令哈希值

匹配吗？

不带密钥的哈希函数的发展1978年，Merkle和Damagad设计MD迭代结构 1993年，莱学家和Messay改进为MD加强结构

M1l l

M2

Mkl

message schedule

Step Function

Step Function

fn n

fn

n

fn

M2

Iterate step functionStep Function

IV

H1

H2

Hk

H2

Step Function

H1

不带密钥的哈希函数的发展散列算法MD族是在90年代初由mit laboratory for computer science和 RSA data security inc的Ron Rivest设计的，MD代表消息摘要 (message-digest ). md2、md4和md5都产生一个128位的信息摘要. MD2 1989年开发出md2算法. 在这个算法中，首先对信息进行数据补位， 使信息的字节长度是16的倍数. 然后，以一个16位的检验和追加到信 息末尾。并且根据这个新产生的信息计算出散列值。后来，rogier和 chauvaud发现如果忽略了检验和将产生md2碰撞. MD4 1990年开发出md4算法. Den boer和bosselaers以及其他人很快的发现 了攻击md4版本中第一步和第三步的漏洞. dobbertin向大家演示了如 何利用一部普通的个人电脑在几分钟内找到md4完整版本中的碰撞. MD5 1991年，rivest开发出技术上更为趋近成熟的md5算法. den boer和 bosselaers曾发现md5算法中的伪碰撞(pseudo-collisions),但除此 之外就没有其他被发现的分析结果了. RIPEMD-128/160/320 RIPEMD由欧洲财团开发和设计.15

不带密钥的哈希函数的发展SHA系列算法是NIST 根据Rivest 设计的MD4和MD5开发的算 法. 国家安全当局发布SHA作为美国政府标准. SHA表示安 全散列算法. SHA-0 SHA-0正式地称作SHA,这个版本在发行后不久被指出存 在弱点. SHA-1 SHA-1是NIST于1994年发布的，它与MD4和MD5散列算法 非常相似，被认为是MD4和 MD5的后继者. SHA-2 SHA-2

实际上分为SHA-224、SHA-256、SHA-384和SHA512算法.

不带密钥的哈希函数的发展

HAVAL 1992年Yuliang Zheng 设计了HAVAL函数， 它与许多其他散列函数不同.

Gost Gost是一套苏联标准.17

不带密钥的哈希函数的发展主要hash算法：MD4 MD5 HAVAL SHA-1 SHA-2 Ext. MD4 RIPEMD RIPEMD-160 Tiger Whirlpool

不带密钥的哈希函数的发展

碰撞攻击复杂度19

不带密钥的哈希函数的发展90 Brute force: 1 million PCs or US$ 100 000 hardware 80 70 60 50 40 30 20 10 0

MD4 MD5 SHA-0 SHA-1 Brute force

19 92 19 92 19 94 19 96 19 98 20 00 20 02 20 04 20 06 20 08

碰撞攻击复杂度20

不带密钥的哈希函数的发展

NESSIE工程推荐使用的hash算法有SHA-256/384/512和 Whirlpool; 日本密码研究与评估委员会推荐使用的算法有RIPEMD160、SHA-256/384/512。 ECRYPT也在hash算法研究方面举办了一系列活动。 此外，NIST于2008年启动新的hash标准的征集活动。除迭代结构以外的结构 适用于任何平台的压缩函数

2008年10月提交文档，收到64个算法，公开56个，51个 进入第一轮评估 2009年10月，第二轮评估开始，剩余14个算法 目前剩下5个算法进入第三轮21

本文来源：https://www.bwwdw.com/article/ir31.html