非平衡r-碰撞问题的高效解决算法

摘要

目前,在非平衡环境下的r-碰撞问题还没有得到有效的解决.本文提出了一种新的高效算法来对r个不同的非平衡函数寻找对应的r-碰撞.新算法是将现有的r-碰撞算法、并行碰撞搜索算法与非平衡中间相遇攻击技术进行有机结合.具体攻击过程如下所示:首先,攻击者把r个函数分成左右两个集合,当r为偶数时,其对应的左右集合分别为■和■,并需要在左右集合中对应位置的两个非平衡函数fli和■之间寻找碰撞.以第i对为例,攻击者在碰撞-收集阶段可以采用PCS算法收集两个非平衡函数fli和fti的2mi个碰撞.注意到,攻击者需要对左右集合中?r/2?个位置对重复上述寻找碰撞的操作.如果r是奇数,攻击者还需要对剩下的函数f收集2m0个函数值.在碰撞-收集阶段之后,攻击者采用中间相遇攻击在r-?r/2?个列表中寻找r-碰撞.新算法的主要结果是:(1)与现有的r-碰撞算法不同,新算法的时间复杂度是由所需存储量和所选择的分组方法决定的.(2)在存储足够的情况下,新的r-碰撞算法的时间复杂度公式为:当r=2k时,时间复杂度为■;当r=2k+1时,时间复杂度为■,其中Rlj表示左集合中实现代价最大的函数的实现代价,Rc表示未配对函数的实现代价,■表示右集合中各函数实现代价.对于r=2k(或r=2k+1),攻击者首先需要找到■(或■,从而求出该情况下的最佳分组方法和最佳时间复杂度.(3)在存储有限的情况下,如果不知道所有分组方法所需的时间复杂度,攻击者就无法得到最佳的时间复杂度.