Анализ RSA-криптосистемы в абстрактных числовых кольцах
Аннотация
Квантовые компьютеры могут представлять реальную угрозу для некоторых современных криптосистем, например таких, как RSA-криптосистема. Аналог последней в абстрактных числовых кольцах не подвержен этой угрозе, так как в настоящий момент нет алгоритмов факторизации идеалов, использующих квантовые вычисления. В настоящей работе исследована RSA-криптосистема в абстрактных числовых кольцах, доказаны аналоги теорем, связанных с ее криптостойкостью. В частности, доказан аналог теоремы Винера о малой секретной экспоненте. Изучен метод, аналогичный методу повторного шифрования, и на его основе получены необходимые ограничения на параметры криптосистемы. Также показано, что в числовых дедекиндовых кольцах задача факторизации полиномиально эквивалентна факторизации в целых числах.
Литература
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Petukhova KA, Tronin SN. RSA Cryptosystem for Dedekind rings. Lobachevskii Journal of Mathematics. 2016;37:284–287. DOI: 10.1134/S1995080216030197.
- 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.
- Cohen HA. Course in computational algebraic number theory. Berlin: Springer; 1996. 545 p.
- Cohen H. Advanced topics in computational number theory. New York: Springer; 1999. 599 p.
- Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology. 1997;10:233–260. DOI: 10.1007/s001459900030.
- 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.
- 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.
- Wiener MJ. Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory. 1990;36(3):553–558. DOI: 10.1109/18.54902.
- 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.
- 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.
- 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.
- 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.
- Pohst ME. Computational algebraic number theory. Basel: Birkhäuser; 1993. 88 р. DOI: 10.1007/978-3-0348-8589-8.
- 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.
- Vaskouski MM, Matveev GV. Verification of modular secret sharing. Journal of the Belarusian State University. Mathematics and Informatics. 2017;2:17–22. Russian.
- Matveev GV, Matulis VV. Perfect verification of modular scheme. Journal of the Belarusian State University. Mathematics and Informatics. 2018;2:4–9. Russian.
- 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.
- 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.
- 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.
- Koblitz N. Course in number theory and cryptography. New York: Springer-Verlag; 1994. 235 p.
Copyright (c) 2020 Журнал Белорусского государственного университета. Математика. Информатика
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Авторы, публикующиеся в данном журнале, соглашаются со следующим:
- Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).