Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases

1369
Downloads

1499
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, 5164
AMA Style
Sharifi Sakineh, Esmaeildoust Mohammad, Taheri Mohammad Reza, Navi Keivan, Efficient Implementation of Rns Montgomery Multiplication Using Balanced Rns Bases. J Math Comput SCIJM. (2014); 12(1):5164
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): 5164
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 PublicKey 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: SpringerVerlag 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), 519521

[5]
J. Bajard, L. Didier, P. Kornerup, An RNS Montgomery’s Modular Multiplication Algorithm, IEEE Trans. Computers, 47 (1998), 167178

[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), 5965

[7]
J. C. Bajard, M. Kaihara, T. Plantard, Selected RNS Bases for Modular Multiplication, In 19th IEEE International Symposium on Computer Arithmetic, (2009), 2532

[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), 7396

[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), 153158

[11]
A. S. Molahosseini, K. Navi, C. Dadkhah, O. Kavehei, S. Timarchi, Efficient Reverse Converter Designs for the new 4Moduli Set \(\{2^n1, 2^n,2^n+1, 2^{2n+1}1\}\) and \(\{2^n1, 2^n+1, 2^{2n}, 2^{2n}+1\}\) Based on New CRTs, IEEE Transactions on Circuits and SystemsI, 57(4) (2010), 823835.

[12]
B. Cao, C. Chang, T. Srikanthan, An Efficient Reverse Converter for the 4Moduli Set \(\{2^n1, 2^n, 2^n+1, 2^{2n}+1\}\) Based on the New Chinese Remainder Theorem, IEEE Transactions on Circuits and SystemsI: Fundamental Theory and Applications, 50(10) (2003), 12961303.

[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, Powerdelayarea efficient modulo \(2^n + 1\) adder architecture for rns, Electronics Letters, 231  232 (2005)

[16]
R. Zimmermann, Binary adder architectures for cellbased VLSI and their synthesis, Ph.D. dissertation, Swiss Federal Institute of Technology (ETH) Zurich, HartungGorre Verlag (1998)

[17]
R. Chaves, L. Sousa, Improved \(2n + 1\) multipliers, Technical Report RT/14/2003, INESCID (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, BinarytoRNS 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^n1, 2^n+1, 2^n3, 2^{n1}1\}\), TJMCS, (2009), 438450

[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 4moduli 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), 264273.

[26]
B. Cao, T. Srikanthan, C. H. Chang, Efficient reverse converters for the fourmoduli 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 carrysave 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), 3638

[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)