Molecular solutions of the RSA public-key cryptosystem on a DNA-based computer

详细信息    查看全文

• 作者：Weng-Long Chang (1) changwl@cc.kuas.edu.tw
  Kawuu Weicheng Lin (1) linwc@cc.kuas.edu.tw
  Ju-Chin Chen (1) joan@csie.ncku.edu.tw
  Chih-Chiang Wang (1) Steven.cc.wang@gmail.com
  Lai Chin Lu (2) rachel@cc.kuas.edu.tw
  Minyi Guo (3) minyi@u-aizu.ac.jp
  Michael (Shan-Hui) Ho (4) MHoInCerritos@yahoo.com
• 关键词：The RSA public ; key cryptosystem – ; Plain ; text – ; Cipher ; text – ; Biomolecular computing – ; DNA ; based computing
• 刊名：The Journal of Supercomputing
• 出版年：2012
• 出版时间：September 2012
• 年：2012
• 卷：61
• 期：3
• 页码：642-672
• 全文大小：895.8 KB
• 参考文献：1. Rivest RL, Shamir A, Adleman L (1978) A method for obtaining digital signatures and public-key crytosystem. Commun ACM 21:120–126
  2. Feynman RP (1961) There’s plenty of room at the bottom. In: Gilbert DH (ed) Minaturization. Reinhold, New York, pp 282–296
  3. Adleman L (1994) Molecular computation of solutions to combinatorial problems. Science 266:1021–1024
  4. Lipton RJ (1995) DNA solution of hard computational problems. Science 268:542–545
  5. Quyang Q, Kaplan PD, Liu S, Libchaber A (1997) DNA solution of the maximal clique problem. Science 278:446–449
  6. Amos M (1997) DNA computation. PhD thesis, Department of Computer Science, the University of Warwick
  7. Harju T, Li C, Petre I, Rozenberg G (2005) Parallelism in gene assembly. In: DNA computing. Lecture notes in computer science, vol 3384, p 686. doi:10.1007/11493785_12
  8. Thachuk C, Manuch J, Rafiey A, Mathieson L-A, Stacho L, Condon A (2010) An algorithm for the energy barrier problem without pseudoknots and temporary arcs. Pac Symp Biocomput 15:108–119
  9. Zadeh JN, Wolfe BR, Pierce NA (2010) Nucleic acid sequence design via efficient ensemble defect optimization. J Comput Chem. doi:10.1002/jcc.21633
  10. Xiao D, Li W, Zhang Z, He L (2005) Solving the maximum cut problems in the Adleman–Lipton model. Biosystems 82:203–207
  11. Yeh C-W, Chu C-P, Wu K-R (2006) Molecular solutions to the binary integer programming problem based on DNA computation. Biosystems 83(1):56–66
  12. Zhang DY, Turberfield AJ, Yurke B, Winfree E (2007) Engineering entropy-driven reactions and networks catalyzed by DNA. Science 318(5853):1121–1125
  13. Boneh D, Dunworth C, Lipton RJ (1996) Breaking DES using a molecular computer. In: Proceedings of the 1st DIMACS workshop on DNA based computers, 1995. DIMACS series in discrete mathematics and theoretical computer science, vol 27. American Mathematical Society, Providence, pp 37–66
  14. Adleman L, Rothemund PWK, Roweis S, Winfree E (1999) On applying molecular computation to the data encryption standard. In: The 2nd annual workshop on DNA computing, Princeton University. DIMACS series in discrete mathematics and theoretical computer science. American Mathematical Society, Providence, pp 31–44
  15. Zhang DY, Seelig G (2011) DNA-based fixed gain amplifiers and linear classifier circuits. In: DNA 16. Lecture notes in computer science, vol 6518, p 176
  16. Yeh C-W, Chu C-P (2008) Molecular verification of rule-based systems based on DNA computation. IEEE Trans Knowl Data Eng 20(7):965–975
  17. Guarnieri F, Fliss M, Bancroft C (1996) Making DNA add. Science 273:220–223
  18. Ho M(S-H) (2005) Fast parallel molecular solutions for DNA-based supercomputing: the subset-product problem. Biosystems 80:233–250
  19. Ahrabian H, Nowzari-Dalini A (2004) DNA simulation of nand Boolean circuits. Adv Model Optim 6(2):33–41
  20. Schuster A (2005) DNA databases. Biosystems 81:234–246
  21. Paun G, Rozenberg G, Salomaa A (1998) DNA computing: new computing paradigms. Springer, New York. ISBN:3-540-64196-3
  22. Boneh D, Dunworth C, Lipton RJ, Sgall J (1996) On the computational power of DNA. Discrete Appl Math 71:79–94. Special Issue on Computational Molecular Biology
  23. Amos M (2005) Theoretical and experimental DNA computation. Springer, Berlin
  24. Braich RS, Johnson C, Rothemund PWK, Hwang D, Chelyapov N, Adleman LM Solution of a satisfiability problem on a gel-based DNA computer. In: Proceedings of the 6th international conference on DNA computation. Lecture notes in computer science. Springer, Berlin
  25. Braich RS, Johnson C, Rothemund PWK, Hwang D, Chelyapov N, Adleman LM (2002) Solution of a 20-variable 3-SAT problem on a DNA computer. Science 296(5567):499–502
  26. Diffie W, Hellman M (1976) New directions in cryptography. IEEE Trans Inf Theory IT-22(6):644–654
  27. Shor PW (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26(5):1484–1509
  28. Chang W-L, Ho M, Guo M (2005) Fast parallel molecular algorithms for DNA-based computation: factoring integers. IEEE Trans Nanobiosci 4(2):149–163
  29. Li K, Zou S, Xv J (2008) Fast parallel molecular algorithms for DNA-based computation: solving the elliptic curve discrete logarithm problem over GF(2 n ). J Biomed Biotechnol 2008:518093. doi:
  30. Chang W-L, Huang S-C, Lin KW, Ho M(SH) (2009) Fast parallel DNA-based algorithms for molecular computation: discrete logarithm. J Supercomput
• 作者单位：1. Department of Computer Science and Information Engineering, National Kaohsiung University of Applied Sciences, No 415, Chien Kung Road, Kaohsiung, 807 Taiwan, R.O.C.2. Department of Industrial and Management Engineering, National Kaohsiung University of Applied Sciences, No 415, Chien Kung Road, Kaohsiung, 807 Taiwan, R.O.C.3. Department of Computer Software, The University of Aizu, Aizu-Wakamatsu City, Fukushima, 965-8580 Japan4. Computer Center and Institute of Electrical Engineering, National Taipei University, 151, University Rd., San Shia 237, Taipei County, Taiwan, R.O.C.
• ISSN：1573-0484

文摘

The RSA public-key cryptosystem is an algorithm that converts a plain-text to its corresponding cipher-text, and then converts the cipher-text back into its corresponding plain-text. In this article, we propose five DNA-based algorithms—parallel adder, parallel subtractor, parallel multiplier, parallel comparator, and parallel modular arithmetic—that construct molecular solutions for any (plain-text, cipher-text) pair for the RSA public-key cryptosystem. Furthermore, we demonstrate that an eavesdropper can decode an encrypted message overheard with the linear steps in the size of the encrypted message overheard.