# 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
This conversion also costs negligible clock cycles, since it is only required for coordinates \(X\) and \(Y\) of the output point. ```
0:\(X=(x_{0},\dots,x_{31})\in\mathbb{F}_{P_{256}}\)
0:\(X^{\prime}=(x^{\prime}_{0},\dots,x^{\prime}_{31})\in\mathbb{F}_{P_{256}\cdot W ^{-16}}\)
1:Define 256-bit integers
2:\(S_{1}=(x_{16},x_{17},\dots,x_{31},x_{0},x_{1},\dots,x_{15})\)
3:\(S_{2}=(x_{20},x_{21},\dots,x_{31},x_{28},x_{29},x_{30},x_{31},0,0,\dots,0,x_{16 },x_{17},x_{18},x_{19})\)
4:\(S_{3}=(x_{28},x_{29},x_{30},x_{31},0,0,\dots,0,x_{20},x_{21},\dots,x_{31},x_{ 20},x_{21},\dots,x_{27})\)
5:\(S_{4}=(0,0,\dots,0,x_{16},x_{17},\dots,x_{27},x_{16},x_{17},x_{18},x_{19},x_{ 28},x_{29},x_{30},x_{31})\)
6:Return\(X^{\prime}=S_{1}+S_{2}-S_{3}-S_{4}\pmod{P_{256}\cdot W^{-16}}\)
```

**Algorithm 4** Conversion from original representation to RSR \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Range of \(Z=X+Y\)** & _Carry_ & **First Sub** & _Borrow_ & **Second Sub** \\ \hline \([0,2^{128}-1]\) & \(0\) & \(-0\) & \(0\) & \(-0\) \\ \hline \([2^{128},2^{128}+P_{256}\cdot W^{-16}-1]\) & \(1\) & \(-P_{256}\cdot W^{-16}\) & \(1\) & \(-0\) \\ \hline \([2^{128}+P_{256}\cdot W^{-16},2^{129}-2]\) & \(1\) & \(-P_{256}\cdot W^{-16}\) & \(0\) & \(-P_{256}\cdot W^{-16}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Number of cases of carry and borrow in modular addition. ## 5 Optimization of Elliptic Curve Group Arithmetic

### Coordinate System for Point Arithmetic

A scalar multiplication is composed of a two point arithmetic operation, i.e., point addition and doubling. There are several ways to represent the points. Affine coordinate system uses two coordinates \(x,y\) and it requires the computation of field inversion in point arithmetic. Because field inversion is a relatively expensive operation, most previous works represent the points in a projective coordinate system. There are plenty of researches that proposed an efficient projective coordinate system, such as Jacobian, Chudnovsky, and mixed coordinate system [21; 22; 23; 24]. When comparing these projective coordinates, it is preferable to choose Jacobian coordinates for the fastest pointer arithmetic operations. While using Jacobian coordinates, the point addition requires \(4M+4S+9A\) (M = modular multiplication, S = modular squaring, A = modular addition) and point doubling requires \(8M+3S+7A\). ### Co-Z Arithmetic

We choose the co-Z arithmetic, which was proposed by [PERSON] in [25], for point arithmetic. It provides a very efficient point addition in Jacobian coordinates, where the two involved points share the same Z-coordinate. The co-Z point addition is faster than a point addition in Jacobian coordinates and even faster than a point doubling. Let \(P=(X_{1},Y_{1},Z)\) and \(Q=(X_{1},Y_{1},Z)\), the point addition of \(P\) and \(Q\) is defined by \(P+Q=(X_{3},Y_{3},Z_{3})\), which is computed, as follows:

\[A =(X_{2}-X_{1})^{2},\ B=X_{1}A,\] \[C =X_{2}A,\ D=(Y_{2}-Y_{1})^{2},\] \[E =Y_{1}(C-B),\] \[X_{3} =D-B-C,\] \[Y_{3} =(Y_{2}-Y_{1})(B-X_{3})-E,\] \[Z_{3} =Z(X_{2}-X_{1}).\]

The co-Z point addition has a computational cost of \(5M+2S+7A\). Moreover, the Z-coordinate of \(P\) is updated to be equal with the Z-coordinate of \(P+Q\) for free. Through the expression of \(B\) and \(E\), we can find out that \(B=X_{1}(X_{2}-X_{1})^{2}=x_{1}Z_{3}^{2}\) and \(E=Y_{1}(X_{2}-X_{1})^{3}=y_{1}Z_{3}^{3}\), where \((x_{1},y_{1})=(X_{1}/Z^{2},Y_{1}/Z^{3})\) represents the affine coordinates of \(P\). Thus, we have \(P\equiv(B:E:Z_{3})\). Such a free update allows for the subsequent use of co-Z point addition between \(P+Q\) and \(P\) during scalar multiplication. In [25], it was shown that the conjugate \(P-Q\) can be obtained with a small additional cost, sharing the same Z coordinate as \(P+Q\).