# An Optimized Flexible Accelerator for Elliptic Curve Point Multiplication over NIST Binary Fields
## 2 Lopez-Dahab Projective Form of ECC over \(GF(2^{m})\)
Similarly, for \(GF(2^{571})\), the memory size would be \(11\times 571\). Nevertheless, the total number of addresses remains the same across different values of \(m\). On the other hand, the total number of stored bits in each memory location varies according to the key length, represented by \(m\). Amongst 11 memory addresses, four addresses are dedicated to storing ECC curve parameters: \(x_{p}\) (the \(x\) component of the starting point \(P\)), \(y_{p}\) (the \(y\) component of the starting point \(P\)), \(b\) (the constant of the curve), and a secret key. These parameters are essential for performing computations and are inputs to Algorithm 1. The remaining seven addresses hold intermediate and end results. The internal structure of the data memory consists of two multiplexers with sizes of \(11\times 1\) and one demultiplexer of \(1\times 11\) size. They take inputs from the data memory. On the other hand, the demultiplexer allows one to write on a specific register using \(AU_{out}\) signal. The corresponding control signals related to read and write operations are marked with red dotted lines in Figure 1.

#### 3.2.2 Arithmetic Unit (AU)

The gray filled area in Figure 1 represents the AU, which consists of an adder, square block, multiplier, a reduction block, and two multiplexers (\(Mux-A\) and \(Mux-B\)). The description of these architectural components is as follows:

Adder, Square and Routing Multiplexers

Reduction

As depicted in Figure 2, the resultant polynomial after each square and multiplication has a \(2\times m-1\) bits length. To produce a polynomial of length \(m\)-bit, polynomial reduction is necessary. In this work, we have implemented NIST-recommended reduction algorithms for polynomial reduction after each square and multiplier unit, as described in [3]. Some existing accelerators, such as the one in [17], utilize separate reduction units after each square and multiplier block. However, we have employed only one reduction block to conserve hardware resources with an additional \(2\times 1\) multiplexer, as illustrated in Figure 2. This decision enables us to minimize hardware requirements while achieving the desired polynomial reduction in the same clock cycle. For complete details about the reduction algorithms specific to \(GF(2^{163})\) to \(GF(2^{571})\), we refer interested readers to algorithms 2.41 to 2.45 of [3]. The computational cost, including the square/multiplication and reduction, is one clock cycle, as we have used combinational logic for the design implementation. Inversion

Apart from polynomial addition, square, and multiplication, implementing Algorithm 1 for PM computation also requires polynomial inversion computations, as shown in the last two lines of Algorithm 1. Therefore, we have utilized a square version of the Itoh-Tsujii algorithm [26], which requires \(m-1\) times repeated squares followed by 9, 10, 10, 11, and 12 modular multiplications over \(GF(2^{163})\), \(GF(2^{233})\), \(GF(2^{283})\), \(GF(2^{409})\), and \(GF(2^{571})\) fields. The Itoh-Tsujii algorithm is used because it only needs square and multiplication computations for modular inversion. Therefore, it is better to utilize the hardware resources of the square and multiplier to compute the inversion, which benefits

Figure 2: Proposed digit-parallel polynomial multiplier architecture over \(GF(2^{m})\) with \(m=163,233,283,409\) and \(571\). minimizing the overall hardware resources. In our architecture, we have utilized the design components marked in orange in Figure 1 to implement the Itoh-Tsujii inversion algorithm. As described, the computational cost for one modular square and multiplier, including reduction, is one clock cycle. Thus, implementing the Itoh-Tsujii algorithm for modular inversion over \(GF(2^{163})\) requires 162 clock cycles for square computations and 9 clock cycles for modular multiplications. Hence, the total cycles required over \(GF(2^{163})\) field is 171 (162 for \(m-1\) square operations and nine for nine modular multiplications).