4.6
mm假定f:{0,1}?{0,1}是一个原像稳固的双射。定义
h:{0,1}2m?{0,1}m如下：给定x?{0,1}，记
x?x'||x''
2m其中x',x''?{0,1}m，然后定义
h(x)?f(x'?x'')
证明：h不是第二原像稳固的。 解：
由于x?x'||x''，不妨这样构造第二原像：取x1?x''||x' ，显然
x1?{0,1}2m且
x1?x，因为
x'?x''?x''?x'故
h(x1)?f(x''?x')?h(x)?f(x'?x'')，得证。
4.9假定
h1:{0,1}2m?{0,1}m 是一个碰撞稳固的Hash函数。
(a)定义 h2:{0,1}4m?{0,1}m 如下：
2m4m 1、将 x?{0,1} 记为 x?x1||x2 ，其中 x1,x2?{0,1} 。
2、定义 h2(x)?h1(h1(x1)||h1(x2)) 。 证明：h2 是碰撞稳固的。
(b)对整数 i?2 ，从 hi?1 递归定义Hash函数 hi:{0,1}2m?{0,1}m
i如下：
1、将 x?{0,1}2im 记为 x?x1||x2 ，其中 x1,x2?{0,1}2i?1m 。
2、定义 hi(x)?h1(hi?1(x1)||hi?1(x2)) 。 证明： hi 是碰撞稳固的。
解：
(a)对于函数h2(x)，x?h1(x1)||h2(x2)，而且h1(x1),h2(x2)?{0,1},
2m2mm故 h1(x1)||h2(x2)?{0,1}，因为h1:{0,1}?{0,1}是碰撞稳固的，
m所以h2 是碰撞稳固的。 (b)利用归纳法来证明：
当i?1时，由(a)可知成立；
当i?2时，假定hi-1是碰撞稳固的，则对于函数hi(x)，
x?hi?1(x1)||hi?1(x2)，而且hi?1(x1),hi?1(x2)?{0,1}m,故
hi?1(x1)||hi?1(x2)?{0,1}2m，因为h1:{0,1}2m?{0,1}m是碰撞稳固的，
所以hi 是碰撞稳固的。
4.10在这个习题中，我们考虑Derkle-Damgard结构的一个简化版本。
1}m?t?{0,1}m,其中 t?1 ，假定x?x1||x2||...||xk 假定compress:{0，其中 |x1|?|x2|?...?|xk|?t ，我们研究下面的迭代Hash函数：(函数略)，假定compress是碰撞稳固的，进一步假定compress是零原像稳固的，也就是说，难以找到满足compress(z)?0的z?{0,1}mm?t。在
这些假设条件下，证明：h是碰撞稳固的。 解：
假定可以找到x?x'使得h(x)?h(x')，现在说明可以在多项式时间内找到compress的碰撞。
令 x=x1||x2||...||xk
x'=x1'||x2'||...||xl'，由题意可知
compress(gk-1||xk)=gk=h(x)=h(x')=gl'=compress(gl-1'||xk') 显然满足条件|x|≠|x'|(modt)，因为xk≠xk'，所以找到了h的一个碰撞。