Parameter Space for the Architecture of FFT-Based Montgomery Modular Multiplication

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

17 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number7070700
Pages (from-to)147-160
Journal / PublicationIEEE Transactions on Computers
Volume65
Issue number1
Online published26 Mar 2015
Publication statusPublished - Jan 2016

Abstract

Modular multiplication is the core operation in public-key cryptographic algorithms such as RSA and the Diffie-Hellman algorithm. The efficiency of the modular multiplier plays a crucial role in the performance of these cryptographic methods. In this paper, improvements to FFT-based Montgomery Modular Multiplication (FFTM3) using carry-save arithmetic and pre-computation techniques are presented. Moreover, pseudo-Fermat number transform is used to enrich the supported operand sizes for the FFTM3. The asymptotic complexity of our method is O(l log, l log log l), which is the same as the Schönhage-Strassen multiplication algorithm (SSA). A systematic procedure to select suitable parameter set for the FFTM3 is provided. Prototypes of the improved FFTM3 multiplier with appropriate parameter sets are implemented on Xilinx Virtex-6 FPGA. Our method can perform 3,100-bit and 4,124-bit modular multiplications in 6.74 and 7.78 μs, respectively. It offers better computation latency and area-latency product compared to the state-of-the-art methods for operand size of 3,072-bit and above.

Research Area(s)

  • field-programmable gate array (FPGA), Montgomery modular multiplication, number theoretic transform (NTT), parallel computation, Schonhage-Strassen Algorithm

Citation Format(s)

Parameter Space for the Architecture of FFT-Based Montgomery Modular Multiplication. / Chen, Donald Donglong; Yao, Gavin Xiaoxu; Cheung, Ray C.C.; Pao, Derek; Koç, Çetin Kaya.

In: IEEE Transactions on Computers, Vol. 65, No. 1, 7070700, 01.2016, p. 147-160.

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