2010-5-14 1
第七章 消息认证和杂凑算法
Message Authentication and Hash
Algorithms
2010-5-14 2
杂凑函数
Hash Functions
2010-5-14 3
迭代型杂凑函数的一般结构
f f f
Y0 Y1 YL-1
b b b
n n n n n
IV=CV0 CV1 CVL-1
CVL
明文 M被分为 L个分组
Y0,Y1,…,Y L-1
b:明文分组长度
n:输出 hash长度
CV：各级输出，最后
一个输出值是 hash值
无碰撞压缩函
数 f是设计的
关键
2010-5-14 4
MD5杂凑算法
MD5 Hash Algorithm
2010-5-14 5
算法 步骤 (1)－ 分组填充
? Ron Rivest于 1990年提出 MD-4杂凑算法。输
入消息可任意长，压缩后输出为 128bits。
1992年改进为 MD-5。
消息 100…0 64bit
消息长度填充图样
L× 512bit
Kbit
2010-5-14 6
算法 步骤 (2)－ 缓冲初始化
每轮输出为 128 bit,可用 4个 32bits字表示：
A,B,C,D。 初始存数以十六进制表示为
A=01234567，
B=89ABCDEF，
C=FEDCBA98，
D=76543210。
2010-5-14 7
算法步骤 (3) -HMD5运算
? 对 512 bit(16-字 )组进行运算,Yq表示输入
的第 q组 512 bit数据，在各轮中参加运算。
? T[1,…,64]为 64个元素表，分四组参与不同
轮的计算。 T[i]为 232× abs(Sine(i))的整数部
分,i是弧度。 T[i]可用 32 bit二元数表示,T
是 32 bit随机数源。
2010-5-14 8
MDq, 128
Yq
512 A B C D 32
ABCD＂ fF(ABCD,Yq,T[1… 16])
A B C D
ABCD＂ fG(ABCD,Yq,T[17… 32])
A B C D
ABCD＂ fH(ABCD,Yq,T[33… 48])
A B C D
ABCD＂ fI(ABCD,Yq,T[49… 64])
+ + + + +, mod 232
MD-5的一个
MDq+1 128 512-bit组的处理
2010-5-14 9
轮运算
? MD-5是四轮运算，各轮逻辑函数不同。每轮又
要进行 16步迭代运算,4轮共需 64步完成。每步
完成
a ? b＋ CLSS(a＋ g(B,C,D)＋ X[k]＋ T[i])
其中
a,b,c,d=缓存器中的四个字，按特定次序变化。
g=基本逻辑函数 F,G,H,I中之一，算法的每一轮
用其中之一。
2010-5-14 10
A B C D
A B C D
+
+
+
CLSS
+
+
X[k]
T[i]
CLSs:循环左移 s位。
X[k]:第 q-512-bit组
的第 k个 32-bit字。
T[i]：矩阵 T中第 I个
32-bit字。
＋：模 232加法。
2010-5-14 11
基本逻辑函数定义
轮 基本函数 g g(b,c,d)
f F F( b,c,d) ( b?c) V ( b?d)
f G G( b,c,d) ( b?d) V (c? dˉ )
f H H( b,c,d) b ? c ? d
f I I( b,c,d) c ? ( b?dˉ)
2010-5-14 12
MD0=IV（ ABCD缓存器的初始矢量）
MDq+1 =MDq+fI[Yq,fH[Yq,fG[Yq,fF[Yq,MDq]]]]
MD=MDL— 1（最终的杂凑值）。
MD5的数学表达式
2010-5-14 13
MD-5的安全性
? MD-5的输出为 128-bit，若采用纯强力攻
击寻找一个消息具有给定 Hash值的计算困
难性为 2128，用每秒可试验 1 000 000 000
个消息的计算机需时 1.07× 1022年。
? 采用生日攻击法，寻找有相同 Hash值的两
个消息需要试验 264个消息，易受第 II类生
日攻击。
? 差分攻击攻击 MD-5单轮可以在合理的时
间内找到具有相同杂凑值的两个不同的消
息。但未能推广到 4轮
2010-5-14 14
? 可找到一个消息分组和两个相关的连接变量，
使算法产生相同的输出，但还未能成功的推广到
4轮。
? 对单个 512比特长的消息分组已经成功的找出了
碰撞，为推广到在有初值 IV时整个消息运算该算
法。
MD-5的安全性
2010-5-14 15
SHA 算法
Secure Hash Algorithm
2010-5-14 16
算法简介
? 美国 NIST设计
? 1993年成为联邦信息处理标准 (FIPS PUB
180)
? 基于 MD4算法，与之非常类似。
? 输入为小于 264比特长的任意消息
? 分组 512bit长
? 输出 160bit
2010-5-14 17
算法描述
? 消息填充：与 MD5完全相同
? 附加消息长度,64bit长度
? 缓冲区初始化
? A＝ 67452301
? B＝ EFCDAB89
? C＝ 98BADCFB
? D＝ 10325476
? E＝ C3D2E1F0
2010-5-14 18
分组处理
模 232加
2010-5-14 19
SHA的压缩函数
? A,B,C,D,E?(E+ft(B,C,D)+CLS5(A)+Wt+
Kt),A,CLS30(B),C,D)
2010-5-14 20
SHA中基本逻辑函数定义
2010-5-14 21
SHA分组处理所需的 80个字的产生过
程
第七章 消息认证和杂凑算法
Message Authentication and Hash
Algorithms
2010-5-14 2
杂凑函数
Hash Functions
2010-5-14 3
迭代型杂凑函数的一般结构
f f f
Y0 Y1 YL-1
b b b
n n n n n
IV=CV0 CV1 CVL-1
CVL
明文 M被分为 L个分组
Y0,Y1,…,Y L-1
b:明文分组长度
n:输出 hash长度
CV：各级输出，最后
一个输出值是 hash值
无碰撞压缩函
数 f是设计的
关键
2010-5-14 4
MD5杂凑算法
MD5 Hash Algorithm
2010-5-14 5
算法 步骤 (1)－ 分组填充
? Ron Rivest于 1990年提出 MD-4杂凑算法。输
入消息可任意长，压缩后输出为 128bits。
1992年改进为 MD-5。
消息 100…0 64bit
消息长度填充图样
L× 512bit
Kbit
2010-5-14 6
算法 步骤 (2)－ 缓冲初始化
每轮输出为 128 bit,可用 4个 32bits字表示：
A,B,C,D。 初始存数以十六进制表示为
A=01234567，
B=89ABCDEF，
C=FEDCBA98，
D=76543210。
2010-5-14 7
算法步骤 (3) -HMD5运算
? 对 512 bit(16-字 )组进行运算,Yq表示输入
的第 q组 512 bit数据，在各轮中参加运算。
? T[1,…,64]为 64个元素表，分四组参与不同
轮的计算。 T[i]为 232× abs(Sine(i))的整数部
分,i是弧度。 T[i]可用 32 bit二元数表示,T
是 32 bit随机数源。
2010-5-14 8
MDq, 128
Yq
512 A B C D 32
ABCD＂ fF(ABCD,Yq,T[1… 16])
A B C D
ABCD＂ fG(ABCD,Yq,T[17… 32])
A B C D
ABCD＂ fH(ABCD,Yq,T[33… 48])
A B C D
ABCD＂ fI(ABCD,Yq,T[49… 64])
+ + + + +, mod 232
MD-5的一个
MDq+1 128 512-bit组的处理
2010-5-14 9
轮运算
? MD-5是四轮运算，各轮逻辑函数不同。每轮又
要进行 16步迭代运算,4轮共需 64步完成。每步
完成
a ? b＋ CLSS(a＋ g(B,C,D)＋ X[k]＋ T[i])
其中
a,b,c,d=缓存器中的四个字，按特定次序变化。
g=基本逻辑函数 F,G,H,I中之一，算法的每一轮
用其中之一。
2010-5-14 10
A B C D
A B C D
+
+
+
CLSS
+
+
X[k]
T[i]
CLSs:循环左移 s位。
X[k]:第 q-512-bit组
的第 k个 32-bit字。
T[i]：矩阵 T中第 I个
32-bit字。
＋：模 232加法。
2010-5-14 11
基本逻辑函数定义
轮 基本函数 g g(b,c,d)
f F F( b,c,d) ( b?c) V ( b?d)
f G G( b,c,d) ( b?d) V (c? dˉ )
f H H( b,c,d) b ? c ? d
f I I( b,c,d) c ? ( b?dˉ)
2010-5-14 12
MD0=IV（ ABCD缓存器的初始矢量）
MDq+1 =MDq+fI[Yq,fH[Yq,fG[Yq,fF[Yq,MDq]]]]
MD=MDL— 1（最终的杂凑值）。
MD5的数学表达式
2010-5-14 13
MD-5的安全性
? MD-5的输出为 128-bit，若采用纯强力攻
击寻找一个消息具有给定 Hash值的计算困
难性为 2128，用每秒可试验 1 000 000 000
个消息的计算机需时 1.07× 1022年。
? 采用生日攻击法，寻找有相同 Hash值的两
个消息需要试验 264个消息，易受第 II类生
日攻击。
? 差分攻击攻击 MD-5单轮可以在合理的时
间内找到具有相同杂凑值的两个不同的消
息。但未能推广到 4轮
2010-5-14 14
? 可找到一个消息分组和两个相关的连接变量，
使算法产生相同的输出，但还未能成功的推广到
4轮。
? 对单个 512比特长的消息分组已经成功的找出了
碰撞，为推广到在有初值 IV时整个消息运算该算
法。
MD-5的安全性
2010-5-14 15
SHA 算法
Secure Hash Algorithm
2010-5-14 16
算法简介
? 美国 NIST设计
? 1993年成为联邦信息处理标准 (FIPS PUB
180)
? 基于 MD4算法，与之非常类似。
? 输入为小于 264比特长的任意消息
? 分组 512bit长
? 输出 160bit
2010-5-14 17
算法描述
? 消息填充：与 MD5完全相同
? 附加消息长度,64bit长度
? 缓冲区初始化
? A＝ 67452301
? B＝ EFCDAB89
? C＝ 98BADCFB
? D＝ 10325476
? E＝ C3D2E1F0
2010-5-14 18
分组处理
模 232加
2010-5-14 19
SHA的压缩函数
? A,B,C,D,E?(E+ft(B,C,D)+CLS5(A)+Wt+
Kt),A,CLS30(B),C,D)
2010-5-14 20
SHA中基本逻辑函数定义
2010-5-14 21
SHA分组处理所需的 80个字的产生过
程
