Modified VLSI Architecture for Montgomery Modular Multiplication

Authors(5) :-Bhagyamma S, A L Choodarathnakara, Vindya N D, Swamy Y T, Meghana H

This paper proposes a simple and efficient Montgomery multiplication algorithm such that the low-cost and high-performance Montgomery modular multiplier can be implemented accordingly. The proposed multiplier receives and outputs the data with binary representation and uses only one-level carry-save adder (CSA) to avoid the carry propagation at each addition operation. This CSA is also used to perform operand pre computation and format conversion from the carry save format to the binary representation, leading to a short critical path delay at the expense of extra clock cycles for completing one modular multiplication. To overcome the weakness of extra clock cycle, a configurable CSA (CCSA), which could be one full-adder or two serial half-adders, is proposed to reduce the extra clock cycles for operand pre computation and format conversion by half. In addition, a mechanism that can detect and skip the unnecessary carry-save addition operations in the one-level CCSA architecture while maintaining the short critical path delay is developed. As a result, the extra clock cycles for operand pre computation and format conversion can be hidden and high throughput can be obtained. The experimental results show that the proposed Semi Carry Save Montgomery Modular Multiplier New (SCS-MM New) Architecture utilizes Delay of 2.5 ns, Clock cycle of 10, Area of 245 slices and achieves moderate Throughput of 387.78 Mbps.

Authors and Affiliations

Bhagyamma S
Department of Electronics & Communication Engineering, GEC, Kushalnagar, Kodagu, Karnataka, India
A L Choodarathnakara
Department of Electronics & Communication Engineering, GEC, Kushalnagar, Kodagu, Karnataka, India
Vindya N D
Department of Electronics & Communication Engineering, GEC, Kushalnagar, Kodagu, Karnataka, India
Swamy Y T
Department of Electronics & Communication Engineering, GEC, Kushalnagar, Kodagu, Karnataka, India
Meghana H
Department of Electronics & Communication Engineering, GEC, Kushalnagar, Kodagu, Karnataka, India

Carry Save Addition, Semi-carry save Adder, configurable CSA, Semi Carry Save Montgomery Modular Multiplier New (SCS-MM New)

  1. C. McIvor, M. McLoone, and J. V. McCanny, “Modified Montgomery”, IEE Proc.-Comput. Digit. Techn., Vol. 151, No. 6, Nov. 2004, pp. 402-408.
  2. D. Bayhan, S. B. Ors, and G. Saldamli, “Analyzing and comparing the Montgomery multiplication algorithms for their power consumption”, Proc. Int. Conf. Comput. Eng. Syst., Nov. 2010, pp. 257-261.
  3. G. Perin, D. G. Mesquita, F. L. Herrmann, and J. B. Martins, “Montgomery modular multiplication on reconfigurable hardware: Fully systolic array vs parallel implementation”, Proc. 6th Southern Program. Logic Conf., Mar. 2010, pp. 61-66.
  4. J. C. Neto, A. F. Tenca, and W. V. Ruggiero, “A parallel k-partition method to perform Montgomery multiplication”, Proc. IEEE Int Conf. Appl:-Specific Syst., Archit., Processors, Sep. 2011, pp. 251-254.
  5. -P. Amberg, N. Pinckney, and D. M. Harris, “Parallel high-radix Montgomery multipliers”, Proc. 42nd Asilomar Conf. Signals, Syst., Comput., Oct. 2008, pp. 772-776.
  6. V. Bunimov, M. Schimmler, and B. Tolg, “A complexity-effective version of Montgomery’s algorithm”, Proc. Workshop Complex Effective Designs, May 2002.
  7. N. Koblitz, “Elliptic curve cryptosystems”, Math. Comput., Vol. 48, N. 177, 1987, pp. 203-20.
  8. V. S. Miller, “Use of elliptic curves in cryptography”, Advances in Cryptology. Berlin, Germany: Springer-Verlag, 1986, pp. 417-426.
  9. R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Common.ACM, Vol. 21, No. 2, pp. 120-126, Feb. 1978.
  10. Vinodhin N, Suganya C, “Pipelined VLSI Architecture for RSA Based on Montgomery Modular Multiplication”.
  11. A Akilavathi, A Vijaya Prabhu, “Design and Implementation of Energy Efficient and High Throughput Vedic Multiplier”.
  12. C. D. Walter, “Montgomery exponentiation needs no final subtractions”, Electron. Lett., Vol. 35, No. 21, Oct. 1999, pp. 1831-1832.

Publication Details

Published in : Volume 3 | Issue 3 | May-June 2017
Date of Publication : 2017-06-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 305-313
Manuscript Number : IJSRSET173368
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

Bhagyamma S, A L Choodarathnakara, Vindya N D, Swamy Y T, Meghana H, " Modified VLSI Architecture for Montgomery Modular Multiplication, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 3, Issue 3, pp.305-313, May-June-2017.
Journal URL : http://ijsrset.com/IJSRSET173368

Follow Us

Contact Us