# 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
In _reduction part_ 1, we can avoid load instructions that are related to \(H_{B}\), because some of portion of the required result, i.e., \((h_{20},h_{21},\ldots,h_{31})\), computed in Step 5 is kept in working registers. Hence, 20 load instructions are required for the remaining portion \((h_{16},h_{17},h_{18},h_{19})\) of \(H_{B}\) and \((l_{0},\ldots,l_{15})\). In the starting point of _reduction part_ 2, we can avoid load instructions for \(L_{A}\), since \((l_{0},\ldots,l_{15})\) from the end point of _reduction part_ 1 can be continuously used. Eventually, an additional 20 load instructions for \((l_{0},l_{1},l_{2},l_{3})\) and \((h_{16},\ldots,h_{31})\) are required in order to complete _reduction part_ 2. At the end of Algorithm 1, the positive carry \(carry_{12}\) and the negative carry \(carry_{15}\) are reduced to the intermediate result \(T=(T_{L},T_{R})\). ### Modular Squaring

We propose an optimized modular squaring on RSR. Modular squaring consists of a _product part_, an _accumulation part_, and two _reduction parts_, as shown in Algorithm 3. We adopt 2-level subtractive Karatsuba method for implementation of modular squaring. For three 128-bit squaring operations \(L,H\), and \(M\) in _product part_ in Algorithm 3, the 128-bit Karatsuba technique can be applied, which make use of left shift instruction for the processing of equal cross-product terms. Note that the absolute difference of \(M\) in the subtractive Karatsuba multiplication is always positive. Thus, no calculation for the sign of \(M\) is required in _product part_. Through combining squaring operation with reduction, we can get the duplicated accumulations as same as \((L_{A}+L_{B}+H_{A}+H_{B})\) in modular multiplication (17). This can be used in order to avoid redundant memory access during modular squaring by reusing it in _reduction part_ 2 in Algorithm 3. Hence, an _accumulation part_ and two _reduction parts_ in Algorithm 3 follow the same process of Algorithm 1. ```
0:\(X=(x_{0},\ldots,x_{31})\)
0:\(Z=X^{2}\pmod{P_{256}\cdot W^{-16}}=(z_{0},\ldots,z_{31})\)
1:Product part
2:\(X_{A}\gets X_{B}\) {Load: \(X\),Store:\((X_{A}-X_{B})\)}
3:\(M=(X_{A}-X_{B})^{2}=(m_{0},\ldots,m_{31})\) {Load: \((X_{A}-X_{B})\),Store:\(M\)}
4:\(L\gets X_{2}^{2}=(l_{0},\ldots,l_{31})\) {Load: \(X_{A}\),Store: \(L\)}
5:\(H\gets X_{B}^{2}=(h_{0},\ldots,h_{31})\) {Load: \(X_{B}\),Store: \(H\)}
6:Accumulation part and Reduction part 1,2 as in the Algorithm 1
```
**Algorithm 3** 256-bit \(\times\) 256-bit modular squaring over \(\mathbb{F}_{P_{256}\cdot W^{-16}}\)

### Modular Addition

Because we use operands \(X,Y\in[0,2^{128}-1]\) for modular addition, \(X+Y=Z\in[0,2^{129}-2]\) needs to be subtracted by \(P_{256}\cdot W^{-16}\), at most, twice in order to ensure \(Z\) becoming less than \(2^{128}\). If \(Z\in[0,2^{128}-1]\), there is nothing to do. If \(Z\in[2^{128},2^{128}+P_{256}\cdot W^{-16}-1]\), only one subtraction of \(P_{256}\cdot W^{-16}\) is needed in order to ensure that the final result is smaller than \(2^{128}\). If \(Z\in[2^{128}+P_{256}\cdot W^{-16},2^{129}-2]\), two subtractions of \(P_{256}\cdot W^{-16}\) are necessary. These conditional subtraction statements, depending on the range of \(Z\), cause observable differences in the execution time that can be used to find a secret value by a side-channel attacker [20]. For the constant execution time implementation, we always execute two final subtractions after the addition \(X+Y\). The two subtractions may be \(-P_{256}\cdot W^{-16}\) or \(-0\). Because the 256-bit addition result cannot be held in 32 working registers, some parts of it have to be stored and reloaded repeatedly through the following two subtractions. We can reduce memory access by minimizing unnecessary register uses. For example, the addition only consists of 32-byte additions without an additional register for the _carry_-byte that is produced from the last byte addition. The _carry_ that is held in carry flag decides whether the next subtraction is \(-P_{256}\cdot W^{-16}\) or \(-0\).