МЕТОД РЕАЛІЗАЦІЇ ОПЕРАЦІЇ ПІДНЕСЕННЯ ДО КВАДРАТУ В КРИПТОСИСТЕМІ РАБІНА НА ОСНОВІ ВИКОРИСТАННЯ СИСТЕМИ ЗАЛИШКОВИХ КЛАСІВ

Д. М. Ковальчук

doi:10.32782/2521-6643-2025-2-70.28

Д. М. Ковальчук Харківський національний університет імені В. Н. Каразіна https://orcid.org/0000-0002-8229-836X

DOI: https://doi.org/10.32782/2521-6643-2025-2-70.28

Ключові слова: криптосистема Рабіна, система залишкових класів, піднесення до квадрату, підвищення швидкодії, паралельні обчислення

Анотація

У статті запропоновано новий метод реалізації операції піднесення числа до квадрату в криптосистемі Рабіна, який спрямований на суттєве підвищення швидкодії виконання арифметичних операцій завдяки застосуванню системи залишкових класів (СЗК). Основна ідея підходу полягає у переході від традиційної позиційної системи числення до СЗК, що дозволяє виконувати обчислення незалежно для кожного модуля, відкриваючи можливості для паралельної обробки даних. Такий підхід суттєво відрізняється від класичних методів, які оперують великими числами послідовно та обмежені необхідністю обробки переносу розрядів, що підвищує часову складність операцій. Використання СЗК дозволяє усунути цей недолік, забезпечуючи значне скорочення обчислювального часу. У роботі розроблено математичну модель множення двох чисел у СЗК, що базується на використанні коду табличного множення. Модель враховує властивості симетрії таблиці множення, що дозволяє зменшити обсяг необхідних обчислень до 25 % від повної таблиці На основі цієї моделі запропоновано метод піднесення чисел до квадрату в СЗК, який демонструє високу ефективність для чисел великої розрядності. Метод дозволяє виконувати обчислення незалежно по кожному модулю, що робить його придатним для апаратної реалізації. Проведений порівняльний аналіз показав, що запропонований підхід забезпечує істотне прискорення обчислень: для 32-розрядних операндів швидкодія зростає у 2048 разів, а для 64-розрядних операндів – до 8192 разів у порівнянні з традиційними методами позиційної системи числення. Це свідчить про високу ефективність використання СЗК у криптосистемі Рабіна та демонструє практичну користь для високопродуктивних криптографічних систем, орієнтованих на обробку великих числових полів. Отримані результати підтверджують доцільність застосування СЗК для реалізації операцій піднесення до квадрату та відкривають перспективи для подальших досліджень. Подальші напрями включають розробку універсальної структури модульних обчислень у СЗК для інших асиметричних криптосистем, оптимізацію алгоритмів для апаратної реалізації та практичну оцінку продуктивності запропонованого методу у різних обчислювальних середовищах. Застосування запропонованого підходу може стати ключовим елементом у створенні швидких і надійних криптографічних рішень, що відповідають сучасним вимогам інформаційної безпеки та обробки великих обсягів даних.

Посилання

1. Usmani Z. A., Rai M., Khan F. Reconfigurable Cryptoprocessor Design for RSA and Rabin-p Cryptosystems. 2024 26th International Multi-Topic Conference (INMIC), Karachi, Pakistan, 2024. P. 1–6. DOI: 10.1109/INMIC64792.2024.11004308.
2. Yakymenko M., Kasianchuk I., Shylinska R., Shevchuk V., Yatskiv V., Karpinski M. Polynomial Rabin Cryptosystem Based on the Operation of Addition. 2022 12th International Conference on Advanced Computer Information Technologies (ACIT), Ruzomberok, Slovakia, 2022. P. 345–350. DOI: 10.1109/ACIT54803.2022.9913089.
3. Schoinianakis D. Residue arithmetic systems in cryptography: a survey on modern security applications. Journal of Cryptographic Engineering, 2020, Vol. 10, P. 249–267. DOI: 10.1007/s13389-020-00231-w.
4. Yakymenko M., Kasianchuk O., Martyniuk S., Martyniuk A., Martyniuk Y., Yakymenko Y. A Symmetric Cryptoalgorithm in a Polynomial Hierarchical Residual Number System. 2025 15th International Conference on Advanced Computer Information Technologies (ACIT), Sibenik, Croatia, 2025. P. 501–504. DOI: 10.1109/ACIT65614.2025.11185808.
5. Yatskiv V., Yatskiv N., Ivasiev S., Kulyna S., Tsavolyk T., Yatskiv I. The McEliece Cryptosystem Based on the Redundant Residue Number System. 2025 15th International Conference on Advanced Computer Information Technologies (ACIT), Sibenik, Croatia, 2025. P. 573–577. DOI: 10.1109/ACIT65614.2025.11185887.
6. Nykolaychuk Y. M., Yakymenko I. Z., Vozna N. Y. et al. Residue Number System Asymmetric Cryptoalgorithms. Cybernetics and Systems Analysis, 2022, Vol. 58, No. 4, P. 611–618. DOI: 10.1007/ s10559-022-00494-7.
7. Zhan J., Shiue P. J., Huang S. C., Lowe B. J. Towards a Novel Generalized Chinese Remainder Algorithm for Extended Rabin Cryptosystem. IEEE Access, 2020, Vol. 8, P. 26433–26444. DOI: 10.1109/ACCESS.2020.2967396.
8. Nykolaychuk Y. M., Yakymenko I. Z., Vozna N. Y., Kasianchuk M. M. Residue number system asymmetric cryptoalgorithms. Cybernetics and Systems Analysis, 2022, Vol. 58, No. 4, P. 611–618.
9. Selianinau M., Woźna-Szcześniak B. An Efficient Implementation of Montgomery Modular Multiplication Using a Minimally Redundant Residue Number System. Applied Sciences, 2025, Vol. 15, No. 10, 5332. DOI: 10.3390/app15105332.
10. Kawamura S., Komano Y., Shimizu H. et al. RNS Montgomery Reduction Algorithms Using Quadratic Residuosity. Journal of Cryptographic Engineering, 2019, Vol. 9, P. 313–331. DOI: 10.1007/s13389-018-0195-8.
11. Hollmann H. D. L., Rietman R., de Hoogh S., Tolhuizen L. M. G. M., Gorissen P. A Multi-layer Recursive Residue Number System. arXiv, 2018. DOI: 10.48550/arxiv.1801.07561.
12. Jacquemin D., Mert A. C., Roy S. S. Exploring RNS for Isogeny-Based Cryptography. Cryptology ePrint Archive, 2022. URL: https://eprint.iacr.org/2022/1289.
13. Krasnobayev V., Yanko A., Koshman S. Conception of Realization of Cryptographic RSA Transformations with Using of the Residue Number System. Computer Science and Cybersecurity, 2016, No. 2, P. 5–12. URL: https://periodicals.karazin.ua/cscs/article/view/6207.
14. Yatskiv V., Kulyna S., Bykovyy P., Maksymyuk T., Sachenko A. Method of Reliable Data Storage Based on Redundant Residue Number System. 2020 IEEE 5th International Symposium on Smart and Wireless Systems within the Conferences on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS-SWS), Dortmund, Germany, 2020. P. 1–4. DOI: 10.1109/IDAACS-SWS50031.2020.9297052.
15. Krasnobayev V., Yanko A., Kovalchuk D. Method of Tabular Implementation of the Arithmetic Operation of Multiplying Two Numbers Represented in the System of Residual Classes. 2022 IEEE 9th International Conference on Problems of Infocommunications, Science and Technology (PIC S&T), Kharkiv, Ukraine, 2022. P. 63–68. DOI: 10.1109/PICST57299.2022.10238624.
16. Yatskiv V., Kulyna S., Yatskiv N., Kulyna H. Protected Distributed Data Storage Based on Residue Number System and Cloud Services. 2020 10th International Conference on Advanced Computer Information Technologies (ACIT), Deggendorf, Germany, 2020. P. 796–799. DOI: 10.1109/ACIT49673.2020.9208849.
17. Krasnobayev V. A., Yanko A. S., Kovalchuk D. M. Mathematical Model of the Process of Raising Integers to an Arbitrary Power of a Natural Number in the System of Residual Classes. Theoretical and Applied Cybersecurity, 2023, Vol. 5, No. 2, P. 5–14. DOI: 10.20535/tacs.2664-29132023.2.278891.
18. Ochoa-Jiménez E., Rivera-Zamarripa L., Cruz-Cortés N., Rodríguez-Henríquez F. Implementation of RSA Signatures on GPU and CPU Architectures. IEEE Access, 2020, Vol. 8, P. 9928–9941. DOI: 10.1109/ACCESS.2019.2963826.