High-speed modular multiplication algorithm for RSA cryptosystem
Koon-Shik Cho, Je-Hyuk Ryu, Jun‐Dong Cho · 2002
This paper presents a new radix-4 modular multiplication algorithm based on the sign estimation technique. The sign estimation technique detects the sign of a number represented in the form of a carry-sum pair. It can be implemented with 5-bit carry look-ahead adder. The hardware speed of the cryptosystem is dependent on the performance of modular multiplication of large numbers. Our algorithm requires only n/2+3 clock cycle for n bit modulus in performing modular multiplication. Our algorithm outperforms existing algorithms in terms of required clock cycles by a half. It is efficient for modular exponentiation with large modulus used in the RSA cryptosystem. Also, we use a high-speed adder instead of carry propagation adder for modular multiplication hardware performance in the final stage of the CSA output. We apply the RL (right-and-left) binary method for modular exponentiation because the number of clock cycles required to complete the modular exponentiation takes n cycles. Thus, one 1024-bit RSA operation can be done after n(n/2+3) clock cycles.