Abstract: The arithmetic operations over GF(2m) have been
extensively used in error correcting codes and public-key
cryptography schemes. Finite field arithmetic includes addition,
multiplication, division and inversion operations. Addition is very
simple and can be implemented with an extremely simple circuit.
The other operations are much more complex. The multiplication
is the most important for cryptosystems, such as the elliptic
curve cryptosystem, since computing exponentiation, division, and
computing multiplicative inverse can be performed by computing
multiplication iteratively. In this paper, we present a parallel
computation algorithm that operates Montgomery multiplication over
finite field using redundant basis. Also, based on the multiplication
algorithm, we present an efficient semi-systolic multiplier over finite
field. The multiplier has less space and time complexities compared
to related multipliers. As compared to the corresponding existing
structures, the multiplier saves at least 5% area, 50% time, and 53%
area-time (AT) complexity. Accordingly, it is well suited for VLSI
implementation and can be easily applied as a basic component for
computing complex operations over finite field, such as inversion and
division operation.
Abstract: Modular multiplication is the basic operation
in most public key cryptosystems, such as RSA, DSA, ECC,
and DH key exchange. Unfortunately, very large operands
(in order of 1024 or 2048 bits) must be used to provide
sufficient security strength. The use of such big numbers
dramatically slows down the whole cipher system, especially
when running on embedded processors.
So far, customized hardware accelerators - developed on
FPGAs or ASICs - were the best choice for accelerating
modular multiplication in embedded environments. On the
other hand, many algorithms have been developed to speed
up such operations. Examples are the Montgomery modular
multiplication and the interleaved modular multiplication
algorithms. Combining both customized hardware with
an efficient algorithm is expected to provide a much faster
cipher system.
This paper introduces an enhanced architecture for computing
the modular multiplication of two large numbers X
and Y modulo a given modulus M. The proposed design is
compared with three previous architectures depending on
carry save adders and look up tables. Look up tables should
be loaded with a set of pre-computed values. Our proposed
architecture uses the same carry save addition, but replaces
both look up tables and pre-computations with an enhanced
version of sign detection techniques. The proposed architecture
supports higher frequencies than other architectures.
It also has a better overall absolute time for a single operation.