17-03-2014, 05:24 PM
Abstract
Large multipliers are important for cryptographic applications
because they need large keys. The ability to modify
key lengths, for security reasons, suggests adaptability
in multiplication bit-length. However, reconfigurability of
multiplication is a difficult task, especially when bit-lengths
are large, say over 500 bits. For fixed bit-lengths, much
work has been done in the range of 32, 64 or even 128 bits
for advanced microprocessors and DSPs. The objective of
this work is to design large adaptable bit-length multipliers
that can be employed in cryptographic systems. We present
a multiplication scheme for higher radix multiplexer-based
array multipliers and we suggest a parallelization of the
scheme within a single FPGA based implementation. We
also suggest a novel partition of the multiplier into folded
pipeline stages such that each stage can be instantiated by
reconfiguration from its preceding stage during the multiplication
operation. The number of partition stages is flexible
to meet the FPGA resource constraints. The rationale
for pipeline folding is that the multiplier size may preclude
a monolithic implementation within one FPGA chip. Using
additional FPGAs reduces performance due to interchip
communication. Results of large reconfigurable multipliers
for 256-bits and over implemented in Xilinx Virtex4 are provided.
1 Introduction
The multiplier is the core component of major cryptographic
applications such as RSA and Elliptic Curve
Cryptosystems [18]. For cryptographic systems, the overall
performance improves with the increase of the multiplier
bit-width [14]. Different multiplication schemes have been
proposed. Some of these schemes are for positive number
multiplication [9], [3], [5], and [6]; two’s complement
multiplication schemes are [1] and [10]; and Booth’s
algorithm schemes are [2] and [13]. These schemes use
iterative circuits that have uniform interconnections [16].
Schemes that are realized by multiplexer-based arrays
which implement both positive and two’s complement
numbers are in [16]. In general, it is difficult to embed
large multipliers in an FPGA.
A large bit-width multiplier to be used in cryptography
should meet the following criteria:
• Adaptability: The multiplier should be bit-width scalable
and not fixed. Scalability can be achieved by reconfigurability
on the fly, which is themajor advantage
of FPGAs.
• Performance: The multiplier should be very fast to improve
the performance of the over all system. This can
be achieved by using a fast multiplier architecture.
• Small size: The multiplier should have a reasonable
size that can fit in one FPGA and permit for other components
in the system to fit in the FPGA. If the size is
very large then, it will need more than one FPGA to
map the system. This means more cost and less performance
because of going out of the chip. As the bitwidth
of the multiplier increases the size of the multiplier
increases. There should be a way to reduce the
size of the multiplier as the bit-width increase. One
way to achieve this is partitioning.
The adapted public-key cryptosystem, such as RSA
[19] and ECC [11], involve modular multiplication which
is repeated in the kernel of these schemes [20] and [22].
The Montgomery algorithm [15] is one of the well-known
algorithms for modular multiplication [20]. The full-word
version of Montgomery’s multiplication algorithm still
requires the basic multiplication of two large numbers [12]
and [14].
Large multipliers are important for cryptographic applications
because they need large keys. The ability to modify
key lengths, for security reasons, suggests adaptability
in multiplication bit-length. However, reconfigurability of
multiplication is a difficult task, especially when bit-lengths
are large, say over 500 bits. For fixed bit-lengths, much
work has been done in the range of 32, 64 or even 128 bits
for advanced microprocessors and DSPs. The objective of
this work is to design large adaptable bit-length multipliers
that can be employed in cryptographic systems. We present
a multiplication scheme for higher radix multiplexer-based
array multipliers and we suggest a parallelization of the
scheme within a single FPGA based implementation. We
also suggest a novel partition of the multiplier into folded
pipeline stages such that each stage can be instantiated by
reconfiguration from its preceding stage during the multiplication
operation. The number of partition stages is flexible
to meet the FPGA resource constraints. The rationale
for pipeline folding is that the multiplier size may preclude
a monolithic implementation within one FPGA chip. Using
additional FPGAs reduces performance due to interchip
communication. Results of large reconfigurable multipliers
for 256-bits and over implemented in Xilinx Virtex4 are provided.
1 Introduction
The multiplier is the core component of major cryptographic
applications such as RSA and Elliptic Curve
Cryptosystems [18]. For cryptographic systems, the overall
performance improves with the increase of the multiplier
bit-width [14]. Different multiplication schemes have been
proposed. Some of these schemes are for positive number
multiplication [9], [3], [5], and [6]; two’s complement
multiplication schemes are [1] and [10]; and Booth’s
algorithm schemes are [2] and [13]. These schemes use
iterative circuits that have uniform interconnections [16].
Schemes that are realized by multiplexer-based arrays
which implement both positive and two’s complement
numbers are in [16]. In general, it is difficult to embed
large multipliers in an FPGA.
A large bit-width multiplier to be used in cryptography
should meet the following criteria:
• Adaptability: The multiplier should be bit-width scalable
and not fixed. Scalability can be achieved by reconfigurability
on the fly, which is themajor advantage
of FPGAs.
• Performance: The multiplier should be very fast to improve
the performance of the over all system. This can
be achieved by using a fast multiplier architecture.
• Small size: The multiplier should have a reasonable
size that can fit in one FPGA and permit for other components
in the system to fit in the FPGA. If the size is
very large then, it will need more than one FPGA to
map the system. This means more cost and less performance
because of going out of the chip. As the bitwidth
of the multiplier increases the size of the multiplier
increases. There should be a way to reduce the
size of the multiplier as the bit-width increase. One
way to achieve this is partitioning.
The adapted public-key cryptosystem, such as RSA
[19] and ECC [11], involve modular multiplication which
is repeated in the kernel of these schemes [20] and [22].
The Montgomery algorithm [15] is one of the well-known
algorithms for modular multiplication [20]. The full-word
version of Montgomery’s multiplication algorithm still
requires the basic multiplication of two large numbers [12]
and [14].