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

[img]PDF - Registered users only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1007/s13389-017-0161-x


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
ID Code:33506
Deposited By:Erkay Savaş
Deposited On:09 Sep 2017 20:30
Last Modified:09 Sep 2017 20:30

Repository Staff Only: item control page