Метод модулярного множення на постійне число з суміщенням групової обробки розрядів множника та редукції Монтґомері

Автор(и)

  • В.Л. Селіванов Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» https://orcid.org/0000-0001-8519-6038
  • Н.А. Гуцуляк Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» https://orcid.org/0009-0009-0472-9695
  • В.В. Володін Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» https://orcid.org/0009-0002-6995-0613

DOI:

https://doi.org/10.18372/2073-4751.81.20135

Ключові слова:

модулярне експоненціювання, модулярне множення, редукція Монтґомері, криптографія з відкритим ключем

Анотація

Розроблено та досліджено метод прискорення обчислювальної реалізації модулярного множення на постійне число, як складової модулярного експоненціювання з старших розрядів – базової обчислювальної операції несиметричної криптографії. Прискорення досягнуто за рахунок використання передобчислень для суміщення групової обробки k розрядів множника та відповідної редукції Монтґомері. Наведено числові приклади, які ілюструють роботу запропонованого методу.

Теоретично доведено та експериментально підтверджено, що розроблений метод дозволяє в k разів прискорити модулярне множення на постійне число в порівнянні з відомими методами.

Посилання

Русанова О. В., Гайдукевич М. А. Метод розподіленого модулярного експоненціювання на термінальних мікроконтролерах IoT із захищеним залученням хмарних технологій. Проблеми автоматизації та управління. 2024. Т. 2, № 76. С. 91–103. DOI: 10.18372/2073-4751.78.18966

Haidukevych O. A. et al. Secure Cloud Computing Method for Rapid Implementation of Cryptographic Data Protection in IoT. 2023 13th International Conference on Dependable Systems, Services and Technologies (DESSERT) : proceedings, Athens, Greece, 13–15 October 2023 / IEEE. 2023. P. 1–4. DOI: 10.1109/DESSERT61349.2023.10416477.

Daiko I., Selivanov V. Fast exponential method on Galois field for cryptographic applications. 2023 13th International Conference on Dependable Systems, Services and Technologies (DESSERT) : proceedings, Athens, Greece, 13–15 October 2023 / IEEE. 2023. P. 1–4. DOI: 10.1109/DESSERT61349.2023.10416519.

Menezes A., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. CRC Press, 2001. 780 p.

Селіванов В. Л., Аль-Мріят Гассан Абдель Жаліль. Метод модулярного множення на постійне число для швидкої реалізації криптографії з відкритим ключем в IoT. Проблеми автоматизації та управління. 2024. Вип. 3(79). С. 50–58. DOI: 10.18372/2073-4751.79.19371.

Markovskyi O. et al. An Accelerate Approach for Public Key Cryptography Implementation on IoT Terminal Platforms. 2023 13th International Conference on Dependable Systems, Services and Technologies (DESSERT) : proceedings, Athens, Greece, 13–15 October 2023 / IEEE. 2023. P. 1–4. DOI: 10.1109/DESSERT61349.2023.10416516.

Buhrow B., Gilbert B., Haider C. Parallel modular multiplication using 512-bit advanced vector instructions: RSA fault-injection countermeasure via interleaved parallel multiplication. Journal of Cryptographic Engineering. 2021. No. 2. P. 46–55. DOI: /10.1007/s13389-021-00256-9.

Марковський О. П., Аль-Мріят Гассан Абдель Жаліль. Метод прискорення модулярного множення для механізмів криптографічного захисту з відкритим ключем. Проблеми управління та інформатизації. 2023. Вип. 4(76). С. 48–58. DOI: 10.18372/2073-4751.76.18240.

Марковский О. П., Аль-Мріят Гассан Абдель Жаліль. Метод прискореного модулярного множення для ефективної реалізації механізмів криптографічного захисту з відкритим ключом. Адаптивні системи автоматичного управління. 2024. Т. 1, № 44. С. 142–152. DOI: 10.20535/1560-8956.44.2024.302429.

Boiarshyn I., Markovskyi O., Ostrovska B. Organization of parallel execution of modular multiplication to speed up the computational implementation of public-key cryptography. Information, Computing and Intelligent systems. 2022. № 3. P. 26–32. DOI: 10.20535/2708-4930.3.2022.265418.

Карацуба А. О., Офман Ю. П. Множення багатоцифрових чисел на автоматах. Доповіді Академії наук СРСР. 1962. № 2. С. 293–294.

Fừrer M. Faste Integer Multiplication. SIAM Journal on Computing. 2009. Vol. 39, no. 3. P. 979–1005. DOI: 10.1137/070711716.

Barrett P. Implementing the Rivest Shamir and Adleman Public Key Encryption Algorithm on a Standard Digital Signal Processor. Lecture Notes in Computer Science. Vol. 263. Advances in Cryptology - CRYPTO '86. Proceedings / ed. by A. M. Odlyzko. Berlin, 1987. P. 311–323.

Montgomery P. Modular multiplication without trial division. Mathematics of Computation. 1985. Vol. 44, no. 170. P. 519–521.

Downloads

Опубліковано

2025-06-01

Як цитувати

Селіванов, В., Гуцуляк, Н., & Володін, В. (2025). Метод модулярного множення на постійне число з суміщенням групової обробки розрядів множника та редукції Монтґомері. Проблеми iнформатизацiї та управлiння, 1(81), 95–104. https://doi.org/10.18372/2073-4751.81.20135

Номер

Том 1 № 81 (2025)

Розділ

Статті

Ліцензія

Науковий журнал дотримується принципів відкритого доступу (Open Access) та забезпечує вільний, негайний і постійний доступ до всіх опублікованих матеріалів без фінансових, технічних або юридичних обмежень для читачів.

Усі статті публікуються у відкритому доступі відповідно до ліцензії Creative Commons Attribution 4.0 International (CC BY 4.0).

Авторські права

Автори, які публікують свої роботи в журналі:

  • зберігають за собою авторські права на свої публікації;

  • надають журналу право на перше опублікування статті;

  • погоджуються на поширення матеріалів за ліцензією CC BY 4.0;

  • мають право повторно використовувати, архівувати та поширювати свої роботи (у тому числі в інституційних та тематичних репозитаріях) за умови посилання на первинну публікацію в журналі.