Montgomery inversion

Savaş, Erkay and Koç, Çetin Kaya (2018) Montgomery inversion. Journal of Cryptographic Engineering, 8 (3). pp. 201-210. ISSN 2190-8508 (Print) 2190-8516 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)


Multiplicative inversion in finite fields is an essential operation in many cryptographic applications such as elliptic curve and pairing-based cryptography. While the classical extended Euclidean algorithm involves expensive division operations, the binary extended Euclidean and Kaliski’s algorithms use simple shift, addition and subtraction operations. The Montgomery inverse operation is applied when the Montgomery multiplication operation is used for fast arithmetic. As the inversion operation is applied to sensitive data, a constant-time inversion algorithm is useful against a class of side-channel attacks. In this paper, we show different ways of computing the Montgomery inverse of a given integer and compare their complexity in terms of the number of additions/subtractions and shift operations. We also propose a simple parallel algorithm to compute Montgomery inverse, which can be useful in multi-core processors where data sharing among cores is relatively inexpensive. Finally, we propose two efficient constant-time Montgomery inversion algorithms, which are useful as countermeasures against side-channel attacks.
Item Type: Article
Uncontrolled Keywords: Constant-time implementation; Extended Euclidean algorithm; Montgomery inverse; Multiplicative inverse; Parallelization
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 06 Jun 2023 12:05
Last Modified: 06 Jun 2023 12:05

Available Versions of this Item

Actions (login required)

View Item
View Item