Design of a linear systolic array for computing modular multiplication and squaring in GF(2m)

One of the main operations for the public key cryptosystem is the modular exponentiation. In this paper, we analyze the Montgomeryʹs algorithm and design a linear systolic array for performing both modular multiplication and modular squaring simultaneously. The proposed systolic array with less hardware complexity can be designed by making use of common-multiplicand multiplication in the right-to-left modular exponentiation over GF(2m). For the fast computation of the modular exponentiation, the proposed systolic array has 1.25 times improvement in area-time complexity when compared to existing multipliers. The proposed systolic array suffers a little loss in time complexity, but it has 1.44 times improvement in area complexity since it executes the common parts that exist in the simultaneous computation of both modular multiplication and squaring only once. It could be designed on VLSI hardware and used in IC cards.