АЛГОРИТМ ПОЛУЧЕНИЯ ИНВАРИАНТОВ

Юрий Л. Зачёсов, Игорь М. Ядыкин

Аннотация


Для защиты информации часто используются две криптографических парадигмы: хэш-функции и алгоритмы, стойкость которых основана на сложности задачи факторизации. При этом хэш-функции обеспечивают стойкость разовых ключей, а алгоритмы, требующие для своего дешифрования решения задачи факторизации, долговременные ключи. Лучшие алгоритмы, решающие задачу факторизации, это субэкспоненциальные алгоритмы, которые для своего выполнения требуют много ресурсов. С 1994 г. часто обсуждается квантовый алгоритм Питера Шора, который также требует для решения большие ресурсы из-за сложностей связанных с новой техникой. Известно, что наиболее стойкий модуль факторизации состоит из двух множителей . Поэтому актуален любой подход, позволяющий снизить объём ресурсов для решения задач такого рода. В статье описан и, по возможности, строго доказан алгоритм получения инвариантных систем многочленов, взаимно-однозначно соответствующих элементам приведённой системы вычетов (ПСВ). Алгебраические структуры, получаемые на выходе алгоритма, в случае удачного решения с их помощью задачи выбора, приводят к полиномиальному методу факторизации. Алгоритм развивает некоторые идеи, связанные с решением задачи «короткой экспоненты», Д. Копперсмита и других авторов. Излагаемый материал относится к первой подзадаче динамической системы (ДС), которая состоит в том, что исходная задача включается в семейство подзадач разного размера, и они решаются одна за другой в правильном порядке. Для получения систем инвариантных уравнений применяется аппарат полиномиальных сравнений и LLL-алгоритм. Доказывается, что с помощью алгоритма всегда можно получать необходимое число многочленов. Предполагается, что алгоритм будет выполняться несколько раз с различными небольшими простыми числами , в качестве управляющих входных параметров. Выполнение алгоритма позволит подготовить возмущающие входные данные для подзадачи выбора, описание которой выходит за рамки статьи. Подзадача выбора наведёт соответствие между элементом множества множеств многочленов и элементом ПСВ, который фактически является остатком  от деления простого числа на управляющий параметр  в формуле замены переменных . Без наличия инвариантных многочленов взаимно-однозначно связанных с ПСВ такая подзадача была бы в принципе невозможна. Набрав достаточное количество пар , применив аппарат китайской теоремы об остатках, найдём множители числа, состоящего из двух множителей. В статье предлагается описание первого этапа ДС, который заменит алгоритм факторизации, зависящий от разрядности составного числа, на новый алгоритм, который будет иметь другие входные данные, меньшей, чем составное число разрядности.

Ключевые слова


алгебраические инварианты, алгоритм факторизации, короткая экспонента, сравнения, китайская теорема об остатках, динамическая система. Для цитирования:

Полный текст:

PDF

Литература


1. Peter Shor, Polynomial-Time Algorithms for Prime Factorization and Descrete Logarithms on Quantum Computer. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS ’94), DOI: 10.1109/SFCS.1994.365700, 1994.

2. Пучков А.Ю., Соколов А.М., Широков С.С., Прокимнов Н.Н., Алгоритм выявления угроз информационной безопасности в распределённых мультисервисных сетях органов государственного управления. Прикладная информатика. 2023, т. 18, № 2, с. 85–102. DOI: 10.37791/2687-0649-2023-18-2-85-102. – EDN: FUXPSC.

3. William Stallings, Cryptography and Network Security: Principles and Practice, Pearson, 2022. – 832 p.
ISBN-13: 978-1-2924-3748-4.

4. Douglas R. Stinson, Maura B. Paterson. Cryptography: Theory and Practice, CRC Press, 2018. – 598 p.
ISBN-13: 978-1-1381-9701-5.

5. Jonathan Katz, Yehuda Lindell. Introduction to Modern Cryptography, Chapman and Hall/CRC, 2014. – 603 p. ISBN-13: 978-1-4665-7027-6.

6. Coppersmith, D. (1996). Finding a Small Root of a Univariate Modular Equation. In: Maurer, U. (eds) Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science, v. 1070. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/3-540-68339-9_14.

7. Coppersmith D. Solving low degree polynomials. Asiacrypt 2003. URL: https://www.iacr.org/publications/dl/coppersmith03/dcasia.pdf (дата обращения: 10.04.2024).

8. Coron, JS. (2004). Finding Small Roots of Bivariate Integer Polynomial Equations Revisited. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology – EUROCRYPT 2004. Lecture Notes in Computer Science,
v. 3027. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/978-3-540-24676-3_29.

9. Herrmann, M., May, A. (2008). Solving Linear Equations Modulo Divisors: On Factoring Given Any Bits. In: Pieprzyk, J. (eds) Advances in Cryptology – ASIACRYPT 2008. Lecture Notes in Computer Science, v. 5350. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/978-3-540-89255-7_25.

10. Josef Pieprzyk (eds), Advances in Cryptology – ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 2008, Proceedings, Springer. – XIV, 572 p.

11. Coppersmith, D. Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities.
J. Cryptology 10, p. 233–260 (1997).
DOI: https://doi.org/10.1007/s001459900030.

12. Nguyen, P.Q., Stern, J. (2001). The Two Faces of Lattices in Cryptology. In: Silverman, J.H. (eds) Cryptography and Lattices. CaLC 2001. Lecture Notes in Computer Science, v. 2146. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/3-540-44670-2_12.

13. Зачёсов Ю.Л., Салихов Н.П. О методе решения полиномиального сравнения P(x)≡0(mod N). Обозрение прикладной и промышленной математики. 2008, т. 15, № 5, c. 769–784. – EDN: KAXSIZ.

14. Зачёсов Ю.Л., Салихов Н.П. Экспериментальная программная оценка размера списка простых чисел, необходимых для отсева полиномиальных уравнений без целых корней. ISSN 2311-2263 (online), ISSN 2071-0410 (print). Прикладная дискретная математика. Приложение. Тезисы докладов VIII Сибирской научной школы-семинара с международным участием «Компьютерная безопасность и криптография» SIBECRYPT'09. Омск, ОмГТУ, 8-11 сентября 2009.
DOI: http://journals.tsu.ru/pdm2/&journal_page=archive&id=1137&article_id=18523 (дата обращения 10.04.2024).

15. Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. М.: Мир, 1987. – 415 c.

16. Coppersmith, D. (1996). Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. In: Maurer, U. (eds) Advances in Cryptology – EUROCRYPT ’96. Lecture Notes in Computer Science, v. 1070. Springer, Berlin, Heidelberg.
DOI: https://doi.org/10.1007/3-540-68339-9_16.

17. Шарый С.П. Конечномерный интервальный анализ. Институт вычислительных технологий СО РАН. Новосибирск: Издательство XYZ, 2013. – 606 с.

18. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. – М.: Мир, 1984. – 318 c.




DOI: http://dx.doi.org/10.26583/bit.2024.2.04

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.