TY - JOUR AU - Sharifi, Sakineh AU - Esmaeildoust, Mohammad AU - Taheri, Mohammad Reza AU - Navi, Keivan PY - 2014 TI - Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases JO - Journal of Mathematics and Computer Science SP - 51-64 VL - 12 IS - 1 AB - 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. SN - ISSN 2008-949X UR - http://dx.doi.org/10.22436/jmcs.012.01.05 DO - 10.22436/jmcs.012.01.05 ID - Sharifi2014 ER - TY - JOUR TI - A Method for Obtaining Digital Signatures and Public-Key Cryptosystems AU - R. L. Rivest AU - A. Shamir AU - L. M. Adleman JO - Commun. ACM PY - 1978 DA - 1978// VL - 21 ID - Rivest1978 ER - TY - JOUR TI - Use of elliptic curves in cryptography AU - V. S. Miller JO - in Lecture notes in computer sciences; 218 on Advances in cryptology—CRYPTO 85. New York, NY, USA: Springer-Verlag New York, Inc. PY - 1986 DA - 1986// VL - ID - Miller1986 ER - TY - JOUR TI - Elliptic Curve Cryptosystem AU - N. Koblitz JO - J. Cryptology Math. Comp. PY - 1987 DA - 1987// VL - 48 ID - Koblitz1987 ER - TY - JOUR TI - Modular Multiplication without Trial Division AU - P. Montgomery JO - Mathematics of Computation PY - 1985 DA - 1985// VL - 44 ID - Montgomery1985 ER - TY - JOUR TI - An RNS Montgomery’s Modular Multiplication Algorithm AU - J. Bajard AU - L. Didier AU - P. Kornerup JO - IEEE Trans. Computers PY - 1998 DA - 1998// VL - 47 ID - Bajard1998 ER - TY - JOUR TI - Modular Multiplication and Base Extensions in Residue Number Systems AU - J. Bajard AU - L. Didier AU - and P. Kornerup JO - Proc. 15th IEEE Symp. Computer Arithmetic (ARITH’01) PY - 2001 DA - 2001// VL - ID - Bajard2001 ER - TY - JOUR TI - Selected RNS Bases for Modular Multiplication AU - J. C. Bajard AU - M. Kaihara AU - T. Plantard JO - In 19th IEEE International Symposium on Computer Arithmetic PY - 2009 DA - 2009// VL - ID - Bajard2009 ER - TY - JOUR TI - Four Moduli RNS Bases for Efficient Design of Modular Multiplication AU - M. Gerami AU - M. Esmaeildoust AU - Sh. Rezaie AU - K. Navi AU - O. Hashemipour JO - Journal of Computations & Modelling PY - 2011 DA - 2011// VL - 1 ID - Gerami2011 ER - TY - BOOK TI - High Dynamic Range RNS Bases for Modular Multiplication AU - Sh. Rezaie AU - M. Esmaeildoust AU - M. Gerami AU - K. Navi AU - O. Hashemipour PB - IJCSI International Journal of Computer Science Issues PY - 2011 DA - 2011// CY - Vol. 8, Issue 4, No 1 ID - Rezaie2011 ER - TY - JOUR TI - VLSI implementation of New Arithmetic Residue to Binary decoders AU - A. A. Hiasat JO - IEEE Transactions on VLSI systems PY - 2005 DA - 2005// VL - 13 ID - Hiasat2005 ER - TY - JOUR TI - 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 AU - A. S. Molahosseini AU - K. Navi AU - C. Dadkhah AU - O. Kavehei AU - S. Timarchi JO - IEEE Transactions on Circuits and Systems-I PY - 2010 DA - 2010// VL - 57(4) ID - Molahosseini2010 ER - TY - JOUR TI - 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 AU - B. Cao AU - C. Chang AU - T. Srikanthan JO - IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications PY - 2003 DA - 2003// VL - 50(10) ID - Cao2003 ER - TY - BOOK TI - Arithmetic units for RNS moduli \(\{2^n − 3\}\) and \(\{2^n + 3\}\) operations AU - P. M. Matutino AU - R. Chaves AU - L. Sousa PB - in 13th EUROMICRO Conference on Digital System Design: Architectures PY - 2010 DA - 2010// CY - Methods and Tools ID - Matutino2010 ER - TY - BOOK TI - Efficient vlsi implementation of modulo (2n ± 1) addition and multiplication AU - R. Zimmermann PB - in 14th IEEE Symposium on Computer Arithmetic PY - 1999 DA - 1999// CY - ID - Zimmermann1999 ER - TY - BOOK TI - Power-delay-area efficient modulo \(2^n + 1\) adder architecture for rns AU - S. B. R. A. Patel AU - M. Benaissa AU - N. Powell PB - Electronics Letters PY - 2005 DA - 2005// CY - 231 - 232 ID - Patel2005 ER - TY - BOOK TI - Binary adder architectures for cell-based VLSI and their synthesis AU - R. Zimmermann PB - Ph.D. dissertation, Swiss Federal Institute of Technology (ETH) Zurich PY - 1998 DA - 1998// CY - Hartung-Gorre Verlag ID - Zimmermann1998 ER - TY - BOOK TI - Improved \(2n + 1\) multipliers AU - R. Chaves AU - L. Sousa PB - Technical Report RT/14/2003 PY - 2003 DA - 2003// CY - INESC-ID ID - Chaves2003 ER - TY - BOOK TI - \(2^n + 1, 2^n+k, 2^n − 1\): A new RNS moduli set extension AU - R. Chaves AU - L. Sousa PB - in EUROMICRO Systems on Digital System Design PY - 2004 DA - 2004// CY - ID - Chaves2004 ER - TY - BOOK TI - Binary-to-RNS conversion units for moduli \(\{2n±3\}\) AU - P. M. Matutino AU - R. Chaves AU - L. Sousa PB - in 14th EUROMICRO Conference on Digital System Design: Architectures PY - 2011 DA - 2011// CY - Methods and Tools ID - Matutino2011 ER - TY - JOUR TI - Residue arithmetic: A tutorial with examples AU - F. J. Taylor JO - Computer PY - 1984 DA - 1984// VL - 17 ID - Taylor1984 ER - TY - JOUR TI - High Speed Reverse Converter for the Five Moduli Set \(\{2^n, 2^n-1, 2^n+1, 2^n-3, 2^{n-1}-1\}\) AU - M. Esmaeildoust AU - A. Kaabi JO - TJMCS PY - 2009 DA - 2009// VL - ID - Esmaeildoust2009 ER - TY - JOUR TI - How to teach residue number system to computer scientists and engineers? AU - K. Navi AU - A. S. Molahosseini AU - M. Esmaeildoust JO - IEEETrans. Edu. PY - 2011 DA - 2011// VL - 54 ID - Navi2011 ER - TY - BOOK TI - Computer Arithmetic: Algorithms and Hardware Design AU - B. Parhami PB - Oxford, U.K.: Oxford Univ PY - 2000 DA - 2000// CY - Press ID - Parhami2000 ER - TY - JOUR TI - Adder based residue to binary converters for a new balanced 4-moduli set AU - B. Cao AU - C. H. Chang AU - T. Srikanthan JO - in Proc. 3rd IEEE Symp.Image, Signal Process. Anal. PY - 2003 DA - 2003// VL - 2 ID - Cao2003 ER - TY - JOUR TI - A General Reverse Converter Architecture with Low Complexity and High Performance AU - N. Keivan AU - M. Esmaeildoust AU - AS. Molahosseini JO - IEICE TRANSACTIONS on Information and Systems PY - 2011 DA - 2011// VL - 94 (2) ID - Keivan2011 ER - TY - JOUR TI - 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\}\) AU - B. Cao AU - T. Srikanthan AU - C. H. Chang JO - IEE Proc. Comput. Digit.Tech. PY - 2005 DA - 2005// VL - 152 ID - Cao2005 ER - TY - BOOK TI - Computer Arithmetic: Principle, Architecture and Design AU - K. Hwang PB - Wiley PY - 1979 DA - 1979// CY - New York ID - Hwang1979 ER - TY - JOUR TI - Design of residue generators and multioperand modular adders using carry-save adders AU - S. J. Piestrak JO - IEEE Trans. Comput. PY - 1994 DA - 1994// VL - 423 ID - Piestrak1994 ER - TY - JOUR TI - A high speed realization of a residue to binary converter AU - S. J. Piestrak JO - IEEE Trans. Circuits Syst. II, Analog.Digit. Signal Process PY - 1995 DA - 1995// VL - 42 ID - Piestrak1995 ER - TY - JOUR TI - Novel Modulo \(2^n+1\) Subtractor and Multiplier AU - D. Younes AU - P. Steffan JO - ICONS: The Sixth International Conference on Systems PY - 2011 DA - 2011// VL - ID - Younes2011 ER - TY - BOOK TI - Lecture notes on Computer Arithmetic: Principles, Architectures and VLSI Design AU - Reto Zimmermann PB - Integrated System Laboratory PY - 1999 DA - 1999// CY - Swiss Federal Institute of Technology (ETH) Zurich ID - Zimmermann1999 ER - TY - BOOK TI - An RNS Implementation of an Fp Elliptic Curve Point Multiplier AU - D. M. Schinianakis AU - A. P. Fournaris AU - H. E. Michail AU - A. P. Kakarountas AU - T. Stouraitis PB - IEEE Transactions on Circuits and Systems—I PY - 2009 DA - 2009// CY - VOL. 56, NO. 6 ID - Schinianakis2009 ER -