学位论文 > 优秀研究生学位论文题录展示

分组密码与图论中的DNA算法研究

作　者: 耿修堂
导　师: 许进
学　校: 华中科技大学
专　业: 系统分析与集成
关键词: 难计算问题 DNA计算分组密码 IDEA DES 最大团问题 Ramsey图
分类号: O157.5
类　型: 博士论文
年　份: 2008年
下　载: 234次
引　用: 0次
阅　读: 论文下载

内容摘要

计算复杂度由计算时间复杂度和计算空间复杂度组成。算法对时间的需要量称为算法的时间复杂度;算法对空间的需要量称为算法的空间复杂度。现实生活中存在许多难计算问题,使用传统的电子计算机求解这些难计算问题通常需要指数的计算时间。既然传统的电子计算机求解这些难计算问题显得无能为力,那么就有必要提出一种新的计算方法。已经有十几年发展历史的DNA计算正是在这样的背景下产生的。高度的并行计算处理、极大的空间存储密度是DNA计算的两大突出优点。DNA计算正是凭借这两个优点,使用天然的空间优势,通过高度的并行计算处理,发挥着它的巨大计算潜能。从某种意义上说,这种计算潜能是传统的电子计算机所无法比拟的。论文以分组密码与图论中的几个难计算问题为研究对象,展开了基于粘贴模型、剪接模型的DNA算法研究、设计与分析。破译分组密码国际数据加密算法或破译数据加密标准都是难计算问题,同时,二进制串逻辑运算是分组密码算法中频繁使用的运算。论文设计了一个二进制串循环左移运算的DNA粘贴算法;然后,提出了一个二进制串异或运算的DNA粘贴算法;并且结合两个具体实例,对粘贴算法过程进行了详细地描述;最后,对所提算法进行了复杂性分析,分析结果表明DNA计算用于破译分组密码具有可行性。论文设计了一个破译国际数据加密算法的递归式DNA剪接算法。该算法首先对国际数据加密算法的异或、加模、乘模运算进行了DNA剪接算法设计;然后,对国际数据加密算法的8轮迭代采用了递归方式并行计算处理,控制了生成链的长度,降低了DNA操作的难度。同时,论文设计了一个破译数据加密标准的递归式DNA粘贴、剪接算法。首先,该算法使用递阶方式生成了完备的初始密钥,保证了算法的理论成功率为百分之百;然后,使用同样的方式对数据加密标准的16轮迭代采用了递归处理,控制了生成链的长度,降低了DNA操作的难度,提高了算法的可靠性。求解最大团问题或构造对角Ramsey图也是两个难计算问题。使用穷举搜索算法来解决这两个问题,必然导致计算量的指数爆炸,穷举搜索DNA算法也不例外。论文设计了一个求解最大团问题的递阶法DNA粘贴、剪接算法。该算法使用递阶方式的并行计算处理,利用分层剪枝法来分离问题的非解,最终删除这些非解,在一定程度上缓解了算法的空间计算量的指数爆炸。同时,论文提出了一个构造对角Ramsey图的递阶法DNA粘贴、剪接算法。该算法通过逐个添加顶点的递阶方法,逐步删除了问题的绝大部分非解,在一定程度上缓解了问题解空间的指数爆炸。特别地,专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算量分析,分析结果充分地肯定了该算法的有效性。

全文目录

摘要  4-6
ABSTRACT  6-10
1 绪论  10-20
  1.1 研究背景  10-11
  1.2 研究现状  11-14
  1.3 研究思路  14-16
  1.4 研究内容  16-18
  1.5 论文创新点  18-20
2 DNA 计算的理论基础  20-29
  2.1 DNA 的结构  20-21
  2.2 DNA 的操作  21-24
  2.3 剪接模型简介  24-27
  2.4 粘贴模型简介  27-29
3 分组密码中两种位操作的DNA 粘贴算法  29-41
  3.1 引言  29-30
  3.2 循环左移操作的DNA 粘贴算法设计  30-35
  3.3 异或操作的DNA 粘贴算法设计  35-38
  3.4 算法分析  38-39
  3.5 总结  39-41
4 破译IDEA 的递归式DNA 剪接算法  41-60
  4.1 引言  41-42
  4.2 IDEA 的介绍  42-44
  4.3 IDEA 的安全性讨论  44
  4.4 破译IDEA 的递归式DNA 剪接算法设计  44-57
  4.5 复杂度分析  57-58
  4.6 总结  58-60
5 破译DES 的递归式DNA 算法  60-77
  5.1 引言  60-62
  5.2 DES 的介绍  62-63
  5.3 DES 的安全性  63-64
  5.4 破译DES 的递归式DNA 算法设计  64-74
  5.5 复杂度分析  74-75
  5.6 总结  75-77
6 求解最大团问题的递阶法DNA 算法  77-88
  6.1 引言  77-78
  6.2 最大团问题  78-79
  6.3 最大团问题的递阶法DNA 算法设计  79-82
  6.4 实例分析  82-86
  6.5 算法分析  86-87
  6.6 总结  87-88
7 构造对角 Ramsey 图的递阶法 DNA 算法  88-101
  7.1 引言  88-91
  7.2 递阶法粘贴、剪接算法  91-92
  7.3 构造对角 Ramsey 图的 DNA 算法设计  92-98
  7.4 算法分析  98-99
  7.5 总结  99-101
8 总结与展望  101-104
  8.1 全文总结  101-102
  8.2 尚待研究的工作  102-103
  8.3 后期研究困难总结  103-104
致谢  104-106
参考文献  106-118
附录1 攻读博士学位论文期间发表论文目录  118-120
附录2 博士学位论文章节内容与博士期间发表论文的关系  120-121
附录3 攻读博士学位期间参加的科研课题  121-122
附录4 攻读博士学位论文期间获得的奖项  122

相似论文

DNA自组装模型在组合优化问题中的应用研究,TP399-C8
基于多信息融合技术的安检信息系统研究,V328.3
DES_RSA混合加密以及传输实现,TP309.7
基于Winsock的C/S模式即时通信系统的设计及实现,TN914
河北省高校教师资格认定考试信息系统研究与设计,TP311.52
DNA计算机中数据结构的设计与研究,TP311.12
用于文档加密的Rijndael算法研究,TP309.7
DNA计算中若干问题的研究,TP301
分组密码抗差分攻击分析技术研究,TN918.2
混沌网络文件密码系统研究,TN918.2
边界扫描测试与故障诊断系统开发,TN607
西方法治理念对我国社会主义法制观教育的双重影响,D920.0
（X+K）mod2~n加密环节的性质及其在数据库加密中的应用研究,TP309.7
DNA计算中若干理论的研究,TP301.6
基于0-1规划的DNA计算模型的设计与实现,TP3
分组密码的关键组件检测及实际安全性研究,TN918.1
DES密码算法的彩虹攻击技术及其GPU实现,TN918.1
分组密码扩散结构的构造与分析,TN918.1
分组密码的差分故障分析,TN918.1
冠脉多支病变在糖尿病患者中血运重建策略疗效的meta分析,R587.1
遗传算法在DNA计算中的研究与应用,TP18