第5章 Hash 函数与消息认证
习题及参考答案
1. 指出强抗碰撞H ash 函数与弱抗碰撞H ash 函数之间的区别。
答：弱抗碰撞H ash 函数是任给一个消息x,寻找另一个不同的消息x ，
使得他们的H ash 函数值相等是不可行；强抗碰撞Hash 函数是同时寻找两个不同的消息使得他们的Hash 函数值相等是计算上不看行的，可以看出强抗碰撞Hash 函数一定是弱抗碰撞的。
2. 考虑Gibson Hash 函数h 。
设p 、q 是两个素数，N =p ⨯q ，g 是(Z N )*的生成元。
N 作为公钥，p 与q 作为签名者的私钥。
对任意消息m ，其摘要定义为：
h (m )= g m mod N 。
(1) 令N =4897，g =2231。
分别计算消息m =132748，m '=75676的摘要。
(2) 证明：如果得到了两个碰撞的消息，那么就可以求出N 的分解。
(3) 证明：如果得到了N 的分解，那么就可以找到碰撞的消息。
解：(1)由h (m )= g m mod N 。
所以h (132748)=2231
132748
mod4897=2611 h(75676)=2611
(2)证明：若h (m)= h (m ')则有g m mod N= g m ' mod N
假设 N 的分解为 N=p*q 所以代入 然后根据中国剩余定理可以解得 p ，q 。
3. 设p 是一个素数，g 1、g 2是(Z p )*
的两个生成元，使得离散对数
p g g mod log
21
的计算是困难的。
对任意消息m =(m 1, m 2)，定义H ash 函数h 的摘要为：
p g g m m h m m mod ),(2
1
2
1
21⨯=。
(1) 设p =65867，g 1=11638，g 2=22770。
分别计算消息m =(33123, 11789)，m '=(55781, 9871)的摘要。
(2) 证明：求解H ash 函数h 的碰撞等价于计算离散对数p g g mod log
21。
解：(1)由p g g m m h m m mod ),(2
1
2121⨯=并把题中数据代入公式中 得 h(33123,11789)=56381 h （55781，9871）=15899
(2)证明：求解Hash 函数h 的碰撞，即寻找m 和m '，使得)'()(m H m H =，也即
使得：p g g p g g m
m
m m mod mod '
2
'
12
1212
1⨯=⨯
两边同时在关于模p 求以1g 为底的对数，整理后得到：
p g m m m m g mod log
)'()'(2
22111
-=-，
这里就涉及到计算离散对数p g g mod log 21。
因此，求解H ash 函数h 的碰撞等价于
计算离散对数p g g mod log
21。
4. 设H 1是一个从(Z 2)2n 到(Z 2)n 的Hash 函数，这里n ≥1，Z 2={0, 1}。
对任意整数i ≥2，按下述方式定义一个从n
i
22)
(Z 到(Z 2)n 的H ash 函数H i ：
对任意n i
x 22)(Z ∈，设
x = x 1||x 2，
其中n
-i x x 1
2
221)
(Z ,∈，定义
H i (x )= H 1(H i -1(x 1) || H i -1(x 2) )。
假设H 1是强抗碰撞的。
试证H i 也是强抗碰撞的。
证明：根据定义))(||)(()(21111x H x H H x H i i i --=， 以此类推：))(||)(()(122112111x H x H H x H i i i ---=， ……
))(||)(()(121111111112 x H x H H x H =。
我们不妨假设i H 不是强抗碰撞的，则找得到'x 和已知的)(x H i 碰撞，即有
)'()(x H x H i i =，根据以上推导，可以找到1H 的一对碰撞111' x 和111 x ，这与1H 是
强抗碰撞是矛盾的。
因此，如果H 1是强抗碰撞的那么H i 也是强抗碰撞的。
5. 考虑用公钥加密算法构造Hash 函数。
假设使用公钥加密算法RSA ，首先将消息进行分组；用RSA 加密第一个分组；将加密结果与第二个分组作异或，再对其进行加密；一直进行下去。
例如，如果消息M 被分成二个分组B 1和B 2，则其H ash 值为H (B 1,
B 2)=RSA (RSA(B 1)⊕ B 2)。
证明对任一分组
C 1，可找到分组C 2，使得H (C 1, C 2)=H (B 1, B 2)。
进一步证明用这种攻击方法，可攻击该Hash 函数。
证明：
我们先来证明可以找到2C ，使得在已知1C 的情况下使得),(),(2121B B H C C H =。
在RSA 密码体制下，设加密密钥是e 。
则),(),(2121B B H C C H =即为
e
e
e e
B B
C C )()(2121⊕=⊕，我们这里不妨令2121B B C C e
e ⊕=⊕， 则e
e C B B C 1122⊕⊕=，这里的2C 总是能找到的，并且它就满足题目要求，使得H (C 1, C 2)=H (B 1, B 2)。
在多个分组的情况下，利用证明的方法，总是能找到满足要求的分组消息，即实现对该H ash 函数的攻击。
6. 参考利用分组密码构造H ash 函数的方法，试利用公钥加密算法RSA 构造一个Hash 函数，并分析其安全性能。
解：上题即是一个基于RSA 算法构造的H ash 函数，其安全性不能好，在实际应用中必须加以改进。
7. 设E k 是一个分组长度为n 的分组密码的加密算法，密钥为k 。
假设密钥长度也为n 。
对于任意消息x ，首先对x 进行分组，每组长度为n 。
如果x 的长度不是n 的倍数，则在x 的最后适当添加一些数据使得x 的长度恰好是n 的倍数。
设
x = x 1 x 2…x l ，
其中x i ∈GF(2)n (1≤i ≤ l )。
任选IV ∈GF(2)n 作为初始向量，令y 0=IV ，按下面四个不同的公式分别计算y i (1≤i ≤ l )，最后定义H (x )= y l 。
试分析四个H ash 函数H 的安全性。
,)(,)(1-⊕⊕=⊕=i i i k i i i k i y x x E y x x E y
.
)(,)(111---⊕⊕⊕=⊕⊕=i i i i k i i i i k i y x y x E y x y x E y
解：H ash 函数一的安全性依赖于分组密码加密的安全性。
Hash 函数二的安全性依赖反馈序列的安全性和分组加密的安全性。
Hash 函数三的安全性依赖于加密密钥的复杂度。
Hash 函数四的安全性依赖于序列的安全性以及加密密钥的安全性。
8. 为什么在密钥公开的条件下，基于分组密码的CBC 工作模式和CFB 工作模式的Hash 函数H 是不安全的？对于任意给定的消息x ，试寻找一个与x 不同的消息x '，使得H (x ')=H (x )。
答案参见第5题。
9.实现MD5-MAC，设密钥K=“001122…99aabb…ff”。
分别对消息x=“”，“abc”，“abc…xyz”，求出MD5-MAC(x)。
答略
10.对于SHA，计算W16，W17，W18和W19。
答略
11.用高级语言编写实现SHA-1算法的程序。
略。