The Journal of the Korea institute of electronic communication sciences (한국전자통신학회논문지)

Korea Institute of Electronic Communication Science (한국전자통신학회)
권호 표지
DOI QR코드

DOI QR Code

On a Deterministic Attack Against The RSA Cryptosystem

RSA 암호계에 대한 결정적 공격법에 관한 연구

  • Kim, Yong-Tae (Dept. of Mathematics Education, Gwangju National University of Education)
  • 김용태 (광주교육대학교 수학교육과)
  • Received : 2018.06.01
  • Accepted : 2018.08.15
  • Published : 2018.08.31
Download PDF
⟨ Previous Next ⟩

Abstract

The RSA cryptosystem is a one of the first public-key cryptosystems and is widely used for secure data transmission and electric signature. The security of the RSA cryptosystem is based on the difficulty of factoring large numbers.. Though many studies on finding methods for factoring large numbers are going on, the results of that are all experimental or probabilistic. We, in this paper, construct an algorithm for finding large prime factors of integers without factoring integers using properties of the structure of semigroup of imaginary quadratic order and non-invertible ideal, then propose our methods foe deterministic attack against RSA cryptosystem.

RSA 암호계는 가장 널리 쓰이는 공개키 암호계로서, 암호화뿐만 아니라 전자서명이 가능한 최초의 알고리즘으로 알려져 있다. RSA 암호계의 안정성은 큰 수를 소인수 분해하는 것이 어렵다는 것에 기반을 두고 있다. 이러한 이유로 큰 정수의 소인수분해 방법에 많은 연구가 진행되고 있으나, 지금까지 알려진 연구 결과는 모두 실험적이거나 확률적이다. 본 논문에서는, 복소 이차체의 order의 류 반군의 구조와 비 가역 이데알의 성질을 이용하여 인수분해를 하지 않으면서 큰 정수의 소인수를 구하는 알고리즘을 구성한 다음, RSA 암호계에 대한 결정적 공격법을 제안하기로 한다.

Keywords

References

  1. R. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Comm. of the Association for Computing Machinery, vol. 21, no. 2, 1978, pp. 120-126. https://doi.org/10.1145/359340.359342
  2. G. Simmons, Contemporary Cryptology; The Science of Information Integrity. New York: IEEE Press, 1992.
  3. J. Buchmann and H. Cilliams, "A key-exchange system based on imaginary quadratic fields," J. of Cryptology vol. 1, no. 3, 1988, pp.107-118. https://doi.org/10.1007/BF02351719
  4. K. Fauss, Disquisitiones Arithmeticae. New Haven, USA: Translated by A. C. Clarke, Yale Univ. Press, 1966.
  5. G. Catagnos and F. Laguillaumite, "On the Security of Cryptosystems with Quadratic Decryption; The Nicest Cryptanalysis," In Proc. of Eurocrypt '09, Koln, Germany, Lecture Notes in Computer Science 5479, Springer-Verlag, Berlin, Germany, 2009, pp.260-277.
  6. P. Zanardo and U. Zannier, "The class semigroup of orders in number fields", Mathematical Proc. Philosophy Society. vol. 115. no.1, London, 1994, pp.379-391. https://doi.org/10.1017/S0305004100072170
  7. M. Kwon, S. Cho, J. Kim, and U. Choi, "Rearrangement of Sequences through the Generation Principle," J. of the Korea Institute of Electronic Communication Sciences, vol. 13, no. 1, 2018, pp. 133-140. https://doi.org/10.13067/JKIECS.2018.13.1.133
  8. H. Kim, S. Cho, and U. Choi, "On the Construction of the 90/150 State Transition Matrix Corresponding to the Trinomial $x^{2^n-1}+x+1$," J. of the Korea Institute of Electronic Communication Sciences, vol. 13, no. 2, 2018, pp. 383-389. https://doi.org/10.13067/JKIECS.2018.13.2.383
  9. A. Lone and M. Udd, "Common attacks on RSA and its variants with possible countermeasures," Int. J. of Emerging Rearch in Management & Technology, vol. 5, no.5, 2016, pp.65-70.
  10. D. Coppersmith, "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities," J. of Cryptology, vol 10 no. 4, 1997, pp. 233-260. https://doi.org/10.1007/s001459900030
  11. U. Choi, S. Cho, H. Kim, M. Kwon, and S. Kim,"Synthesis of 90/102(170)/150 linear CA using 90/150 linear CA," J. of the Korea Institute of Electronic Communication Sciences, vol. 11, no. 9, 2016, pp. 885-891. https://doi.org/10.13067/JKIECS.2016.11.9.885
  12. A. Schlosser, "Hot electron Luminescence in silicon structures as photonic side channel." Ph.D. thesis, Berlin Institute of Technology, Berlin, 2014.
  13. R. Alvarez, X. Zhou, and J. O'Brien, "Experimental realization of Shor's quantum factoring algorithm using qubit recycling," Nature Photonics, vol. 6 no.11, 2012, pp. 773-779. https://doi.org/10.1038/nphoton.2012.259
  14. W. Adams and L. Goldstein, Introduction to number theory. New Jersey, USA: Prentice-Hall, 1976.
  15. D. Cox, "Primes of the form $x^2+ny^2$." New York, USA: John Wiley & Sons, 1989.
  16. M. Jacobson, Jr., "The Security of Cryptosystems Based on Class Semigroups of Imaginary Quadratic Non-maximal Orders," ACISP 2004, Sidney, July, Lecture Notes in Computer Science 3108, Springer-Verlag. Berlin, 2004, pp.149-156.