# 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
```
0:\(X=(x_{0},\ldots,x_{31})\), \(Y=(y_{0},\ldots,y_{31})\)
0:\(Z=X\cdot Y\pmod{P_{256}\cdot W^{-16}}=(z_{0},\ldots,z_{31})\)
1:Product part
2:\(|X_{A}-X_{B}|\) and \(|Y_{A}-Y_{B}|\) [Load: \(X\),\(Y\),Store:\(|X_{A}-X_{B}|,|Y_{A}-Y_{B}|\)]
3:\(M\leftarrow|X_{A}-X_{B}|\cdot|Y_{A}-Y_{B}|=(m_{0},\ldots,m_{31})\) [Load: \(|X_{A}-X_{B}|,|Y_{A}-Y_{B}|\),Store:\(M\)]
4:\(L\gets X_{A}\cdot Y_{A}=(l_{0},\ldots,l_{31})\) [Load: \(X_{A},Y_{A}\),Store: \(L\)]
5:\(H\gets X_{B}\cdot Y_{B}=(h_{0},\ldots,h_{31})\) [Load: \(X_{B}\),\(Y_{B}\),Store: \(H\)]
6:Accumulation part
7:\((t_{0},\ldots,t_{15},carry_{1})\gets H_{A}+H_{B}\) [Load: \(H_{A}\)]
8:\((t_{0},\ldots,t_{15},carry_{2})\leftarrow(t_{0},\ldots,t_{15},carry_{1})+L_{A} +L_{B}\) [Load: \(L_{A},L_{B}\)]
9:Store \((T_{R},carry_{2})=(t_{0},\ldots,t_{15},carry_{2})\) [Store: \(T_{R},carry_{2}\)]
10:Reduction part
11:\((T_{L},carry_{3})\leftarrow(t_{0},\ldots,t_{15},carry_{2})+(h_{120},h_{21}, \ldots,h_{31},h_{28},h_{29},h_{30},h_{31})\)
12:\((T_{L},carry_{4})\gets T_{L}-(h_{28},h_{29},h_{30},h_{31},0,\ldots,0,h_{20},h _{21},h_{22},h_{23})\)
13:\((T_{L},carry_{5})\leftarrow(T_{L},carry_{4})-(0,\ldots,0,h_{16},h_{17},h_{18},h _{19})\) [Load: \((h_{16},h_{17},h_{18},h_{19})\)]
14:\((T_{L},carry_{6})\leftarrow(T_{L},carry_{3})+(0,\ldots,0,l_{0},l_{1},\ldots,l_{7}) +(0,0,0,0,0,0,0,l_{0},l_{1},l_{2},l_{3},0,0,0,0)\) [Load:\((l_{0},\ldots,l_{7})\)]
15:\((T_{L},carry_{7})\leftarrow(T_{L},carry_{5})-(0,\ldots,0,l_{0},l_{1},l_{2},l_{3})\)
16:\((T_{L},carry_{8})\leftarrow(T_{L},carry_{6})+(l_{4},l_{5},\ldots,l_{15},0,0,0,0)\) [Load:\((l_{8},l_{9},\ldots,l_{15})\)]
17:\(T_{L}\leftarrow T_{L}-M_{A}\) [Load:\(M_{A}\),Store: \((T_{L},carry_{7},carry_{8})\)]
18:Reduction part
19:\((T_{R},carry_{9})\gets T_{R}-M_{B}\) [Load:\(T_{R},M_{B}\)]
20:\((T_{R},carry_{10})\leftarrow(T_{R},carry_{9})-(l_{4},l_{5},\ldots,l_{15},0,0,0,0)\)
21:\((T_{R},carry_{11})\gets T_{R}+(l_{8},l_{9},\ldots,l_{15},0,0,0,0,l_{0},l_{ 0},l_{1},l_{2},l_{3})\) [Load:\((l_{0},l_{1},l_{2},l_{3})\)]
22:\((T_{R},carry_{12})\leftarrow(T_{R},carry_{11})+(carrys,0,0,0,l_{0},l_{1},l_{2},l_{3},0,0,0,0,h _{16},h_{17},h_{18},h_{19},carry_{2})\) [Load:\((h_{16},h_{17},h_{18},h_{19},carry_{2},carry_{8})\)]
23:\((T_{R},carry_{13})\leftarrow(T_{R},carry_{10})-(carry_{7},0,0,0,0,0,0,l_{0},l_{1},l_{2},l_{3},h _{24},h_{25},h_{26},h_{27})\)
24:\((T_{R},carry_{14})\leftarrow(T_{R},carry_{13})-(h_{24},\ldots,h_{31},h_{16},h_{17},h _{18},h_{19},h_{28},h_{29},h_{30},h_{31})\)
25:\((T_{R},carry_{15})\leftarrow(T_{R},carry_{14})-(h_{20},\ldots,h_{27},h_{20},h _{21},h_{22},h_{23},0,0,0)\) [Load:\((h_{20},h_{21},h_{22},h_{23})\)]
26:Reduce \(carry_{12},carry_{15}\) through \(T=(T_{L},T_{R})\) [Load:\(T_{L}\)]
27:Store \(T\) to \((z_{0},\ldots,z_{31})\) [Store: \(T_{L},T_{R}\)]Figure 1: Process of 256-bit Modular multiplication with RSR. Generally, for a reduction operation, the result of multiplication should be first computed. Subsequently, reduction is proceeded with handling of double-sized result, such as 512-bit result \((z_{0},\ldots,z_{63})\) in Algorithm 2, which causes huge memory access, since the number of registers is limited. However, for the case of Algorithm 1, we only need to reduce \(L_{A}\) and \(H_{B}\) at both sides, as shown in Figure 0(a). In other words, we can easily merge reduction operation into multiplication without requiring the complete result of multiplication, as shown in Figure 0(b). In _reduction part_ 1 and 2, we cannot hold \(L_{A}\) and \(H_{B}\) altogether in registers, because 16 working registers are always occupied by the intermediate results \(T_{L}\) or \(T_{R}\). Hence, repeated load instructions for them are required during _reduction part_ 1 and 2. In order to minimize the number of load instructions, we carefully schedule the order of load instructions for \(L_{A}\) and \(H_{B}\), as shown in Figure 0(b).