遗传算法在密码分析中的应用研究

论文摘要

遗传算法是一种具有全局搜索功能的优化算法,其思想起源于生物学中达尔文的“适者生存”自然选择理论。它的运算并行性好、简单易行、可操作性强,因此得到了广泛的应用。本文的目的就是通过将遗传算法与密码分析中的密钥搜索相结合,设计出能够破译Vernam密码的实用程序,从而也能够证明遗传算法的高效大规模搜索性能。本文共分为4个部分:第一部分首先介绍了生物学中关于进化论的一些基本知识,然后引申出遗传算法的思想来源、基本流程以及发展过程和本身的特点,并通过实际的例子做了说明。第二部分主要讲述遗传算法的数学理论基础,重点是模式定理的证明及分析,然后详细介绍了设计和实现的方法,包括将其在密码分析中的应用也做了初步的分析和设计。第三部分提出了一个能够破译密钥为8字节字母组合的Vernam密码的程序总体设计以及详细设计方案,对其中所要用到的常量、变量和成员函数都做了数值和性能上的规定,接着展示了一些成功破译的密钥搜索结果,证明了遗传算法在密钥搜索中的优秀表现。第四部分则是通过多次实验对设计出来的程序做一些参数上的分析比较,进一步验证遗传算法各个参数的效用,还得出了一些较优的参数组合,最后还尝试破译了更长的密钥以测试程序的性能。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 引言
• 1.2 生物进化的基本知识
• 1.3 遗传算法简介
• 1.4 遗传算法的发展与特点
• 1.5 本文的工作
• 2 遗传算法与密码分析
• 2.1 遗传算法的数学基础理论
• 2.1.1 模式定理
• 2.1.2 隐含并行性
• 2.1.3 基因块假设
• 2.1.4 欺骗问题
• 2.2 遗传算法的设计与实现方法
• 2.2.1 编码方法
• 2.2.2 群体设定
• 2.2.3 适应度函数
• 2.2.4 遗传算子
• 2.2.5 选择参数
• 2.3 遗传算法在密码分析中的应用
• 3 应用遗传算法破解VERNAM 密码
• 3.1 VERNAM 密码简介
• 3.2 破解VERNAM 密码的遗传算法设计
• 3.2.1 总体设计
• 3.2.2 详细设计
• 3.3 破译过程及结果展示
• 4 破译结果对比与分析
• 4.1 初始群体数量的影响
• 4.2 适应度阈值的影响
• 4.3 变异概率的影响
• 4.4 优化参数组合
• 4.5 增加密钥长度的破译分析
• 5 总结与展望
• 参考文献
• 致谢
• 攻读学位期间发表的论文