内容发布更新时间 : 2024/12/22 18:11:14星期一 下面是文章的全部内容请认真阅读。

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的一个碰撞。