# Fast Implementation of NIST P-256 Elliptic Curve Cryptography on 8-Bit AVR Processor
## 1 Introduction
### Related Work  
In [1], [PERSON] et al. presented the first ECC implementation on an 8-bit AVR processor. Before this result, it is believed that ECC is infeasible to be implemented for constrained devices, since it requires a significant amount of computation. This work focuses on numerous data transport to and from memory during multi-precision multiplication of large integers in limited register space. For minimizing the number of load instruction on a processor with a large register file, they proposed the new hybrid method, which combines the advantage of conventional byte-wise multiplication techniques, such as the row-wise and the column-wise methods. They could compute a scalar multiplication in 2.19 s for NIST P-224 curve at a frequency of 8 MHz, i.e., 17.52 \(\times\) 10\({}^{6}\) clock cycles on AVR processor. In 2008, [PERSON] et al. presented TinyECC [2], which is a first well-known and widely used cryptographic library containing various platforms, such as 8-bit AVR-based, 16-bit MSP-based, and 32-bit ARM-based devices. TinyECC includes a set of optimization switches for flexible configuration by developer's needs, which gives different execution time and memory consumption. TinyECC supports all 128-bit, 160-bit, and 192-bit NIST-recommended elliptic curves. TinyECC is evaluated on MICAz, TelosB, Tmote Sky, and Imote2, which provide the measurement of performance and resource consumption from the low-end devices to high-end devices. They also used the hybrid method for optimizations for the multiplication and squaring operation. Recently, researches on ECC implementations over NIST prime curves on an 8-bit AVR processor were conducted in [3; 6]. [PERSON] et al. implemented ECC over NIST P-192 curve on 8-bit AVR processor [3] and achieved an execution time of 8.62 \(\times\) 10\({}^{6}\) clock cycles for scalar multiplication, which is the best result. With respect to NIST P-256 curve, [PERSON] et al. [6] achieved the fastest performance, with an execution time of 25.38 \(\times\) 10\({}^{6}\) clock cycles. Both of the works adopted the Karatsuba method that was proposed by [PERSON] and [PERSON] [7] for the optimization of multiplication and squaring operations, which leads to the best performance with respect to scalar multiplication. Hence, this Karatsuba method is considered to be the best way for the implementation of multiplication. In summary, many researches showed that ECC implementations can be feasible for resource-constrained devices and their main purpose is to optimize the performance of a scalar multiplication by using fast multiplication techniques. However, they did not consider modular reduction operation as a crucial part for improving performance, despite it always following every multiplication and squaring. The reduction operation introduces huge memory access by recalling the previous results of multiplication and squaring. In the context of modular multiplication, [PERSON] et al. [8] introduced new Karatsuba technique while using new integer representation, namely, Range Shifted Representation (RSR). Their work achieved the best performance for 192-bit modular multiplication over NIST P-192 prime. Because their optimization technique is highly prime-dependent, different optimization approaches are required to adopt their technique to modular multiplication over other primes. Moreover, in order to apply RSR to other field operations i.e., squaring, addition, and inversion, new attempts need to be considered for efficient implementation. In addition, resistance against side channel attacks is required to ensure secure ECC implementation. Traditional ECC implementations did not consider any countermeasures for preventing side-channel attacks, such as Simple Power Analysis (SPA), which might cause security threats on embedded devices [9; 10; 11]. SPA attacks usually exploit the conditional statements in ECC implementation, which leak secret information.