Research On The Application Of The DNA Computation In Cryptoanalysis Based On Discrete Logarithm Problem

After the theory of biological computer was first proposed by L.Adleman, an American computer scientist, who also showed the solution to Hamilton Path Problem using an biological computer, DNA computing is believed as a potential solution to NPC and other difficult mathematical problems and successful in solving most famous NP hard problems in polynomial time, due to its huge storage and ability of parallel computing, compared with lack of storage and computing rate in traditional computer. The advantage of DNA computing has already caused attention in the field of cryptoanalysis, for most of the cryptosystems rely on the NPC mathematical problems for their security, which indicates that the ability of parallel computing in exponential level provides possibility of breakthrough to these cryptosystems.This paper was dedicated to the research of the application of DNA computing in attacks of Public Key Cryptosystem based on Discrete Logarithm Problem and Elliptic Curve Cryptosystem which has been proven most popular and safest in current world, respectively. Cryptographic algorithms based on these two hard problems convert input data to unrecognizable encryption and the unrecognizable data back again into its original decrypted form. The security of this form of encryption hinges on the enormous difficulty that is required to solve the Discrete Logarithm Problem(DLP) and Elliptic Curve Discrete Logarithm Problem (ECDLP), especially over GF ( 2n), n∈Z+. This paper describes an effective method to find solutions to the DLP and ECDLP by means of a molecular computer. We propose that this research accomplishment would represent a breakthrough for applied biological computation and this paper demonstrates that in principle this is possible. First we design the DNA-based algorithm to solve the DLP over group ( Z p,+) and group Z p*. Then three DNA-based algorithms: a parallel adder, a parallel multiplier, and a parallel inverse over GF ( 2n) are described, which lead to the final goal: solve the DLP and the ECDLP. The biological operation time of all of these algorithms is polynomial with respect to n.Considering this analysis, cryptography using a public-key might be less secure if the technology of DNA computing is mature enough in the future. In this respect, a principal contribution of this paper is to provide enhanced evidence of the potential of molecular computing to tackle such ambitious computations.