METHOD FOR IMPLEMENTING THE SQUARING OPERATION IN THE RABIN CRYPTOSYSTEM BASED ON THE USE OF THE RESIDUE NUMBER SYSTEM
Abstract
The article proposes a method for implementing the operation of squaring a number in the Rabin cryptosystem, which increases the speed of arithmetic operations by using the Residue Number System (RNS). The proposed approach is based on the transition from the positional numeral system to RNS, which allows computations to be performed independently for each modulus and enables parallel data processing. Unlike traditional methods that rely on sequential execution of arithmetic operations with large numbers, the use of RNS avoids carry propagation, thereby reducing time complexity. A mathematical model of the process of multiplying two numbers represented in RNS has been developed based on the use of table multiplication coding. This approach takes into account the symmetry properties of table multiplication, allowing the volume of required computations to be reduced to 25% of the full table. Based on this mathematical model, a method for squaring numbers in RNS has been proposed. A comparative analysis showed that the use of the proposed approach provides a significant performance gain: for 32-bit operands, the speedup is 2048 times, and for 64-bit operands, up to 8192 times compared to the positional numeral system. The research results confirm the feasibility of applying the Residue Number System in the Rabin cryptosystem for implementing the squaring operation. The proposed method can be effectively used in high-performance cryptographic systems designed for processing large numerical fields. Further research should focus on developing a universal structure for modular computations in RNS for other asymmetric cryptosystems, as well as creating a hardware implementation of the method to practically evaluate its performance.
References
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.
This work is licensed under a Creative Commons Attribution 4.0 International License.
ISSN 
