# 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
We only use three registers, \(R0,R1\), and \(R2\), in order to hold \(P_{256}\cdot W^{-16}\), because it can only be expressed with three bytes 0x00, 0x01, and 0 xFF in hexadecimal. Let \(R0,R1\), and \(R2\) be zeros. Through the following instructions after the addition, we can hold \(P_{256}\cdot W^{-16}\) or \(0\) in \(R0,R1\), and \(R2\), depending on the carry flag. \[ \begin{split}&\mathit{SBC}\ \mathit{R1}\ \mathit{R0}\\ &\mathit{ADC}\ \mathit{R2}\ \mathit{R0}\end{split} \]

After the 32-byte additions for \(Z=X+Y\), if there is no _carry_, then all three registers are set to zero. Subsequently, the following two subtractions have no effect on the result. If _carry_ from the addition exists, the carry flag is set. Subsequently, the subtract-with-borrow instruction (\(\mathit{SBC}\)) sets \(R1\) as 0 xFF and the carry flag is set again. Afterwards, \(R2\) is set to 0x01 by the following the add-with-carry (\(\mathit{ADC}\)) instruction. Through these instructions, we can hold \(P_{256}\cdot W^{-16}\) in \(R0,R1\), and \(R2\). After the first 32-byte subtractions for \(Z^{\prime}=Z-P_{256}\cdot W^{-16}\), the carry flag may be set by the _borrow_ originating from the last byte subtraction. Note that this new _borrow_ means that \(Z^{\prime}\) is smaller than \(2^{128}\). In other words, no _borrow_ means that \(Z^{\prime}\) is bigger than or equal to \(2^{128}\). Through the following instructions after the first subtraction, we can hold \(P_{256}\cdot W^{-16}\) or \(0\) in \(R0,R1\), and \(R2\). \[ \begin{split}&\mathit{ADC}\ \mathit{R1}\ \mathit{R0}\\ &\mathit{SBC}\ \mathit{R2}\ \mathit{R0}\end{split} \]

If _borrow_ from the first subtraction exists, then \(\mathit{ADC}\) instruction sets \(R1\) as 0x00 and carry flag is set again, because \(R1\) was set to 0 xFF from the previous step. Subsequently, \(R2\) is set to 0x00 through \(\mathit{SBC}\) instruction and we can hold zeros in \(R0,R1\), and \(R2\). If there was no _borrow_, \(P_{256}\cdot W^{-16}\) remains on the three registers. Through these simple carry processes, we can always execute one addition and two final subtraction for a constant time of modular addition. Table 1 represents all of the cases of the _carry_ and the _borrow_, which decide whether the next subtraction is \(-P_{256}\cdot W^{-16}\) or \(-0\). ### Modular Inversion

Extended Euclidean Algorithm (EEA) is widely known as an efficient method for modular inversion. However, EEA has a non-constant execution time, depending on input, which can be exploited by side channel attack, such as timing attack. In order to prevent side channel leakage, we implement [PERSON]'s Little Theorem-based inversion, which has a constant execution time. For \(a\in\mathbb{F}_{\mathbb{P}_{256}\cdot W^{-16}}\), the inversion of \(a\) can be computed via \(a^{-1}\equiv a^{\mathbb{P}_{256}-2}\pmod{P_{256}\cdot W^{-16}}\), which is significantly slower than EEA. ### Conversion of Representation

In order to apply RSR to field operations, conversions from the original representation to RSR and vice versa are required to shift the range of integer representation. Algorithm 4 describes the conversion from the original representation to RSR, where the range is changed from \([0,P_{256}]\) to \([2^{-128},P_{256}\cdot W^{-16}]\). This conversion consists of one 256-bit addition, two 256-bit subtractions, and final subtraction of \(P_{256}\cdot W^{-16}\). This conversion has a negligible amount of clock cycles when compared to a modular multiplication or squaring and is only required for coordinates \(x\) and \(y\) for the input point of scalar multiplication. Reversely, the conversion from RSR to the original representation is required for the output point of scalar multiplication, where the range is restored from \([2^{-128},P_{256}\cdot W^{-16}]\) to \([0,P_{256}]\). Three 256-bit addition, two 256-bit subtractions, and final subtraction of \(P_{256}\) are required, as shown in Algorithm 5.