Automatic Generation of Modular Multipliers for FPGA Applications

Since redundant number systems allow constant time addition, they are often at the heart of modular multipliers designed for public key cryptography (PKC) applications. Indeed, PKC involves large operands (160 to 1024 bits) and several researchers proposed carry-save or borrow-save algorithms. Howev...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2008-12, Vol.57 (12), p.1600-1613
Main Authors: Beuchat, J.-L., Muller, J.-M.
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Arithmetic and Logic Structures
Computer Science
Cryptography
Digits
Equations
Field programmable gate arrays
Hardware
High-Speed Arithmetic
Logic gates
Modular
Multipliers
Other
Representations
Signal generators
VHDL
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Since redundant number systems allow constant time addition, they are often at the heart of modular multipliers designed for public key cryptography (PKC) applications. Indeed, PKC involves large operands (160 to 1024 bits) and several researchers proposed carry-save or borrow-save algorithms. However, these number systems do not take advantage of the dedicated carry logic available in modern field programmable gate arrays (FPGAs). To overcome this problem, we suggest to perform modular multiplication in a high-radix carry-save number system, where a sum bit of the carry-save representation is replaced by a sum word. Two digits are then added by means of a small Carry-Ripple Adder (CRA). Furthermore, we propose an algorithm which selects the best high-radix carry-save representation for a given modulus, and generates a synthesizable VHDL description of the operator.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2008.102