现代密码学-第5章Hash函数与消息认证习题与解答-20091202

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