Анализ RSA-криптосистемы в абстрактных числовых кольцах

  • Никита Васильевич Кондратёнок Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь https://orcid.org/0000-0002-6109-5635

Аннотация

Квантовые компьютеры могут представлять реальную угрозу для некоторых современных криптосистем, например таких, как RSA-криптосистема. Аналог последней в абстрактных числовых кольцах не подвержен этой угрозе, так как в настоящий момент нет алгоритмов факторизации идеалов, использующих квантовые вычисления. В настоящей работе исследована RSA-криптосистема в абстрактных числовых кольцах, доказаны аналоги теорем, связанных с ее криптостойкостью. В частности, доказан аналог теоремы Винера о малой секретной экспоненте. Изучен метод, аналогичный методу повторного шифрования, и на его основе получены необходимые ограничения на параметры криптосистемы. Также показано, что в числовых дедекиндовых кольцах задача факторизации полиномиально эквивалентна факторизации в целых числах.

Биография автора

Никита Васильевич Кондратёнок, Белорусский государственный университет, пр. Независимости, 4, 220030, г. Минск, Беларусь

магистрант факультета прикладной математики и информатики. Научный руководитель – кандидат физико-математических наук М. М. Васьковский

Литература

  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.
Опубликован
2020-03-30
Ключевые слова: RSA-криптосистема, абстрактное числовое кольцо, дедекиндово кольцо, факторизация, идеал
Поддерживающие организации Автор признателен за полезные замечания по данной статье своему научному руководителю – кандидату физико-математических наук М. М. Васьковскому.
Как цитировать
Кондратёнок, Н. В. (2020). Анализ RSA-криптосистемы в абстрактных числовых кольцах. Журнал Белорусского государственного университета. Математика. Информатика, 1, 13-21. https://doi.org/10.33581/2520-6508-2020-1-13-21
Раздел
Математическая логика, алгебра и теория чисел