Research On Molecular Algorithms In Block Cipher And Graph Theory

Computational complexity is composed of computational time complexity and computational space complexity. The need of time for an algorithm denotes computational time complexity of the algorithm, and the need of space for an algorithm denotes computational space complexity of the algorithm. Intractable computation problems can be seen everywhere in our life, it usually takes exponential time to compute the intractable computation problems with traditional electronic computer. Since it is difficult for traditional electronic computer to compute the intractable computation problems, it is necessary to study a new computational method.As a result, DNA computing had been brought into being 15 years ago. The two major advantages of DNA computing are its high parallelism in data processing and its higher storge capacity than normal systems. By the two advantages, DNA computing plays adequately its potential in computing. In a sence, traditional electronic computer can not be compared with DNA computer. This paper takes several intractable computation problems in block cipher and graph theory as instances, DNA algorithms based on sticker model and splicing model are researched, designed and analysed.Breaking international data encryption algorithm and attacking data encryption standard are both intractable computation problems in block cipher. At the same time, the logic operations of binary strings happen frequently in the two block cipher algorithms. Firstly, a DNA sticker algorithm to execute cycle left shift of binary strings is designed. Secondly, a DNA sticker algorithm to carry out XOR between two binary strings is proposed. And the two designed algorithms are illuminated in detail by two simple examples. Finally, to analyse the two proposed algorithms, the analysis results of the two proposed algorithms show that it is feasible to attack some block cipher systems with DNA computing.This paper proposes a recursive DNA splicing algorithm to attack the international data encryption algorithm. Firstly, the XOR, module addition and module multiplication operations in the international data encryption algorithm are designed in detail in the proposed algorithm. And recursive processings are carried out in the eight rounds of the international data encryption algorithm. As a result, the length of the DNA strands in the proposed algorithm is controlled, and the difficulties of DNA operations are decreased. At the same time, a recursive DNA sticker-splicing algorithm to break the data encryption standard is proposed. The proposed algorithm can generate all keys with a recursive method, which can ensure 100% rate of success to attack the data encryption standard in theory. And then, recursive processings are carried out in the 16 rounds of the data encryption standard with the same way, the length of the DNA strands is controlled, the difficulties of DNA operations are decreased, and the reliability of the proposed algorithm is improved.Solving the maximum clique problem and constructing diagonal Ramsey graph are both intractable computation problems. To compute the two problems with brute-force search algorithm, the computation complexity will grow exponentially, and the instance is also similar for primitive DNA algorithm. In this paper, in order to solve the maximum clique problem, a recursive DNA sticker-splicing algorithm is designed. Recursive processings are carried out in the designed algorithm, and some incorrect solutions are deleted by known branch and cut algorithm with DNA operations. In a sence, the designed algorithm relieves the need of computational space, i.e. space exponent explosion problem. At the same time, a recursive DNA sticker-splicing algorithm to construct diagonal Ramsey graph is presented. The presented algorithm can delete some incorrect solutions by adding the remainder vertices one by one. As a result, the presented algorithm relieves the need of computational space. Particularly, computational complexity of the presented algorithm is analyzed with the construction problem of diagonal Ramsey graph with 43 vertices for R(5,5). The analysis results of the computation complexity show that the presented algorithm is effective.