项目实现:implement the Rho method of reduced SM3
实验内容:该实验设计f函数为\(f: H(x)\),即\(W_i = H(W_{i - 1})\)(除第一次输入信息\(m\)外,f函数输入输出均为256bit)
Polladr rho method to fing collision:利用了生日悖论,使碰撞的复杂度降到\(O(\sqrt n)\)级别,同时能有效避免内存过大
其思想是:利用\(f\)函数随机游走,构造出随机序列,可以发现,该序列发展到一定程度,会得到与之前相同的元素,形成环。因此可以应用到哈希函数中。
如何找环?如何找到进入环的元素(即找到哈希碰撞)?可以通过Floyd判圈法,规定两个指针,其中一个按照序列一步一步走,另外一个两步两步走。当两者相遇时,即找到了一个环,此时找到进入环的元素的两个前驱,即可找到一对碰撞。
如何找到刚进入环的元素?定义两个指针,一个指向初始信息\(m\),另外一个指向上一步两个指针相遇的点\(h\),两个指针都是一步一步走,最后相遇的点即为第一次进入环的点。
值得注意的是,要避免信息\(m\)在环上,因此初始值要大于256bit