Fast point multiplication on Koblitz curves: Parallelization method and implementations

Point multiplication is required in every elliptic curve cryptosystem and its efficient implementation is essential. Koblitz curves are a family of curves defined over F2mF2m allowing notably faster computation. We discuss implementation of point multiplication on Koblitz curves with parallel field multipliers. We present a novel parallelization method utilizing point operation interleaving. FPGA implementations are described showing the practical feasibility of our method. They compute point multiplications on average in 4.9 μs, 8.1 μs, and 12.1 μs on the standardized curves NIST K-163, K-233, and K-283, respectively, in an Altera Stratix II FPGA.