# Fast Implementation of NIST P-256 Elliptic Curve Cryptography on 8-Bit AVR Processor
## 3 Range Shifted Representation for Modular Multiplication
### Modular Multiplication on RSR
The conjugate \(P-Q=(X_{3}^{\prime},Y_{3}^{\prime},Z_{3})\) can be computed, as follows:

\[F =(Y_{1}+Y_{2})^{2},\] \[X_{3}^{\prime} =F-(B+C),\] \[Y_{3}^{\prime} =(Y_{1}+Y_{2})(X_{3}^{\prime}-B)-E.\]

With computation of two co-Z points \(P+Q\) and \(P-Q\), we can compute the co-Z point addition with the cost of \(6M+3S+16A\). ### Montgomery Ladder for Regular Scalar Multiplication

For resistance against SPA attack, we consider a regular scalar multiplication algorithm, which always performs the same operations in each iteration, regardless of input scalar. For regular scalar multiplication, we choose the Montgomery ladder proposed by _[PERSON]_ in [26] for the short Weierstrass-form elliptic curves over large prime field. This Montgomery algorithm is based on the co-Z arithmetic, which only uses \((X,Y)\) coordinates without the computation of \(Z\) coordinate in aJacobian coordinate system. The co-Z point addition takes the \((X,Y)\) coordinates of two co-Z points \(P\) and \(Q\) and computes the \((X,Y)\) coordinates of \(P+Q\) and \(P\) at the cost of \(4M+2S+7A\). On the other hand, the co-Z conjugate point addition computes the \((X,Y)\) coordinates of \(P+Q\) and of \(P-Q\) at the cost of \(5M+3S+11A\). The Montgomery ladder algorithm computes scalar multiplication with a regular pattern, which always performs the co-Z point addition and the co-Z conjugate point addition in each iteration. Hence, our scalar multiplication provides resistance against SPA attack. ## 6 Performance Analysis and Comparison

We implement scalar multiplication over NIST P-256 curve on 8-bit AVR ATmega128 processor. More precisely, we optimize field level operations on RSR, including modular multiplication, modular squaring, and modular addition by assembly language. We implement the elliptic curve group operations and scalar multiplication by C language. We use the computer algebra system _Magma_ in order to validate the results of scalar multiplication. We simulate all test programs with AVR studio 7.0 in order to obtain execution time in clock cycles. Table 2 compares the execution time of the proposed field arithmetic operations with the best result previously published. A modular addition and subtraction require 390 clock cycles, while a modular multiplication and squaring need 5355 and 3691 clock cycles, respectively. When compared with the work conducted by [PERSON] et al. [6], our implementation of modular addition and subtraction is slightly faster, while modular multiplication and squaring provide about 20% and 24% of improved performance, respectively. Table 3 compares our work with other prime field ECC implementations over different NIST curves with respect to execution time, SPA resistance, and code size. Those implementations use NIST primes that range from 192-bit to 256-bit, which provide more than 80-bit security. Our ECC implementation over NIST P-256 curve only requires \(20.98\times 10^{6}\) cycles which is faster than previous work in [6]. Our proposed implementation achieves the best performance for the P-256 curve. The work of [PERSON] et al. [6] on NIST P-256 curve adopted Montgomery ladder with \((x,y)\)-only co-Z addition for implementation of scalar multiplication as our work. Hence, the gap of performance between the work in [6] and our work comes from our optimization of field level operations, especially modular multiplication and modular squaring. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Implementation** & **ADD** & **SUB** & **MUL** & **SQL** & **INV** \\ \hline [PERSON] et al. [6] & 418 & 424 & 6609 & 4919 & 1,347,009 \\ This paper & 390 & 390 & 5355 & 3691 & 1,031,682 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of field arithmetic on ATmega128 processor in clock cycles.