Comparing design approaches for elliptic curve point multiplication over GF(2k)GF(2k) with polynomial basis representation

Point Multiplication (PM) is considered the most computationally complex and resource hungry Elliptic Curve Cryptography (ECC) mathematical operation. PM hardware accelerator design can follow several approaches that lead to a fast, small or flexible implementation, meeting related application specifications. However, each PM design decision has certain outcomes in utilized hardware resources and computation speed. Such a key design decision is related to the structure of the GF(2k)GF(2k) multipliers to be employed in the PM accelerator. In this paper, we highlight the GF(2k)GF(2k) multiplication role in the overall PM performance and investigate what are the trade-offs on a PM accelerator when using bit serial or bit parallel multiplication approach in terms of speed, chip covered area and flexibility. To achieve this goal, we estimate these tradeoffs for a single point operation and specify realistic design cases for bit serial and bit parallel multiplier based PM design approaches. To evaluate the theoretical modeling, a point operation design methodology based on the parallelism and rescheduling of GF(2k)GF(2k) operations is proposed. This design approach is adapted to two characteristic PM algorithm realizations, the traditional double & add algorithm and the side channel attack resistant Montgomery power ladder algorithm. Our goal is to assess the resulting PM accelerator overall performance so as to achieve high speed with an acceptable cost on chip covered area (hardware resources). Using this methodology, PM is performed in series of GF(2k)GF(2k) parallelism stages. To test the proposed methodology, 8 PM accelerator use cases are identified that can offer high speed, flexibility, side channel attack resistance or small chip covered area. To provide fair comparisons and results, a common PM architecture is devised and the use case PM accelerators are implemented in FPGA technology. Depending on the designers goal, the proposed architectures and 8 implementations can offer the benefit of either high speed (the proposed work is currently one of the fastest known GF(2k)GF(2k) bit parallel multiplier based PM realization) or flexibility with reasonable compromises in chip covered area.