In this paper, we present a highly optimized implementation of elliptic curve cryptography (ECC) over NIST P-256 curve for an 8-bit AVR microcontroller. For improving the performance of ECC implementation, we focus on optimizing field arithmetics. In particular, we optimize the modular multiplication and squaring method exploiting the state-of-the-art optimization technique, namely range shifted representation (RSR). With optimized field arithmetics, we significantly improve the performance of scalar multiplication and set the speed record for execution time of variable base scalar multiplication over NIST P-256 curve. When compared with previous works, we achieve a performance gain of 17.3% over the best previous result on the same platform. Moreover, the execution time of our result is even faster than that over the NIST P-192 curve of the well-known TinyECC library. Our result shows that RSR can be applied to all field arithmetics and evaluate the impact of the adoption of RSR over the performance of scalar multiplication. Additionally, our implementation provides a high degree of regularity to withstand side-channel attacks.
Modular multiplication is one of the most time-consuming operations that account for almost 80% of computational overhead in a scalar multiplication in elliptic curve cryptography. In this paper, we present a new speed record for modular multiplication over 192-bit NIST prime P-192 on 8-bit AVR ATmega microcontrollers. We propose a new integer representation named Range Shifted Representation (RSR) which enables an efficient merging of the reduction operation into the subtractive Karatsuba multiplication. This merging results in a dramatic optimization in the intermediate accumulation of modular multiplication by reducing a significant amount of unnecessary memory access as well as the number of addition operations. Our merged modular multiplication on RSR is designed to have two duplicated groups of 96-bit intermediate values during accumulation. Hence, only one accumulation of the group is required and the result can be used twice. Consequently, we significantly reduce the number of load/store instructions which are known to be one of the most time-consuming operations for modular multiplication on constrained devices. Our implementation requires only 2888 cycles for the modular multiplication of 192-bit integers and outperforms the previous best result for modular multiplication over P-192 by a factor of 17%. In addition, our modular multiplication is even faster than the Karatsuba multiplication (without reduction) which achieved a speed record for multiplication on AVR processor.