2010-5-14 1
第七章 消息认证和杂凑算法
Message Authentication and Hash
Algorithms
2010-5-14 2
消息认证和杂凑算法
? 消息认证用于抗击主动攻击
? 验证接收消息的真实性和完整性
? 真实性
? 的确是由所声称的实体发过来的
? 完整性
? 未被篡改、插入和删除
? 验证消息的顺序性和时间性（未重排、
重放和延迟）
2010-5-14 3
消息认证码 (MAC)
Message Authenticaion Code
2010-5-14 4
消息认证码的定义和使用方式
? 消息被一密钥控制的公开函数作用后产
生的、用于认证符的、固定长度的数值，
也称为密码校验和。
? 通信双方共享密钥 K
M ||
C
K
M
CK(M)
C
K 比较
消息认证
1,接收方相信
发送方发来
的消息未受
篡改。
2,接收方相信
发送方不是
冒充的
2010-5-14 5
消息认证码的定义和使用方式
? 认证性和保密性 -对明文认证
M ||
C
K1
CM
CK(M)
K1 比较
E
K2
)](||[ 12 MCME KK
D
K2
2010-5-14 6
消息认证码的定义和使用方式
? 认证性和保密性 -对密文认证
M ||
C
K1
C
K1 比较
E
K2
)]([ 21 MEC KK
D
K2
2010-5-14 7
产生 MAC函数应满足的要求
? 产生 MAC的函数一般为多到 1映射。 nbit长的 MAC共有
2n个可能的取值，可能的消息数远大于 2n。
? 密钥长度为 kbit，可能的密钥数为 2k。
? 敌手可获得明文和 MAC,敌手可穷举攻击密钥。如果
k>n,很多密钥,(2k-n个 )可产生相同的 MAC,敌手无法确
定，还需要在这 2k-n个密钥中继续试验。
? 对消息认证码的穷举攻击代价大于攻击加密算法。
? 敌手有可能不直接攻击密钥，而伪造能够通过检验的
MAC和 M。
2010-5-14 8
产生 MAC函数应满足的要求
? 假定敌手知道函数 C，不知道 K
? 如果敌手得到 M和 CK(M)，则构造一满足
CK(M’)= CK(M)的新消息在计算上不可行
? CK(M)在以下意义下是均匀分布的：随机
选两个 M,M’,Pr[CK(M)=CK(M’)]=2-n
? 若 M’是 M的某个变换，
Pr[CK(M)=CK(M’)]=2-n
2010-5-14 9
CBC-MAC
? 基于 CBC模式的 DES算法，初始向量取为
零。
D1
DES加密
O1
K
第 1次
D2
DES加密
O2
K
第 2次
+
D2
DES加密
ON
K
第 N次
+ON-1
2010-5-14 10
杂凑函数
Hash Functions
2010-5-14 11
杂凑函数的定义
? 杂凑函数 H是一个公开函数，将任意长的
消息映射为较短的、固定长度的一个值
H(M)
? H(M)称为杂凑值、消息摘要，是消息中
所有 bit的函数，提供了错误检测的能力
2010-5-14 12
杂凑函数的使用方式
? 消息于杂凑连接后用单钥加密，密钥为
A,B共享，保证消息来自 A并且不被篡改
M ||
H
HM
H(M)
比较
E
K
)](||[ MHME K
D
K
2010-5-14 13
杂凑函数的使用方式
? 单钥加密函数仅对 hash值加密
2010-5-14 14
杂凑函数的使用方式
? 使用发送方秘密钥加密杂凑值
2010-5-14 15
杂凑函数的使用方式
? 用发送方秘密钥加密 hash，再用单钥加
密整个数据
2010-5-14 16
杂凑函数的使用方式
? 通信双方共享一个秘密值 S
2010-5-14 17
杂凑函数的使用方式
? 在上一方式基础上加上加密
2010-5-14 18
杂凑函数应满足的条件
? 函数的输入可以是任意长
? 函数的输出是固定长
? 已知 x,求 H(x)较为容易
? 已知 h，求 H(x)＝ h的在计算上不可行，
即单向杂凑函数，如果满足这一性质，
称为弱单向杂凑函数
? 找出任意两个不同的 x,y，是 H(x)=H(y)
在计算上不可行，满足这一性质，称为
强单向杂凑函数
2010-5-14 19
生日攻击
? （第 I类生日攻击） H有 n个输出,H(x)是
一个特定的输出，如果对 H随机取 k个输
入，至少有一个 y使 H(y)=H(x)的概率为
0.5时,k有多大？
H(y)=H(x)的概率为 1/n，不等的概率
为 1-1/n.取 k个值都不等的为 [1-1/n]k.至少
有一个等的概率为 1－ [1-1/n]k，近似等于
k/n。所以概率为 0.5,k为 n/2。
2010-5-14 20
生日悖论
? 在一个会场参加会议的人中，问使参会人员中至
少有两个同日生的概率超过 0.5的参会人数仅为
23人。
t个人都不同时生日概率为
，因此，至少有两人于同日生的概率为
解之，当 t?23时,p>0.5。对于 n比特杂凑值的
生日攻击，由上式可计算出，当进行 2n/2次的选
择明文攻击下成功的概率将超过 0.63。
?????? ???????? ??????? 3 6 511.,,3 6 5213 6 511 t－
?????? ???????? ????????? 365 11.,,365 21365 111 tp －
2010-5-14 21
迭代型杂凑函数的一般结构
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是设计的
关键
第七章 消息认证和杂凑算法
Message Authentication and Hash
Algorithms
2010-5-14 2
消息认证和杂凑算法
? 消息认证用于抗击主动攻击
? 验证接收消息的真实性和完整性
? 真实性
? 的确是由所声称的实体发过来的
? 完整性
? 未被篡改、插入和删除
? 验证消息的顺序性和时间性（未重排、
重放和延迟）
2010-5-14 3
消息认证码 (MAC)
Message Authenticaion Code
2010-5-14 4
消息认证码的定义和使用方式
? 消息被一密钥控制的公开函数作用后产
生的、用于认证符的、固定长度的数值，
也称为密码校验和。
? 通信双方共享密钥 K
M ||
C
K
M
CK(M)
C
K 比较
消息认证
1,接收方相信
发送方发来
的消息未受
篡改。
2,接收方相信
发送方不是
冒充的
2010-5-14 5
消息认证码的定义和使用方式
? 认证性和保密性 -对明文认证
M ||
C
K1
CM
CK(M)
K1 比较
E
K2
)](||[ 12 MCME KK
D
K2
2010-5-14 6
消息认证码的定义和使用方式
? 认证性和保密性 -对密文认证
M ||
C
K1
C
K1 比较
E
K2
)]([ 21 MEC KK
D
K2
2010-5-14 7
产生 MAC函数应满足的要求
? 产生 MAC的函数一般为多到 1映射。 nbit长的 MAC共有
2n个可能的取值，可能的消息数远大于 2n。
? 密钥长度为 kbit，可能的密钥数为 2k。
? 敌手可获得明文和 MAC,敌手可穷举攻击密钥。如果
k>n,很多密钥,(2k-n个 )可产生相同的 MAC,敌手无法确
定，还需要在这 2k-n个密钥中继续试验。
? 对消息认证码的穷举攻击代价大于攻击加密算法。
? 敌手有可能不直接攻击密钥，而伪造能够通过检验的
MAC和 M。
2010-5-14 8
产生 MAC函数应满足的要求
? 假定敌手知道函数 C，不知道 K
? 如果敌手得到 M和 CK(M)，则构造一满足
CK(M’)= CK(M)的新消息在计算上不可行
? CK(M)在以下意义下是均匀分布的：随机
选两个 M,M’,Pr[CK(M)=CK(M’)]=2-n
? 若 M’是 M的某个变换，
Pr[CK(M)=CK(M’)]=2-n
2010-5-14 9
CBC-MAC
? 基于 CBC模式的 DES算法，初始向量取为
零。
D1
DES加密
O1
K
第 1次
D2
DES加密
O2
K
第 2次
+
D2
DES加密
ON
K
第 N次
+ON-1
2010-5-14 10
杂凑函数
Hash Functions
2010-5-14 11
杂凑函数的定义
? 杂凑函数 H是一个公开函数，将任意长的
消息映射为较短的、固定长度的一个值
H(M)
? H(M)称为杂凑值、消息摘要，是消息中
所有 bit的函数，提供了错误检测的能力
2010-5-14 12
杂凑函数的使用方式
? 消息于杂凑连接后用单钥加密，密钥为
A,B共享，保证消息来自 A并且不被篡改
M ||
H
HM
H(M)
比较
E
K
)](||[ MHME K
D
K
2010-5-14 13
杂凑函数的使用方式
? 单钥加密函数仅对 hash值加密
2010-5-14 14
杂凑函数的使用方式
? 使用发送方秘密钥加密杂凑值
2010-5-14 15
杂凑函数的使用方式
? 用发送方秘密钥加密 hash，再用单钥加
密整个数据
2010-5-14 16
杂凑函数的使用方式
? 通信双方共享一个秘密值 S
2010-5-14 17
杂凑函数的使用方式
? 在上一方式基础上加上加密
2010-5-14 18
杂凑函数应满足的条件
? 函数的输入可以是任意长
? 函数的输出是固定长
? 已知 x,求 H(x)较为容易
? 已知 h，求 H(x)＝ h的在计算上不可行，
即单向杂凑函数，如果满足这一性质，
称为弱单向杂凑函数
? 找出任意两个不同的 x,y，是 H(x)=H(y)
在计算上不可行，满足这一性质，称为
强单向杂凑函数
2010-5-14 19
生日攻击
? （第 I类生日攻击） H有 n个输出,H(x)是
一个特定的输出，如果对 H随机取 k个输
入，至少有一个 y使 H(y)=H(x)的概率为
0.5时,k有多大？
H(y)=H(x)的概率为 1/n，不等的概率
为 1-1/n.取 k个值都不等的为 [1-1/n]k.至少
有一个等的概率为 1－ [1-1/n]k，近似等于
k/n。所以概率为 0.5,k为 n/2。
2010-5-14 20
生日悖论
? 在一个会场参加会议的人中，问使参会人员中至
少有两个同日生的概率超过 0.5的参会人数仅为
23人。
t个人都不同时生日概率为
，因此，至少有两人于同日生的概率为
解之，当 t?23时,p>0.5。对于 n比特杂凑值的
生日攻击，由上式可计算出，当进行 2n/2次的选
择明文攻击下成功的概率将超过 0.63。
?????? ???????? ??????? 3 6 511.,,3 6 5213 6 511 t－
?????? ???????? ????????? 365 11.,,365 21365 111 tp －
2010-5-14 21
迭代型杂凑函数的一般结构
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是设计的
关键
