FFT-based McLaughlin's montgomery exponentiation without conditional selections
Yükleniyor...
Dosyalar
Tarih
2018
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
IEEE Computer Society
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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. © 2012 IEEE.
Açıklama
Koç, Çetin Kaya ( isu author)
Anahtar Kelimeler
Field-Programmable Gate Array (Fpga), Modular Exponentiation, Montgomery Modular Multiplication, Number-Theoretic Weighted Transform, Rsa Encryption
Kaynak
IEEE Transactions on Computers
WoS Q Değeri
Scopus Q Değeri
Q1
Cilt
67
Sayı
9
Künye
Dai, W., Chen, D., Cheung, R. C., & Koç, Ç. K. (2018). FFT-Based McLaughlin's Montgomery Exponentiation without Conditional Selections. IEEE Transactions on Computers, 67(9), 1301-1314.
