research-article

A compact FPGA-based montgomery multiplier over prime fields

Authors:

Miguel Morales-Sandoval,

Arturo Diaz-PerezAuthors Info & Claims

GLSVLSI '13: Proceedings of the 23rd ACM international conference on Great lakes symposium on VLSI

Pages 245 - 250

https://doi.org/10.1145/2483028.2483102

Published: 02 May 2013 Publication History

Abstract

This work describes a compact FPGA hardware architecture for computing modular multiplications over GF(p) using the Montgomery method, suitable for public key cryptography for embedded or mobile systems. The multiplier is parameterizable, allowing to evaluate the hardware design for different prime fields using different radix of the form β = 2^k. The design uses only three k x k multipliers and three 2k-bit adders. The hardware organization of the multiplier maximizes the use of the multipliers processing iteratively the multiplicand, multiplier and modulus. The parametric design allows to study area-performance trade offs, in order to meet system requirements such as available resources, throughput, and efficiency. The proposed multiplier achieves a 1024-bit modular multiplication in 15.63 μs using k = 32. Compared to the most compact FPGA implementation previously reported, our proposed design uses 79% less FPGA resources with better efficiency expressed as Mbps/Slice.

References

[1]

Digital signature standard (DSS). National Institute of Standards and Technology, Washington, 2000.

[2]

M. Brown, D. Hankerson, J. López, and A. Menezes. Software implementation of the NIST elliptic curves over prime fields. In Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, CT-RSA 2001, pages 250--265, London, UK, UK, 2001. Springer-Verlag.

Digital Library

[3]

W. Diffie and M. Hellman. New directions in cryptography. Information Theory, IEEE Transactions on, 22(6):644--654, nov 1976.

Digital Library

[4]

Y. Gong and S. Li. High-throughput FPGA implementation of 256-bit Montgomery modular multiplier. In IEEE on Second International Workshop on Education Technology and Computer Science, pages 173--177, jan. 2010.

[5]

M. Hamilton, W. Marnane, and A. Tisserand. A comparison on FPGA of modular multipliers suitable for elliptic curve cryptography over GF(p) for specific p values. In 2011 International Conference on Field Programmable Logic and Applications, pages 273--276, sept. 2011.

Digital Library

[6]

M. Huang, K. Gaj, and T. A. El-Ghazawi. New hardware architectures for Montgomery modular multiplication algorithm. IEEE Trans. Computers, 60(7):923--936, 2011.

Digital Library

[7]

M. Huang, K. Gaj, S. Kwon, and T. El-Ghazawi. An optimized hardware architecture for the Montgomery multiplication algorithm. In Proceedings of the 11th International Conference on Public Key cryptography, PKC'08, pages 214--228, Berlin, Heidelberg, 2008. Springer-Verlag.

Digital Library

[8]

K. Itoh, M. Takenaka, N. Torii, S. Temma, and Y. Kurihara. Fast implementation of public-key cryptography on a DSP TMS320C6201. In Proceedings of the First International Workshop on Cryptographic Hardware and Embedded Systems, CHES '99, pages 61--72, London, UK, UK, 1999. Springer-Verlag.

Digital Library

[9]

C. K. Koç, T. Acar, and B. S. Kaliski, Jr. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro, 16(3):26--33, June 1996.

Digital Library

[10]

A. Mondal, S. Ghosh, A. Das, and D. R. Chowdhury. Efficient FPGA implementation of Montgomery multiplier using DSP blocks. In Proceedings of the 16th International Conference on Progress in VLSI Design and Test, VDAT'12, pages 370--372, Berlin, Heidelberg, 2012. Springer-Verlag.

Digital Library

[11]

P. L. Montgomery. Modular multiplication without trial division. Math. Computation, 44:519--521, 1985.

[12]

E. Oksuzoglu and E. Savas. Parametric, secure and compact implementation of RSA on FPGA. In International Conference on Reconfigurable Computing and FPGAs, pages 391--396, dec. 2008.

Digital Library

[13]

R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120--126, Feb. 1978.

Digital Library

[14]

A. F. Tenca and C. K. Koç. A scalable architecture for modular multiplication based on Montgomery's algorithm. IEEE Trans. Computers, 52(9):1215--1221, 2003.

Digital Library

[15]

C. D. Walter. Montgomery's multiplication technique: How to make it smaller and faster. In CHES'99, pages 80--93, 1999.

Digital Library

Cited By

Reddy SSinha SZhang W(2023)Design and Analysis of RSA and Paillier Homomorphic Cryptosystems Using PSO-Based Evolutionary ComputationIEEE Transactions on Computers10.1109/TC.2023.3234213(1-14)Online publication date: 2023
https://doi.org/10.1109/TC.2023.3234213
Rodríguez-Flores LMorales-Sandoval MCumplido RFeregrino-Uribe CAlgredo-Badillo I(2018)Compact FPGA hardware architecture for public key encryption in embedded devicesPLOS ONE10.1371/journal.pone.019093913:1(e0190939)Online publication date: 23-Jan-2018
https://doi.org/10.1371/journal.pone.0190939
Rodriguez-Flores LMorales-Sandoval MCumplido RFeregrino-Uribe CAlgredo-Badillo I(2017)A compact FPGA-based microcoded coprocessor for exponentiation in asymmetric encryption2017 IEEE 8th Latin American Symposium on Circuits & Systems (LASCAS)10.1109/LASCAS.2017.7948095(1-4)Online publication date: Feb-2017
https://doi.org/10.1109/LASCAS.2017.7948095
Show More Cited By

Index Terms

A compact FPGA-based montgomery multiplier over prime fields
1. Hardware
  1. Robustness
    1. Design for manufacturability
      1. Yield and cost modeling
      2. Yield and cost optimization

Recommendations

New bit-parallel Montgomery multiplier for trinomials using squaring operation

A new bit-parallel Montgomery multiplier for GF ( 2 m ) is presented, where the field is generated with an irreducible trinomial. We first present a slightly generalized version of a newly proposed divide and conquer approach. Then, by combining this ...
Efficient FPGA implementation of RNS Montgomery multiplication using balanced RNS bases
Abstract
This paper presents a new architecture to perform modular multiplication using Montgomery multiplication in Residue Number System (RNS). Two new balanced four-moduli RNS bases are selected, and the process of RNS Montgomery ...
Highlights
- Selection of two new balanced RNS bases to exploit the benefits of the well-formed moduli.
Efficient pipelining for modular multiplication architectures in prime fields
GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI

This paper presents a pipelined architecture of a modular Montgomery multiplier, which is suitable to be used in public key coprocessors. Starting from a baseline implementation of the Montgomery algorithm, a more compact pipelined version is derived. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GLSVLSI '13: Proceedings of the 23rd ACM international conference on Great lakes symposium on VLSI

May 2013

368 pages

ISBN:9781450320320

DOI:10.1145/2483028

General Chair:
Jose L. Ayala
Complutense University of Madrid, Spain
,
Program Chairs:
Alex Jones
University of Pittsburgh, USA
,
Patrick Madden
Binghamton University, USA
,
Publications Chair:
Ayse K. Coskun
Boston University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE CEDA
IEEE CASS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 May 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GLSVLSI'13

Sponsor:

SIGDA

GLSVLSI'13: Great Lakes Symposium on VLSI 2013

May 2 - 3, 2013

Paris, France

Acceptance Rates

GLSVLSI '13 Paper Acceptance Rate 76 of 238 submissions, 32%;

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
242
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Reddy SSinha SZhang W(2023)Design and Analysis of RSA and Paillier Homomorphic Cryptosystems Using PSO-Based Evolutionary ComputationIEEE Transactions on Computers10.1109/TC.2023.3234213(1-14)Online publication date: 2023
https://doi.org/10.1109/TC.2023.3234213
Rodríguez-Flores LMorales-Sandoval MCumplido RFeregrino-Uribe CAlgredo-Badillo I(2018)Compact FPGA hardware architecture for public key encryption in embedded devicesPLOS ONE10.1371/journal.pone.019093913:1(e0190939)Online publication date: 23-Jan-2018
https://doi.org/10.1371/journal.pone.0190939
Rodriguez-Flores LMorales-Sandoval MCumplido RFeregrino-Uribe CAlgredo-Badillo I(2017)A compact FPGA-based microcoded coprocessor for exponentiation in asymmetric encryption2017 IEEE 8th Latin American Symposium on Circuits & Systems (LASCAS)10.1109/LASCAS.2017.7948095(1-4)Online publication date: Feb-2017
https://doi.org/10.1109/LASCAS.2017.7948095
Xiuze Dong Xiaonan Zhang (2016)A high performance FPGA implementation of 256-bit Modular multiplication processor over GF(p)2016 2nd IEEE International Conference on Computer and Communications (ICCC)10.1109/CompComm.2016.7924847(961-965)Online publication date: Oct-2016
https://doi.org/10.1109/CompComm.2016.7924847
Morales-Sandoval MDiaz-Perez A(2016)Scalable GF(p) Montgomery multiplier based on a digit–digit computation approachIET Computers & Digital Techniques10.1049/iet-cdt.2015.005510:3(102-109)Online publication date: 1-May-2016
https://doi.org/10.1049/iet-cdt.2015.0055

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents