Performance Improvement of Montgomery Multiplier Architecture Using Pre-Computation and Unfolding Technique

Author Name(s): Prafulani Gajbhiye, Pankaj Joshi
Author Email:


The Modern era of information and communication technology demands security. It is a prime important parameter along with other features. Data encryption and decryption algorithms such as RSA and ECC are popularly used to get the desired level of security. Modular multiplication is the integral part of these algorithms. Montgomery Multiplication is most efficient algorithm for modular multiplication. The modulo multiplication is a slow process for large bit size computations for key size more than 512. The critical path delay in architecture affects the iteration delay and overall computation time of encryption and decryption. The slow ripples of the carries in the Montgomery multiplication are often replaced by the carry save architectures of additions. The paper optimizes this traditional approach using a novel combination of an unfolding algorithm and a pre-computation technique. A new architectureMM4_2 multiplier, which holds input and output in carry save format and consuming the smallest critical path, is also modified using unfolding approach . The novel approach improves the overall computation time by 37.89% and 34.68% for ASIC and FPGA implementations as compared to traditional carry save approach. Further, unfolding of MM42_Multiplier in resent architecture gives improvement of 10.98 % in ASIC and 31.24% in FPGA as compare to original MM42 multiplier architecture.

Keywords Montgomery Multiplication, Delay Optimization, Pre-Computation, Unfolded Technique.


The modern communication trends are more concerned over the security of the information. Cryptography, meaning a secret writing helps in encryption and decryption of the information to be transmitted and received respectively. The time required to encrypt and decrypt the information is one of the key role players in deciding the efficiency of these algorithms. The trend of using a larger key size for more security is popular but affects the overall time of encryption. Elliptic curve cryptography (ECC) uses much smaller key size as compared to traditional RSA algorithm to achieve the same level of security. For example, the security level achieved by the key size of 2048 in RSA algorithm is achieved by key size of 256 only in ECC algorithm. The basic operation for data encryption in cryptographic algorithm is series of modular multiplication given below. Z= X.Y Mod M



The VLSI implementations of Montgomery multiplication algorithm with a combined approach of pre-computation technique and unfolding technique is studied in this paper. The pre-computation in the Montgomery architecture uses only one carry save adder as compared to traditional two carry save design. Therefore, the operating frequency increases. We further improved this operating frequency using unfolding technique. The speed performance of traditional Two Carry save architectures is improved by pre-computation in [8] by 19%. We improve the performance of traditional Two CSA architecture using unfolded pre-computation architecture to 37.89% and 34.68% for ASIC and FPGA implementations. Further, unfolded version of MM42_ Multiplier gives reduced delay by 65.47 % in ASIC and 40.78% in FPGA than traditional CSA architecture and require least area.

311 total views, 3 views today

Download PDF File

About the author: admin