Very efficient point multiplication on Koblitz curves

This paper presents a very efficient scheme for point multiplication on Koblitz curves. The proposed scheme reduces the critical path in the data dependency graph of the point addition operation and increases the utilization of the three parallel multipliers that are used. The proposed scheme exploits an idle multiplier to perform an extra field operation that will be needed in the next iteration. Furthermore, the proposed scheme is implemented on an Altera Stratix II EP2S180F1020C3 FPGA over GF(2(163)) and compared with the related parallel schemes in the literature. The results show that the proposed scheme outperforms the previous schemes in terms of the area-time (AT) and AT(2) products. Accordingly, the proposed scheme is very attractive for use in high-performance applications.