—按位与运算 —按位取反 —模264加
" " " " " "
" " —按位异或运算
k>2t-1
• SHA-1: t=160
k 2t 1 2159 7.311047
难以奏效
2、生日攻击（birthday attack）
• 在一个房间中坐了k人，k的数量至少为多 少时，找一个与某特定人生日相同的概率 大于1/2？
183
• K至少为多少时，此房间中至少有两个人 生日相同的概率大于1/2？
• 也称密码校验和 • 功能与HASH函数基本相同
• 可认为是带密钥的Hash函数
• 可以认证以下内容：
接收者可以判断消息是否被篡改。 HASH函数也可 接收者可以判断消息发送者的真假。 HASH函数不可
二、消息认证码（MAC）
2、要求
• 已知输入消息m和Ck(m)，找到另一满足 Ck(m’)=Ck(m)的消息m’在计算上不可行。
HASH函数填充举例
•HASH函数MD4 要求输入为512比特的整数倍长度 •假设输入m是1800比特 1800264 mod 512 •输入填充结果：
512×4=2048
512-264-1-64=183
512
512
512
信息位
512
264 1 183(0串) 64(L)
标 填 志 充 位 0
长 度
• SUM64
• MD
——对应的字进行模264加
——输入消息的消息摘要值
二、轮函数：SHA-512算法核心
• 对缓冲区中8个64比特字和消息字、轮常数进行运 b c d e f g h 算并代换。 a
Ch + + + + T1 +
∑
+ T2 +
Maj
∑
Wt Kt
a
b
c
d
e
f
g
h
轮函数运算过程
T1，T2 — 两个中间变量
山东大学王小云教授成功破解MD系列算法
2004 年 8 月 17 日 的 美 国 加 州 圣 巴 巴 拉 ， 正 在 召 开 的 国 际 密 码 学 会 议 （Crypto’2004）安排了三场关于杂凑函数的特别报告。在国际著名密码学家 Eli Biham和Antoine Joux相继做了对SHA-1的分析与给出SHA-0的一个碰撞之 后，来自山东大学的王小云教授做了破译 MD5 、HAVAL-128 、 MD4 和 RIPEMD 算 法的报告。在会场上，当她公布了MD 系列算法的破解结果之后，报告被激动 的掌声打断。王小云教授的报告轰动了全场，得到了与会专家的赞叹。报告 结束时，与会者长时间热烈鼓掌，部分学者起立鼓掌致敬，这在密码学会议 上是少见的盛况。王小云教授的报告缘何引起如此大的反响？因为她的研究 成果作为密码学领域的重大发现宣告了固若金汤的世界通行密码标准 MD ５的 堡垒轰然倒塌，引发了密码学界的轩然大波。会议总结报告这样写道：“我 们该怎么办？ MD5 被重创了；它即将从应用中淘汰。 SHA-1 仍然活着，但也见 到了它的末日。现在就得开始更换SHA-1了。” 果然，2005年初，王小云教授就宣布，已经成功破解SHA-1。美国《新科 学家》立即发表了《崩溃！密码学的危机》文章，美国的 NIST 也宣布，美国 政府5年内将不再使用SHA-1。
步骤2：初始化消息摘要缓冲区
• 缓冲区用8个64比特的寄存器（a,b,c,d,e,f,g,h） 表示，初始化数值为 a=H0(0)= 6a09e667f3bcc908 b=H0(1)= bb67ae8584caa73b 64比特字取 c=H0(2)= 3c6ef372fe94f82b 自前8个素 d=H0(3)= a54ff53a5f1d36f1 数的平方 e=H0(4)= 510e527fade682d1 根，取小 f=H0(5)= 9b05688c2b3e6c1f 数部分的 g=H0(6)= 1f83d9abfb41bd6b 前 64 比特 h=H0(7)=5be0cd19137e2179
• Ck(m)应均匀分布，即随机选取两个消息m和m’， Ck(m’)=Ck(m)的概率是2-n。 • 若m’是m的某个变换，即m’=f(m)，Ck(m’)=Ck(m) 的概率是2-n。
三、hash类函数的攻击类型
• 直接攻击 • 生日攻击
1、直接攻击
• • • • 对消息的穷举攻击 t比特长度的消息摘要 消息摘要输出有2t个可能 采用穷举搜索法，攻击者要尝试的消息数k 至少要多大，才能找到一个特定的m’，使 h(m’)=h(m) 的概率超过1/2?
g
h
轮函数（第t轮）
Kt
• Wt为消息字
• Kt为轮常数
W79
a
b c
d
e
f
g
h
轮函数（第79轮）
K79
• 轮函数后面介绍
+ + + + + + + +
512bit H
i
步骤3：SHA-512算法的主循环
H i(0) a H i(0) 1
• 每一个消息分组 经处理后的中间 摘要值计算 • 模264加 • Hi(j)为Hi的第j个 64比特
ROTR n ( x )
SHR n ( x )
80个轮常数Kt
取自前 80个素 数的立 方根小 数部分 的前64 比特
步骤4：输出
• 依次对消息m的n个1024比特分组进行处理， 第n个分组处理后的输出值Hn即是消息m的 消息摘要值：
H
(0) n
|| H
(1) n
|| H
(2) n
|| H
(3) n
512
hg g f f e e d T1 d c cb ba a T1 T2

512 1 512 0
(e) [ ROTR14 (e)] [ ROTR18 (e)] [ ROTR 41 (e)] (a ) [ ROTR 28 (a )] [ ROTR 34 (a )] [ ROTR 39 (a )]
T1 h 1 (e) Ch(e, f , g ) K t Wt
512
Ch(e, f , g ) (e f ) (e g ) Maj(a, b, c) (a b) (a c) (b c)
T2 0 (a ) Maj (a, b, c)
第4章
Hash函数与消息认证码
本章内容
• • • • hash函数和MAC概述 安全hash函数算法SHA-512 欧洲hash函数算法Whirlpool MAC算法
第4章
hash函数与消息认证码
教学பைடு நூலகம்求
• • • • 了解hash函数和MAC的基本概念 掌握SHA-512的基本原理 了解Whirlpool算法 了解MAC算法
一、SHA-512的算法原理
128bit
输入消息m
n*1024bit
填充
消息长度
m1
1024bit 1024bit
m2
mn
1024bit
H0
512bit
f
+
H1
f
+
H2
Hn-1
f
+
Hn
512bit
消息摘要值
图6-2 SHA-512的算法结构
一、SHA-512的算法原理
•实现步骤
• 步骤1：添加填充位，并附加消息 长度值（消息预处理） • 步骤2：初始化消息摘要的缓冲区 • 步骤3：以1024比特的消息分组为 单位进行处理 • 步骤4：输出
4.1 概述
一、hash函数
散列函数 杂凑函数 哈希函数
功能
将任意长度文本 变换为很短的固 定长度文本
困难
特点 •单向特性 •雪崩特性 •无陷门 应用
容易
散列值，消息摘要码 数字指纹
•数字签名
•消息认证
hash函数的相关术语
HASH和 消息摘要
密码校验和 压缩编码 消息摘要码 指纹
印章，记号
一、hash函数
H i(1) b H i(1) 1 H
(2) i
cH
(2) i 1
H i(3) d H i(3) 1 H i(4) e H i(4) 1 H i(5) f H i(5) 1 H i(6) g H i(6) 1 H
(7) i
hH
(7) i 1
1、定义
设M是所有可能消息m的集合，Y是由 所有可能的消息摘要码y构成的有限集，则 把从M到Y的映射 h：M→Y 称为一个hash函数。
M是无限集，Y是有限集。
一、hash函数
2、要求
• 基本要求：
有密钥时为MAC
算法公开 有数据压缩 易于计算
一、hash函数
2、要求
• 安全要求：
单向性 弱抗碰撞特性 强抗碰撞特性
1、步骤1：消息的预处理
• 首先在输入消息m的右边添加若干比特，使其长度恰 好为一个比1024的倍数大896的数，即模1024与896 同余。填充比特的第1位是“1”，后续均为“0”； • 然后用128个比特的无符号整数表示原始消息m的长 度（最高有效字节在前），附加在最后； • 经预处理后产生了一个长度为1024整数倍的扩展消 息，将其以1024比特分组划分为n个消息分组 m1,m2,…,mn，其中每个分组mi(i=1,2,…,n)都是 1024比特。
二、消息认证码（MAC）
（message authentication code，MAC）
1、定义
MAC=Ck(m)
• • • • k —— 通信双方共享的密钥 m —— 输入的消息（长度不固定） C —— MAC函数 MAC —— 消息认证码（固定长度）