Article

Efficient pipelining for modular multiplication architectures in prime fields

Authors:

Kazuo Sakiyama,

Ingrid VerbauwhedeAuthors Info & Claims

GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI

Pages 534 - 539

https://doi.org/10.1145/1228784.1228911

Published: 11 March 2007 Publication History

Abstract

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. The design makes use of 16-bit integer multiplication blocks that are available on recently manufactured FPGAs. The critical path is optimized by omitting the exact computation of intermediate results in the Montgomery algorithm using a 6-2 carry-save notation. This results in a high-speed architecture,which outperforms previously designed Montgomery multipliers. Because a very popular application of Montgomery multiplication is public key cryptography, we compare our implementation to the state-of-the-art in Montgomery multipliers on the basis of performance results for 1024-bit RSA.

References

[1]

L. Batina and G. Muurling. Montgomery in Practice: How to Do It More Efficiently in Hardware. In B. Preneel, editor, In Topics in Cryptology - CT-RSA - The Cryptographers' Track at the RSA Conference, number 2271 in Lecture Notes in Computer Science, pages 40--52, San Jose, USA, February 18-22 2002. Springer-Verlag.

Digital Library

[2]

V. Bunimov and M. Schimmler. Area and time efficient modular multiplication of large integers. In Proceedings of IEEE 14th International Conference on Application-specific Systems, Architectures and Processors (ASAP), pages 400--409. IEEE, 2003.

[3]

C. K. Koc. High-radix and bit recoding techniques for modular exponentiation. International Journal of Computer Mathematics, 40(3+4):139--156, 1991.

[4]

C. K. Koc, T. Acar, and B. S. Kaliski. Analyzing and comparing montgomery multiplication algorithms. IEEE Micro, 16:2633, 1996.

Digital Library

[5]

K. Kelley and D. Harris. Parallelized very high radix scalable Montgomery multipliers. In Conference Record of the Thirty-Ninth Asilomar Conference on Signals, Systems and Computers, pages 1196--1200, 2005.

[6]

D. E. Knuth. The Art of Computer Programming: Seminumerical Algorithms, volume 2. Addison-Wesley, 1981.

Digital Library

[7]

P. Kocher, J. Jaffe, and B. Jun. Introduction to differential power analysis and related attacks. http://www.cryptography.com/dpa/technical, 1998.

[8]

K. Manochehri and S. Pourmozafari. Fast Montgomery modular multiplication by pipelined CSA architecture. In Proceedings of International Conference on Microelectronics (ICM), pages 144--147, 2004.

[9]

C. McIvor, M. McLoone, J. McCanny, A. Daly, and W. Marnane. Fast Montgomery Modular Multiplication and RSA Cryptographic Processor Architectures. In Proceedings of 37th Annual Asilomar Conference on Signals, Systems and Computers, pages 379--384, November 2003.

[10]

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

[11]

J.-J. Quisquater and C. Couvreur. Fast decipherment algorithm for RSA public-key cryptosystem. Electronic Letters, 1 (21):905--907, 1982.

[12]

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

Digital Library

[13]

A. Tenca and C. K. Koc. A scalable architecture for Montgomery multiplication. In C. K. Koc and C. Paar, editors, Proceedings of 1st International Workshop on Cryptographic Hardware and Embedded Systems (CHES), number 1717 in Lecture Notes in Computer Science, pages 94--108, Worcester, Massachusetts, USA, August 12--13 1999. Springer-Verlag.

Digital Library

[14]

C. Walter. Montgomery's multiplication technique: How to make it smaller and faster. In C. K. Koc and C. Paar, editors, Proceedings of 1st International Workshop on Cryptographic Hardware and Embedded Systems (CHES), number 1717 in Lecture Notes in Computer Science, pages 80- 93, Worcester, MA, USA, August 12-13 1999. Springer-Verlag.

Digital Library

[15]

C. D. Walter. Montgomery exponentiation needs no final subtraction. Electronic letters, 35(21):1831--1832, October 1999.

[16]

Xilinx. Xilinx: The programmable logic company. http://www.xilinx.com, 2006.

Cited By

Vollala SRamasubramanian NTiwari UVollala SRamasubramanian NTiwari U(2021)Introduction to Montgomery MultiplicationEnergy-Efficient Modular Exponential Techniques for Public-Key Cryptography10.1007/978-3-030-74524-0_6(121-133)Online publication date: 14-Jul-2021
https://doi.org/10.1007/978-3-030-74524-0_6
Pirotte NVliegen JBatina LMentens N(2018)Design of a Fully Balanced ASIC Coprocessor Implementing Complete Addition Formulas on Weierstrass Elliptic Curves2018 21st Euromicro Conference on Digital System Design (DSD)10.1109/DSD.2018.00095(545-552)Online publication date: Aug-2018
https://doi.org/10.1109/DSD.2018.00095
Miyamoto ESugawara TSakiyama K(2018)Efficient Software Implementation of Modular Multiplication in Prime Fields on TI’s DSP TMS320C6678Information Security Applications10.1007/978-3-319-93563-8_22(261-273)Online publication date: 23-Jun-2018
https://doi.org/10.1007/978-3-319-93563-8_22
Show More Cited By

Index Terms

Efficient pipelining for modular multiplication architectures in prime fields
1. Hardware
  1. Robustness
    1. Design for manufacturability
      1. Yield and cost modeling
      2. Yield and cost optimization
2. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

New Hardware Architectures for Montgomery Modular Multiplication Algorithm

Montgomery modular multiplication is one of the fundamental operations used in cryptographic algorithms, such as RSA and Elliptic Curve Cryptosystems. At CHES 1999, Tenca and Koç proposed the Multiple-Word Radix-2 Montgomery Multiplication (MWR2MM) ...
A compact FPGA-based montgomery multiplier over prime fields
GLSVLSI '13: Proceedings of the 23rd ACM international conference on Great lakes symposium on VLSI

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 ...
Fast truncated multiplication for cryptographic applications
CHES'05: Proceedings of the 7th international conference on Cryptographic hardware and embedded systems

The Truncated Multiplication computes a truncated product, a contiguous subsequence of the digits of the product of 2 integers. A few truncated polynomial multiplication algorithms are presented and adapted to integers. They are based on the most often ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI

March 2007

626 pages

ISBN:9781595936059

DOI:10.1145/1228784

General Chairs:
Hai Zhou
Northwestern University
,
Enrico Macii
Politecnico di Torino
,
Program Chairs:
Zhiyuan Yan
Lehigh University
,
Yehia Massoud
Rice University

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GLSVLSI07

Sponsor:

GLSVLSI07: Great Lakes Symposium on VLSI 2007

March 11 - 13, 2007

Stresa-Lago Maggiore, Italy

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
310
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vollala SRamasubramanian NTiwari UVollala SRamasubramanian NTiwari U(2021)Introduction to Montgomery MultiplicationEnergy-Efficient Modular Exponential Techniques for Public-Key Cryptography10.1007/978-3-030-74524-0_6(121-133)Online publication date: 14-Jul-2021
https://doi.org/10.1007/978-3-030-74524-0_6
Pirotte NVliegen JBatina LMentens N(2018)Design of a Fully Balanced ASIC Coprocessor Implementing Complete Addition Formulas on Weierstrass Elliptic Curves2018 21st Euromicro Conference on Digital System Design (DSD)10.1109/DSD.2018.00095(545-552)Online publication date: Aug-2018
https://doi.org/10.1109/DSD.2018.00095
Miyamoto ESugawara TSakiyama K(2018)Efficient Software Implementation of Modular Multiplication in Prime Fields on TI’s DSP TMS320C6678Information Security Applications10.1007/978-3-319-93563-8_22(261-273)Online publication date: 23-Jun-2018
https://doi.org/10.1007/978-3-319-93563-8_22
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
Rahimzadeh LEshghi MTimarchi S(2014)Radix-4 implementation of redundant interleaved modular multiplication on FPGA2014 22nd Iranian Conference on Electrical Engineering (ICEE)10.1109/IranianCEE.2014.6999599(523-526)Online publication date: May-2014
https://doi.org/10.1109/IranianCEE.2014.6999599
Fouque PGuillermin NLeresteux DTibouchi MZapalowicz J(2013)Attacking RSA–CRT signatures with faults on montgomery multiplicationJournal of Cryptographic Engineering10.1007/s13389-013-0050-x3:1(59-72)Online publication date: 20-Feb-2013
https://doi.org/10.1007/s13389-013-0050-x
Knežević MBatina LDe Mulder EFan JGierlichs BLee YMaes RVerbauwhede I(2013)Signal Processing for Cryptography and Security ApplicationsHandbook of Signal Processing Systems10.1007/978-1-4614-6859-2_7(223-241)Online publication date: 10-May-2013
https://doi.org/10.1007/978-1-4614-6859-2_7
Wolfs DAerts KMentens N(2012)Design space exploration for automatically generated cryptographic hardware using functional languages22nd International Conference on Field Programmable Logic and Applications (FPL)10.1109/FPL.2012.6339174(671-674)Online publication date: Aug-2012
https://doi.org/10.1109/FPL.2012.6339174
Fouque PGuillermin NLeresteux DTibouchi MZapalowicz J(2012)Attacking RSA---CRT signatures with faults on montgomery multiplicationProceedings of the 14th international conference on Cryptographic Hardware and Embedded Systems10.1007/978-3-642-33027-8_26(447-462)Online publication date: 9-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-33027-8_26
Ghosh SMukhopadhyay DRoychowdhury D(2011)Petrel: Power and Timing Attack Resistant Elliptic Curve Scalar Multiplier Based on Programmable ${\rm GF}(p)$ Arithmetic UnitIEEE Transactions on Circuits and Systems I: Regular Papers10.1109/TCSI.2010.210319058:8(1798-1812)Online publication date: Aug-2011
https://doi.org/10.1109/TCSI.2010.2103190
Show More Cited By

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