Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases

Volume 12, Issue 1, pp 51-64 http://dx.doi.org/10.22436/jmcs.012.01.05

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 2442 Downloads
• 3249 Views

Authors

Sakineh Sharifi - Department of Information Technology Engineering, Qom University, Qom, Iran. Mohammad Esmaeildoust - Faculty of Marine Engineering, Khorramshahr University of Marine Science and Technology, Iran. Mohammad Reza Taheri - Nanotechnology and Quantum Computing Laboratory, Shahid Beheshti University, GC, Tehran, Iran. Keivan Navi - Faculty of Electrical and Computer Engineering, Shahid Beheshti University GC, Tehran, Iran.

Abstract

Point multiplication is the most important part of elliptic curve cryptography which consumes remarkable time of implementation. Therefore efficiency enhancement of entire system is depending on efficiency of this part. Increasing the efficiency of the modular multiplication improve overall performance of the cryptographic system as it frequency used in some application such as Elliptic Curve Cryptography. By applying Residue Number System (RNS) to Montgomery multiplication as a method for modular multiplication, delay of modular multiplication will be reduced. Appropriate RNS moduli sets replace time consuming operation of multiplication by smaller operations. In this paper two balanced moduli set with proper dynamic range is presented and the efficiency of conversion from RNS to RNS which is the most time consuming part of the Montgomery modular multiplication will be increased.

Share and Cite

Keywords

• residue number system (RNS)
• RNS Montgomery
• reverse converter
• elliptic curve cryptography

MSC

•  65Y04
•  94A60

References

• [1] R. L. Rivest, A. Shamir, L. M. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Commun. ACM, 21 (1978), 120–126
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [2] V. S. Miller, Use of elliptic curves in cryptography, in Lecture notes in computer sciences; 218 on Advances in cryptology—CRYPTO 85. New York, NY, USA: Springer-Verlag New York, Inc., (1986), 417–426.
  • View Article
  • Google Scholar


• [3] N. Koblitz, Elliptic Curve Cryptosystem, J. Cryptology Math. Comp., 48 (1987), 203–209
  • View Article
  • MathSciNet
  • Google Scholar


• [4] P. Montgomery, Modular Multiplication without Trial Division, Mathematics of Computation, 44 (1985), 519-521
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [5] J. Bajard, L. Didier, P. Kornerup, An RNS Montgomery’s Modular Multiplication Algorithm, IEEE Trans. Computers, 47 (1998), 167-178
  • Google Scholar


• [6] J. Bajard, L. Didier, and P. Kornerup, Modular Multiplication and Base Extensions in Residue Number Systems, Proc. 15th IEEE Symp. Computer Arithmetic (ARITH’01), (2001), 59-65
  • View Article
  • Google Scholar


• [7] J. C. Bajard, M. Kaihara, T. Plantard, Selected RNS Bases for Modular Multiplication, In 19th IEEE International Symposium on Computer Arithmetic, (2009), 25-32
  • View Article
  • Google Scholar


• [8] M. Gerami, M. Esmaeildoust, Sh. Rezaie, K. Navi, O. Hashemipour, Four Moduli RNS Bases for Efficient Design of Modular Multiplication, Journal of Computations & Modelling, 1 (2011), 73-96
  • Google Scholar
  • MATH


• [9] Sh. Rezaie, M. Esmaeildoust, M. Gerami, K. Navi, O. Hashemipour, High Dynamic Range RNS Bases for Modular Multiplication, IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 4, No 1 (2011)
  • Google Scholar


• [10] A. A. Hiasat, VLSI implementation of New Arithmetic Residue to Binary decoders, IEEE Transactions on VLSI systems, 13 (2005), 153-158
  • View Article
  • Google Scholar


• [11] A. S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, S. Timarchi, Efficient Reverse Converter Designs for the new 4-Moduli Set \(\{2^n-1, 2^n,2^n+1, 2^{2n+1}-1\}\) and \(\{2^n-1, 2^n+1, 2^{2n}, 2^{2n}+1\}\) Based on New CRTs, IEEE Transactions on Circuits and Systems-I, 57(4) (2010), 823-835.
  • View Article
  • MathSciNet
  • Google Scholar


• [12] B. Cao, C. Chang, T. Srikanthan, An Efficient Reverse Converter for the 4-Moduli Set \(\{2^n-1, 2^n, 2^n+1, 2^{2n}+1\}\) Based on the New Chinese Remainder Theorem, IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, 50(10) (2003), 1296-1303.
  • View Article
  • MathSciNet
  • Google Scholar
  • MATH


• [13] P. M. Matutino, R. Chaves, L. Sousa, Arithmetic units for RNS moduli \(\{2^n − 3\}\) and \(\{2^n + 3\}\) operations, in 13th EUROMICRO Conference on Digital System Design: Architectures, Methods and Tools (2010)
  • View Article
  • Google Scholar


• [14] R. Zimmermann, Efficient vlsi implementation of modulo (2n ± 1) addition and multiplication, in 14th IEEE Symposium on Computer Arithmetic, (1999)
  • View Article
  • Google Scholar


• [15] S. B. R. A. Patel, M. Benaissa, N. Powell, Power-delay-area efficient modulo \(2^n + 1\) adder architecture for rns, Electronics Letters, 231 - 232 (2005)
  • View Article
  • Google Scholar


• [16] R. Zimmermann, Binary adder architectures for cell-based VLSI and their synthesis, Ph.D. dissertation, Swiss Federal Institute of Technology (ETH) Zurich, Hartung-Gorre Verlag (1998)
  • Google Scholar


• [17] R. Chaves, L. Sousa, Improved \(2n + 1\) multipliers, Technical Report RT/14/2003, INESC-ID (2003)


• [18] R. Chaves, L. Sousa, \(2^n + 1, 2^n+k, 2^n − 1\): A new RNS moduli set extension, in EUROMICRO Systems on Digital System Design, (2004)
  • View Article
  • Google Scholar


• [19] P. M. Matutino, R. Chaves, L. Sousa, Binary-to-RNS conversion units for moduli \(\{2n±3\}\), in 14th EUROMICRO Conference on Digital System Design: Architectures, Methods and Tools (2011)
  • View Article
  • Google Scholar


• [20] F. J. Taylor, Residue arithmetic: A tutorial with examples, Computer, 17 (1984), 50–62
  • View Article
  • Google Scholar


• [21] M. Esmaeildoust, A. Kaabi, High Speed Reverse Converter for the Five Moduli Set \(\{2^n, 2^n-1, 2^n+1, 2^n-3, 2^{n-1}-1\}\), TJMCS, (2009), 438-450
  • Google Scholar


• [22] K. Navi, A. S. Molahosseini, M. Esmaeildoust, How to teach residue number system to computer scientists and engineers?, IEEETrans. Edu., 54 (2011), 156–163
  • View Article
  • Google Scholar


• [23] B. Parhami, Computer Arithmetic: Algorithms and Hardware Design, Oxford, U.K.: Oxford Univ, Press (2000)
  • Google Scholar


• [24] B. Cao, C. H. Chang, T. Srikanthan, Adder based residue to binary converters for a new balanced 4-moduli set, in Proc. 3rd IEEE Symp.Image, Signal Process. Anal., 2 (2003), 820–825.
  • View Article
  • Google Scholar


• [25] N. Keivan, M. Esmaeildoust, AS. Molahosseini, A General Reverse Converter Architecture with Low Complexity and High Performance, IEICE TRANSACTIONS on Information and Systems, 94 (2) (2011), 264-273.
  • Google Scholar


• [26] B. Cao, T. Srikanthan, C. H. Chang, Efficient reverse converters for the four-moduli sets \(\{2n–1, 2n, 2n+1, 2n+1–1\}\) and \(\{2n–1, 2n, 2n+1, 2n–1–1\}\), IEE Proc. Comput. Digit.Tech., 152 (2005), 687–696
  • Google Scholar


• [27] K. Hwang, Computer Arithmetic: Principle, Architecture and Design, Wiley, New York (1979)
  • Google Scholar


• [28] S. J. Piestrak, Design of residue generators and multioperand modular adders using carry-save adders, IEEE Trans. Comput., 423 (1994), 68–77
  • View Article
  • Google Scholar


• [29] S. J. Piestrak, A high speed realization of a residue to binary converter, IEEE Trans. Circuits Syst. II, Analog.Digit. Signal Process, 42 (1995), 661–663
  • View Article
  • Google Scholar


• [30] D. Younes, P. Steffan, Novel Modulo \(2^n+1\) Subtractor and Multiplier , ICONS: The Sixth International Conference on Systems, (2011), 36-38
  • Google Scholar


• [31] Reto Zimmermann, Lecture notes on Computer Arithmetic: Principles, Architectures and VLSI Design, Integrated System Laboratory , Swiss Federal Institute of Technology (ETH) Zurich (1999)
  • Google Scholar


• [32] D. M. Schinianakis, A. P. Fournaris, H. E. Michail, A. P. Kakarountas, T. Stouraitis, An RNS Implementation of an Fp Elliptic Curve Point Multiplier, IEEE Transactions on Circuits and Systems—I, VOL. 56, NO. 6 (2009)
  • View Article
  • MathSciNet
  • Google Scholar