题目：DNA计算模型设计、软件分析及其对密码攻击的应用

DNA计算由美国科学家Adleman于1994年创立，它是以DNA和相关生物酶为基本材料、利用一些生物化学反应来实现计算的一种分子计算方法，实现DNA计算的装置与实验技术则称为DNA计算机。DNA计算机与传统的电子计算机相比具有超高并行计算能力、海量存储密度与极少耗能三大优点，它与量子计算机、人工神经网络计算机、光子计算机一起被作为未来计算机的候选者，而DNA计算机的前景最被科学家看好。本文首先综述了DNA计算的发展历史，简述了六种已有的DNA计算模型，接着设计了一种基于粘附子模型的攻击分组密码的DNA算法与基于DNA自动机的素性测试法，随后提出了一种新的DNA计算模型，并采用这种模型对公钥密码体制进行了攻击，最后分析与研究了DNA计算机的软件内涵与特点。本论文的主要工作与研究成果如下：1．为了有效地应用DNA计算攻击公钥密码体制，提出了一种新的DNA计算模型：并类计算模型。这种模型根据数据在算法运行中的不同变化对数据进行分类，属于同一种类的数据均用同一段存储链来编码，通过在该段存储链两端添加的碱基序列来标志它所编码的数据种类，无论每类数据的数据量多少，同类数据都可通过拼接运算进行替换，故数据可以反复使用，即数据具有极佳的可移动性。2．针对分组密码的加密特点，提出了一种用DNA计算攻击分组密码的方案，详细给出了基于DNA计算的粘附子模型攻击国际数据加密算法（IDEA，一种分组密码）的方法，该方法使用已知明文攻击，采用DNA储存链编码各种可能的密钥与已知明文，通过组合、分离、设置、清除四种操作筛选出密钥，由凝胶电泳确定密钥的具体值。该攻击方法所需的数据量仅为一组明文密文对，时间复杂度为O(n2)。论文还论证了所提方法相应生物化学实验的可行性。该方法的最大优点在于用粘附子装置实现模乘运算时，充分发挥了DNA计算的并行性，计算多组乘法运算与计算一组乘法运算所需的时间相同，并且多组乘法运算能在一个试管内开始，而国外已有的工作做不到这一点。3．通过构造法证明了有穷自动机的计算能力能满足整数素性测试的要求，在此基础上设计了一种能实现素性测试法的DNA有穷自动机，详细给出了这种DNA有穷自动机的构造方法，该有穷自动机的状态用DNA单链分子编码，输入用DNA双链分子编码，状态转移规则用带环的双链DNA分子编码，状态的转移通过限制性内切酶的切割反应实现。所设计的方法不仅能判断一个大整数是否是素数，还能用于大数的素因子分解，实验实现容易，所需的时间是输入的多项式函数而不是指数函数。本文还论证了所提方法相应生物化学实验的可行性。该方法的最大优点在于它是基于有穷自动机这种计算能力极其有限的计算模型。4．针对当今主要的公开密钥加密体制的攻击都是基于分解一个大数的问题，提出了基于DNA计算的公钥密码体制攻击方案，设计了基于DNA计算的并类计算模型的RSA公钥密码的攻击算法，该算法采用DNA分子编码陷门库与公钥，通过组合、设置、分离、清除等操作筛选出陷门，由电泳确定陷门的值，再用陷门计算私钥的值。该方法所需的时间为O(log2n)3(n是公钥的长度)，所使用的DNA的体积不超过1立方米。论文还论证了所提方法相应生物化学实验的可行性。5．通过类比法分析出DNA计算机的软件就是能完成某一任务的若干用碱基序列编码生物操作种类与操作数种类的DNA分子的集合，编制DNA计算机的软件就是设计能描述算法的DNA分子的碱基序列与结合方式，DNA计算机的机器语言是由碱基组成的代码。本文还阐述了DNA计算机软件的详细内涵、特点以及如何编制DNA计算机软件的一般规则，从可行性与完全性的角度提出了一套DNA计算机的基本操作，论证了这套基本操作在计算上的完全性，阐明了DNA计算机的两种程序设计语言的特点与使用方法，提出能描述操作种类与操作数种类的DNA分子是DNA计算机的分子指令，详细分析了各种分子指令的结构，探讨了DNA软件的设计与生产过程。