tailieunhanh - A Review of Modular Multiplication Methods and Respective Hardware Implementations

Generally speaking, public-key cryptographic systems 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 element. | Informatica 30 2006 111-129 111 A Review of Modular Multiplication Methods and Respective Hardware Implementations Nadia Nedjah Department of Electronics Engineering and Telecommunications Engineering Faculty State University of Rio de Janeiro Rio de Janeiro Brazil nadia@ http nadia Luiza de Macedo Mourelle Department of System Engineering and Computation Engineering Faculty State University of Rio de Janeiro Rio de Janeiro Brazil ldmm@ http .br ldmm Keywords cryptography encryption modular multiplication modular reduction. Received April 18 2005 Generally speaking public-key cryptographic systems 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 element. 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 these are at the 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 an adequate hardware implementation. Povzetek Podan je pregled modernih metod kriptografije. 1 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. .