杂凑函数的分析方法研究

论文摘要

杂凑函数的分析是目前密码学领域的研究热点之一。由于MD5是重要的杂凑函数之一,故本文对MD5的碰撞攻击算法进行了深入的研究并据此提出杂凑函数抵抗碰撞攻击的设计方法,主要做出了以下几方面的工作:1.分析了模2n减法与循环左移运算可交换的充要条件,指出了Liang Jie和Lai Xuejia给出的总能产生MD5碰撞的充分条件集中的两个条件是冗余的,证明了Yuto等给出的16个冗余条件中的两个并不是冗余的;分析了产生MD5碰撞的充分条件集中条件的相互制约性,指出了Liang Jie和Lai Xuejia提出的快速碰撞攻击算法中存在错误并做出了修正,给出了新的总能产生MD5碰撞的充分条件集,并通过实验对所得结果进行了验证。2.分析了MD5碰撞攻击中的消息修改技术,给出了确保一个链接变量同时满足多个充分条件的方法,指出了新的产生MD5碰撞的充分条件集中Yu Sasaki等提出的多重消息修改技术对其中的两个条件不再实施,并提出了对其中一个的新的消息修改技术;对另外的三个充分条件,本文提出了新的多重消息修改技术,从而将消息的搜索范围扩大为原来的27倍。最后,本文通过实验对所得结果进行了验证。3.分析了MD5算法中非线性函数的性质以及异或差分和模减差分的性质,证明了Liang Jie和Lai Xuejia给出的产生MD5碰撞的充分条件集中的条件是保证第23-62步的差分路径满足的充要条件,给出了保证第63-64步的输出差分满足的充要条件集。利用得到的充要条件集,本文提出了对MD5的改进的碰撞攻击算法,该算法的平均计算复杂度约为已有碰撞攻击算法计算复杂度的0.7187倍,并通过实验对该结果进行了验证。4.深入分析了杂凑函数碰撞攻击算法中用到的差分路径的构造、充分条件集及消息修改技术,并据此提出了杂凑函数抵抗碰撞攻击的一些设计方法。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 杂凑函数的安全性原则
• 1.1.2 杂凑函数的一般攻击方法
• 1.1.3 主要的杂凑函数
• 1.1.4 主要杂凑函数的研究现状
• 1.2 MD5算法的描述及符号说明
• 1.2.1 MD5算法的描述
• 1.2.2 符号说明
• 1.3 王小云等提出的MD5碰撞攻击算法的基本思路
• 1.4 本章小结
• 第二章 产生MD5碰撞的新的充分条件集
• 2.1 产生 MD5碰撞的充分条件集的推导
• 32减差分与异或差分的转化'>2.1.1 模2³²减差分与异或差分的转化
• 2.1.2 差分的传播
• 2.1.3 充分条件的推导
• n减法可交换的充要条件'>2.2 循环左移运算和模2ⁿ减法可交换的充要条件
• 2.3 碰撞攻击的充分条件集的冗余性分析
• 2.3.1 Liang Jie和 Lai Xuejia的充分条件集的冗余性分析
• 2.3.2 Yuto Nakano等指出的两个冗余条件的不冗余性
• 2.4 充分条件之间的制约性分析
• 2.5 产生 MD5碰撞的新充分条件集
• 2.6 本章小结
• 第三章 MD5碰撞攻击的消息修改技术的研究
• 3.1 消息修改技术的介绍
• 3.1.1 单一消息修改技术
• 3.1.2 多重消息修改技术
• 3.2 实施多重消息修改的方法的分类及存在的问题
• 3.3 确保一个链接变量同时满足多个充分条件的方法
• 3.4 对一些充分条件的新的多重消息修改方法
• 3.5 碰撞攻击算法的描述
• 3.6 本章小结
• 第四章 改进的MD5碰撞攻击算法
• 4.1 保证差分路径成立的充要条件集
• 4.1.1 王小云等提出的产生MD5碰撞的差分路径
• 4.1.2 保证差分路径成立的充要条件集
• 4.1.2.1 MD5中的非线性函数的性质
• 4.1.2.2 保证第23-64步的输出差分成立的充要条件集
• 4.2 改进的碰撞攻击算法及计算复杂度分析
• 4.2.1 改进的碰撞攻击算法
• 4.2.2 改进的碰撞攻击算法与现有算法的计算复杂度比较
• 4.3 本章小结
• 第五章 对抗碰撞攻击的设计方法研究
• 5.1 差分路径构造技术分析
• 5.2 充分条件集的分析
• 5.3 消息修改技术分析
• 5.4 与代数方程求解的关系
• 5.5 本章小结
• 第六章 结束语
• 参考文献
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢