第 11章 杂凑（ hash）函数
11.1 杂凑函数的定义
?定义 11.1 一个函数族 称为强无
碰撞压缩函数族，若下面两个条件成立。
（ 1）计算 hn(x)是容易的，即存在一个多项式时间
算法 F，若 F的输入为 1n和,则其输出为
hn(x) 。
（ 2）给定算法 F要找两个不同的消息,
使得 是困难的，即对每一个多项式时
间概率算法 M’，每一正多项式 p(n)和一切充分大
的 n有 （ 11.1）
其中 Un表示 {0,1}n上的均匀分布随机变量。
? ? ? ?? ?mnh mnn ?? ;1,01,0:
? ?nx 1,0?
)( 2121 xxxx ??
)()( 21 21 xhxh xx ?
? ? )(/1)()1),((P ' npUCUhMr nnnnn ??
?定理 11.1 若一个函数族 为
一强单向函数族，则它也是一个强无碰撞
压缩函数族。反之，若函数族 为一强
无碰撞压缩函数族，且对（充分大的）每
个 n及 x∈ {0,1}n,hn(x)的原象集 中
至少包含两个原象，则它也是一个强单向
函数族。
?强无碰撞压缩函数族中的函数也称无碰撞
压缩函数或单向压缩函数。
? ? ? ?? ?mnh mnn ?? ;1,01,0:
? ?mnhn ?;
))((1 xhh nn?
?定义 11.2 一个强无碰撞杂凑函数是一个满足下列
条件的函数 h。
(1)h可应用于任意长的消息或文件；
(2)h的值（杂凑值）是固定长的，但要足够长才能
抵抗生日攻击。
(3)计算 h的值 h(x)是容易的，即 h(x)是多项式时间可
计算的；
(4)给定算法 h，要找两个不同的消息 x1≠x2，使其杂
凑值 h(x1)=h(x2)是困难的（计算不可行的），即
是由强无碰撞压缩函数族中的压缩函数所构造的
（构造方法见后）。
11.2 无碰撞杂凑函数的构造方法
11.2.1 用单向压缩函数构造无碰撞杂凑函数的一般方法
? 设 为一单向压缩函数，其中 l≥m+2为一选
定的正整数。首先将输入 h的消息 分为长 l-m-1的组，
记作 。若 x的长 |x|不能被 l-m-1整除，则在 xr后面添
加 d个 0使 n=|x|+d被 l-m-1整除。不妨将 x,0d仍记作 x，使
|xr|=l-m-1，再附加一个分组 xr+1，它由 d的二进数表示在其
前面添加若干个 0构成，使 |xr+1|=l-m-1。杂凑函数 h(x)的值
由下面的迭代算法定义。
? 定理 11.2 杂凑函数和用来构造它的单向压缩函数有几乎
同样的安全性。
? ? ? ?mllh 1,01,0,?
? ?*1,0?x
rxxxx ?21?
)0( 111 xhh ml ??
rixhhh iili,,2,1)1( 11 ??? ??
1)( ?? rhxh
11.2.2 用分组加密函数构造杂凑函数
?Rabin方案
?密码组链接方案
?密钥链接方案
11.2.3 用候选单向函数构造杂凑函数
?单向函数输出值链接方案
?单向无爪函数输出值链接方案
b
Y0
n f
b
Y1
n f
b
YL-1
n
CVL-1
f
CV1
n n
IV = 初始值
CV = 链接值
Yi = 第 i 个输入数据块
f = 压缩算法
n = 散列码的长度
b = 输入块的长度
8 安全杂凑算法的一般结构
CVL
CV0=IV= initial n-bit value
CVi=f(CVi-1,Yi-1) (1 ? i ? L)
H(M) = CVL
9 MD5 算法逻辑
?输入：任意长度的消息
?输出,128位消息摘要
?处理：以 512位输入数据块为单位
MD5 (RFC 1321) developed by Ron Rivest
at MIT in 90’s,
报文
K bits
L?512 bits=N ?32bits
报文长度
(K mod 264)
100…0
Y0
512 bits
Y1
512 bits
Yq
512 bits
YL-1
512 bits
HMD5
IV
128 H
MD5 CV
1
128 H
MD5 CV
q
128 H
MD5 CV
L-1
128
512 512 512 512
128-bit
摘要
MD5产生报文摘要的过程
填充
(1 to 512
bits)
11 MD5算法描述
?步骤 1,添加填充位 (一个 1 和若干个 0)。在消息的
最后添加适当的填充位使得数据位的长度满足 length
? 448 mod 512。
?步骤 2,添加长度。原始消息长度（二进制位的个数
），用 64位表示。
表示为 L个 512位的数据块,Y0,Y1,…,YL-1。 其长度为
L?512bits。令 N=L?16,则长度
为 N个 32位的字。令 M[0… N-1]表示以字为单位的消息表
示。
12 MD5算法描述 (Cont.)
?步骤 3：初始化 MD缓冲区。一个 128位 MD缓冲区
用以保存中间和最终散列函数的结果。它可以表
示为 4个 32位的寄存器 (A,B,C,D)。
寄存器初始化为以下的 16进制值。
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
13
Word A,01 23 45 67
Word B,89 AB CD EF
Word C,FE DC BA 98
Word D,76 54 32 10
14 MD5算法描述 (Cont.)
?步骤 4：处理消息块（ 512位 = 16个 32位
字）。一个压缩函数是本算法的核心 (HMD5)。
它包括 4轮处理。四轮处理具有相似的结构,
但每次使用不同的基本逻辑函数，记为
F,G,H,I。每一轮以当前的 512位数据块 (Yq)
和 128位缓冲值 ABCD作为输入，并修改缓
冲值的内容。每次使用 64元素表 T[1…64]
中的四分之一
?T表，由 sin 函数构造而成。 T的第 i个元素表示
为 T[i]，其值等于 232?abs(sin(i)),其中 i是弧度。
由于 abs(sin(i))是一个 0到 1之间的数,T的每
一个元素是一个可以表示成 32位的整数。 T表
提供了随机化的 32位模板,消除了在输入数据
中的任何规律性的特征
15 T 表
T[49] = F4292244
T[50] = 432AFF97
T[51] = AB9423A7
T[52] = FC93A039
．．,
T[64] = EB86D391
T[1] = D76AA478
T[2] = E8C7B756
T[3] = 242070DB
T[4] = C1BDCEEE
．．,
T[16] = 49b40821
16 MD5算法描述 (Cont.)
? 步骤 5：输出结果。所有 L个 512位数据块处理完毕后，最后的结果
就是 128位消息摘要。
CV0 = IV
CVq+1 = SUM32(CVq,RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]])
MD = CVL
其中,IV = ABCD的初始值（见步骤 3）
Yq = 消息的第 q个 512位数据块
L = 消息中数据块数；
CVq = 链接变量，用于第 q个数据块的处理
RFx = 使用基本逻辑函数 x的一轮功能函数。
MD = 最终消息摘要结果
SUM32=分别按 32位字计算的模 232加法结果。
F,T[1…16],X[i]
16 steps
G,T[17…32],X[ ?2i]
16 steps
H,T[33…48],X[ ?3i]
16 steps
I,T[49…64],X[ ?4i]
16 steps
+ + + +
A B C D
A B C D
A B C D
A B C D
CVq 128
32
Yq
512
CVq+1 128
+ is mod 232
单个 512-bit 分组的
MD5 处理过程
17 MD5 压缩函数
每一轮包含对缓冲区 ABCD的 16步操作所组成的一个序列。
a?b + (( a + g(b,c,d) + X[k] +T[i])<<<s)
其中,
a,b,c,d = 缓冲区的四个字，以一个给定的次序排列 ;
g = 基本逻辑函数 F,G,H,I之一；
<<<s = 对 32位字循环左移 s位
X[k] = M[q?16 + k] = 在第 q个 512位数据块中的第 k个 32
位字
T[i] = 表 T中的第 i个 32位字；
+ = 模 232的加；
A B C D
A B C D
+
+
+
CLSs
+
g
X[k]
T[i]
?2i = (1+5i) mod 16
?3i = (5+3i) mod 16
?2i = 7i mod 16
基本 MD5操作 (单步 )
Function g g(b,c,d)
1 F(b,c,d) (b?c)?(b?d)
2 G(b,c,d) (b?d)?(c?d)
3 H(b,c,d) b?c?d
4 I(b,c,d) c?(b?d)
19 MD4 (1990年 10月作为 RFC1320发表 )
by Ron Rivest at MIT
? MD4的设计目标
? 安全性,
? 速度,32位体系结构下计算速度快,
? 简明与紧凑：易于编程,
? 有利的小数在前的结构 (Intel 80xxx,Pentium )
? MD4与 MD5的区别
? MD4用 3轮,每轮 16 步,MD5用 4轮,每轮 16步,
? MD4中第一轮没有常量加； MD5中 64步每一步用了一个
不同的常量 T[i]；
? MD5用了四个基本逻辑函数，每轮一个； MD4用了三个,
? MD5每轮加上前一步的结果； MD4没有,
11.2.5 安全 Hash标准（ SHS）
是 MD4的变形, SHS中使用的几点改变,
?SHS的设计是以 big-endian结构为基础的。
?SHS可将任意长的消息杂凑到 160比特长的
消息摘要。
?SHS与 MD4一样每次处理 16个 32比特数组，
可是与 MD4不同,SHS首先将输入的 16个
数组扩展为 80个数组，然后再对这 80个数
组执行四轮计算。
11.3 杂凑函数的攻击方法与安全性
?生日攻击 (基于生日悖论 )
在 k个人中,找一个与某人生日相同的人的
概率超过 0.5时,只需 k>183; 而在此人群中,
至少有两个人生日相同的概率超过 0.5,只需
k>23,
11.3.2 特殊攻击
? 中间相遇攻击
攻击者可随意选出若干消息分组，将它们分为两部分。第一部分消
息分组从初值开始进行迭代，到中间某一步为止，得到 J1个输出。
第二部分消息分组从杂凑值 h(x)开始用逆函数反向迭代，到中间某
一步为止，得到 J2个输出。然后比较这两部分输出，若能找到一对
输出值相等，则可得到一对碰撞消息。
? 修正分组攻击
这种攻击方法是用伪造消息与一个分组连接，目的是要修正杂凑值
使它等于所期望的值。修正分组攻击通常用于最后一个分组，故也
称修正最后分组攻击。基于模算术的杂凑函数对修正最后分组攻击 特别敏感。如基于 RSA函数和离散对数的单向函数输出值链接方案
就属于这一类杂凑函数。
? 差分攻击
差分分析是攻击分组密码的一种方法。在第八章 8.5.1节中已作了详
细介绍。它可以用来攻击基于分组加密函数构造的杂凑函数，也可 以用于攻击另外一些特殊的杂凑函数，如 MD5,Snefru等软件杂凑
函数。
11,4 时戳
?签名者 B自己可产生一个可信的时戳。 B可首先收
集若干目前公开可获得消息，这些消息在它们发
生之前是不可预测的。例如，这些消息可由北京
前一天所有主要股票的交易额构成，将这些消息
记作 pub。
? 现在若 B想时戳他对消息 x的签名。设 h为一公开
的杂凑函数。 B可采用下面的方法,
(1)B计算 z=h(x);
(2)B计算 z’=h(z pub),z pub表示 z和 pub的连接；
(3)B计算 y=Sigk(z’)( z’的签名 )；
(4)B在第二天的报纸上公布（ z,pub,y）。
小结
?杂凑（ Hash）函数的定义,构造方法和攻击
方法。
?无碰撞压缩函数族的定义，在很轻微的条
件下，单向函数族与无碰撞压缩函数族是
等价的。
?用压缩函数构造安全性相同的 Hash函数
11.1 杂凑函数的定义
?定义 11.1 一个函数族 称为强无
碰撞压缩函数族，若下面两个条件成立。
（ 1）计算 hn(x)是容易的，即存在一个多项式时间
算法 F，若 F的输入为 1n和,则其输出为
hn(x) 。
（ 2）给定算法 F要找两个不同的消息,
使得 是困难的，即对每一个多项式时
间概率算法 M’，每一正多项式 p(n)和一切充分大
的 n有 （ 11.1）
其中 Un表示 {0,1}n上的均匀分布随机变量。
? ? ? ?? ?mnh mnn ?? ;1,01,0:
? ?nx 1,0?
)( 2121 xxxx ??
)()( 21 21 xhxh xx ?
? ? )(/1)()1),((P ' npUCUhMr nnnnn ??
?定理 11.1 若一个函数族 为
一强单向函数族，则它也是一个强无碰撞
压缩函数族。反之，若函数族 为一强
无碰撞压缩函数族，且对（充分大的）每
个 n及 x∈ {0,1}n,hn(x)的原象集 中
至少包含两个原象，则它也是一个强单向
函数族。
?强无碰撞压缩函数族中的函数也称无碰撞
压缩函数或单向压缩函数。
? ? ? ?? ?mnh mnn ?? ;1,01,0:
? ?mnhn ?;
))((1 xhh nn?
?定义 11.2 一个强无碰撞杂凑函数是一个满足下列
条件的函数 h。
(1)h可应用于任意长的消息或文件；
(2)h的值（杂凑值）是固定长的，但要足够长才能
抵抗生日攻击。
(3)计算 h的值 h(x)是容易的，即 h(x)是多项式时间可
计算的；
(4)给定算法 h，要找两个不同的消息 x1≠x2，使其杂
凑值 h(x1)=h(x2)是困难的（计算不可行的），即
是由强无碰撞压缩函数族中的压缩函数所构造的
（构造方法见后）。
11.2 无碰撞杂凑函数的构造方法
11.2.1 用单向压缩函数构造无碰撞杂凑函数的一般方法
? 设 为一单向压缩函数，其中 l≥m+2为一选
定的正整数。首先将输入 h的消息 分为长 l-m-1的组，
记作 。若 x的长 |x|不能被 l-m-1整除，则在 xr后面添
加 d个 0使 n=|x|+d被 l-m-1整除。不妨将 x,0d仍记作 x，使
|xr|=l-m-1，再附加一个分组 xr+1，它由 d的二进数表示在其
前面添加若干个 0构成，使 |xr+1|=l-m-1。杂凑函数 h(x)的值
由下面的迭代算法定义。
? 定理 11.2 杂凑函数和用来构造它的单向压缩函数有几乎
同样的安全性。
? ? ? ?mllh 1,01,0,?
? ?*1,0?x
rxxxx ?21?
)0( 111 xhh ml ??
rixhhh iili,,2,1)1( 11 ??? ??
1)( ?? rhxh
11.2.2 用分组加密函数构造杂凑函数
?Rabin方案
?密码组链接方案
?密钥链接方案
11.2.3 用候选单向函数构造杂凑函数
?单向函数输出值链接方案
?单向无爪函数输出值链接方案
b
Y0
n f
b
Y1
n f
b
YL-1
n
CVL-1
f
CV1
n n
IV = 初始值
CV = 链接值
Yi = 第 i 个输入数据块
f = 压缩算法
n = 散列码的长度
b = 输入块的长度
8 安全杂凑算法的一般结构
CVL
CV0=IV= initial n-bit value
CVi=f(CVi-1,Yi-1) (1 ? i ? L)
H(M) = CVL
9 MD5 算法逻辑
?输入：任意长度的消息
?输出,128位消息摘要
?处理：以 512位输入数据块为单位
MD5 (RFC 1321) developed by Ron Rivest
at MIT in 90’s,
报文
K bits
L?512 bits=N ?32bits
报文长度
(K mod 264)
100…0
Y0
512 bits
Y1
512 bits
Yq
512 bits
YL-1
512 bits
HMD5
IV
128 H
MD5 CV
1
128 H
MD5 CV
q
128 H
MD5 CV
L-1
128
512 512 512 512
128-bit
摘要
MD5产生报文摘要的过程
填充
(1 to 512
bits)
11 MD5算法描述
?步骤 1,添加填充位 (一个 1 和若干个 0)。在消息的
最后添加适当的填充位使得数据位的长度满足 length
? 448 mod 512。
?步骤 2,添加长度。原始消息长度（二进制位的个数
），用 64位表示。
表示为 L个 512位的数据块,Y0,Y1,…,YL-1。 其长度为
L?512bits。令 N=L?16,则长度
为 N个 32位的字。令 M[0… N-1]表示以字为单位的消息表
示。
12 MD5算法描述 (Cont.)
?步骤 3：初始化 MD缓冲区。一个 128位 MD缓冲区
用以保存中间和最终散列函数的结果。它可以表
示为 4个 32位的寄存器 (A,B,C,D)。
寄存器初始化为以下的 16进制值。
A = 67452301
B = EFCDAB89
C = 98BADCFE
D = 10325476
13
Word A,01 23 45 67
Word B,89 AB CD EF
Word C,FE DC BA 98
Word D,76 54 32 10
14 MD5算法描述 (Cont.)
?步骤 4：处理消息块（ 512位 = 16个 32位
字）。一个压缩函数是本算法的核心 (HMD5)。
它包括 4轮处理。四轮处理具有相似的结构,
但每次使用不同的基本逻辑函数，记为
F,G,H,I。每一轮以当前的 512位数据块 (Yq)
和 128位缓冲值 ABCD作为输入，并修改缓
冲值的内容。每次使用 64元素表 T[1…64]
中的四分之一
?T表，由 sin 函数构造而成。 T的第 i个元素表示
为 T[i]，其值等于 232?abs(sin(i)),其中 i是弧度。
由于 abs(sin(i))是一个 0到 1之间的数,T的每
一个元素是一个可以表示成 32位的整数。 T表
提供了随机化的 32位模板,消除了在输入数据
中的任何规律性的特征
15 T 表
T[49] = F4292244
T[50] = 432AFF97
T[51] = AB9423A7
T[52] = FC93A039
．．,
T[64] = EB86D391
T[1] = D76AA478
T[2] = E8C7B756
T[3] = 242070DB
T[4] = C1BDCEEE
．．,
T[16] = 49b40821
16 MD5算法描述 (Cont.)
? 步骤 5：输出结果。所有 L个 512位数据块处理完毕后，最后的结果
就是 128位消息摘要。
CV0 = IV
CVq+1 = SUM32(CVq,RFI[Yq,RFH[Yq,RFG[Yq,RFF[Yq,CVq]]]])
MD = CVL
其中,IV = ABCD的初始值（见步骤 3）
Yq = 消息的第 q个 512位数据块
L = 消息中数据块数；
CVq = 链接变量，用于第 q个数据块的处理
RFx = 使用基本逻辑函数 x的一轮功能函数。
MD = 最终消息摘要结果
SUM32=分别按 32位字计算的模 232加法结果。
F,T[1…16],X[i]
16 steps
G,T[17…32],X[ ?2i]
16 steps
H,T[33…48],X[ ?3i]
16 steps
I,T[49…64],X[ ?4i]
16 steps
+ + + +
A B C D
A B C D
A B C D
A B C D
CVq 128
32
Yq
512
CVq+1 128
+ is mod 232
单个 512-bit 分组的
MD5 处理过程
17 MD5 压缩函数
每一轮包含对缓冲区 ABCD的 16步操作所组成的一个序列。
a?b + (( a + g(b,c,d) + X[k] +T[i])<<<s)
其中,
a,b,c,d = 缓冲区的四个字，以一个给定的次序排列 ;
g = 基本逻辑函数 F,G,H,I之一；
<<<s = 对 32位字循环左移 s位
X[k] = M[q?16 + k] = 在第 q个 512位数据块中的第 k个 32
位字
T[i] = 表 T中的第 i个 32位字；
+ = 模 232的加；
A B C D
A B C D
+
+
+
CLSs
+
g
X[k]
T[i]
?2i = (1+5i) mod 16
?3i = (5+3i) mod 16
?2i = 7i mod 16
基本 MD5操作 (单步 )
Function g g(b,c,d)
1 F(b,c,d) (b?c)?(b?d)
2 G(b,c,d) (b?d)?(c?d)
3 H(b,c,d) b?c?d
4 I(b,c,d) c?(b?d)
19 MD4 (1990年 10月作为 RFC1320发表 )
by Ron Rivest at MIT
? MD4的设计目标
? 安全性,
? 速度,32位体系结构下计算速度快,
? 简明与紧凑：易于编程,
? 有利的小数在前的结构 (Intel 80xxx,Pentium )
? MD4与 MD5的区别
? MD4用 3轮,每轮 16 步,MD5用 4轮,每轮 16步,
? MD4中第一轮没有常量加； MD5中 64步每一步用了一个
不同的常量 T[i]；
? MD5用了四个基本逻辑函数，每轮一个； MD4用了三个,
? MD5每轮加上前一步的结果； MD4没有,
11.2.5 安全 Hash标准（ SHS）
是 MD4的变形, SHS中使用的几点改变,
?SHS的设计是以 big-endian结构为基础的。
?SHS可将任意长的消息杂凑到 160比特长的
消息摘要。
?SHS与 MD4一样每次处理 16个 32比特数组，
可是与 MD4不同,SHS首先将输入的 16个
数组扩展为 80个数组，然后再对这 80个数
组执行四轮计算。
11.3 杂凑函数的攻击方法与安全性
?生日攻击 (基于生日悖论 )
在 k个人中,找一个与某人生日相同的人的
概率超过 0.5时,只需 k>183; 而在此人群中,
至少有两个人生日相同的概率超过 0.5,只需
k>23,
11.3.2 特殊攻击
? 中间相遇攻击
攻击者可随意选出若干消息分组，将它们分为两部分。第一部分消
息分组从初值开始进行迭代，到中间某一步为止，得到 J1个输出。
第二部分消息分组从杂凑值 h(x)开始用逆函数反向迭代，到中间某
一步为止，得到 J2个输出。然后比较这两部分输出，若能找到一对
输出值相等，则可得到一对碰撞消息。
? 修正分组攻击
这种攻击方法是用伪造消息与一个分组连接，目的是要修正杂凑值
使它等于所期望的值。修正分组攻击通常用于最后一个分组，故也
称修正最后分组攻击。基于模算术的杂凑函数对修正最后分组攻击 特别敏感。如基于 RSA函数和离散对数的单向函数输出值链接方案
就属于这一类杂凑函数。
? 差分攻击
差分分析是攻击分组密码的一种方法。在第八章 8.5.1节中已作了详
细介绍。它可以用来攻击基于分组加密函数构造的杂凑函数，也可 以用于攻击另外一些特殊的杂凑函数，如 MD5,Snefru等软件杂凑
函数。
11,4 时戳
?签名者 B自己可产生一个可信的时戳。 B可首先收
集若干目前公开可获得消息，这些消息在它们发
生之前是不可预测的。例如，这些消息可由北京
前一天所有主要股票的交易额构成，将这些消息
记作 pub。
? 现在若 B想时戳他对消息 x的签名。设 h为一公开
的杂凑函数。 B可采用下面的方法,
(1)B计算 z=h(x);
(2)B计算 z’=h(z pub),z pub表示 z和 pub的连接；
(3)B计算 y=Sigk(z’)( z’的签名 )；
(4)B在第二天的报纸上公布（ z,pub,y）。
小结
?杂凑（ Hash）函数的定义,构造方法和攻击
方法。
?无碰撞压缩函数族的定义，在很轻微的条
件下，单向函数族与无碰撞压缩函数族是
等价的。
?用压缩函数构造安全性相同的 Hash函数
