异构模型下彩虹表密码分析算法的改进与实现

摘要

密码分析的问题可以通过穷搜索或查表法解决。但是它们分别需要需要大量的时间与存储空间。进而，穷搜索与查表法存在比较大的局限。彩虹表密码分析算法是时间与空间两个维度上的一类折中算法。与前者相比，彩虹表的适用性更广。
　　2003年，Oechslin提出了彩虹表算法，并使用它实现了对Win-dows XP登录系统使用的LM算法的破解。但是，Oechslin没有深入分析预计算所需要的时间。我们发现，在彩虹表的很多应用中，预计算所需的时间仍然在可接受的范围之外。因此，本课题主要动机是减少预计算所需要的时间。近些年来，科学计算领域已经开始大量采用基于中央处理器与图形处理器的异构模型。在所有异构计算解决方案中，NVIDIA的统一计算架构(CUDA)应用最为广泛。新架构给我们带来了新的机遇，与此同时也带来了新的挑战。
　　鉴于彩虹表算法的实际需求以及CUDA异构模型能提供的强大计算能力，本课题基于CUDA异构模型，改进与实现了彩虹表算法。具体而言，本文涉及的主要工作与创新点如下：
　　一、研究彩虹表算法，并提出改进方案。本文分析了在线阶段中，理论研究与工程实现之间的差异。基于此，提出了优化参数选择与改进表结构的方法。优化参数选择侧重在通用性。而改进表结构侧重在一类新的结构。
　　二、研究CUDA编程模型，实现彩虹表算法。本文讨论了CUDA编程的特性与优化方法。首次全面考虑异构模型的引进对彩虹表每一个阶段的影响。与此同时，考虑到图形处理器的特点，本文还讨论了归约函数的实现与线程参数的选择。最后，基于彩虹表与图形处理器的特性，对HMAC-MD5算法的实现提出了改进的方法。
　　三、基于改进与实现，完成了对比实验。基于提出的方案，在多平台上完成了离线与在线阶段的对比实验。通过对比实验，一方面，验证了文章中的一些结论；另外一方面，也验证了与传统的计算模型相比，异构模型下，离线阶段与在线阶段分别只需要410与13的成本。最后，通过深入分析实验结果，我们得出彩虹表的瓶颈在硬件与函数实现。破解的瓶颈则在对链重构上。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 本文的主要工作

1.4 本文的内容安排

第二章 背景知识

2.1 时空折中算法

2.2 CUDA并行编程

2.3 HMAC-MD5

2.4 本章小结

第三章 彩虹表密码分析算法的改进

3.1 在线阶段

3.2 参数选择与改进

3.3 改进的表结构

3.4 本章小结

第四章 彩虹表密码分析算法的实现

4.1 框架设计

4.2 具体实现

4.3 函数实现

4.4 本章小结

第五章 实验结果与分析

5.1 实验环境

5.2 对比实验

5.3 结果分析

5.4 本章小结

第六章 总结和展望

6.1 全文总结

6.2 研究展望

参考文献

致谢

攻读学位期间发表的学术论文目录