DNA计算在密码学上的应用

《DNA计算在密码学上的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、effectininformationfieldinthefuture．摘要Keyword：DNAcomputation；cryptology；knapsackproblem；dichotomy独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或证书而使用过的材料。与我～同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名蛆同期：彬．，关于论文使用授权的说明本人完全了解北京工业大

2、学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。(保密的论文在解密后应遵守此规定)躲塑耻翩虢仫经同期醴丝夕第l章绪论第1章绪论1。1DNA计算的发展以及研究现状随着现代计算机科学技术的发展，人们一直在追求一种计算速度更快、体积更小的计算机。1956年，理查德·冯纽曼就曾经充满幻想的描述了构建一台“亚显微”计算机的可能性。目前，尽管计算机在提高计算的速度、容量和性能上已经取得了巨大的进步，但“亚显微”计算机的目标还远远没有实现，不少计算科学的研究者难在这些方面

3、进行着不懈的努力，并取得了一些初步的成果，影响了计算科学的发展。1994年，美国南加州大学的Adleman教授在Science上发表了第一篇DNA计算的论文【Il，解决了NP问题的一有向哈密顿路径问题，开创了计算科学的一个新领域。DNA计算的研究属于生物、化学、数学等学科的一个交叉领域，其研究内容所涉及的范围很广。很快DNA计算吸引了大量的计算机、数学、生物学以及化学研究者的目光，越来越多的研究者投身到这一研究领域中。在Adleman等人的工作的基础上，最近几年里在这门学科上不断出现许多创新成果，人们正逐渐发现DNA计算的内在规则，创造出一些DNA计算的方法和模型。DNA

4、计算的～些代数运算、基于表面的DNA计算以及DNA自装配计算等方法可用于在理论上解决一些图论、网络、优化以及密码等问题。逻辑和算术运算是DNA计算中一个很重要性的研究问题，1995年，Beaver提出了用DNA分子插入和缺失的方法[401，来实现DNA计算机的逻辑和算术运算[4”。96年Guamieril6j等人实现了用DNA计算来作加法。1999年，JohnS．Olilver提出了矩阵乘法的DNA计算方法【7’叭。后来Boneh等人用动态规划方法解决了图可达性的背包问题f91；Leete等人解决了符号决定性问题1101；N。Jonoska等人解决了道路染色问题⋯l；以及

5、超标量计算机代数问题【121等等。在神经网络方面，贝尔实验室的A．P．Mills，Jr．B．Yurke，PM．Platzman．提出了模拟神经网络模型的DNA计算方法1131。DNA计算的表面基方法1421是在1996年提出的，它的优越性在于能够方便地实现自动操作。2000年Nature刊载了Qin曲uaLiu的文章㈣，标志着表面上的DNA计算正在逐步完善，现在DNA计算的表面基方法越来越得到广泛的应用。北京J=业大学理学硕士学位论文DNA自装配计算方法是DNA计算的一种重要方法，Winfree对DNA自装配计算的发展作出了重要贡献，他的关于二维DNA格的设计和自装配的论

6、文12】奠定了自装配计算方法的基础，后来自装配计算成为DNA计算一个重要的计算方法，ChengdeMao等人的论文用DNA三螺旋分子的自装配来实现加法和逻辑异或运算【3l'AshishGehani和tHLabean等人把这种方法用于密码学领域，提出了一种基于一次性密码本的DNA加密和解密方法【4l。日本的KensakuSakamoto等人提出的发卡状计算模型解决可满足性问题【5】，也是建立在分子自装配的基础上的。由于DNA计算的高度并行性和DNA的密集的储存信息的能力，这使得DNA计算非常适合解决密码问题，Lipton和DanBoneh最早在这一领域进行了研究，96年他们

7、给出了使用分子计算机破译DES的方法[341，在此基础上Adleman等人又给出了使用sticker模型破译DES的方法【361，AshishGehani和T．H．Labean等人提出了一种基于一次性密码本的DNA加密和解密方法14I，此外AndreLeier等人还给出了使用DNA二进制串进行加密和解密的方法【4"。DNA计算在密码学上的应用必然对信息领域的发展产生巨大影响。我们也把目光投向了密码学上背包公钥密码体制中背包密码的破译问题，并且找到了两种解决背包问题的有效算法，特别是二分法能较好地降低计算的时间和空间复杂度。DN