MD5碰撞攻击中的充要条件集

摘要

通过分析MD5中非线性函数的性质以及模232减差分和异或差分的性质,证明了Liang Jie和Lai Xuejia 给出的产生MD5碰撞的充分条件集中的条件是保证第23～62步的差分路径满足的充要条件,给出了保证第63、64步的输出差分满足的充要条件集.利用得到的充要条件集,提出了对MD5的改进的碰撞攻击算法,该算法的平均计算复杂度约为已有碰撞攻击算法的0.7187倍,并通过实验对该算法的改进效果进行了验证.