# Throughput/Area Optimized Architecture for Elliptic-Curve Diffie-Hellman Protocol
## 3 Proposed ECDH Architecture
### Arithmetic and Logic Unit (ALU)  
It consists of an \(ADDER\), \(MULT\) and a reduction unit. The polynomial addition in \(GF(2^{m})\) is less complex as compared to the prime field. The implementation of an \(ADDER\) includes an array of bitwise Exclusive (OR) gates. It bears two polynomials, i.e., \(MD_{1}\) and \(MD_{2}\), as input and results an \(m\)-bit polynomial (\(A_{out}\)) as output. The performance of the entire crypto accelerator architecture depends on the performance of the used multiplier. Based on several polynomial multiplication techniques, described in [25], there are four possibilities to implement a multiplier circuit. These possibilities are (i) bit-serial, (ii) digit-serial, (iii) bit-parallel and (iv) digit-parallel. For two \(m\) bit input operands, the bit-serial multipliers require \(m\) clock cycles for computation. A schoolbook multiplication method is a typical example of bit-serial multiplication. In digit-serial multipliers, \(\frac{p}{q}\) clock cycles are required for one polynomial multiplication, where \(p\) determines the operand length and \(q\) is the digit size. Moreover, the computational cost in bit/digit parallel multipliers is one clock cycle. Based on the clock cycles requirement of several multiplication approaches, as discussed in [25], the bit-serial multipliers are suitable for area-constrained applications. Similarly, the bit/digit parallel multipliers are useful for high-speed cryptographic applications. Finally, the digit-serial multiplication approaches are more convenient where the speed and hardware resources are simultaneously important. Based on the aforementioned discussion, we have implemented a bit-parallel Karatsuba multiplier over \(GF(2^{233})\). The mathematical structure (in the simplest way) to perform Karatsuba multiplication is explained in [22]. It uses the splitting of \(m\) bit input polynomials into two \(m/2\) bit polynomials. Each \(m/2\) bit polynomial is further divided into two smaller polynomials (\(m/4\) bit). This division is duplicated until the smaller polynomials for multiplication are acquired. After dividing polynomials, the resultant polynomial is generated by performing multiplication in chronological order. For further descriptions, we refer interested readers to [22]. In short, the Karatsuba multiplier in \(MULT\) unit takes two polynomials (\(MD_{1}\) and \(MD_{2}\)) as input and results in \(2\times m-1\) bit polynomial (\(M_{out}\)) as output. It is important to note that the size of the resultant polynomial generated after the \(MULT\) unit is \(2\times m-1\) bit (not shown in Figure 3). Therefore, in this work, the reduction from \(2\times m-1\) bit to \(m\) bit is performed using a NIST-recommended polynomial reduction algorithm (see Algorithm 2.41 of [14]). The \(PAdd\) and \(PDbl\) functions in Algorithm 1 requires some squaring instructions (e.g., \(Inst_{5}\) in \(PAdd\) while \(Inst_{1}\), \(Inst_{2}\), \(Inst_{4}\) and \(Inst_{6}\) in \(PDbl\)). In our work, these squaring instructions are computed by providing similar inputs to the Karatsuba multiplier as performed in [12]. Subsequently, this shows a decrease in hardware resources without affecting the clock cycles. As shown in Algorithm 1, the reconversion from projective to affine needs two polynomial inversion computations. There are several inversion methods in the literature to perform the multiplicative inverse of the polynomials. However, the Itoh-Tsujii inversion algorithm is more frequently utilized in state-of-the-art approaches as it requires only the multiplications and square operations for the computation [12; 18; 19]. Therefore, in our implementation, we have utilized the hardware resources of our _MULT_ unit to perform the polynomial inversion using the square Itoh-Tsujii algorithm. The Itoh-Tsujii inversion algorithm over \(GF(2^{233})\) requires ten polynomial multiplications followed by \(m-1\) squares [40]. Each multiplication over \(GF(2^{233})\) using the Karatsuba multiplier is accomplished in one clock cycle.