# Fast Implementation of NIST P-256 Elliptic Curve Cryptography on 8-Bit AVR Processor
## 1 Introduction
### Our Contributions  
The contributions of this paper are summarized, as follows:  
* We present an efficient algorithm for 256-bit modular multiplication over NIST P-256 prime for 8-bit AVR processor taking advantage of the optimization technique of modular multiplication on RSR in [8]. Because the technique presented in [8] is highly prime-dependent, it cannot be directly adopted to other prime field multiplications and it requires different approaches to other bigger operand lengths considering the limited number of registers. Because the 256-bit intermediate result of multiplication occupies 32 registers, it cannot be held in working registers at a time during the modular multiplication. Hence, careful scheduling of accumulation for processing the intermediate result is required in order to avoid unnecessary memory access, i.e., load/store instructions, which is known to be the most time-consuming instructions for modular multiplication on constrained devices. In order to extend the optimization technique on RSR in [8] for the 256-bit modular multiplication, we propose a new algorithm, which divides the reduction process into two 128-bit parts and carefully schedules the accumulation of the intermediate results of multiplication. Consequently, we significantly reduce the number of load/store instructions during modular multiplication.
* In [8], they only introduce modular multiplication on RSR not including other field operations, such as squaring, addition, and inversion. We focus on applying all field operations on RSR in order to improve the performance of scalar multiplication. Firstly, we propose a new modular squaring over NIST P-256 prime, which is based on the optimization of our 256-bit modular multiplication resulting in a dramatic optimization. This modular squaring set the speed record for 256-bit modular squaring over NIST P-256 prime for 8-bit AVR processor, providing about 24% of improved performance as compared with the state-of-the-art method. Moreover, we propose a modular addition on RSR providing a constant execution time in order to protect from SPA attacks. Finally, we present conversion algorithms from the original integer representation to RSR, and vice versa, which are required for applying RSR to field operations.
* We present a highly optimized ECC implementation over NIST P-256 curve providing 128-bit security on an 8-bit AVR ATmega128 processor. The result of our work only requires \(20.98\times 10^{6}\) cycles, which is faster than previous work in [6]. Our proposed implementation achieves the best performance for P-256 curve on an AVR processor.  
The rest of this paper is organized, as follows. In Section 2, we briefly review the basic ECC, including NIST curve P-256, and also describe the main features of the 8-bit AVR ATmega128 microcontroller. In Section 3, we overview RSR for modular multiplication applied to the NIST P-256 prime. In Section 4, we describe the optimization technique for field operations on RSR. In particular, we propose modular multiplication and squaring method that is optimized for 8-bit AVR processor. Section 5 compares our implementation of scalar multiplication with other previous works. Finally, we conclude this work in Section 6.