# Large Field-Size Throughput/Area Accelerator for Elliptic-Curve Point Multiplication on FPGA
## 2 ECC Background over \(GF(2^{m})\)
\(for\)\((i\) from \(35\) down to \(18)\) do
``` Input: Polynomial, \(D(x)\) with \(2\times m-1\)-bit length Output: Polynomial, \(D(x)\) with \(m\)-bit length
1. \(for\)\((i\) from \(35\) down to \(18)\) do

```
Input: Polynomial, \(D(x)\) with \(2\times m-1\)-bit length Output: Polynomial, \(D(x)\) with \(m\)-bit length
1. \(for\)\((i\) from \(35\) down to \(18)\) do
``` Input: Polynomial, \(D(x)\) with \(2\times m-1\)-bit length Output: Polynomial, \(D(x)\) with \(m\)-bit length
1. \(for\)\((i\) from \(35\) down to \(18)\) do

```
Input: Polynomial, \(D(x)\) with \(2\times m-1\)-bit length Output: Polynomial, \(D(x)\) with \(m\)-bit length
1. \(for\)\((i\) from \(35\) down to \(18)\) do
``` Input: Polynomial, \(D(x)\) with \(2\times m-1\)-bit length Output: Polynomial, \(D(x)\) with \(m\)-bit length
1. \(for\)\((i\) from \(35\) down to \(18)\) do

\end{table}

Figure 2: Proposed Karatsuba modular multiplier. Modular inversionAs shown in Algorithm 1, the last two lines include a modular inversion computation. We have plenty of methods in the literature to perform the modular inversion. Not all inversion approaches are suitable to accelerate performances on hardware platforms due to the involvement of different mathematical structures [10]. Consequently, in our accelerator design, we have used a square version of an Itoh-Tsujii algorithm [22] which requires squares equivalent to the field length followed by 12 modular multiplications over \(GF(2^{571})\) field. The modular inversion unit is not highlighted in Figure 1 because the beauty of the Itoh-Tsujii inversion algorithm is the square and multiplication requirements. Hence, the modular inversion operation is performed using the existing resources of the square and multiplication circuits as employed in PM architectures of [12; 14; 17]. Thus, this approach reduces the hardware cost as well as the consumed power. As we described earlier in this work, the cost for one square and multiplier circuit is one clock cycle. Then, over \(GF(2^{571})\), the implementation of the Itoh-Tsujii algorithm for modular inversion requires 571 clock cycles for square computations and 12 clock cycles for modular multiplication computation. The total cycle counts for one modular inversion computation is 583. ### Control Unit and Clock Cycles Calculation

We employed an FSM-based dedicated controller to implement the Algorithm 1 for PM computation. For our implementations, we divide Algorithm 1 in four portions: (i) LSV, (ii) INT, (iii) PMC and (iv) GOP. The details are as follows. Moreover, FSM generates the corresponding control signals for the Curve Parameters unit, RegFile unit and the arithmetic unit. * _Loading secret vectors (LSV)_. A bit stream of a scalar multiplier \(k\) and coordinates of initial point \(P\) are required as input to Algorithm 1. Therefore, based on the related control signals, LSV determines the loading of ECC parameters and a scalar multiplier into the corresponding buffers (in the Curve Parameters unit). When a one-bit \(ld\) signal becomes 1, then it means that we have to load \(x\) and \(y\) coordinates of the initial point \(P\) and a curve constant \(b\) into the corresponding buffers of the Curve Parameters unit. The related control signals to our Curve Parameters unit are shown in Figure 1 and the related details are provided in Table 1. Similarly, when a one-bit \(lk\) signal becomes 1, it implies that we have to load a secret key (or a scalar multiplier \(k\)) into a KeyReg buffer, as shown in Figure 1. It is essential to provide that the interface of our processor architecture supports only 8-bit data loading using an 8-bit \(din\) pin. Therefore, the 571-bit ECC parameters (i.e., \(xp\), \(yp\) and \(b\)) and a secret key \(k\) needs to load in 8-bit form. For example, to load a 571-bit secret key in our KeyReg buffer, 72 clock cycles are required. Similarly, our design requires 3\(\times\)72 clock cycles to load \(xp\), \(yp\) and \(b\) in buffers of the Curve Parameters unit. * _Initialization (INT)_.