FFT-Based McLaughlin’s Montgomery Exponentiation without Conditional Selections

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

4 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1301-1314
Journal / PublicationIEEE Transactions on Computers
Volume67
Issue number9
Online published5 Mar 2018
Publication statusPublished - Sep 2018

Abstract

Modular multiplication forms the basis of many cryptographic functions such as RSA, Diffie-Hellman key exchange, and ElGamal encryption. For large RSA moduli, combining the fast Fourier transform (FFT) with McLaughlin’s Montgomery modular multiplication (MLM) has been validated to offer cost-effective implementation results. However, the conditional selections in McLaughlin’s algorithm are considered to be inefficient and vulnerable to timing attacks, since extra long additions or subtractions may take place and the running time of MLM varies. In this work, we restrict the parameters of MLM by a set of new bounds and present a modified MLM algorithm involving no conditional selection. Compared to the original MLM algorithm, we inhibit extra operations caused by the conditional selections and accomplish constant running time for modular multiplications with different inputs. As a result, we improve both area-time efficiency and security against timing attacks. Based on the proposed algorithm, efficient FFT-based modular multiplication and exponentiation are derived. Exponentiation architectures with dual FFT-based multipliers are designed obtaining area-latency efficient solutions. The results show that our work offers a better efficiency compared to the state-of-the-art works from and above 2048-bit operand sizes. For single FFT-based modular multiplication, we have achieved constant running time and obtained area-latency efficiency improvements up to 24.3% for 1,024-bit and 35.5% for 4,096-bit operands, respectively.

Research Area(s)

  • Computer architecture, Convolution, Cryptography, field-programmable gate array (FPGA), Hardware, modular exponentiation, Montgomery modular multiplication, number-theoretic weighted transform, RSA encryption, Timing, Transforms