Modular Multiplication Methods and Respective Hardware Implementations


  Modular Multiplication Methods and Respective.pdf (Size: 993.55 KB / Downloads: 0)


Introduction

Electronic communication is growing exponentially
so should be the care for information security issues [10].
Data exchanged over public computer networks must be
authenticated, kept confidential and its integrity protected
against alteration. In order to run successfully, electronic
businesses require secure payment channels and digital
valid signatures. Cryptography provides a solution to all
these problems and many others [17].
One of the main objectives of cryptography consists
of providing confidentiality, which is a service used to
keep secret publicly available information from all but
those authorized to access it. There exist many ways to
providing secrecy. They range from physical protection
to mathematical solutions, which render the data
unintelligible. The latter uses encryption/decryption
methods [10], [17], [30], [31].


Efficient Multiplication Methods

The multiply-then-reduce methods consist of first
computing the product then reducing it with respect to
the given modulus. This method is generally preferred as
there are very fast on-the-shelf multiplication algorithms
as they were over studied [3], [12], [33]. The nowadays
most popular multiplication methods that are suitable for
hardware implementation are Karatsuba-Ofman’s
method and Booth’s method.


Karatsuba-Ofman Method
Karatsuba-Ofman’s algorithm is considered one of the
fastest ways to multiply long integers. Generalizations of
this algorithm were shown to be even faster than
Schönhage-Strassen’s FFT method [35], [36]. Karatsuba-
Ofman’s algorithm is based on a divide-and-conquer
strategy. A multiplication of a 2n-digit integer is reduced
to two n-digits multiplications, one (n+1)-digits
multiplication, two n-digits subtractions, two left-shift
operations, two n-digits additions and two 2n-digits
additions.


Booth’s Multiplication Method

Algorithms that formalize the operation of multiplication
generally consist of two steps: one generates a partial
product and the other accumulates it with the previous
partial products. The most basic algorithm for
multiplication is based on the add-and-shift method: the
shift operation generates the partial products while the
add step sums them up [3].


The Montgomery Algorithm
Algorithms that formalize the operation of modular
multiplication generally consist of two steps: one
generates the product P = A×B and the other reduces this
product P modulo M.
The straightforward way to implement a
multiplication is based on an iterative adder-accumulator
for the generated partial products. However, this solution
is quite slow as the final result is only available after n
clock cycles, n is the size of the operands [19].