Montgomery Reduction for Gaussian Integers

Cryptography

Jürgen Freudenberger¹  Malek Safieh¹ 

[1] Institute for System Dynamics (ISD), HTWG Konstanz, University of Applied Sciences, 78462 Konstanz, Germany;

关键词: public-key cryptography;    elliptic curve point multiplication;    Gaussian integers;    Montgomery modular reduction;   

DOI  :  10.3390/cryptography5010006

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown