Researches On Several Cryptological Problems Based On DNA Computing By Self-Assembly

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.