Analysis of the RSA-cryptosystem in abstract number rings

Abstract

Quantum computers can be a real threat to some modern cryptosystems (such as the RSA-cryptosystem). The analogue of the RSA-cryptosystem in abstract number rings is not affected by this threat, as there are currently no factorization algorithms using quantum computing for ideals. In this paper considered an analogue of RSA-cryptosystem in abstract number rings. Proved the analogues of theorems related to its cryptographic strength. In particular, an analogue of Wiener’s theorem on the small secret exponent is proved. The analogue of the re-encryption method is studied. On its basis the necessary restrictions on the parameters of the cryptosystem are obtained. It is also shown that in numerical Dedekind rings the factorization problem is polynomial equivalent to factorization in integers.

Author Biography

Nikita V. Kondratyonok, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

master’s degree student at the faculty of applied mathematics and computer science

References

  1. Rivest RL, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978;21(2):120–126. DOI: 10.1145/359340.359342.
  2. Li B. Generalizations of RSA public key cryptosystem. IACR, Cryptology ePrint Archive [Preprint]. 2005 [cited 2019 August 23]. Available from: https://arxiv.org/ia.cr/2005/285.
  3. Elkamchouchi H, Elshenawy K, Shaban H. Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers. In: ICCS 2002. Proceedings of the 8th International conference on communication systems; 2002 November 28; Singapore, Singapore. Volume 1. [S. l.]: IEEE; 2002. p. 91–95. DOI: 10.1109/ICCS.2002.1182444.
  4. Koval A, Verkhovsky B. Analysis of RSA over Gaussian Integers Algorithm. In: ITNG 2008. Proceedings of the Fifth International conference on information technology: new generations; 2008 April 7–9; Las Vegas, Nevada. Washington: IEEE Computer Society; 2008. p. 101–105. DOI: 10.1109/ITNG.2008.44.
  5. El-Kassar AN, Haraty RA, Awad YA, Debnath NC. Modified RSA in the domains of Gaussian integers and polynomials over finite fields. In: Proceedings of the ISCA 18th International conference on computer applications in industry and engineering; 2005 November 9–11; Honolulu, Hawaii. [S. l.]: International Society for Computers and their Applications (ISCA); 2005. p. 298–303.
  6. Vaskouski M, Kondratyonok N, Prochorov N. Primes in quadratic unique factorization domains. Journal of Number Theory. 2016;168:101–116. DOI: 10.1016/j.jnt.2016.04.022.
  7. Petukhova KA, Tronin SN. RSA Cryptosystem for Dedekind rings. Lobachevskii Journal of Mathematics. 2016;37:284–287. DOI: 10.1134/S1995080216030197.
  8. Brunyate A, Clark PL. Extending the Zolotarev – Frobenius approach to quadratic reciprocity. The Ramanujan Journal. 2015;37(1):25–50. DOI: 10.1007/s11139-014-9635-y.
  9. Cohen HA. Course in computational algebraic number theory. Berlin: Springer; 1996. 545 p.
  10. Cohen H. Advanced topics in computational number theory. New York: Springer; 1999. 599 p.
  11. Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology. 1997;10:233–260. DOI: 10.1007/s001459900030.
  12. Dedekind R. Über den zusammenhang zwischen der theorie der ideale und der theorie der höheren congruenzen. Abhandlungen der Königlichen Gesellschaft der Wissenschaften in Göttingen. 1878;23:3–38.
  13. Wikstrom D. On the l-Ary GCD-algorithm in rings of integers. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M, editors. Automata, Languages and Programming. 32nd International Colloquium, ICALP; 2005 July 11–15; Lisbon, Portugal. Berlin: Springer; 2005. p. 1189–1201. DOI: 10.1007/11523468_96.
  14. Wiener MJ. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory. 1990;36(3):553–558. DOI: 10.1109/18.54902.
  15. Coron JS, May A. Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. Journal of Cryptology. 2007;20(1):39–50. DOI: 10.1007/s00145-006-0433-6.
  16. Vaskouski M, Kondratyonok N. Shortest division chains in unique factorization domains. Journal of Symbolic Computation. 2016;77:175–188. DOI: 10.1016/j.jsc.2016.02.003.
  17. Vaskouski MM. Polynomial equivalence of computing Euler’s function from RSA modulus and searching for private key in euclidean quadratic domains. In: International congress on computer science: information systems and technologies. Proceedings of the International scientific congress; 2011 October 31 – November 3; Minsk, Belarus. Part 2. Minsk: Belarusian State University; 2016. p. 427–430. Russian.
  18. Babul OV, Vasilyev DV. [Ideals factorization in the number]. Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series. 2011;1;32–36. Russian.
  19. Pohst ME. Computational algebraic number theory. Basel: Birkhäuser; 1993. 88 р. DOI: 10.1007/978-3-0348-8589-8.
  20. Kannan R, Bachem A. Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix. SIAM Journal on Computing. 1979;8(4):499–507. DOI: 10.1137/0208040.
  21. Vaskouski MM, Matveev GV. Verification of modular secret sharing. Journal of the Belarusian State University. Mathematics and Informatics. 2017;2:17–22. Russian.
  22. Matveev GV, Matulis VV. Perfect verification of modular scheme. Journal of the Belarusian State University. Mathematics and Informatics. 2018;2:4–9. Russian.
  23. Matveev GV. Chinese remainder theorem secret sharing in multivariate polynomials. Journal of the Belarusian State University. Mathematics and Informatics. 2019;3:129–133. Russian. DOI: 10.33581/2520-6508-2019-3-129-133.
  24. Hecke E. Vorlesung über die theorie der algebraischen zahlen. Leipzig: Akademische Verlagsgesellschaft; 1923. 264 p. Russian edition: Hecke E. Lektsii po teorii algebraicheskikh chisel. Ol’shanskii GI, Raikov DA, translators. Moscow: Gosudarstvennoe izdatel’stvo tekhniko-teoreticheskoi literatury; 1940. 261 p.
  25. Glukhov MM, Kruglov IA, Pichkur AB, Cheremushkin AV. Vvedenie v teoretiko-chislovye metody kriptografii [Introduction to number theoretical methods in cryptography]. Saint Petersburg: Lan’; 2011. 400 р. Russian.
  26. Koblitz N. Course in number theory and cryptography. New York: Springer-Verlag; 1994. 235 p.
Published
2020-03-30
Keywords: RSA-cryptosystem, abstract number ring, Dedekind ring, factorization, ideal
Supporting Agencies I thank my supervisor PhD (physics and mathematics) M. M. Vas’kovskii for reading the work and comments.
How to Cite
Kondratyonok, N. V. (2020). Analysis of the RSA-cryptosystem in abstract number rings. Journal of the Belarusian State University. Mathematics and Informatics, 1, 13-21. https://doi.org/10.33581/2520-6508-2020-1-13-21
Section
Mathematical Logic, Algebra and Number Theory