Highly Efficient Implementation of NIST-Compliant Koblitz Curve for 8-bit AVR-Based Sensor Nodes

This paper presents an efficient implementation of elliptic curve cryptography (ECC) over the National Institute of Standards and Technology (NIST) K-233 curve for 8-bit AVR microcontrollers commonly used for sensor nodes in wireless sensor networks. Until now, several ECC implementations over NIST-compliant curves have been presented on 8-bit sensor nodes. However, most of them do not provide 112-bit security level currently recommended by NIST. Although some works provide more than 112-bit security level, their performance needs to be improved in order to be executed properly on resource-constrained sensor nodes. For optimizing the performance of ECC, we focus on the efficiency of field arithmetics and propose several optimization techniques. First, we present a novel polynomial multiplication technique based on multiplier encoding. The proposed method significantly reduces the required number of registers for a multiplier, which allows the larger block size for the Karatsuba Block-Comb method. The proposed method provides around 17.05% of improvement compared with the best result previously presented. Second, we optimize modular squaring and reduction algorithms considering the features of 8-bit AVR, and each of them provides around 21.86% and 3.7% improvements compared with the related works. With proposed methods, we present two versions of ECC implementation: (highly fast) $HF$ and (highly secure) $HS$ over NIST K-233 curve on an 8-bit ATmega128. Especially, $HF$ version outperforms the best result previously implemented on the same curve by 18.6% and 34.5% for a variable and a fixed-based scalar multiplication, respectively. Furthermore, on the 8-bit AVR platform, our ECC implementation shows the best performance compared with other existing implementations over both NIST-standardized prime or binary curves.