Applying systolic multiplication–inversion architectures based on modified extended Euclidean algorithm for GF(2k) in elliptic curve cryptography

Elliptic curve cryptography is a very promising cryptographic method offering the same security level as traditional public key cryptosystems (RSA, El Gamal) but with considerably smaller key lengths. However, the computational complexity and hardware resources of an elliptic curve cryptosystem are very high and depend on the efficient design of EC point operations and especially point multiplication. Those operations, using the elliptic curve group law, can be analyzed in operations of the underlined GF(2k) Field. Three basic GF(2k) Field operations exist, addition–subtraction, multiplication and inversion–division. In this paper, we propose an optimized inversion algorithm that can be applied very well in hardware avoiding well known inversion problems. Additionally, we propose a modified version of this algorithm that apart from inversion can perform multiplication using the architectural structure of inversion. We design two architectures that use those algorithms, a two-dimensional multiplication/inversion systolic architecture and an one-dimensional multiplication/inversion systolic architecture. Based on either one of those proposed architectures a GF(2k) arithmetic unit is also designed and used in a EC arithmetic unit that can perform all EC point operations required for EC cryptography. The EC arithmetic unit’s design methodology is proposed and analyzed and the effects of utilizing the one or two-dimensional multiplication/inversion systolic architecture are considered. The performance of the system in all its design steps is analyzed and comparisons are made with other known designs. We manage to design a GF(2k) arithmetic unit that has the space and time complexity of an inverter but can perform all GF(2k) operations and we show that this architecture can apply very well to an EC arithmetic unit required in elliptic curve cryptography.