METHOD FOR IMPLEMENTING THE SQUARING OPERATION IN THE RABIN CRYPTOSYSTEM BASED ON THE USE OF THE RESIDUE NUMBER SYSTEM - Kovalchuk, D. M. (Systems and Technologies, 2025)
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.