Abstract:

Computation by self-assembly of DNA is an efficient method of executing parallel DNA computing where information is encoded in DNA tiles and a large number of tiles can be self-assembled via sticky end associations.This paper shows that how the DNA self-assembly process can be used for breaking the RSA public key cryptosystem, whose security is based on the difficulty of factoring the product of two large prime numbers. Thus, a method for implementing the product of two primers using self-assembled DNA computing is expounded. Then, a non-deterministic algorithmic is provided to break efficiently the RSA public key cryptosystem. By creating billions of copies of the participating DNA tiles, the algorithmic will run in parallel on all possible factors. The computation takes advantage of non-determinism, but theoretically, each of the nondeterministic paths is executed in parallel, yielding the solution in time linear in the size of the input, with high probability. It presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.