【作者】 陈智华；

【导师】 许进；

【作者基本信息】 华中科技大学 ， 系统分析与集成， 2009， 博士

【摘要】 密码分析和密码设计是信息安全领域最重要的组成部分，它的发展关系到国家安全、经济安全和金融安全等多个方面。现代密码系统的安全性是建立在密钥搜索的指数增长时间复杂度上，而新兴的DNA计算具有超大规模并行性、高密度存储和低能耗等特性，不仅对传统密码安全提出了挑战，同时也为海量信息存储提供了新的存储和加密模式。实验已经证明DNA分子自组装是一种自底向上进行纳米尺度计算的有效机制。1维和2维的自组装作为DNA计算的工具，其并行计算能力已经得到认可，并得到了大量的研究。已经证明1维线性自组装具有正则语言的计算能力，而二维自组装的计算能力是图灵等价的。基于这样的背景，本文以DNA计算中的Tile自组装模型为核心，密码问题为主要研究对象，对DNA计算Tile自组装模型在密码中的各种应用及其有效性进行了探索研究，设计并实现了基于DNA计算Tile自组装的密码系统和密码算法破译模型，定量分析了DNA计算用于密码分析和数据加密的有效性、时间复杂度、空间复杂度。本文主要创新内容如下：首先，实现了基于DNA计算的一次一密密码系统。本文针对DNA计算的并行性和海量存储能力，使用DNA计算中的Tile自组装模型设计实现一次一密密码系统，为海量数据信息的加密存储和传输提供了新的方法。该密码系统包括加密子系统、密文提取子系统、密钥计算子系统和解密子系统，这四个子系统组成了一个完整的密码系统。同时使用已有的生物技术，实现了秘密密钥的安全传输。所有的子系统的Tile类型复杂度为（?）（1），计算时间复杂度为（?）（n）。最后，对该一次一密密码系统的安全性进行了分析，表明基于Tile模型和生物技术实现的密码系统可以保证海量数据的存储和传输安全。第二，基于自组装模型的编程能力，设计了使用自组装模型破译Diffie-Hellman算法的方法。首先根据g mod p，g² mod p，…，g^p-1mod p得到的整数值构建计算Tile，完成整数排列的自组装Tile系统。这里p为素数，g为这个素数的原根。通过PCR和凝胶电泳，可以读出不同的整数对应的g的幂次，即g的离散对数值。通过这样的方法，可以威胁到Diffie—Hellman密钥交换的安全。整个系统使用（?）（p）种Tile类型和（?）（p）的组装时间来完成整数的排列。这个模型对于有限位数的Diffie-Hellman算法是有效的。但是由于Tile种类与输入位数线性相关，因此限制了破译Diffie-Hellman算法的规模。然后，本文利用DNA计算自组装模型的封装编程能力，设计了除法自组装模型，并且充分利用DNA计算分布式并行计算优势，在除法自组装模型中嵌入除数生成系统，构建了非确定性大数分解自组装模型，用于解决大数分解问题。该模型的Tile种类复杂度为（?）（1），时间复杂度为（?）（n²）。该DNA计算实验允许至少10¹⁸个除法自组装系统同时进行运算，这些除法系统具有相同的被除数，但是除数是系统随机生成，各不相同。为解决除法完成后商的检测问题，在非确定性大数分解自组装模型中嵌入了判别余数是否为零的判断系统，该系统能够在大量结果中标记出能够整除被除数的除数，通过标记提取出对应的除数和商，完成大数分解。最后分析了这个非确定性自组装Tile模型能成功搜索到目标除数的概率，并且证明了通过增大参加运算的DNA分子的量可以使该概率接近于1。以目前的生物技术，该模型完全可以解决2⁵⁶位的大数分解。进一步，利用自组装自底向上的编程能力和封装能力，设计实现了基于自组装模型的DES和3DES加密算法。通过对DES算法中的轮函数，包括置换、交换、异或等进行封装和巧妙级联，实现了轮函数的循环调用。为了可以使用已知明文-密文对攻击的方法实现DES算法的破译，在DES算法模型中嵌入了主密钥生成系统，利用自组装的并行计算能力可以同时随机生成各不相同的主密钥对已知明文进行加密。本文以简化DES（SDES）作为模版，详细解释了各个函数的设计思想和方法，然后扩展到标准DES和3DES算法上。在已有的加密算法模型上，嵌入主密钥生成系统，随机生成主密钥，利用DNA计算的并行性，使用已知明文-密文攻击方法破译SDES、DES和3DES。最后分析了生物技术的误差率与成功破译DES和3DES加密算法的关系。从结果可以看到，随着生物技术的进一步提高，误差率的减小，自组装模型完全可以使用已知明文-密文攻击方法成功破译DES和3DES算法。最后，利用DNA芯片并行计算和荧光显像的特性，使用DNA生物芯片技术、杂交和酶切构建了XOR函数，并且应用这个技术分析DES算法中S盒子的抗差分密码分析能力。利用荧光图像，可以快速有效地评估S盒子异或输出的统计分布，从而实现对S盒子的抗差分密码分析能力的判断，为改进DES安全性提供了依据。更多还原

【Abstract】 Cryptanalysis and encryption system are related to national security and financialsecurity.The security of modern cryptography system depends on the key searching timecomplexity,which is exponential to the length of key.With the characteristics ofultra-large-scale parallelism,high-density storage and low power consumption,DNAcomputation not only for traditional encryption poses a challenge,but also for massiveinformation storage provides a new encryption model.Recently,self-assemble has beendemonstrated as an efficient mechanism for bottom-up construction of nanostructures innanotechnology.The ability of linear and two-dimensional assemblies to perform paralleluniversal computations has been explored in development of self-assembly of DNA Tiles asa tool for DNA computation.It is improved that linear self-assembly is equivalent toregular languages and two dimensional self-assembly is universal.This dissertation brings forward contributions in information security by using DNAcomputing self-assembly.The research is focused on applying the self-assembly models tovarious encryption problems and cryptoanalysis.The validity,time complexity,spacecomplexity,operational complexity and error rate of the self-assembly models to solvingthe problems in information security field,are analyzed quantitatively.Firstly,to make use of parallel universal computations and significantly high density ofDNA Tiles,we hope to store information in DNA molecules.We detail procedures forOne-Time-Pads（OTP）cryptography based on DNA Tile self-assembly model,which is inprinciple unbreakable.In order to implement the whole encrypting and decryptingprocesses,we propose four Tile systems:encrypting system,ciphertext extracting system,key extracting system and decrypting system.And some biotechnologies are used totransfer the secret key in security.All the Tile systems useΘ（1）input Tiles and compute inΘ（n）steps according to the length of the input massage.At last,we analysed the security ofthe method of implementing OTP in the self-assemble Tile models and the results indicated that OTP in the self-assemble Tile models achieve storing information in security andsharing the secret key safely.And we show how the Tile assembly process can be used to break Diffie-Hellman keyexchange.In order to achieve this,we propose Tile systems to construct the integerspermutation from 1 to p-1 based on the truth table of the following numbers modular p（p isprime number）:g mod p,g² mod p,...,g^p-1mod p.The output of the systems can be read bythe standard sequence-reading operation that uses a combination of PCR and gelelectrophoresis.Through the processes of Tile systems,we can pick out the discretealgorithm result which is the secret key in the Diffie-Hellman algorithm.So the keyexchange by Diffie-Hellman algorithm is unsafe.This work indicates that the system can becarried out inΘ（p-1）assembly time withΘ（p）Tiles.Our methods are valid for breakingDiffie-Hellman algorithm for limited input p,for the Tile types is linear with p.Then,we present ways to compute division in the Tile assembly model:a highlydistributed parallel model of computation that may be implemented using molecules.Idemonstrate constructions of such systems with optimalΘ（1）distinct Tile types and provethe assembly time is linear in the size of the input.Here,I present Tile assembly modelsystems that factor numbers nondeterministically usingΘ（1）distinct components.Thecomputation takes advantage of nondeterminism,but theoretically,each of thenondeterministic paths is executed in parallel,yielding the solution in time linear in the sizeof the input,with high probability.I describe mechanisms for finding the successfulsolutions among the many parallel executions and explore bounds on the probability ofsuch a nondeterministic system succeeding and prove that the probability can be madearbitrarily close to 1.Further more,we utilize the attribute of self-assembly,which is an efficient mechanismfor bottom-up construction of nanostructures in nanotechnology,to design simplified DESand DES in self-assembly models.A main key generating system is proposed to achieve theobject of breaking DES.The simplified DES is introduced to enhance understanding of DES and our breaking algorithm.We use the simplified DES as an example to elucidate ourbreaking scheme in the Tile assembly models.Following the introduction of the simplifiedDES,we cover full DES and 3DES.Then we embed a main key generating system in theSDES and DES Tile assembly models to implement a plaintext-ciphertext attack forbreaking DES and 3DES at a logical level.And we analyze the errors,success probabilityand the feasibility of the breaking model.We provide a description of such an attack usingthe Tile self assembly model inΘ（1）distinct components.The computation takes advantageof Tiles’ autonomy,but theoretically,each of the self assembly models is executed insuper-parallelism,yielding the ciphertext in time linear in the round times of DES.Ouranalysis suggests that such an attack might succeed by using a little of DNA.At last,the paper outlines the application of DNA computing in DES.In this paper,wedescribe a kind of parallel XOR function model based on DNA chip,hybridization,andenzyme-cut technology.Then we apply the model to the efficient evaluation of theresistance to differential cryptanalysis by S-boxes.From the results,we evaluate the outputXOR value distribution statistics of S-boxes and estimate the security of DES.更多还原