基于dna自组装eigamal系统破译

《基于dna自组装eigamal系统破译》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、hengYan（LuoHeVocationalCollegeofFoodHenanLuoHe462000）【Abstract】ComputationbytileassemblymodelisanexcellentwayofexecutingparallelDNAcomputingwhereinformationisencodedinDNAtilesandthousandsoftilescanbeself-assembledviastickyendcombination.ThispapershowshowtheDNAself-a

3、ssemblyprocesscanbeusedforbreakingtheEIGamalcryptography.Anon-deterministic10algorithmicisproposedtobreakefficientlytheEIGamalcryptography.BycreatingthousandsofcopiesoftheparticipatingDNAtiles，thealgorithmicwillruninparallelonallpossibleprivatekeys.Thecomputationtak

4、esadvantageofnon-determinism，buttheoretically，eachofthenon-deterministicpathsisexecuted，creatingsolutionintimepolynomialwiththeinputandhighprobability.【Keywords】self-assembly；DNAtile；EIGamalcryptography1引言EIGamal算法既可用于数字签名又可用于加密，其安全性依赖于计算有限域上离散对数的难度。要产生一对密钥，首先选择一素数p

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

6、基于DNA的加密和解密技术。本文通过深入分析公钥密码系统地特点，给出基于自组装DNA计算的EIGamal公钥密码系统破译方案2EIGamal公钥密码系统对消息M加密，首先要选择随机数k，只要k与p-1互素。然后计算：a=gkmodpb=ykMmodpa和b是密文对。注意密文的大小是明文的两倍。解密a和b时，计算：M=b/ax（modp）因为ax=gkxmodp以及b/ax=ykM/ax=gxkM/gxk=Mmodp都成立，除了y是密钥的一部分以及加密是和yk相乘得来。EIGamal加密：公开密钥p：素数（可由一组用户共享）g　

7、　3.1指数函数系统10基于DNA自组装模型的整数模乘排列瓦片系统，其中，S1为整数模乘排列所使用的所有分子瓦集合，这个系统的粘贴强度函数相等，g=1。令这个系统=2，即当一个瓦片的邻域粘贴强度之和等于或者大于2，瓦片才能稳定地粘结到已有的集合上。系统S1是由YuriyBrun提出的乘法系统中延伸而来，使用了28种不同类型的瓦片。着写瓦片都含有两个输入端（一般为瓦片的东和南两个方向），还有两个输出端（一般为瓦片的西和北两个方向）。在我们的指数系统中包括了24种计算瓦片和4种蓝色瓦片来开始计算，如图1所示。让S1={0，1，00

8、，01，10，11，20，21}，g=1，=2，分子瓦片集的定义如图2所示，种子瓦和种子结构的设计如图1所示。这样，系统可以用于计算函数y=gx显然，如果b=Σibi2i，bi∈{0，1}，这里第i位是bi，那么ab可以被写为ab=Σibia2i.那么可以对b的每一位分别相乘