Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases
-
2459
Downloads
-
3301
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
ISRP Style
Sakineh Sharifi, Mohammad Esmaeildoust, Mohammad Reza Taheri, Keivan Navi, Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases, Journal of Mathematics and Computer Science, 12 (2014), no. 1, 51-64
AMA Style
Sharifi Sakineh, Esmaeildoust Mohammad, Taheri Mohammad Reza, Navi Keivan, Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases. J Math Comput SCI-JM. (2014); 12(1):51-64
Chicago/Turabian Style
Sharifi, Sakineh, Esmaeildoust, Mohammad, Taheri, Mohammad Reza, Navi, Keivan. "Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases." Journal of Mathematics and Computer Science, 12, no. 1 (2014): 51-64
Keywords
- residue number system (RNS)
- RNS Montgomery
- reverse converter
- elliptic curve cryptography
MSC
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
-
[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.
-
[3]
N. Koblitz, Elliptic Curve Cryptosystem, J. Cryptology Math. Comp., 48 (1987), 203–209
-
[4]
P. Montgomery, Modular Multiplication without Trial Division, Mathematics of Computation, 44 (1985), 519-521
-
[5]
J. Bajard, L. Didier, P. Kornerup, An RNS Montgomery’s Modular Multiplication Algorithm, IEEE Trans. Computers, 47 (1998), 167-178
-
[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
-
[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
-
[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
-
[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)
-
[10]
A. A. Hiasat, VLSI implementation of New Arithmetic Residue to Binary decoders, IEEE Transactions on VLSI systems, 13 (2005), 153-158
-
[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.
-
[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.
-
[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)
-
[14]
R. Zimmermann, Efficient vlsi implementation of modulo (2n ± 1) addition and multiplication, in 14th IEEE Symposium on Computer Arithmetic, (1999)
-
[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)
-
[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)
-
[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)
-
[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)
-
[20]
F. J. Taylor, Residue arithmetic: A tutorial with examples, Computer, 17 (1984), 50–62
-
[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
-
[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
-
[23]
B. Parhami, Computer Arithmetic: Algorithms and Hardware Design, Oxford, U.K.: Oxford Univ, Press (2000)
-
[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.
-
[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.
-
[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
-
[27]
K. Hwang, Computer Arithmetic: Principle, Architecture and Design, Wiley, New York (1979)
-
[28]
S. J. Piestrak, Design of residue generators and multioperand modular adders using carry-save adders, IEEE Trans. Comput., 423 (1994), 68–77
-
[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
-
[30]
D. Younes, P. Steffan, Novel Modulo \(2^n+1\) Subtractor and Multiplier , ICONS: The Sixth International Conference on Systems, (2011), 36-38
-
[31]
Reto Zimmermann, Lecture notes on Computer Arithmetic: Principles, Architectures and VLSI Design, Integrated System Laboratory , Swiss Federal Institute of Technology (ETH) Zurich (1999)
-
[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)