FFT-Based McLaughlin's Montgomery Exponentiation without Conditional Selections

• Published in: IEEE transactions on computers 2018-09, Vol.67 (9), p.1301-1314
• Main Authors: Dai, Wangchen, Chen, Donglong, Cheung, Ray C. C., Koc, Cetin Kaya
• Format: Article
• Language: English
• Subjects: Algorithms; Computer architecture; Convolution; Cryptography; Efficiency; Encryption; Fast Fourier transformations; field-programmable gate array (FPGA); Fourier transforms; Hardware; modular exponentiation; Montgomery modular multiplication; Multiplication; Multiplication & division; number-theoretic weighted transform; RSA encryption; Run time (computers); Timing; Transforms
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2018.2811466

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 percent for 1,024-bit and 35.5 percent for 4,096-bit operands, respectively.