将消息m分成k组,即,固定一个RSA密钥(e, n)并定义如下一个Hash函数:hi=(hi-1 modn)异或mi,i为2到k,h1=m1.最后一个分组的输出即是Hash值。试找出上述Hash的一个碰撞。
时间: 2024-04-03 21:30:52 浏览: 337
为了构造一个碰撞,我们需要找到两个不同的消息m和m',它们经过这个Hash函数的计算得到相同的结果。我们可以通过反证法来构造这样的两个消息。
假设我们已经找到了两个不同的消息m和m',它们经过Hash函数的计算得到了相同的结果,即:
hk = hk'
根据Hash函数的定义,可以得到:
hk = (hk-1 xor mk) mod n
hk' = (hk'-1 xor m'k) mod n
由于hk和hk'相等,因此有:
hk-1 xor mk = hk'-1 xor m'k
我们将这个等式代入第k-1个分组的计算中,得到:
hk-1 = (hk-2 xor mk-1) mod n
hk'-1 = (hk-2 xor m'k-1) mod n
将上面的等式代入hk-1 xor mk = hk'-1 xor m'k中,得到:
(hk-2 xor mk-1) xor mk = (hk-2 xor m'k-1) xor m'k
根据异或运算的性质,上面的等式可以简化为:
mk-1 xor m'k = mk xor m'k-1
根据上面的等式,我们可以逐个求出mk和m'k,并由此构造出消息m和m',使得它们经过Hash函数的计算得到相同的结果。
因此,我们找到了一个碰撞,即将m和m'构造为上述方式,可以得到相同的Hash值,从而证明这个Hash函数不是强度碰撞性的。
阅读全文