2012-3-19 1
第五章 Hash函数与消息认证
一,Hash函数概述
二,Hash函数 MD5
三、安全 Hash算法 SHA
四,基于分组密码与离散对数的 Hash函数
五、消息认证
2012-3-19 2
一,Hash函数概述
2012-3-19 3
Hash函数
? 单向函数
函数 f(x):A→ B若满足下面两个条件, 则
称为单向函数
– 对于任意 x*∈ A计算 y=f(x)是容易的,
其中 y ∈ B。
– 对于 x∈ A,求 y∈ B 使满足 y=f(x)是计
算上不可能的 。
2012-3-19 4
Hash函数
Hash函数
? 设 H：将 A*映射到 An,H满足,
– H是单向函数。
– 已知 x,找 x*∈ A*,使 H (x)= H (x*)在计
算上是不可能的。
– 找一对 x 和 x*, x ≠ x*,使 H (x)= H (x*)
在计算上也是不可能的。
H称为安全的 Hash函数。
2012-3-19 5
Hash函数
Hash函数的分类
根据安全水平,
? 弱无碰撞：散列函数 H称为是弱无碰撞
的，是指对给定消息,在计算上几乎
找不到异于 x的 x*使 H (x)= H (x*) 。
? 强无碰撞：散列函数 H被称为是强无碰
撞的,是指在计算上几乎不可能找到相
异的 x, x* 使得 H (x)= H (x*) 。
2012-3-19 6
Hash函数
Hash函数的分类
? 根据是否使用密钥
– 带秘密密钥的 Hash函数,消息的散列值由
只有通信双方知道的秘密密钥 K来控制
。此时 Hash值称作 MAC。
– 不带秘密密钥的 Hash函数：消息的散列
值的产生无需使用密钥。此时 Hash值称
作 MDC。
2012-3-19 7
Hash函数
Hash函数的用途
? 消息的完整性检测
? 数字签名
2012-3-19 8
Hash函数
h h
发送者对 h(x)
进行加密
接收者对 y
进行解密
不安全信道
不安全信道
x
x
y
x
y
h(x)
h(x)
h(x)
相等？
2012-3-19 9
Hash函数
使用 Hash函数进行数字签名的好处
? 提高数字签名的速度。
? 无需泄露签名所对应的消息，可将签名
泄露，如对消息 x的签名是 Sig(x)，其
z=H(x)可将 (z,y)公开，而保密 x。
? 可将签名变换和加密变换分开，可以在
OSI的不同层提供消息的完整性和机密
性 。
2012-3-19 10
Hash函数
Hash函数的安全性,Hash函数的安全性取
决于其抗击各种攻击的能力，对手的目标是
找到两个不同消息映射为同一杂 Hash值。一
般假定对手知道 Hash算法，采用选择明文攻
击法。
2012-3-19 11
Hash函数
对 Hash函数的基本攻击方法
? 穷举攻击法：给定 H=H(H0,M),其中 H0为
初值, 攻击者在所有可能的 M中寻求有利于
攻击者的 M’,使 H(H0,M’)=H(H0,M),由于
限定了目标 H(H0,M)来寻找 H(H0,M’),这种
攻击法称为目标攻击 。 若对算法的初值 H0不
限定, 使其 H(H0,M)等于 H(H0,M’),则称这
种攻击法为自由起始目标攻击 。
2012-3-19 12
Hash函数
对 Hash函数的基本攻击方法
? 生日攻击：这种攻击法不涉及 Hash算法的
结构, 可用于攻击任何 Hash算法 。 强无碰撞
函数正是基于生日悖论一类的攻击法定义的
。 穷举和生日攻击都属选择明文攻击 。 生日
攻击给定初值 H0 寻找 M?M’,
使 H(H0,M’)=H(H0,M),也可对初始值 H0不
加限制, 即 寻 找 H0’,M’ 使满足 h(H0’,
M’)=h(H0,M)。
2012-3-19 13
Hash函数
生日悖论
在一个会场参加会议的人中，找一个与某人
生日相同的概率超过 0.5时，所需参会人员为
183人。但要问使参会人员中至少有两个同日
生的概率超过 0.5的参会人数仅为 23人。这是
因为，对于与某个已知生日的人同日生的概
率为 1/365，若房中有 t人，则至少找到一人与
此人同日生的概率为。易于解出当 t?183时可
使 p>0.5。
2012-3-19 14
Hash函数
Hash函数的迭代构造
将不限定长度的输入数据压缩成定长输出的
Hash值过程,
– 将输入数字串划分成固定长的段如 m比特段
– 将此 m比特映射成 n比特, 称完成此映射的
函数为迭代函数 。
– 对一段 m比特输入做类似映射, 以此类推,
直到全部输入数字串完全做完, 以最后的输
出值作为整个输入的 Hash值 。
2012-3-19 15
Hash函数
将 m bit到 n bit的分组映射或迭代函数的三
种选择
? m>n。 有数据压缩, 例如,MD4,MD5
SHA等算法 。 是不可逆映射 。
? m=n。 无数据压缩, 亦无数据扩展, 通
常分组密码采用这类 。
? m<n。 有数据扩展的映射 。 认证码属
于此类 。
2012-3-19 16
Hash函数
? 迭代函数以 E表示, 一般 E又都是通过
基本轮函数的多轮迭代实现的, 因此,
轮函数的设计是 Hash函数设计的核心 。
? 迭代 Hash函数的构造方法
– 安全迭代函数 E
– 消息 M划分成组 M1,M2,…,Mi,…,Mt
– 选定密钥为 K,
– H0为初始向量 IV,
2012-3-19 17
Hash函数
? Rabin法,
H0=IV； Hi=E(Mi,Hi-1) i=1,…,t ；
H(M)=Ht 。
? 密码分组链接 (CBC)法,
H0=IV； Hi=E(K,Mi ?Hi-1) i=1,2,…,t ；
H(M)=Ht 。
? 密码反馈 (CFB)法,
Hi=E(K,Hi-1?Mi),i=1,2,…,t； H(M)=Ht
2012-3-19 18
Hash函数
? 组合明 /密文链接法,
Mt+1=IV； Hi=E(K,Mi?Mi-1?Hi-1)
i=1,2,…,t ； H(M)=Ht+1。
? 修正 Daveis-Meyer法,
H0=IV； Hi=E(Hi-1,Mi,Hi-1) (Hi和 Mi共
同作为密钥 )
2012-3-19 19
Hash函数
B,Preneel总结的下述 12种基本方式构造
的分组迭代 Hash函数。令 E是迭代函数，
它可以是一种分组加密算法,E(K,X),K
是密钥,X是输入数据组或某种压缩算法
。令消息分组为 M1,…,M i,…,H 0=I为初始
值。
– Hi=E(Mi,Hi-1)?Hi-1
– Hi=E(Hi-1,Mi)?Mi?Hi-1
– Hi=E(Hi-1,Mi?Hi-1)?Mi
2012-3-19 20
Hash函数
– Hi=E(Hi-1,Mi?Hi-1)?Mi?Hi-1
– Hi=E(Hi-1,Mi)?Mi
– Hi=E(Mi,Mi?Hi-1)?Mi?Hi-1
– Hi=E(Mi,Hi-1)?Mi?Hi-1
– Hi=E(Mi,Mi?Hi-1)?Hi-1
– Hi=E(Mi?Hi-1,Mi)?Mi
– Hi=E(Mi?Hi-1,Hi-1,)?Hi-1 [Brown等 1990]
– Hi=E(Mi?Hi-1,Mi)?Hi-1
– Hi=E(Mi?Hi-1,Hi-1)?Mi
2012-3-19 21
二,Hash函数 MD5
2012-3-19 22
Hash函数 MD5
设计目标,
MD5是 R.Rivest在 MIT开发研究的 Hash函数
– 输入：任意长度的消息
– 输出,128位消息摘要
– 处理：以 512位输入数据块为单位
2012-3-19 23
Hash函数 MD5
MD5算法
? 对明文输入按 512bit分组，最后要填充使
其成为 512 bit的整数倍，且最后一组的后
64 bit用来表示消息长在 mod 264下的值 K
,故填充位数为 1～ 512 bit,填充数字图
样为 (100…0),得 Y0,Y1,…, YL-1。 其中，
Yl为 512 bit,即 16个长为 32 bit的字，按字
计消息长为 N=L× 16。
。
2012-3-19 24
Hash函数 MD5
MD5算法
? 每轮输出为 128 bit,可用下述 4个 32 bits字表
示,A,B,C,D。 其初始存数以十六制表
示为,
A=01234567 B=89ABCDEF C=FEDCBA98
D=76543210。
2012-3-19 25
Hash函数 MD5
MD5算法
? 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随机数源。
2012-3-19 26
Hash函数 MD5
MD5是四轮运算，各轮逻辑函数不同。每轮
又要进行 16步迭代运算,4轮共需 64步完成。
每步完成
a ? b＋ CLSS (a＋ g(B,C,D)＋ X[k]＋ T[i])
其中 a,b,c,d=缓存器中的四个字，按特定次序
变化。 g=基本逻辑函数 F,G,H,I中之一，算
法的每一轮用其中之一。
2012-3-19 27
ABCD＂ fI(ABCD,Yq,T[49…64])
+ + + +
ABCD＂ fF(ABCD,Yq,T[1…16])
ABCD＂ fH(ABCD,Yq,T[33…48])
ABCD＂ fH(ABCD,Yq,T[33…48])
MDq,128
A B C D
A B C D
A B C D
A B C D
Yq
512
MDq+1,128
2012-3-19 28
+
g
a b c d
+
+
+
CLSS
X [k]
T [i]
2012-3-19 29
Hash函数
– CLSs,32-bit 存数循环左移 s位 。
– X[k]=M[q× 16＋ k]：消息的第 q-512-bit组
的第 k个 32-bit字
– T[i],232× abs(sin(i))的整数部分 。
– ＋：模 232加法 。
T[i]由 sin 函数构造。每个输入的 32 bit字被
采用 4次，每轮用一次，而 T[i]中每个元素
恰只用一次。每一次,ABCD中只有 4个字
节更新，共更新 16次，在最后第 17次产生
此组的最后输出。
2012-3-19 30
Hash函数
轮 基本函数 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ˉ)
表 -1各轮的逻辑函数
2012-3-19 31
Hash函数
表 -2 逻辑函数的真值表
b c d F G H I
0 0 0 0 0 0 1
0 0 1 1 0 1 0
0 1 0 0 1 1 0
0 1 1 1 0 0 1
1 0 0 0 0 1 1
1 0 1 0 1 0 1
1 1 0 1 1 0 0
1 1 1 1 1 1 0
2012-3-19 32
Hash函数
MD0=IV（ ABCD缓存器的初始矢量）
MDq+1 =MDq+fI[Yq,fH[Yq,fG[Yq,fF[Yq,MDq]]]]
MD=MDL— 1（ 最终输出值）。
2012-3-19 33
Hash函数
MD5的安全性,
求具有相同 Hash值的两个消息在计算上是
不可行的。 MD-5的输出为 128-bit,若采用
纯强力攻击寻找一个消息具有给定 Hash值
的计算困难性为 2128。若采用生日攻击法，
寻找有相同 Hash值的两个消息需要试验 264
个消息。差分攻击对 MD5的安全性不构成
威胁。
2012-3-19 34
Hash函数
MD5的安全性,
对单轮 MD5已有攻击结果。与 Snefru比
较，两者均为 32 bits字运算。 Snefru采用
S-BOX,XOR函数,MD5用 mod 232加。
最近山东大学的王小云教授利用用差分分
析的方法研究 MD5，得到了比较好的算
法使 MD5能够产生碰撞。因此 MD5的安
全性还需要进一步提高。
2012-3-19 35
三、安全 Hash算法 SHA
2012-3-19 36
安全 Hash算法 SHA
SHA是美国 NIST和 NSA设计的一种标准
算法 SHA (Secure Hash Algorithm),用于
数字签字标准算法 DSS (Digital Signature
Standard),亦可用于其它需要用 Hash算
法的情况 。 SHA具有较高的安全性。
– 输入消息长度小于 264 bit
– 输出压缩值为 160 bit
2012-3-19 37
安全 Hash算法 SHA
SHA的描述
? 输入长度少于 264比特，输出 160比特。输入
分成 512比特块。
? 附加信息位使长度 mod512与 448同余。
? 一组 64比特附在后面，看作是 64比特的整
数，包含原来未加附加位的信息长度。
2012-3-19 38
安全 Hash算法 SHA
SHA的描述
? MD缓冲器初始化。缓冲区分为５个寄存器
(A,B,C,D,E)，每个 32比特，初始值分别为,
A=67 45 32 10 B=EF CD AB 89
C=98 BA DC FE D=10 32 54 76
E=C3 D2 E1 F0
2012-3-19 39
安全 Hash算法 SHA
对 512比特组的信息的处理,
算法的核心是４轮操作，每轮 20步，每
轮的结构类似但是逻辑函数不同，分别为
f1,f2,f3,f4 每轮输入 512比特，输出 160比
特。
2012-3-19 40
安全 Hash算法 SHA
对 512比特组的信息的处理,
ABCDE,每轮用的常数 Kt,,0≤t≤79,其实只有
4个不同的常数
5A827999 0 ≤t≤19
6ED9EBA1 20≤t≤39
Kt＝ 8F1BDBDC 40≤t≤59
CA62C1D6 60≤t≤79
? 当 L组运算结束后，由第 L步的输出 160比
特作 H(m)。
2012-3-19 41
＋ ＋ ＋ ＋ ＋
P1,K,W[0…19]
P2,K,W[20…39]
P3,K,W[40…59]
P4,K,W[60…79]
512 160 32
A C D B E
A C D B E
A C D B E
A C D B E
160
2012-3-19 42
安全 Hash算法 SHA
SHA每一步是如下计算的,
(A,B,C,D,E) ←
((E+f (t,B,C,D))+S5(A)+Wt),A,S30(B),C,D)
– t为步数,
– f (t,B,C,D)为第 t步的逻辑函数。
– Sk为左旋转移位 k位。
– Wt为由 512比特的输入组导出 32比特的第 t块。
– Kt为附加的常数。
– +为 mod 232的加法。
2012-3-19 43
A E D C B
A E D C B
f
S5
S30 +
+
+
+
Wt
Kt
2012-3-19 44
安全 Hash算法 SHA
每个函数的输入为 32比特，输出是一个 32比
特字，有一系列逻辑运算而得到的。输出的
第 n位为 BCD3输入第 n位的函数。
(B∧ C) ∨ ( B∧ D) 0 ≤t≤19
B ? C ? D 20≤t≤39
f(t,B,C,D)=(B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D)
40≤t≤59
B ? C ? D 60≤t≤79
?
2012-3-19 45
安全 Hash算法 SHA
SHA 与 MD5的比较
? 最主要不同点,SHA比 MD5长了 32比特，如果
采用强行攻击,SHA显然比 MD5抗攻击能力
强。
? MD5已有了密码分析的攻击方法，顾较脆弱。
? MD5效率比 SHA高。
? 两者都比较容易实现。
? R.L.Rivest公开了 MD-5的设计决策，但 SHA的
设计者则不愿公开。
2012-3-19 46
四、基于分组密码与离散对数的
Hash函数
2012-3-19 47
基于分组密码的 Hash函数
利用 DES构造 Hash函数
我们将介绍利用 DES构造 Hash函数的若干
模式，实际上也是利用和 DES类似的明文
、密文长度和密钥长度一样的分组密码来
构造 Hash函数的模式。
设 m=m1m2…m l,m=m1m2…m l 都是 64比特的
明文块,k是密钥，也是 64比特。
2012-3-19 48
基于分组密码的 Hash函数
? 第 1种构造模式
– S1,i←1,K ← k;
– S2,K ← DES k( mi ),i ← i+1;
– S3:若 i ≤ l,则转 S2,否则作 H k( m ) ← K
k DES DES DES
m1 m2 ml
… Hk ( m )
2012-3-19 49
基于分组密码的 Hash函数
? 第 2种构造模式
– S1,i←1,S ← S 0;
– S2,mi ← m i ? S,S← DES k( mi ),
– S3:若 i ≤ l;则转 S2,否则作 H k( m ) ← S
S0 DES DES DES
m1 m2 ml
… ? ? ?
k k k
2012-3-19 50
基于分组密码的 Hash函数
?第 3种构造模式
– S1,i←1,m i ← 0,H 0 ← 0,m h+1 ← V;
– S2,H0 ← DES k( mi ? mi -1 ? Hi-1 ),i← i + 1 ；
– S3:若 i ≤ l+1;则转 S2,否则作 H k( m ) ← H i+1；
其中 V为和 k类似的参数,H0 和 M0 都取为零
2012-3-19 51
基于分组密码的 Hash函数
DES DES DES
m1 m2 ml
… ? ? ?
k k k
…
2012-3-19 52
基于离散对数的 Hash函数
2012-3-19 53
五、消息认证
2012-3-19 54
消息认证
认证目的,
? 验证信息的发送者是真的、而不是冒充的，
此为实体认证，包括信源、信宿等的认证和
识别；
? 验证信息的完整性，此为消息认证，验证数
据在传送或存储过程中未被窜改、重放或延
迟等。
认证的理论与技术：认证和认证系统, Hash
函数, 数字签名, 身份证明, 认证协议 。
2012-3-19 55
消息认证
认证系统
一个纯认证系统的模型如图所示 。 在这个
系统中的发送者通过一个公开信道将消息
送给接收者, 接收者不仅想收到消息本身
,而且还要验证消息是否来自合法的发送
者及消息是否经过窜改 。 系统中的密码分
析者不仅要截收和分析信道中传送的密报
,而且可伪造密文送给接收者进行欺诈,
称其为系统的干扰者 (Tamper)更加贴切 。
实际认证系统可能还要防止收, 发之间的
相互欺诈 。
2012-3-19 56
消息认证
信道
干扰者
认证编码器 认证译码器 信 源 信 宿
密钥源
认证信道
纯认证系统模型
2012-3-19 57
消息认证
认证系统的组成
? 鉴别编码器和鉴别译码器可抽象为鉴别函数。
? 一个安全的鉴别系统，需满足
– 特定的接收者能够检验和证实消息的合法性、
真实性和完整性。
– 消息的发送者和接收者不能抵赖。
– 除了合法的消息发送者，其它人不能伪造合法
的消息
2012-3-19 58
消息认证
消息认证编码
在要发送的消息中引入多余度, 使通过
信道传送的可能序列集 Y大于消息集 X。
对于任何选定的编码规则 (相应于某一特
定密钥 )：发方可从 Y中选出用来代表消息
的许用序列, 即码字；收方可根据编码规
则唯一地确定出发方按此规则向他传来的
消息 。 干扰者由于不知道密钥, 因而所伪
造的假码字多是 Y中的禁用序列, 收方将
以很高的概率将其检测出来而被拒绝 。
2012-3-19 59
消息认证
HMAC设计目标
– 无需修改地使用现有的散列函数。
– 当出现新的散列函数时,要能轻易地替换。
– 保持 Hash函数的原有性能不会导致算法性
能的降低。
– 使用和处理密钥的方式简单。
– 对认证机制的安全强度容易分析,与 Hash函
数有同等的安全性。
2012-3-19 60
消息认证
HMAC算法
– 对密钥 K左边补 0以产生一个 hash用块 K+
– K+每个字节与 ipad(00110110)作 XOR以产生 Si
– 对 (Si||M)进行 Hash
– K+每个字节与 opad(01011010)作 XOR以产生
S0
– HMACK = H[K+ ? opad) || H(K+ ? ipad)||
M]]
2012-3-19 61
Si Y0 Y1 YL-1
S0
Hash
Hash
K+ ipad
K+ opad
……
H( Si ‖ M )
HMACK(M)
IV
IV
2012-3-19 62
消息认证
– H = 嵌入散列函数（ MD5,SHA-
1,RIPEMD-160）
– M = 消息（包括散列函数所需填充位）
– Yi = M的第 i 个数据块,0 ≤ i ≤ L-1
– L = M的数据块数
– b = 数据块的位数
2012-3-19 63
消息认证
– n = 嵌入散列函数产生的散列码长度位数
– K = 保密密钥。如果密钥长度大于 b,则密
钥送入散列函数
– 形成一个 n位的密钥；推荐程度大于等于 n
– K+ = K在左部添加 0使得其长度为 b位
– ipad = 00110110重复 b/8次
– opad = 01011010重复 b/8次
第五章 Hash函数与消息认证
一,Hash函数概述
二,Hash函数 MD5
三、安全 Hash算法 SHA
四,基于分组密码与离散对数的 Hash函数
五、消息认证
2012-3-19 2
一,Hash函数概述
2012-3-19 3
Hash函数
? 单向函数
函数 f(x):A→ B若满足下面两个条件, 则
称为单向函数
– 对于任意 x*∈ A计算 y=f(x)是容易的,
其中 y ∈ B。
– 对于 x∈ A,求 y∈ B 使满足 y=f(x)是计
算上不可能的 。
2012-3-19 4
Hash函数
Hash函数
? 设 H：将 A*映射到 An,H满足,
– H是单向函数。
– 已知 x,找 x*∈ A*,使 H (x)= H (x*)在计
算上是不可能的。
– 找一对 x 和 x*, x ≠ x*,使 H (x)= H (x*)
在计算上也是不可能的。
H称为安全的 Hash函数。
2012-3-19 5
Hash函数
Hash函数的分类
根据安全水平,
? 弱无碰撞：散列函数 H称为是弱无碰撞
的，是指对给定消息,在计算上几乎
找不到异于 x的 x*使 H (x)= H (x*) 。
? 强无碰撞：散列函数 H被称为是强无碰
撞的,是指在计算上几乎不可能找到相
异的 x, x* 使得 H (x)= H (x*) 。
2012-3-19 6
Hash函数
Hash函数的分类
? 根据是否使用密钥
– 带秘密密钥的 Hash函数,消息的散列值由
只有通信双方知道的秘密密钥 K来控制
。此时 Hash值称作 MAC。
– 不带秘密密钥的 Hash函数：消息的散列
值的产生无需使用密钥。此时 Hash值称
作 MDC。
2012-3-19 7
Hash函数
Hash函数的用途
? 消息的完整性检测
? 数字签名
2012-3-19 8
Hash函数
h h
发送者对 h(x)
进行加密
接收者对 y
进行解密
不安全信道
不安全信道
x
x
y
x
y
h(x)
h(x)
h(x)
相等？
2012-3-19 9
Hash函数
使用 Hash函数进行数字签名的好处
? 提高数字签名的速度。
? 无需泄露签名所对应的消息，可将签名
泄露，如对消息 x的签名是 Sig(x)，其
z=H(x)可将 (z,y)公开，而保密 x。
? 可将签名变换和加密变换分开，可以在
OSI的不同层提供消息的完整性和机密
性 。
2012-3-19 10
Hash函数
Hash函数的安全性,Hash函数的安全性取
决于其抗击各种攻击的能力，对手的目标是
找到两个不同消息映射为同一杂 Hash值。一
般假定对手知道 Hash算法，采用选择明文攻
击法。
2012-3-19 11
Hash函数
对 Hash函数的基本攻击方法
? 穷举攻击法：给定 H=H(H0,M),其中 H0为
初值, 攻击者在所有可能的 M中寻求有利于
攻击者的 M’,使 H(H0,M’)=H(H0,M),由于
限定了目标 H(H0,M)来寻找 H(H0,M’),这种
攻击法称为目标攻击 。 若对算法的初值 H0不
限定, 使其 H(H0,M)等于 H(H0,M’),则称这
种攻击法为自由起始目标攻击 。
2012-3-19 12
Hash函数
对 Hash函数的基本攻击方法
? 生日攻击：这种攻击法不涉及 Hash算法的
结构, 可用于攻击任何 Hash算法 。 强无碰撞
函数正是基于生日悖论一类的攻击法定义的
。 穷举和生日攻击都属选择明文攻击 。 生日
攻击给定初值 H0 寻找 M?M’,
使 H(H0,M’)=H(H0,M),也可对初始值 H0不
加限制, 即 寻 找 H0’,M’ 使满足 h(H0’,
M’)=h(H0,M)。
2012-3-19 13
Hash函数
生日悖论
在一个会场参加会议的人中，找一个与某人
生日相同的概率超过 0.5时，所需参会人员为
183人。但要问使参会人员中至少有两个同日
生的概率超过 0.5的参会人数仅为 23人。这是
因为，对于与某个已知生日的人同日生的概
率为 1/365，若房中有 t人，则至少找到一人与
此人同日生的概率为。易于解出当 t?183时可
使 p>0.5。
2012-3-19 14
Hash函数
Hash函数的迭代构造
将不限定长度的输入数据压缩成定长输出的
Hash值过程,
– 将输入数字串划分成固定长的段如 m比特段
– 将此 m比特映射成 n比特, 称完成此映射的
函数为迭代函数 。
– 对一段 m比特输入做类似映射, 以此类推,
直到全部输入数字串完全做完, 以最后的输
出值作为整个输入的 Hash值 。
2012-3-19 15
Hash函数
将 m bit到 n bit的分组映射或迭代函数的三
种选择
? m>n。 有数据压缩, 例如,MD4,MD5
SHA等算法 。 是不可逆映射 。
? m=n。 无数据压缩, 亦无数据扩展, 通
常分组密码采用这类 。
? m<n。 有数据扩展的映射 。 认证码属
于此类 。
2012-3-19 16
Hash函数
? 迭代函数以 E表示, 一般 E又都是通过
基本轮函数的多轮迭代实现的, 因此,
轮函数的设计是 Hash函数设计的核心 。
? 迭代 Hash函数的构造方法
– 安全迭代函数 E
– 消息 M划分成组 M1,M2,…,Mi,…,Mt
– 选定密钥为 K,
– H0为初始向量 IV,
2012-3-19 17
Hash函数
? Rabin法,
H0=IV； Hi=E(Mi,Hi-1) i=1,…,t ；
H(M)=Ht 。
? 密码分组链接 (CBC)法,
H0=IV； Hi=E(K,Mi ?Hi-1) i=1,2,…,t ；
H(M)=Ht 。
? 密码反馈 (CFB)法,
Hi=E(K,Hi-1?Mi),i=1,2,…,t； H(M)=Ht
2012-3-19 18
Hash函数
? 组合明 /密文链接法,
Mt+1=IV； Hi=E(K,Mi?Mi-1?Hi-1)
i=1,2,…,t ； H(M)=Ht+1。
? 修正 Daveis-Meyer法,
H0=IV； Hi=E(Hi-1,Mi,Hi-1) (Hi和 Mi共
同作为密钥 )
2012-3-19 19
Hash函数
B,Preneel总结的下述 12种基本方式构造
的分组迭代 Hash函数。令 E是迭代函数，
它可以是一种分组加密算法,E(K,X),K
是密钥,X是输入数据组或某种压缩算法
。令消息分组为 M1,…,M i,…,H 0=I为初始
值。
– Hi=E(Mi,Hi-1)?Hi-1
– Hi=E(Hi-1,Mi)?Mi?Hi-1
– Hi=E(Hi-1,Mi?Hi-1)?Mi
2012-3-19 20
Hash函数
– Hi=E(Hi-1,Mi?Hi-1)?Mi?Hi-1
– Hi=E(Hi-1,Mi)?Mi
– Hi=E(Mi,Mi?Hi-1)?Mi?Hi-1
– Hi=E(Mi,Hi-1)?Mi?Hi-1
– Hi=E(Mi,Mi?Hi-1)?Hi-1
– Hi=E(Mi?Hi-1,Mi)?Mi
– Hi=E(Mi?Hi-1,Hi-1,)?Hi-1 [Brown等 1990]
– Hi=E(Mi?Hi-1,Mi)?Hi-1
– Hi=E(Mi?Hi-1,Hi-1)?Mi
2012-3-19 21
二,Hash函数 MD5
2012-3-19 22
Hash函数 MD5
设计目标,
MD5是 R.Rivest在 MIT开发研究的 Hash函数
– 输入：任意长度的消息
– 输出,128位消息摘要
– 处理：以 512位输入数据块为单位
2012-3-19 23
Hash函数 MD5
MD5算法
? 对明文输入按 512bit分组，最后要填充使
其成为 512 bit的整数倍，且最后一组的后
64 bit用来表示消息长在 mod 264下的值 K
,故填充位数为 1～ 512 bit,填充数字图
样为 (100…0),得 Y0,Y1,…, YL-1。 其中，
Yl为 512 bit,即 16个长为 32 bit的字，按字
计消息长为 N=L× 16。
。
2012-3-19 24
Hash函数 MD5
MD5算法
? 每轮输出为 128 bit,可用下述 4个 32 bits字表
示,A,B,C,D。 其初始存数以十六制表
示为,
A=01234567 B=89ABCDEF C=FEDCBA98
D=76543210。
2012-3-19 25
Hash函数 MD5
MD5算法
? 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随机数源。
2012-3-19 26
Hash函数 MD5
MD5是四轮运算，各轮逻辑函数不同。每轮
又要进行 16步迭代运算,4轮共需 64步完成。
每步完成
a ? b＋ CLSS (a＋ g(B,C,D)＋ X[k]＋ T[i])
其中 a,b,c,d=缓存器中的四个字，按特定次序
变化。 g=基本逻辑函数 F,G,H,I中之一，算
法的每一轮用其中之一。
2012-3-19 27
ABCD＂ fI(ABCD,Yq,T[49…64])
+ + + +
ABCD＂ fF(ABCD,Yq,T[1…16])
ABCD＂ fH(ABCD,Yq,T[33…48])
ABCD＂ fH(ABCD,Yq,T[33…48])
MDq,128
A B C D
A B C D
A B C D
A B C D
Yq
512
MDq+1,128
2012-3-19 28
+
g
a b c d
+
+
+
CLSS
X [k]
T [i]
2012-3-19 29
Hash函数
– CLSs,32-bit 存数循环左移 s位 。
– X[k]=M[q× 16＋ k]：消息的第 q-512-bit组
的第 k个 32-bit字
– T[i],232× abs(sin(i))的整数部分 。
– ＋：模 232加法 。
T[i]由 sin 函数构造。每个输入的 32 bit字被
采用 4次，每轮用一次，而 T[i]中每个元素
恰只用一次。每一次,ABCD中只有 4个字
节更新，共更新 16次，在最后第 17次产生
此组的最后输出。
2012-3-19 30
Hash函数
轮 基本函数 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ˉ)
表 -1各轮的逻辑函数
2012-3-19 31
Hash函数
表 -2 逻辑函数的真值表
b c d F G H I
0 0 0 0 0 0 1
0 0 1 1 0 1 0
0 1 0 0 1 1 0
0 1 1 1 0 0 1
1 0 0 0 0 1 1
1 0 1 0 1 0 1
1 1 0 1 1 0 0
1 1 1 1 1 1 0
2012-3-19 32
Hash函数
MD0=IV（ ABCD缓存器的初始矢量）
MDq+1 =MDq+fI[Yq,fH[Yq,fG[Yq,fF[Yq,MDq]]]]
MD=MDL— 1（ 最终输出值）。
2012-3-19 33
Hash函数
MD5的安全性,
求具有相同 Hash值的两个消息在计算上是
不可行的。 MD-5的输出为 128-bit,若采用
纯强力攻击寻找一个消息具有给定 Hash值
的计算困难性为 2128。若采用生日攻击法，
寻找有相同 Hash值的两个消息需要试验 264
个消息。差分攻击对 MD5的安全性不构成
威胁。
2012-3-19 34
Hash函数
MD5的安全性,
对单轮 MD5已有攻击结果。与 Snefru比
较，两者均为 32 bits字运算。 Snefru采用
S-BOX,XOR函数,MD5用 mod 232加。
最近山东大学的王小云教授利用用差分分
析的方法研究 MD5，得到了比较好的算
法使 MD5能够产生碰撞。因此 MD5的安
全性还需要进一步提高。
2012-3-19 35
三、安全 Hash算法 SHA
2012-3-19 36
安全 Hash算法 SHA
SHA是美国 NIST和 NSA设计的一种标准
算法 SHA (Secure Hash Algorithm),用于
数字签字标准算法 DSS (Digital Signature
Standard),亦可用于其它需要用 Hash算
法的情况 。 SHA具有较高的安全性。
– 输入消息长度小于 264 bit
– 输出压缩值为 160 bit
2012-3-19 37
安全 Hash算法 SHA
SHA的描述
? 输入长度少于 264比特，输出 160比特。输入
分成 512比特块。
? 附加信息位使长度 mod512与 448同余。
? 一组 64比特附在后面，看作是 64比特的整
数，包含原来未加附加位的信息长度。
2012-3-19 38
安全 Hash算法 SHA
SHA的描述
? MD缓冲器初始化。缓冲区分为５个寄存器
(A,B,C,D,E)，每个 32比特，初始值分别为,
A=67 45 32 10 B=EF CD AB 89
C=98 BA DC FE D=10 32 54 76
E=C3 D2 E1 F0
2012-3-19 39
安全 Hash算法 SHA
对 512比特组的信息的处理,
算法的核心是４轮操作，每轮 20步，每
轮的结构类似但是逻辑函数不同，分别为
f1,f2,f3,f4 每轮输入 512比特，输出 160比
特。
2012-3-19 40
安全 Hash算法 SHA
对 512比特组的信息的处理,
ABCDE,每轮用的常数 Kt,,0≤t≤79,其实只有
4个不同的常数
5A827999 0 ≤t≤19
6ED9EBA1 20≤t≤39
Kt＝ 8F1BDBDC 40≤t≤59
CA62C1D6 60≤t≤79
? 当 L组运算结束后，由第 L步的输出 160比
特作 H(m)。
2012-3-19 41
＋ ＋ ＋ ＋ ＋
P1,K,W[0…19]
P2,K,W[20…39]
P3,K,W[40…59]
P4,K,W[60…79]
512 160 32
A C D B E
A C D B E
A C D B E
A C D B E
160
2012-3-19 42
安全 Hash算法 SHA
SHA每一步是如下计算的,
(A,B,C,D,E) ←
((E+f (t,B,C,D))+S5(A)+Wt),A,S30(B),C,D)
– t为步数,
– f (t,B,C,D)为第 t步的逻辑函数。
– Sk为左旋转移位 k位。
– Wt为由 512比特的输入组导出 32比特的第 t块。
– Kt为附加的常数。
– +为 mod 232的加法。
2012-3-19 43
A E D C B
A E D C B
f
S5
S30 +
+
+
+
Wt
Kt
2012-3-19 44
安全 Hash算法 SHA
每个函数的输入为 32比特，输出是一个 32比
特字，有一系列逻辑运算而得到的。输出的
第 n位为 BCD3输入第 n位的函数。
(B∧ C) ∨ ( B∧ D) 0 ≤t≤19
B ? C ? D 20≤t≤39
f(t,B,C,D)=(B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D)
40≤t≤59
B ? C ? D 60≤t≤79
?
2012-3-19 45
安全 Hash算法 SHA
SHA 与 MD5的比较
? 最主要不同点,SHA比 MD5长了 32比特，如果
采用强行攻击,SHA显然比 MD5抗攻击能力
强。
? MD5已有了密码分析的攻击方法，顾较脆弱。
? MD5效率比 SHA高。
? 两者都比较容易实现。
? R.L.Rivest公开了 MD-5的设计决策，但 SHA的
设计者则不愿公开。
2012-3-19 46
四、基于分组密码与离散对数的
Hash函数
2012-3-19 47
基于分组密码的 Hash函数
利用 DES构造 Hash函数
我们将介绍利用 DES构造 Hash函数的若干
模式，实际上也是利用和 DES类似的明文
、密文长度和密钥长度一样的分组密码来
构造 Hash函数的模式。
设 m=m1m2…m l,m=m1m2…m l 都是 64比特的
明文块,k是密钥，也是 64比特。
2012-3-19 48
基于分组密码的 Hash函数
? 第 1种构造模式
– S1,i←1,K ← k;
– S2,K ← DES k( mi ),i ← i+1;
– S3:若 i ≤ l,则转 S2,否则作 H k( m ) ← K
k DES DES DES
m1 m2 ml
… Hk ( m )
2012-3-19 49
基于分组密码的 Hash函数
? 第 2种构造模式
– S1,i←1,S ← S 0;
– S2,mi ← m i ? S,S← DES k( mi ),
– S3:若 i ≤ l;则转 S2,否则作 H k( m ) ← S
S0 DES DES DES
m1 m2 ml
… ? ? ?
k k k
2012-3-19 50
基于分组密码的 Hash函数
?第 3种构造模式
– S1,i←1,m i ← 0,H 0 ← 0,m h+1 ← V;
– S2,H0 ← DES k( mi ? mi -1 ? Hi-1 ),i← i + 1 ；
– S3:若 i ≤ l+1;则转 S2,否则作 H k( m ) ← H i+1；
其中 V为和 k类似的参数,H0 和 M0 都取为零
2012-3-19 51
基于分组密码的 Hash函数
DES DES DES
m1 m2 ml
… ? ? ?
k k k
…
2012-3-19 52
基于离散对数的 Hash函数
2012-3-19 53
五、消息认证
2012-3-19 54
消息认证
认证目的,
? 验证信息的发送者是真的、而不是冒充的，
此为实体认证，包括信源、信宿等的认证和
识别；
? 验证信息的完整性，此为消息认证，验证数
据在传送或存储过程中未被窜改、重放或延
迟等。
认证的理论与技术：认证和认证系统, Hash
函数, 数字签名, 身份证明, 认证协议 。
2012-3-19 55
消息认证
认证系统
一个纯认证系统的模型如图所示 。 在这个
系统中的发送者通过一个公开信道将消息
送给接收者, 接收者不仅想收到消息本身
,而且还要验证消息是否来自合法的发送
者及消息是否经过窜改 。 系统中的密码分
析者不仅要截收和分析信道中传送的密报
,而且可伪造密文送给接收者进行欺诈,
称其为系统的干扰者 (Tamper)更加贴切 。
实际认证系统可能还要防止收, 发之间的
相互欺诈 。
2012-3-19 56
消息认证
信道
干扰者
认证编码器 认证译码器 信 源 信 宿
密钥源
认证信道
纯认证系统模型
2012-3-19 57
消息认证
认证系统的组成
? 鉴别编码器和鉴别译码器可抽象为鉴别函数。
? 一个安全的鉴别系统，需满足
– 特定的接收者能够检验和证实消息的合法性、
真实性和完整性。
– 消息的发送者和接收者不能抵赖。
– 除了合法的消息发送者，其它人不能伪造合法
的消息
2012-3-19 58
消息认证
消息认证编码
在要发送的消息中引入多余度, 使通过
信道传送的可能序列集 Y大于消息集 X。
对于任何选定的编码规则 (相应于某一特
定密钥 )：发方可从 Y中选出用来代表消息
的许用序列, 即码字；收方可根据编码规
则唯一地确定出发方按此规则向他传来的
消息 。 干扰者由于不知道密钥, 因而所伪
造的假码字多是 Y中的禁用序列, 收方将
以很高的概率将其检测出来而被拒绝 。
2012-3-19 59
消息认证
HMAC设计目标
– 无需修改地使用现有的散列函数。
– 当出现新的散列函数时,要能轻易地替换。
– 保持 Hash函数的原有性能不会导致算法性
能的降低。
– 使用和处理密钥的方式简单。
– 对认证机制的安全强度容易分析,与 Hash函
数有同等的安全性。
2012-3-19 60
消息认证
HMAC算法
– 对密钥 K左边补 0以产生一个 hash用块 K+
– K+每个字节与 ipad(00110110)作 XOR以产生 Si
– 对 (Si||M)进行 Hash
– K+每个字节与 opad(01011010)作 XOR以产生
S0
– HMACK = H[K+ ? opad) || H(K+ ? ipad)||
M]]
2012-3-19 61
Si Y0 Y1 YL-1
S0
Hash
Hash
K+ ipad
K+ opad
……
H( Si ‖ M )
HMACK(M)
IV
IV
2012-3-19 62
消息认证
– H = 嵌入散列函数（ MD5,SHA-
1,RIPEMD-160）
– M = 消息（包括散列函数所需填充位）
– Yi = M的第 i 个数据块,0 ≤ i ≤ L-1
– L = M的数据块数
– b = 数据块的位数
2012-3-19 63
消息认证
– n = 嵌入散列函数产生的散列码长度位数
– K = 保密密钥。如果密钥长度大于 b,则密
钥送入散列函数
– 形成一个 n位的密钥；推荐程度大于等于 n
– K+ = K在左部添加 0使得其长度为 b位
– ipad = 00110110重复 b/8次
– opad = 01011010重复 b/8次
