More Web Proxy on the site http://driver.im/

research-article

Hybrid Montgomery Reduction

Authors:

Yasuyuki Nogami,

Howon KimAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 15, Issue 3

Article No.: 58, Pages 1 - 13

https://doi.org/10.1145/2890502

Published: 23 May 2016 Publication History

Abstract

In this article, we present a hybrid method to improve the performance of the Montgomery reduction by taking advantage of the Karatsuba technique. We divide the Montgomery reduction into two sub-parts, including one for the conventional Montgomery reduction and the other one for Karatsuba-aided multiplication. This approach reduces the multiplication complexity of n-limb Montgomery reduction from θ(n² + n) to asymptotic complexity θ (7n²/8 +n). Our practical implementation results over an 8-bit microcontroller also show performance enhancements by 11%.

References

[1]

Atmel Corporation. 2008. 8-bit ARV^® Microcontroller with 128K Bytes In-System Programmable Flash: ATmega128, ATmega128L. Datasheet, available for download at http://www.atmel.com/dyn/resources/prod_documents/doc2467.pdf.

[2]

Daniel J. Bernstein. 2009. Batch binary Edwards. In Advances in Cryptology-CRYPTO 2009. Springer, 317--336.

Digital Library

[3]

Daniel J. Bernstein, Chitchanok Chuengsatiansup, and Tanja Lange. 2014. Curve41417: Karatsuba revisited. In Cryptographic Hardware and Embedded Systems--CHES 2014. Springer, 316--334.

Digital Library

[4]

Joppe W. Bos, Peter L. Montgomery, Daniel Shumow, and Gregory M. Zaverucha. 2014. Montgomery multiplication using vector instructions. In Selected Areas in Cryptography — SAC 2013 (Lecture Notes in Computer Science), Tanja Lange, Kristin Lauter, and Petr Lisonek (Eds.), Vol. 8282. Springer Verlag, 471--489.

[5]

Paul G. Comba. 1990. Exponentiation cryptosystems on the IBM PC. IBM Systems Journal 29, 4 (Dec. 1990), 526--538.

Digital Library

[6]

Michael Düll, Björn Haase, Gesine Hinterwälder, Michael Hutter, Christof Paar, Ana Helena Sánchez, and Peter Schwabe. 2015. High-speed Curve25519 on 8-bit, 16-bit and 32-bit microcontrollers. Design, Codes and Cryptography 77, 2--3 (2015), 493--514. Retrieved from http://cryptojedi.org/papers/#mu25519.

Digital Library

[7]

Johann Großschädl, Roberto M. Avanzi, Erkay Savaş, and Stefan Tillich. 2005. Energy-efficient software implementation of long integer modular arithmetic. In Cryptographic Hardware and Embedded Systems--CHES 2005. Springer, 75--90.

Digital Library

[8]

Nils Gura, Arun Patel, Arvinderpal S. Wander, Hans Eberle, and Sheueling Chang Shantz. 2004. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In Cryptographic Hardware and Embedded Systems — CHES 2004 (Lecture Notes in Computer Science), Marc Joye and Jean-Jacques Quisquater (Eds.), Vol. 3156. Springer Verlag, 119--132.

[9]

Michael Hutter and Peter Schwabe. 2015. Multiprecision multiplication on AVR revisited. Journal of Cryptographic Engineering 5, 3 (2015), 201--214. Retrieved from http://cryptojedi.org/papers/#avrmul.

[10]

Michael Hutter and Erich Wenger. 2011. Fast multi-precision multiplication for public-key cryptography on embedded microprocessors. In Cryptographic Hardware and Embedded Systems--CHES 2011. Springer, 459--474.

Digital Library

[11]

Anatolii Karatsuba and Yu Ofman. 1963. Multiplication of multidigit numbers on automata. In Soviet Physics Doklady, Vol. 7. 595.

[12]

Çetin Kaya Koç, Tolga Acar, and Burton S. Kaliski Jr. 1996. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro 16, 3 (1996), 26--33.

Digital Library

[13]

Younho Lee, Ill-Hee Kim, and Yongsu Park. 2013. Improved multi-precision squaring for low-end RISC microcontrollers. Journal of Systems and Software 86, 1 (2013), 60--71.

Digital Library

[14]

Zhe Liu and Johann Großschädl. 2014. New speed records for Montgomery modular multiplication on 8-bit AVR microcontrollers. In Progress in Cryptology--AFRICACRYPT 2014. Springer, 215--234.

[15]

Zhe Liu, Johann Großschädl, and Ilya Kizhvatov. 2010. Efficient and side-channel resistant RSA implementation for 8-bit AVR microcontrollers. In Proceedings of the Workshop on the Security of the Internet of Things (SOCIOT).

[16]

Zhe Liu, Hwajeong Seo, Johann Groszschädl, and Howon Kim. 2014. Reverse product-scanning multiplication and squaring on 8-bit AVR processors. In Proceedings of the 16th International Conference on Information and Communications Security (ICICS’14). Springer Verlag.

[17]

Stefan Mangard, Elisabeth Oswald, and Thomas Popp. 2008. Power Analysis Attacks: Revealing the Secrets of Smart Cards. Vol. 31. Springer Science & Business Media.

Digital Library

[18]

Peter L. Montgomery. 1985. Modular multiplication without trial division. Mathematics of Computation 44, 170 (1985), 519--521.

[19]

Peter L. Montgomery. 2005. Five, six, and seven-term Karatsuba-like formulae. IEEE Transactions on Computers 54, 3 (2005), 362--369.

Digital Library

[20]

Hwajeong Seo and Howon Kim. 2012. Multi-precision multiplication for public-key cryptography on embedded microprocessors. In Information Security Applications. Springer, 55--67.

[21]

Hwajeong Seo, Zhe Liu, Jongseok Choi, and Howon Kim. 2013. Multi-precision squaring for public-key cryptography on embedded microprocessors. In Progress in Cryptology--INDOCRYPT 2013. Springer, 227--243.

Digital Library

[22]

Hwajeong Seo, Zhe Liu, Johann Großschädl, and Howon Kim. 2015. Efficient arithmetic on ARM-NEON and its application for high-speed RSA implementation. IACR Cryptology ePrint Archive 465.

[23]

T. Yanik, E. Savas, and Ç. K. Koç. 2002. Incomplete reduction in modular arithmetic. In IEE Proceedings on Computers and Digital Techniques, Vol. 149. IET, 46--52.

Cited By

Ren PSuda RSuppakitpaisarn V(2023)Efficient Additions and Montgomery Reductions of Large Integers for SIMD2023 IEEE 30th Symposium on Computer Arithmetic (ARITH)10.1109/ARITH58626.2023.00034(48-59)Online publication date: 4-Sep-2023
https://doi.org/10.1109/ARITH58626.2023.00034
Seo HSanal PLee WAzarderakhsh R(2021)No Silver Bullet: Optimized Montgomery Multiplication on Various 64-Bit ARM PlatformsInformation Security Applications10.1007/978-3-030-89432-0_16(194-205)Online publication date: 11-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-89432-0_16
Ding HHuang M(2017)PolyPC: Polymorphic parallel computing framework on embedded reconfigurable system2017 27th International Conference on Field Programmable Logic and Applications (FPL)10.23919/FPL.2017.8056770(1-8)Online publication date: Sep-2017
https://doi.org/10.23919/FPL.2017.8056770
Show More Cited By

Index Terms

Hybrid Montgomery Reduction
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
      1. Embedded software
2. Security and privacy
  1. Cryptography
    1. Information-theoretic techniques
    2. Public key (asymmetric) techniques
      1. Public key encryption

Recommendations

Faster Interleaved Modular Multiplication Based on Barrett and Montgomery Reduction Methods

This paper proposes two improved interleaved modular multiplication algorithms based on Barrett and Montgomery modular reduction. The algorithms are simple and especially suitable for hardware implementations. Four large sets of moduli for which the ...
Montgomery Multiplication for Public Key Cryptography on MSP430X

For traditional public key cryptography and post-quantum cryptography, such as elliptic curve cryptography and supersingular isogeny key encapsulation, modular multiplication is the most performance-critical operation among basic arithmetic of these ...
A General Approach for Improving RNS Montgomery Exponentiation Using Pre-processing
ARITH '11: Proceedings of the 2011 IEEE 20th Symposium on Computer Arithmetic

The hardware implementation of modular exponentiation for very large integers is a well-known topic in digital arithmetic. An effective approach for obtaining parallel and carry-free implementations consists in using the Montgomery exponentiation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 15, Issue 3

July 2016

520 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2899033

Editor:
Sandeep K. Shukla
Indian Institute of Technology, India

Issue’s Table of Contents

Copyright © 2016 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 23 May 2016

Accepted: 01 January 2016

Revised: 01 November 2015

Received: 01 July 2015

Published in TECS Volume 15, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Institute for Information & communications Technology Promotion (IITP)
MSIP (Ministry of Science, ICT and Future Planning), Korea, under the ITRC (Information Technology Research Center)
Korea government (MSIP)
Development of high performance IoT device and Open Platform with Intelligent Software
IITP (Institute for Information & communications Technology Promotion)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
229
Total Downloads

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

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ren PSuda RSuppakitpaisarn V(2023)Efficient Additions and Montgomery Reductions of Large Integers for SIMD2023 IEEE 30th Symposium on Computer Arithmetic (ARITH)10.1109/ARITH58626.2023.00034(48-59)Online publication date: 4-Sep-2023
https://doi.org/10.1109/ARITH58626.2023.00034
Seo HSanal PLee WAzarderakhsh R(2021)No Silver Bullet: Optimized Montgomery Multiplication on Various 64-Bit ARM PlatformsInformation Security Applications10.1007/978-3-030-89432-0_16(194-205)Online publication date: 11-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-89432-0_16
Ding HHuang M(2017)PolyPC: Polymorphic parallel computing framework on embedded reconfigurable system2017 27th International Conference on Field Programmable Logic and Applications (FPL)10.23919/FPL.2017.8056770(1-8)Online publication date: Sep-2017
https://doi.org/10.23919/FPL.2017.8056770
Ding JLi S(2017)Broken-Karatsuba multiplication and its application to Montgomery modular multiplication2017 27th International Conference on Field Programmable Logic and Applications (FPL)10.23919/FPL.2017.8056769(1-4)Online publication date: Sep-2017
https://doi.org/10.23919/FPL.2017.8056769

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents