Next Article in Journal
Flash-Based Security Primitives: Evolution, Challenges and Future Directions
Previous Article in Journal
Acknowledgment to Reviewers of Cryptography in 2020
Article

Montgomery Reduction for Gaussian Integers

Institute for System Dynamics (ISD), HTWG Konstanz, University of Applied Sciences, 78462 Konstanz, Germany
*
Author to whom correspondence should be addressed.
This paper is an extended version of our paper Safieh, M.; Freudenberger, J. Montgomery Modular Arithmetic over Gaussian Integers. In Proceedings of the 24th International Information Technology Conference (IT), Zabljak, Montenegro, 18–22 February 2020; pp. 1–4.
Received: 13 January 2021 / Revised: 27 January 2021 / Accepted: 29 January 2021 / Published: 1 February 2021
Modular arithmetic over integers is required for many cryptography systems. Montgomery reduction is an efficient algorithm for the modulo reduction after a multiplication. Typically, Montgomery reduction is used for rings of ordinary integers. In contrast, we investigate the modular reduction over rings of Gaussian integers. Gaussian integers are complex numbers where the real and imaginary parts are integers. Rings over Gaussian integers are isomorphic to ordinary integer rings. In this work, we show that Montgomery reduction can be applied to Gaussian integer rings. Two algorithms for the precision reduction are presented. We demonstrate that the proposed Montgomery reduction enables an efficient Gaussian integer arithmetic that is suitable for elliptic curve cryptography. In particular, we consider the elliptic curve point multiplication according to the randomized initial point method which is protected against side-channel attacks. The implementation of this protected point multiplication is significantly faster than comparable algorithms over ordinary prime fields. View Full-Text
Keywords: public-key cryptography; elliptic curve point multiplication; Gaussian integers; Montgomery modular reduction public-key cryptography; elliptic curve point multiplication; Gaussian integers; Montgomery modular reduction
Show Figures

Figure 1

MDPI and ACS Style

Safieh, M.; Freudenberger, J. Montgomery Reduction for Gaussian Integers. Cryptography 2021, 5, 6. https://0-doi-org.brum.beds.ac.uk/10.3390/cryptography5010006

AMA Style

Safieh M, Freudenberger J. Montgomery Reduction for Gaussian Integers. Cryptography. 2021; 5(1):6. https://0-doi-org.brum.beds.ac.uk/10.3390/cryptography5010006

Chicago/Turabian Style

Safieh, Malek, and Jürgen Freudenberger. 2021. "Montgomery Reduction for Gaussian Integers" Cryptography 5, no. 1: 6. https://0-doi-org.brum.beds.ac.uk/10.3390/cryptography5010006

Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.

Article Access Map by Country/Region

1
Back to TopTop