MD5选择前缀碰撞算法的改进及复杂度分析

摘要

针对MD5选择前缀碰撞算法在实际应用时复杂度分布的失衡问题,提出了改进的MD5选择前缀碰撞算法.结合非相邻表示型(NAF),给出了生日搜索复杂度中概率值在特定条件下的推导方式,建立了平衡参数与生日搜索复杂度之间的关系;并基于上述理论结果,通过引入新的消息差分,改进了选择前缀碰撞所需的生日碰撞形式,得到改进算法.在实际应用所需的参数条件下,改进算法相对MD5算法平均可降低1比特的复杂度.分析结果表明:相对于原MD5算法,改进算法缓和了复杂度分布的失衡现象,降低了算法复杂度,更适用于实际应用.