Article

Parallelized radix-4 scalable montgomery multipliers

Authors:

Nathaniel Ross Pinckney,

David Money HarrisAuthors Info & Claims

SBCCI '07: Proceedings of the 20th annual conference on Integrated circuits and systems design

Pages 306 - 311

https://doi.org/10.1145/1284480.1284562

Published: 03 September 2007 Publication History

Get Access

Abstract

This paper describes a parallelized radix-4 scalable Montgomery multiplier implementation. The design does not require hardware multipliers, and uses parallelized multiplication to shorten the critical path. By left-shifting the sources rather than right-shifting the result, the latency between processing elements is shortened from two cycles to nearly one. The new design can perform 1024-bit modular exponentiation in 8.7 ms and 256-bit exponentiation in 0.36 ms using 5916 Virtex2 4-input lookup tables. This is comparable to radix-2 for long multiplies and nearly twice as fast for short ones.

References

[1]

P. Montgomery, "Modular multiplication without trial division," Math. of Computation, vol. 44, no. 170, pp. 519--521, April 1985.

Crossref

Google Scholar

[2]

A. Tenca and Ç. Koç, "A scalable architecture for modular multiplication based on Montgomery's algorithm," IEEE Trans. Computers, vol. 52, no. 9, Sept. 2003, pp. 1215--1221.

Digital Library

Google Scholar

[3]

D. Harris, R. Krishnamurthy, M. Anders, S. Mathew, and S. Hsu, "An improved unified scalable radix-2 Montgomery multiplier," Proc. 17th IEEE Symp. Computer Arithmetic, pp. 172--178, 2005.

Digital Library

Google Scholar

[4]

A. Tenca and L. Tawalbeh, "An efficient and scalable radix-4 modular multiplier design using recoding techniques," Proc. Asilomar Conf. Signals, Systems, and Computers, pp. 1445--1450, 2003.

Google Scholar

[5]

A. Tenca, G. Todorov, and Ç. Koç, "High-radix design of a scalable modular multiplier," Cryptographic Hardware and Embedded Systems, Ç. Koç and C. Paar, eds., 2001, Lecture Notes in Computer Science, No. 1717, pp. 189--206, Springer, Berlin, Germany.

Digital Library

Google Scholar

[6]

Y. Fan, X. Zeng, Y. Yu, G. Wang, and Q. Zhang, "A modified high-radix scalable Montgomery multiplier," Proc. Intl. Symp. Circuits and Systems, pp. 3382--3385, 2006.

Google Scholar

[7]

K. Kelley and D. Harris, "Parallelized very high radix scalable Montgomery multipliers," Proc. Asilomar Conf. Signals, Systems, and Computers, pp. 1196--1200, Nov. 2005.

Google Scholar

[8]

K. Kelley and D. Harris, "Very high radix scalable Montgomery multipliers," Proc. 5th Intl. Workshop on System-on-Chip, pp. 400--404, July 2005.

Digital Library

Google Scholar

[9]

H. Orup, "Simplifying quotient determination in high-radix modular multiplication," Proc. 12th IEEE Symp. Computer Arithmetic, pp. 193--199, July 1995.

Digital Library

Google Scholar

[10]

T. Blum and C. Paar, "High-radix Montgomery multiplication on reconfigurable hardware," IEEE Trans. Computers, vol. 50, no. 7, July 2001, pp. 759--764.

Digital Library

Google Scholar

[11]

C. Walter, "Montgomery exponentiation needs no final subtractions," Electronics Letters, vol. 35, no. 21, pp. 1831--1832, 14 October 1999.

Crossref

Google Scholar

[12]

G. Hachez and J. Quisquater, "Montgomery exponentiation with no final subtractions: improved results," Lecture Notes in Computer Science, C. Koç and C. Paar, eds., vol. 1965, pp. 293--301, 2000.

Digital Library

Google Scholar

[13]

N. Jiang and D. Harris, "Parallelized Radix-2 Scalable Montgomery Multiplier," submitted to IFIP Intl. Conf. on VLSI, 2007.

Google Scholar

Cited By

View all

Zhang BCheng ZPedram M(2022)High-Radix Design of a Scalable Montgomery Modular Multiplier With Low LatencyIEEE Transactions on Computers10.1109/TC.2021.305299971:2(436-449)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TC.2021.3052999
Shieh MLin W(2019)Word-Based Montgomery Modular Multiplication Algorithm for Low-Latency Scalable ArchitecturesIEEE Transactions on Computers10.1109/TC.2010.7259:8(1145-1151)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1109/TC.2010.72
Kwon THong J(2019)Secure and Efficient Broadcast Authentication in Wireless Sensor NetworksIEEE Transactions on Computers10.1109/TC.2009.17159:8(1120-1133)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1109/TC.2009.171
Show More Cited By

Index Terms

Parallelized radix-4 scalable montgomery multipliers
1. Hardware
  1. Integrated circuits
    1. Logic circuits
      1. Arithmetic and datapath circuits
  2. Robustness
    1. Design for manufacturability
      1. Yield and cost modeling
      2. Yield and cost optimization

Recommendations

Montgomery Multiplication with Twice the Bit-Length of Multipliers

We present a novel approach for computing 2 n -bit Montgomery multiplications with n -bit hardware Montgomery multipliers. Smartcards are usually equipped with such hardware Montgomery multipliers; however, due to progresses in factoring algorithms, the ...
High-Speed RSA crypto-processor with radix-4 modular multiplication and chinese remainder theorem
ICISC'06: Proceedings of the 9th international conference on Information Security and Cryptology

Today, RSA is one of the most popular public-key crypto-system in various applications. In this paper, we present a high-speed RSA crypto-processor with modified radix-4 Montgomery multiplication algorithm and Chinese Remainder Theorem (CRT). Our design ...
A unified and reconfigurable Montgomery Multiplier architecture without four-to-two CSA
SBCCI '07: Proceedings of the 20th annual conference on Integrated circuits and systems design

This paper presents an improved version of unified Montgomery multiplier architecture to reduce the critical path delay leading to higher data throughput. It is known that the critical path delay due to four-to-two carry save adders (CSAs), which have ...

Comments

Information & Contributors

Information

Published In

SBCCI '07: Proceedings of the 20th annual conference on Integrated circuits and systems design

September 2007

382 pages

ISBN:9781595938169

DOI:10.1145/1284480

General Chair:
Antonio Petraglia
UFRJ, Brazil
,
Program Chairs:
Volnei A. Pedroni
UTFPR, Brazil
,
Gert Cauwenberghs
UCSD

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 September 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SBCCI07

Sponsor:

SBCCI07: 20th Symposium on Integrated Circuits and System Design

September 3 - 6, 2007

Copacabana, Rio de Janeiro

Acceptance Rates

Overall Acceptance Rate 133 of 347 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
286
Total Downloads

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

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhang BCheng ZPedram M(2022)High-Radix Design of a Scalable Montgomery Modular Multiplier With Low LatencyIEEE Transactions on Computers10.1109/TC.2021.305299971:2(436-449)Online publication date: 1-Feb-2022
https://doi.org/10.1109/TC.2021.3052999
Shieh MLin W(2019)Word-Based Montgomery Modular Multiplication Algorithm for Low-Latency Scalable ArchitecturesIEEE Transactions on Computers10.1109/TC.2010.7259:8(1145-1151)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1109/TC.2010.72
Kwon THong J(2019)Secure and Efficient Broadcast Authentication in Wireless Sensor NetworksIEEE Transactions on Computers10.1109/TC.2009.17159:8(1120-1133)Online publication date: 3-Jan-2019
https://dl.acm.org/doi/10.1109/TC.2009.171
Rezai AKeshavarzi P(2016)High-performance scalable architecture for modular multiplication using a new digit-serial computationMicroelectronics Journal10.1016/j.mejo.2016.07.01255:C(169-178)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1016/j.mejo.2016.07.012
Lin WYe JShieh M(2014)Scalable Montgomery Modular Multiplication Architecture with Low-Latency and Low-Memory Bandwidth RequirementIEEE Transactions on Computers10.1109/TC.2012.21863:2(475-483)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1109/TC.2012.218
Ottoy GLapon JNaessens VPreneel BDe Strycker L(2013)Dedicated Hardware for Attribute-Based Credential VerificationCommunications and Multimedia Security10.1007/978-3-642-40779-6_4(50-65)Online publication date: 2013
https://doi.org/10.1007/978-3-642-40779-6_4
Mourelle LRaposo SNedjah NSantana M(2012)Massively parallel modular exponentiation method and its implementation in software and hardware for high-performance cryptographic systemsIET Computers & Digital Techniques10.1049/iet-cdt.2011.00746:5(290-301)Online publication date: 1-Sep-2012
https://doi.org/10.1049/iet-cdt.2011.0074
Nassar MEl-Sayed L(2012)Radix-4 Modified Interleaved Modular Multiplier Based on Sign DetectionAdvances in Computer Science and Information Technology. Computer Science and Engineering10.1007/978-3-642-27308-7_45(413-423)Online publication date: 2012
https://doi.org/10.1007/978-3-642-27308-7_45
Perin GMesquita DMartins J(2011)Montgomery modular multiplication on reconfigurable hardwareInternational Journal of Reconfigurable Computing10.1155/2011/1271472011(1-10)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.1155/2011/127147
Amberg PPinckney NHarris D(2008)Parallel high-radix Montgomery multipliers2008 42nd Asilomar Conference on Signals, Systems and Computers10.1109/ACSSC.2008.5074513(772-776)Online publication date: Oct-2008
https://doi.org/10.1109/ACSSC.2008.5074513

View Options

Login options

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

Cited By

Index Terms

Recommendations

Montgomery Multiplication with Twice the Bit-Length of Multipliers

High-Speed RSA crypto-processor with radix-4 modular multiplication and chinese remainder theorem

A unified and reconfigurable Montgomery Multiplier architecture without four-to-two CSA

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

Login options

Full Access

PDF

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Montgomery Multiplication with Twice the Bit-Length of Multipliers

High-Speed RSA crypto-processor with radix-4 modular multiplication and chinese remainder theorem

A unified and reconfigurable Montgomery Multiplier architecture without four-to-two CSA

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations