第11章 杂凑（hash）函数.ppt

第11章杂凑(hash)函数
杂凑函数的定义
定义 一个函数族称为强无碰撞压缩函数族,若下面两个条件成立。
(1)计算hn(x)是容易的,即存在一个多项式时间算法F,若F的输入为1n和,则其输出为hn(x) 。
(2)给定算法F要找两个不同的消息,使得是困难的,即对每一个多项式时间概率算法M’,每一正多项式p(n)和一切充分大的n有()
其中Un表示{0,1}n上的均匀分布随机变量。
定理 若一个函数族为一强单向函数族,则它也是一个强无碰撞压缩函数族。反之,若函数族为一强无碰撞压缩函数族,且对(充分大的)每个n及x∈{0,1}n,hn(x)的原象集中至少包含两个原象,则它也是一个强单向函数族。
强无碰撞压缩函数族中的函数也称无碰撞压缩函数或单向压缩函数。
定义 一个强无碰撞杂凑函数是一个满足下列条件的函数h。
(1)h可应用于任意长的消息或文件;
(2)h的值(杂凑值)是固定长的,但要足够长才能抵抗生日攻击。
(3)计算h的值h(x)是容易的,即h(x)是多项式时间可计算的;
(4)给定算法h,要找两个不同的消息x1≠x2,使其杂凑值h(x1)=h(x2)是困难的(计算不可行的),即是由强无碰撞压缩函数族中的压缩函数所构造的(构造方法见后)。
无碰撞杂凑函数的构造方法
用单向压缩函数构造无碰撞杂凑函数的一般方法
设为一单向压缩函数,其中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)的值由下面的迭代算法定义。
定理 杂凑函数和用来构造它的单向压缩函数有几乎同样的安全性。
用分组加密函数构造杂凑函数
Rabin方案
密码组链接方案
密钥链接方案
用候选单向函数构造杂凑函数
单向函数输出值链接方案
单向无爪函数输出值链接方案
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
HMD5
CV1
128
HMD5
CVq
128
HMD5
CVL-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]表示以字为单位的消息表示。