计算机科学论文基于DNA自组装的EIGamal系统破译

　　【摘要】自组装DNA计算在破译密码系统方面，具有传统计算机无法比拟的优势。采用DNA分子瓦编码信息，借助于分子瓦之间的粘性末端进行自组装，通过引入非确定性的指派型分子瓦，提出了用自组装DNA计算破译EIGamal公钥密码系统的非确定性算法。通过创建数以亿计的参与计算的DNA分子瓦，该算法可以并行地以高概率地破译EIGamal公钥密码系统。

　　【关键词】自组装,DNA分子瓦,EIGamal算法

　　1引言

　　密码学算法是多种多样的，利用DNA计算特有的高速并行性和高存储性，人们开始利用DNA计算来实现密码分析和密码加密的技术。与此同时，生物技术获得了飞速的发展，尤其是人类基因组测序计划完成，容易产生大量互异的DNA序列，这诱发了人们利用生物技术的方法对信息进行加密的思想。DNA计算的代数运算、基于表面的DNA计算以及自组装DNA计算等方法已经在理论上解决了一些图论、网络、优化以及密码等问题。目前已有学者提出了基于DNA的加密和解密技术。

　　本文通过深入分析公钥密码系统地特点，给出基于自组装DNA计算的EIGamal公钥密码系统破译方案

　　2EIGamal公钥密码系统

　　对消息M加密，首先要选择随机数k，只要k与p-1互素。然后计算：

　　a=gkmodp

　　b=ykMmodp

　　a和b是密文对。注意密文的大小是明文的两倍。

　　解密a和b时，计算：

　　M=b/ax（modp）

　　因为ax=gkxmodp以及b/ax=ykM/ax=gxkM/gxk=Mmodp都成立，除了y是密钥的一部分以及加密是和yk相乘得来。

　　EIGamal加密：

　　公开密钥p：素数（可由一组用户共享）

　　gy=gx（modp）

　　私人密钥x

　　加密k：随机选择，与p-1互素

　　a（密文）=gkmodp

　　b（密文）=ykMmodp

　　解密M（明文）=b/ax（modp）

　　为了攻破EIGamal公钥密码系统直接的方法是计算离散对数。当所有的因子都是小素数时可以采用Pohlig-Hellman算法。此外可以仿照因子分解算法引入因子库，先计算因子库中素数的离散对数，然后计算期望元素的离散对数，这就是目前最有效的指标计算方法。

　　DNA自组装计算模型是今年来引人关注的计算模型，已有基于自组装模型的二进制加法、乘法、减法和除法。本文利用DNA自组装系统实现了素数p的本原根g连续乘法后于p求模的过程，进而应用于破译EIGamal公钥密码系统。通过PCR和凝胶电泳技术，我们可以得到g的幂次，进而通过减法求模。本模型扩展了DNA自组装计算模型的应用，为求取离散对数提供了新思路。

　　3基于DNA自组装模型的离散对数求取系统

　　瓦片自组装模型是建立在一个方形晶体格上的分子自组装模型，是王氏分子瓦理论的延伸，是包括了特殊生长机制的分子自组装模型。这个模型提供了全新的机制用于解决数学和优化组合中的问题。3.1指数函数系统

　　基于DNA自组装模型的整数模乘排列瓦片系统，其中，S1为整数模乘排列所使用的所有分子瓦集合，这个系统的粘贴强度函数相等，g=1。令这个系统=2，即当一个瓦片的邻域粘贴强度之和等于或者大于2，瓦片才能稳定地粘结到已有的集合上。

　　系统S1是由YuriyBrun提出的乘法系统中延伸而来，使用了28种不同类型的瓦片。着写瓦片都含有两个输入端（一般为瓦片的东和南两个方向），还有两个输出端（一般为瓦片的西和北两个方向）。在我们的指数系统中包括了24种计算瓦片和4种蓝色瓦片来开始计算，如图1所示。

　　让S1={0，1，00，01，10，11，20，21}，g=1，=2，分子瓦片集的定义如图2所示，种子瓦和种子结构的设计如图1所示。这样，系统可以用于计算函数y=gx

　　显然，如果b=Σibi2i，bi∈{0，1}，这里第i位是bi，那么ab可以被写为ab=Σibia2i.那么可以对b的每一位分别相乘，然后再把结果相加。因为二进制乘法比较简单，所以瓦片的设计也较为简单，瓦片的信息从左边演算从右边得到，剩下的事情就是把两两相乘的和相加。系统应该将n个数相加，与两位数的相加不同，可以想象每一行上新加一个新的数字，并且向最后结果处传送。我们让两种不同作用的瓦片相夹产生出新的瓦片集将每一行的结果传递到最后。

　　图1显示的系统S1的的种子结构的建立，这里我们让g=000112。输入g如图中所示被编码在最下面一行和最右边一列上。这是有四个蓝色的瓦片（如图2所示）来处理数和完成刚开始一行的计算。这些瓦片是必需的，因为最少的输入位应为20而且要求没有左转移。红色的瓦片的输入端含有0。这些瓦片都有左转移，但是没有增加总和的能力。绿色和黄色瓦片的输入端都含有1，其中，黄色瓦片的转移位是0而绿色瓦片的转移位是1。每个瓦片，除了粘性末端外还有两个信息标示：下面的信息表示的是2ia的值而上面的信息表示的是目前为止的总和。最上面一行的上面的信息是问题的结果。

　　在种子结构中，如图所示有六种瓦片{0，1，00，01，CT，Str}。注意到在计算开始的时候，只有一个瓦片能与种子结构结合，因为？子=2而且此时只有一个夹角。我们使用瓦片“CT”来使乘法一直进行下去，使用瓦片“Str”用来开始下一个部分中的减法。如图3中的那样，在（x，5）行计算的结果被四种特殊的瓦片读出。

　　图3函数y=gx的组装结果，在（0，5）行设计为“CT”，我们设计了读取瓦片，读出北侧右边的结果，就是我们的乘法结果，CT使乘法继续重复下去；同样地，在行（0，10）=str，同样先使用读取瓦片读出乘法的结果，然后开始求模的过程。乘法重复的次数就是我们要求的函数的解x。

　　3.2求模系统

　　为了求解方程y=gxmodp中的x，我们首先对gx进行计算。由于x是未知的，所以在上一步中我们进行尽可能多的指数计算。然后我们对指数计算的结果对p求模，其结果就是y，我们从组装的结果中提取到正确的y值，然后找出指数计算的次数，就是我们要求的离散对数的值x.在求模系统中，我们利用的是张的减法运算，对指数运算的结果进行连续的减法运算，能得到y的组装就是我们期望的组装结果，我们可以从中读取y、g和我们需要的x值。

　　在指数系统的结果中，我们得到的是尽可能多的gx的值，如图3所示，为了利用张的减法系统进行减法的计算，我们先要将gx的值和p的值合并到同一瓦片上。其中合并系统的瓦片和张设计的减法瓦片如图4所示。

　　让S2={11，10，01，00，0，1，+}，g=1，？子=2，分子瓦片集的定义如图4（a）所示，这样，系统可以自组装成为如图5中的结构，而且组装的时间为（1）。

　　这里，我们使用14种瓦片将两个n位数相结合。很容易设计出一个瓦片系统找出第i行第i个位置。这个系统的主要目的是将两个数结合在一起，然后在顶端显示出结果。S2系统有两种瓦片（如图）浅紫色和深紫色，其中浅紫色瓦片的作用是将信息向上传递而深紫色瓦片的作用是将两个数合并在一个瓦片上。像前面一样，在种子结构中，输入中的一个数被编码在下方，另一个数被编码在最右一列上。

　　让S3={0，1，00，01，10，11}，g=1，？子=2，分子瓦片集的定义如图4（b）所示，这样，系统可以自组装成为独一无的结构，而且组装的时间为（1）。

　　考虑这个分子瓦系统S3，显然在（-1，0）位置上只有一个瓦片能够结合上。以此类推下去，由于？子=2，而bdS（t），bdE（t）又是独一无二的，所以瓦片的组装应该是独特的。这个减法系统的操作逻辑是相同的，包括系统的输入和输出。在DNA瓦片系统模型中，每个瓦片都要从东侧和南侧输入信息，从北侧和西侧输出信息。

　　4结束语

　　在这篇文章中，我们尝试用DNA瓦片建立模型，用自组装攻破EIGamal公钥密码系统。在这个系统中我们使用了48种不同类型的分子瓦。按上所述，第一个子系统使用了33种不同类型的分子瓦，第二个子系统则使用了5种不同类型的分子瓦，而第三个子系统使用了8种不同类型的分子瓦。这时，我们可以说这个系统的瓦片种类与输入呈（1）线性关系。这就使解决EIGamal公钥密码系统成为可能。

　　这个系统的先进性依赖于它的自组装能力。我们需要做的是控制系统作用时的温度和浓度。可以说自组装系统在分子计算方面有超强的控制力，而早期的实验和现在的理论研究都表明自组装有更加广阔的前景。

　　参考文献

　　[1]A.W.OliverPelletier，“Algorithmicself-assemblyofdnatilesanditsapplicationtocryptanalysis，”inProceedubgsoftheGECCO-2002，NewYork，USA，2002，pp.139-146.[2]J.-M.Lehn，“Sopramolecularchemistry，”Science，pp.1762-1763，1993（260）.

　　[3]L.M.Adleman，“Combinatorialoptimizationproblemsinself-assembly，”inProceedingsoftheAnnualACMSymposiumonTheoryofComputing（STOC），Montreal，Canada，2002，pp.23-32.

　　[4]D.C.C.H.G.H.T.F.K.J.R.N.E.R.G.J.S.R.W.HaroldAbelson，DonAllen，“Amorphouscomputing，”CommunicationsoftheACM，vol.43，pp.74-82，2002.

　　[5]Y.Brun，“Arithmeticcomputationinthetileassemblymodel：Additionandmultiplication，”TheoreticalComputerScience378（1），pp.17-31，June2007.

　　[6]——，“Nondeterministicpolynomialtimefactoringinthetileassemblymodel，”TheoreticalComputerScience395（1），pp.3-23，2008.

　　[7]——，“Solvingnp-completeproblemsinthetileassemblymodel，”TheoreticalComputerScience395（1），pp.31-46，2008.

　　[8]Z.C.J.X.G.C.XuncaiZhang，YanfengWang，“Arithmeticcomputationusingself-assemblyofdnatiles：subtractionanddivision，”NaturalScience，vol.19，pp.377-388，2009

　　[9]G.R.ErikWinfree，TonyEng，“Stringtilemodelsfordnacomputingbyself-assembly，”inProceedingsofthe6thInternationalWorkshoponDNA-basedComputers，Leiden，TheNetherlands，2000，pp.65-84.

　　[10]E.Winfree，“Algorithmicself-assemblyofdna，”Ph.D.dissertation，CaliforniaInstituteofTechnology，PasadenaCA，1998.

　　[11]N.C.Seeman，“Dnananotechnology：Noveldnaconstructions，”AnnualReviewofBiophysicsandBiomolecularStructure，vol.27，pp.225-248，1998.

　　[12]C.Mao，W.Sun，andN.C.Seeman，“DesignedtwodimensionalDNAhollidayjunctionarraysvisualizedbyatomicforcemicroscopy，”J.Am.Chem.Soc.，vol.121，pp.5437-5443，1999.

　　[13]C.Mao，T.H.LaBean，J.H.Reif，andN.C.Seeman，“Logicalcomputationusingalgorithmicself-assemblyofDNAtriplecrossovermolecules，”Nature，vol.407，pp.493-496，2000.