Cryptology ePrint Archive: Report 2014/1009

A Preliminary FPGA Implementation and Analysis of Phatak’s Quotient-First Scaling Algorithm in the Reduced-Precision Residue Number System

Christopher D. Nguyen and Dhananjay S. Phatak and Steven D. Houston and Alan T. Sherman

Abstract: We built and tested the first hardware implementation of Phatak’s Quotient-First Scaling (QFS) algorithm in the reduced-precision residue number system (RP-RNS). This algorithm is designed to expedite division in the Residue Number System for the special case when the divisor is known ahead of time (i.e., when the divisor can be considered to be a constant, as in the modular exponentiation required for the RSA encryption/decryption). We implemented the QFS algorithm using an FPGA and tested it for operand lengths up to 1024 bits. The RP-RNS modular exponentiation algorithm is not based on Montgomery’s method, but on quotient estimation derived from the straightforward division algorithm, with substantial amount of precomputations whose results are read from look-up tables at run-time.

Phatak’s preliminary analysis indicates that under reasonable assumptions about hardware capabilities, a single modular multiplication’s (or QFS’s) execution time grows logarithmically with respect to the operand word length. We experimentally confirmed this predicted growth rate of the delay of a modular multiplication with our FPGA implementation. Though our implementation did not outperform the most recent implementations such as that by Gandino, et al., we determined that this outcome was solely a consequence of tradeoffs stemming from our decision to store the lookup tables on the FPGA.

Category / Keywords: implementation / Reduced-Precision Residue Number System, Residue Number System (RNS), modular exponentiation, Quotient-First Scaling (QFS) algorithm, computer arithmetic, FPGA hardware

Date: received 18 Dec 2014

Contact author: cn1 at umbc edu

Available format(s): PDF | BibTeX Citation

Note: We hope this preliminary work will be helpful to anyone wishing to carry out another implementation of this promising method.

Version: 20141225:140522 (All versions of this report)

Short URL: ia.cr/2014/1009

Discussion forum: Show discussion | Start new discussion