Fast Calculation of the Modular Exponential Function in the RSA Cipher

Document Type : Original Article


1 Graduate Student.

2 Faculty ofEnginerring, Ain Shams University.

3 Military Technical College, Cairo.


Two different techniques are used to secure communication between military aircraft and control centers; the conventional secret key system and the public key system. In the public key system, the most famous technique is the RIVEST-SHAMIR-ADLEMAN (RSA) method. In the RSA system, the modular exponential function is used to encipher the plaintext message and to decipher the ciphertext message. The problem considered here is how to speed-up the calculation of the modular exponential function. An improved binary algorithm based on the binary redundant representa-lion (BRR) is proposed. This algorithm requires the minimum number of basic operations (modular multiplications) among all possible binary redundant representations. Compared to the binary algorithm, the proposed algorithm reduces the number of basic operations by 33%. Systolic array of Montgomery is used to decrease the needed number of operations in the calculations. Results show that the time needed to compute the modular multiplication became less than 50% of the original time needed to perform the same operation without using systolic array of Montgomery. The final results show that, the needed time to calculate the modular exponential function will decrease by 66% of the original time.