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

发布时间：2017-08-16 03:09

  本文关键词：异构模型下彩虹表密码分析算法的改进与实现

  更多相关文章： 彩虹表 密码分析 图形处理器 统一计算架构 HMAC-MD5

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

• 摘要3-5
• ABSTRACT5-12
• 第一章 绪论12-18
• 1.1 研究背景12-14
• 1.2 国内外研究现状14-15
• 1.3 本文的主要工作15-16
• 1.4 本文的内容安排16-18
• 第二章 背景知识18-34
• 2.1 时空折中算法18-25
• 2.1.1 Hellman时空折中算法19-22
• 2.1.2 彩虹表密码分析算法22-23
• 2.1.3 时空折中算法的比较23-25
• 2.2 CUDA并行编程25-31
• 2.2.1 CUDA编程模型25-29
• 2.2.2 CUDA优化方法29-31
• 2.3 HMAC-MD531-33
• 2.4 本章小结33-34
• 第三章 彩虹表密码分析算法的改进34-46
• 3.1 在线阶段34-35
• 3.1.1 执行顺序34
• 3.1.2 实际破解34-35
• 3.2 参数选择与改进35-40
• 3.2.1 度量标准35-38
• 3.2.2 通用方法38-40
• 3.3 改进的表结构40-44
• 3.3.1 RR结构40-41
• 3.3.2 性能分析41-44
• 3.4 本章小结44-46
• 第四章 彩虹表密码分析算法的实现46-60
• 4.1 框架设计46-50
• 4.1.1 离线阶段46-48
• 4.1.2 在线阶段48-50
• 4.2 具体实现50-55
• 4.2.1 归约函数的实现50-52
• 4.2.2 CUDA线程参数52-55
• 4.3 函数实现55-58
• 4.3.1 指令级的优化56
• 4.3.2 内存吞吐优化56-58
• 4.4 本章小结58-60
• 第五章 实验结果与分析60-66
• 5.1 实验环境60-62
• 5.2 对比实验62-63
• 5.2.1 离线阶段62
• 5.2.2 在线阶段62-63
• 5.3 结果分析63-64
• 5.4 本章小结64-66
• 第六章 总结和展望66-68
• 6.1 全文总结66-67
• 6.2 研究展望67-68
• 参考文献68-74
• 致谢74-76
• 攻读学位期间发表的学术论文目录76-78

【相似文献】

中国期刊全文数据库 前10条

1 周文利;;基于依赖网络的告警分析算法[J];桂林电子科技大学学报;2007年06期

2 朱述龙;快速近似主成分分析算法[J];遥感学报;1999年01期

3 马奎俊;韩彦军;陶卿;王珏;;基于核的慢特征分析算法[J];模式识别与人工智能;2011年02期

4 郭亚军;何炎祥;;一种有效的匿名分析算法[J];计算机科学;2007年11期

5 吴龙华,唐洪武,严忠民;数字粒子图像测速中相关分析算法的改进[J];水利水运工程学报;2002年01期

6 曾生根,朱宁波,包晔,夏德深;一种改进的快速独立分量分析算法及其在图象分离中的应用[J];中国图象图形学报;2003年10期

7 董晓梅,于戈;入侵报警模式挖掘分析算法研究[J];东北大学学报;2005年11期

8 胡永刚,乔如良;一个有效的并行分析算法[J];计算机学报;1999年02期

9 季策;于洋;于鹏;;改进的独立分量分析算法[J];东北大学学报(自然科学版);2010年08期

10 罗海丽;;算符优先分析算法的探讨与改进[J];计算机教育;2008年24期

中国重要会议论文全文数据库 前10条

1 乔林;黄维通;汤志忠;;软件流水领域二维数组数据相关性分析算法研究[A];2005年全国理论计算机科学学术年会论文集[C];2005年

2 吴琼;谭松波;张刚;段m#毅;程学旗;;基于图排序模型的跨领域倾向性分析算法[A];中国计算机语言学研究前沿进展（2007-2009）[C];2009年

3 吴t熻，

本文编号：681147