A review of modular multiplication methods and respective hardware implementations

english

2006

volume 30, issue 1

Slovensko društvo Informatika
(Obvezni izvod spletne publikacije)

Generally speaking, public-key cryptographic system consist of raising elements of some group such as GF(2n), Z/NZ or elliptic curves, to large powers and reducing the result modulo some given elements. Such operation is often called modular exponentiation and is performed using modular multiplications repeatedly. The practicality of a given cryptographic system depends heavily on how fast modular exponentiations are performed. Consequently, it also depends on how efficiently modular multiplications are done as thee are at base of the computation. This problem has received much attention over the years. Software as well as hardware efficient implementation were proposed. However, the results are scattered through the literature. In this paper we survey most known and recent methods for efficient modular multiplication, investigating and examining their strengths and weaknesses. For each method presented, we provide and adequate hardware implementation.

21.04.2016