2010-5-14 1
第七章 消息认证和杂凑算法
Message Authentication and Hash
Algorithms
2010-5-14 2
杂凑函数
Hash Functions
2010-5-14 3
SHA与 MD5的比较
? 抗穷搜索能力
? 寻找指定 hash值,SHA,O(2160),MD5,O(2128)
? 生日攻击,SHA,O(280),MD5,O(264)
? 抗密码分析攻击的强度
? SHA似乎高于 MD5
? 速度
? SHA较 MD5慢
? 简捷与紧致性
? 描述都比较简单，都不需要大的程序和代换表
2010-5-14 4
HMAC算法
2010-5-14 5
HMAC的设计目标
? Hash函数不使用密钥，不能直接用于 MAC
? HMAC要求
? 可不经修改使用现有 hash函数
? 其中镶嵌的 hash函数可易于替换为更快和更安全的
hash函数
? 保持镶嵌的 hash函数的最初性能，不因适用于
HAMC而使其性能降低
? 以简单方式使用和处理密钥
? 在对镶嵌的 hash函数合理假设的基础上，易于分析
HMAC用于认证时的密码强度
2010-5-14 6
算法描述
Ipad:b/8个 00110110
Opad:b/8个 01011010
K+:左面经填充 0后的 K.K＋
的长度为 b比特
2010-5-14 7
HMAC的安全性
? 取决于 hash函数的安全性
? 证明了算法强度和嵌入的 hash函数强度
的确切关系，即证明了对 HMAC攻击等
价于对内嵌 hash函数的下述两种攻击
? 攻击者能够计算压缩函数的一个输出，即使
IV是秘密的和随机的
? 攻击者能够找出 hash函数的碰撞，即使 IV是
随机的和秘密的。
2010-5-14 8
第八章 数字签字和密码协议
2010-5-14 9
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 10
数字签字的基本概念
2010-5-14 11
数字签字应具有的性质
? 能够验证签字产生者的身份，以及产生
签字的日期和时间
? 能用于证实被签消息的内容
? 数字签字可由第三方验证，从而能够解
决通信双方的争议
2010-5-14 12
数字签字应满足的要求
? 签字的产生必须使用发方独有的一些信
息以防止伪造和否认
? 签字的产生应较为容易
? 签字的识别和验证应较为容易
? 对已知的数字签字构造一些新的消息或
对已知的消息构造一假冒的数字签字在
计算上都是不可行的
2010-5-14 13
消息认证码的不足
? 可以保护通信双方以防止第 3者攻击，不
能保护通信双方中一方防止另一方的欺
骗和伪造。
? B伪造一个消息并使用于 A共享的密钥产生该
消息的认证码，然后生成该消息来自于 A
? B有可能伪造 A发来的消息，所以 A就可以对
自己发过的消息予以否认
2010-5-14 14
数字签字的产生方式
? 由加密算法产生数字签字
? 由签字算法产生数字签字
2010-5-14 15
由加密算法产生数字签字
? 单钥加密
? 向 B保证收到的消息确实来自 A
? B恢复 M后，可相信 B未被窜改，否则 B将
得到无意义的比特序列
M ME
K
][MEK
D
K
2010-5-14 16
由加密算法产生数字签字
? 公钥加密
M ME
SKA
][ME ASK
D
PKA
只有 A才能用 SKA加密，
可使 B相信消息来自 A,不
提供保密性
M ME
SKA
][ME ASK
D
PKA
E
PKB ]][[ MEE
AB SKPK
D
SKB ][ME
ASK
提供保密性和认证性
2010-5-14 17
由加密算法产生数字签字
? RSA签字体制
? 体制参数
? 大素数 p,q,n=p× q,y(n)=(p-1)(q-1)。选整数
1<e< y(n),且 gcd(e,y(n))=1;计算 d满足 de≡ 1 mod
y(n),{e,n}为公开密钥,{d,n}为秘密密钥。
? 签字过程
? S=Md mod n
? 验证过程
? M=Se mod n
? 实际应用中加密是对 H(M)进行的。
2010-5-14 18
由加密算法产生数字签字
? 外部保密
? 数字签字直接对需要签字的消息生成
? 内部保密
? 数字签字对已加密的消息产生
? 外部保密有利于争议的解决。
2010-5-14 19
由签字算法产生数字签字
签字体制 =(M,S,K,V)
M:明文空间,S:签字的集合,K:密钥空间,V,证
实函数的值域，由真、伪组成。
(1) 签字算法,
对每一 M?M和 每一 k?K，易于计算对 M的签
字 S=Sigk(M)?S
签字算法或签字密钥是秘密的，只有签字人掌
握；
(2)验证算法,
Verk(S,M)?{真，伪 }={0,1}
2010-5-14 20
由签字算法产生数字签字
体制的安全性,从 M和其签字 S难于推出 K或伪造一
个 M’使 M’和 S可被证实为真。
与消息加密不同点,消息加密和解密可能是 一次性 的，
它要求在解密之前是安全的；而一个签字的消息可能
作为一个法律上的文件，如合同等，很可能在对消息
签署多年之后才验证其签字，且可能 需要多次验证 此
签字。
Ve r M S S Sig M
S Sig Mk
(,) ( )
( )
? ?
?
?
??
??
真,当
伪,当
2010-5-14 21
数字签字的执行方式
? 直接方式
数字签字的执行过程只有通信的双方参
与，并假定双方有共享的秘密密钥或者
接收一方知道发送方的公开钥。
? 缺点：方案的有效性取决于发方密钥的
安全性。
? 发方可声称秘密钥丢失或被窃
第七章 消息认证和杂凑算法
Message Authentication and Hash
Algorithms
2010-5-14 2
杂凑函数
Hash Functions
2010-5-14 3
SHA与 MD5的比较
? 抗穷搜索能力
? 寻找指定 hash值,SHA,O(2160),MD5,O(2128)
? 生日攻击,SHA,O(280),MD5,O(264)
? 抗密码分析攻击的强度
? SHA似乎高于 MD5
? 速度
? SHA较 MD5慢
? 简捷与紧致性
? 描述都比较简单，都不需要大的程序和代换表
2010-5-14 4
HMAC算法
2010-5-14 5
HMAC的设计目标
? Hash函数不使用密钥，不能直接用于 MAC
? HMAC要求
? 可不经修改使用现有 hash函数
? 其中镶嵌的 hash函数可易于替换为更快和更安全的
hash函数
? 保持镶嵌的 hash函数的最初性能，不因适用于
HAMC而使其性能降低
? 以简单方式使用和处理密钥
? 在对镶嵌的 hash函数合理假设的基础上，易于分析
HMAC用于认证时的密码强度
2010-5-14 6
算法描述
Ipad:b/8个 00110110
Opad:b/8个 01011010
K+:左面经填充 0后的 K.K＋
的长度为 b比特
2010-5-14 7
HMAC的安全性
? 取决于 hash函数的安全性
? 证明了算法强度和嵌入的 hash函数强度
的确切关系，即证明了对 HMAC攻击等
价于对内嵌 hash函数的下述两种攻击
? 攻击者能够计算压缩函数的一个输出，即使
IV是秘密的和随机的
? 攻击者能够找出 hash函数的碰撞，即使 IV是
随机的和秘密的。
2010-5-14 8
第八章 数字签字和密码协议
2010-5-14 9
? 数字签字的基本概念
? 数字签字标准
? 其他签字方案
? 认证协议
? 身份证明技术
? 其他密码协议
2010-5-14 10
数字签字的基本概念
2010-5-14 11
数字签字应具有的性质
? 能够验证签字产生者的身份，以及产生
签字的日期和时间
? 能用于证实被签消息的内容
? 数字签字可由第三方验证，从而能够解
决通信双方的争议
2010-5-14 12
数字签字应满足的要求
? 签字的产生必须使用发方独有的一些信
息以防止伪造和否认
? 签字的产生应较为容易
? 签字的识别和验证应较为容易
? 对已知的数字签字构造一些新的消息或
对已知的消息构造一假冒的数字签字在
计算上都是不可行的
2010-5-14 13
消息认证码的不足
? 可以保护通信双方以防止第 3者攻击，不
能保护通信双方中一方防止另一方的欺
骗和伪造。
? B伪造一个消息并使用于 A共享的密钥产生该
消息的认证码，然后生成该消息来自于 A
? B有可能伪造 A发来的消息，所以 A就可以对
自己发过的消息予以否认
2010-5-14 14
数字签字的产生方式
? 由加密算法产生数字签字
? 由签字算法产生数字签字
2010-5-14 15
由加密算法产生数字签字
? 单钥加密
? 向 B保证收到的消息确实来自 A
? B恢复 M后，可相信 B未被窜改，否则 B将
得到无意义的比特序列
M ME
K
][MEK
D
K
2010-5-14 16
由加密算法产生数字签字
? 公钥加密
M ME
SKA
][ME ASK
D
PKA
只有 A才能用 SKA加密，
可使 B相信消息来自 A,不
提供保密性
M ME
SKA
][ME ASK
D
PKA
E
PKB ]][[ MEE
AB SKPK
D
SKB ][ME
ASK
提供保密性和认证性
2010-5-14 17
由加密算法产生数字签字
? RSA签字体制
? 体制参数
? 大素数 p,q,n=p× q,y(n)=(p-1)(q-1)。选整数
1<e< y(n),且 gcd(e,y(n))=1;计算 d满足 de≡ 1 mod
y(n),{e,n}为公开密钥,{d,n}为秘密密钥。
? 签字过程
? S=Md mod n
? 验证过程
? M=Se mod n
? 实际应用中加密是对 H(M)进行的。
2010-5-14 18
由加密算法产生数字签字
? 外部保密
? 数字签字直接对需要签字的消息生成
? 内部保密
? 数字签字对已加密的消息产生
? 外部保密有利于争议的解决。
2010-5-14 19
由签字算法产生数字签字
签字体制 =(M,S,K,V)
M:明文空间,S:签字的集合,K:密钥空间,V,证
实函数的值域，由真、伪组成。
(1) 签字算法,
对每一 M?M和 每一 k?K，易于计算对 M的签
字 S=Sigk(M)?S
签字算法或签字密钥是秘密的，只有签字人掌
握；
(2)验证算法,
Verk(S,M)?{真，伪 }={0,1}
2010-5-14 20
由签字算法产生数字签字
体制的安全性,从 M和其签字 S难于推出 K或伪造一
个 M’使 M’和 S可被证实为真。
与消息加密不同点,消息加密和解密可能是 一次性 的，
它要求在解密之前是安全的；而一个签字的消息可能
作为一个法律上的文件，如合同等，很可能在对消息
签署多年之后才验证其签字，且可能 需要多次验证 此
签字。
Ve r M S S Sig M
S Sig Mk
(,) ( )
( )
? ?
?
?
??
??
真,当
伪,当
2010-5-14 21
数字签字的执行方式
? 直接方式
数字签字的执行过程只有通信的双方参
与，并假定双方有共享的秘密密钥或者
接收一方知道发送方的公开钥。
? 缺点：方案的有效性取决于发方密钥的
安全性。
? 发方可声称秘密钥丢失或被窃
