# A Crypto Accelerator of Binary Edward Curves for Securing Low-Resource Embedded Devices
## 3 Proposed Hardware Architecture
### Arithmetic Logic Unit
#### 3.5.1 Montgomery Multiplier Algorithm  
The proposed multiplication algorithm is based on the Montgomery reduction method. It works by transforming the input numbers into a special representation called the Montgomery form. In this method, the modular reduction operation is simplified and can be performed in a constant time. Furthermore, it refers to the use of a base-4 representation of the numbers. As a result, faster multiplication and reduction operations are obtained. It multiplies the two n-bit input operands \((X,Y)\) mod \(p\) as follows: \((X\times Y\times R^{-1})\). The greatest common divisor (GCD) of \(R\) and \(p\) is 1, i.e., \(GCD(R,p)\). In this case, \(p\) is frequently a prime integer and \(R=2^{n}\). The two integers \(X\) and \(Y\) should be multiplied by \(GF\) in the \([0,p]\) range. \(X\) and \(Y\) must be converted into the Montgomery domain in order to multiply them. Subsequently, in the Montgomery domain, these numbers are multiplied to calculate the result \(Z_{p}\). The result \(Z_{p}\) is translated back to its original domain after being computed in the Montgomery domain. A division operation must be performed since the multiplication requires reduction (mod \(p\)). The required division process is replaced by the shift and add operations used in the Montgomery multiplication. However, many \(GF\) multiplications are carried out consecutively, making this conversion cost negligible.  
The radix-4 Montgomery multiplication is described in Algorithm 2. The input operands are \(X_{p}\) and \(Y_{p}\), while \(p\) is the prime number mentioned in Algorithm 2. \(Z_{p}\) has the final result calculated by \(X_{p}\times Y_{p}\times R\) mod \(p\). Step 1 of Algorithm 2 defines that the initial value of the accumulator is zero. In step 2 of Algorithm 2, it is demonstrated that each time that the loop iterates, a partial product, or \(X_{pi}\times Y_{p}\), is generated and added to accumulator \(A\). The partial product \(X_{pi}\times Y_{p}\), as illustrated in Table 2, will either be _zero_ or \(Y_{p}\) depending on the value of \(X_{pi}\). Steps 3-5 of Algorithm 2 are performed in order to carry out the operation indicated by the following equation:  
\[A_{(i+1)}=(A_{i}+PP_{i}+q_{i}\times p)/4 \tag{4}\]  
In Equation (4), \(A_{i}\) represents an accumulator, \(PP_{i}\) represents the partial product over each iteration, and \(q_{i}\) represents the quotient resulting from the addition result in step 4 of Algorithm 2. The multiplicands \(X_{p}\) and \(Y_{p}\), which are \(Z_{p}\) in step 6 of Algorithm 2, arefound in \(A_{i}\) after \(n/2\) iterations. Booth encoding, as explained in Section 3.5.2, is employed to construct the partial product.  
```
Input:\(p,X_{p},Y_{p}:X_{p}\geq 0,Y_{p}\leq p\) Output:\((Z_{p}=X_{p}\times R\times\ Y_{p})\bmod p\)  Accumulator (A) = 0 \(\longrightarrow\) Step 1 for(\(i=0\) to length\(-1\); \(i=i+2\)) do \(PP_{i}=X_{p}(i+1:i)\times Y_{p}\longrightarrow\) Step 2 \(B_{i}=PP_{i}+A_{i}\longrightarrow\) Step 3 \(Q_{i}=\)B[1:0] \(mod\) 4 \(\longrightarrow\) Step 4 \(A_{(i+1)}=(Q_{i}+B_{i}\times p)/4\longrightarrow\) Step 5 \(Z_{p}=A\longrightarrow\) Step 6 End For return:\(Z_{p}\)
```  
**Algorithm 2** Montgomery multiplier radix-4 [34].