# Large Field-Size Elliptic Curve Processor for Area-Constrained Applications
## 2 ECC Background  
In the case of \(GF(2^{m})\) field, an affine form of ECC can be represented as a set of points, i.e., \(x\), and \(y\), which obeys the Equation (1) as follows:  
\[E:y^{2}+xy=x^{3}+ax^{2}+b \tag{1}\]  
In Equation (1), \(x\) and \(y\) are the base elements of the \(GF(2^{m})\) field. Points \(a\) and \(b\) represent curve parameters with \(b\
eq 0\). The representation of \(x\) and \(y\) elements of the \(GF(2^{m})\) field in a triplet, i.e., \(X\), \(Y\), and \(Z\), is projective coordinates. Thus, for \(GF(2^{m})\) field, a Lopez Dahab projective form of Equation (1) is represented in Equation (2). It can be seen in Equation (2) that there are three variables (\(X\), \(Y\) and \(Z\)). These variables are the projective elements of point \(P(X:Y:Z)\), such that \(Z\
eq 0\), \(a\) and \(b\) are the curve constants with \(b\
eq 0\).  
\[E:Y^{2}+XYZ=X^{3}Z+aX^{2}Z^{2}+bZ^{4} \tag{2}\]  
The points on the elliptic curve form an additive group. According to the additive group definition, the addition of two elements in a group defines another element in the group. For instance, we have two points, i.e., \(P\) and \(Q\), on an elliptic curve. Then a point addition will be \(R=P+Q\), where \(R\) will be the resultant point on the curve. Similarly, when both the points on the curve are the same (\(P+P=2P\)) then this is called a point double. These point addition and double operations are needed to compute a point multiplication operation in ECC. Consequently, the addition of \(k\) copies of point addition and double determines the ECPM and can be calculated using Equation (3).  
\[Q=RP \tag{3}\]  
The initial point (in Equation (3)) on the curve is \(P\). The resultant point on the curve is \(Q\). Similarly, \(k\) is the scalar multiplier. To implement Equation (3), we have several algorithms in the literature such as Double and Add, Lopez Dahab, Montgomery, etc. Comparatively, the Double and Add algorithm is more suitable for the unified models of ECC, such as Edwards, Huff, Twisted Edwards, etc. Similarly, the Lopez Dahab algorithm is a better choice for achieving instruction-level parallelism (i.e., for performance improvements). However, similar instructions for the computation of point addition and double make the Montgomery point multiplication algorithm suitable for the side-channel resistant implementation of ECC. A detailed comparison of various ECPM algorithms is presented in [28]. To summarize, we have used the Montgomery point multiplication algorithm (given in Algorithm 1) in our implementation. It is important to mention that we are not considering the side channel attacks at the design level. In other words, we have implemented only the side channel attack-protected point multiplication algorithm on FPGA and ASIC platforms.  
The inputs to Algorithm 1 are an initial point \(P\) with \(x\) and \(y\) coordinates (i.e., \(x_{p}\), and \(y_{p}\)), and a scalar multiplier \(k\). The bit stream \(k_{n-1},\ldots,k_{1},k_{0}\) presents the scalar multiplier. The outputs of the Algorithm 1 are the \(x\) and \(y\) coordinates of the final point on the ECC curve. For \(if\) and \(else\) statements, the corresponding sequence of instructions for point addition and double operations are given in Table 1. Columns one and column two show the point addition information in terms of the sequence of instructions (i.e., \(Inst_{i}\)) as well as the corresponding operations. Similarly, columns three and column four show the number of instructions (i.e., \(Inst_{i}\)) as well as the respective finite field operations for point double computations. It can be observed from Table 1 that there are 14 instructions (in total) for point addition and double computations. 6 of these 14 instructions perform finite field multiplications. Similarly, 3 of these 14 instructions perform finite field additions. Finally, the remaining 5 instructions perform finite field squaring.