# A Crypto Accelerator of Binary Edward Curves for Securing Low-Resource Embedded Devices
## 2 Mathematical Background
### Fixed Window Algorithm  
The fixed window method used in Algorithm 1 aims to optimize point multiplication by reducing the required point additions and doublings. This method takes advantage of the binary representation of the scalar multiplier \"\(K\)\" and performs point operations based on the bits of \"\(K\)\" using a fixed window size of \"\(w\)\". The optimization lies in the fact that instead of performing point additions or doublings for each individual bit of \"\(K\)\", Algorithm 1 processes multiple bits simultaneously within a window. By doing so, it reduces the number of expensive point operations and improves the overall efficiency of the point multiplication.  
The outer loop of Algorithm 1 iterates through the bits of \"\(K\)\" from the most significant bit (\(m-1\)) to the least significant bit (0). Within each iteration, the algorithm performs a point addition operation using the dADD function. If the current bit is 1, an additional point doubling operation is performed using the dbL function. The inner loop, introduced within the outer loop, handles the fixed window technique. It iterates from the current bit position minus one (\(i-1\)) down to the maximum value of either (\(i-w+1\)) or 0. For each iteration, a point doubling operation is performed using the dbL function. If the  
\begin{table}
\begin{tabular}{c l} \hline \hline
**Instructions** & **Original Formulas** \\ \hline \(Instr_{1}\) & A \(\gets W_{1}\times Z_{1}\) \\ \hline \(Instr_{2}\) & B \(\gets W_{1}\times W_{2}\) \\ \hline \(Instr_{3}\) & C \(\gets Z_{1}\times Z_{2}\) \\ \hline \(Instr_{4}\) & \(W_{d}\gets A\times A\) \\ \hline \(Instr_{5}\) & \(Z_{d}\leftarrow((e_{1}\times W_{1}+Z_{1})^{4})\) \\ \hline \(Instr_{6}\) & \(Z_{a}\leftarrow(e_{2}\times B+\mathsf{C})^{2}\) \\ \hline \(Instr_{7}\) & \(W_{a}\leftarrow(B\times\mathsf{C}+w\times Z_{a})^{2}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: PA and PD instructions.  
corresponding bit is 1, an additional point addition operation is performed using the dADD function. By incorporating the fixed window method, the proposed algorithm reduces the number of point additions and doublings. Instead of performing these operations for each bit, it processes multiple bits at once within a fixed window. This optimization improves the efficiency of point multiplication, especially for large scalar values.  
```
Input:\(E_{B,d_{1},d_{2}}/GF(2^{m}):d_{1}(x+y)+d_{2}(x+y)^{2}=xy(x+1)(y+1)\), \(P\in E_{B,d_{1},d_{2}}\) and \(k=(k_{m-1},\ldots,k_{1},k_{0})\) ; Output:\(Q=w(k.P)\) ; (\(W_{1}:Z_{1}),(W_{2}:Z_{2}),:\); \(W_{1}=0\), \(Z_{1}=1\), \(W_{2}=w(P)\), \(Z_{2}=w(P)\); ; for\((i\ from\ m-1\ down\ to\ 0)\)do (\((W_{1}:Z_{1}),(W_{2}:Z_{2})):=dADD((W_{0}:Z_{0}),(W_{1}:Z_{1}),(W_{2}:Z_{2}))\); if\(k_{i}=1\)then (\((W_{2}:Z_{2}),(W_{1}:Z_{1})):=dADD((W_{0}:Z_{0}),(W_{2}:Z_{2}),(W_{1}:Z_{1}))\); for\((j\ from\ i-1\ down\ to\ max(i-w+1,0))\)do (\((W_{1}:Z_{1}),(W_{2}:Z_{2})):=dbL((W_{0}:Z_{0}),(W_{1}:Z_{1}),(W_{2}:Z_{2}))\); if\(k_{j}=1\)then (\((W_{2}:Z_{2}),(W_{1}:Z_{1})):=dADD((W_{0}:Z_{0}),(W_{2}:Z_{2}),(W_{1}:Z_{1}))\); return\((W_{1}:Z_{1}),(W_{2}:Z_{2})\);
```  
**Algorithm 1**Point multiplication based on fixed window algorithm.