Montgomery inversion

Savaş, Erkay and Koç, Çetin Kaya (2017) Montgomery inversion. Journal of Cryptographic Engineering . ISSN 2190-8508 (Print) 2190-8516 (Online) Published Online First http://dx.doi.org/10.1007/s13389-017-0161-x

Warning
There is a more recent version of this item available.
[thumbnail of s13389-017-0161-x.pdf] PDF
s13389-017-0161-x.pdf
Restricted to Registered users only

Download (493kB) | Request a copy

Abstract

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: Multiplicative inverse; Extended Euclidean algorithm; Montgomery inverse; Constant-time implementation; Parallelization
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences > Basic Sciences > Mathematics
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 09 Sep 2017 20:30
Last Modified: 26 Apr 2022 09:49
URI: https://research.sabanciuniv.edu/id/eprint/33506

Available Versions of this Item

Actions (login required)

View Item
View Item