# Elliptic-Curve Crypto Processor for RFID Applications
## 2 Preliminaries
### PM Computation over \(Gf(2^{M})\)
```
Input: Polynomial, \(W(x)\) with \(2\times m-1\)-bit length Output: Polynomial, \(X(x)\) with \(m\)-bit length \(Y=W[i]\oplus W[i+163]\oplus W[i+319]\) \(Z=W[i]\oplus W[i+157]\oplus W[i+160]\) \(1\)\(for(0\leq i\leq 1)\)\(X[i]=Y\oplus W[i+320]\oplus W[i+323]\) \(2\)\(for(i=2)\)\(X[i]=Y\oplus W[i+320]\) \(3\)\(for(3\leq i\leq 5)\)\(X[i]=Y\oplus W[i+160]\oplus W[i+316]\oplus W[i+317]\) \(4\)\(for(i=6)\)\(X[i]=Z\oplus W[i+163]\oplus W[i+313]\oplus W[i+314]\oplus W[i+316]\) \(5\)\(for(7\leq i\leq 10)\)\(X[i]=Z\oplus W[i+156]\oplus W[i+163]\oplus W[i+312]\oplus W[i+314]\) \(6\)\(for(11\leq i\leq 12)\)\(X[i]=Z\oplus W[i+156]\oplus W[i+163]\oplus W[i+312]\) \(7\)\(for(13\leq i\leq 161)\)\(X[i]=Z\oplus W[i+156]\oplus W[i+163]\) \(8\)\(for(i=162)\)\(X[i]=Z\oplus W[i+156]\)
```

**Algorithm 2**Reduction over \(GF(2^{163})\)[27]

### Dedicated Command Controller and Clock Cycles Calculation

We have described the FSM states involved in the command controller in Section 3.4.1. The clock cycles calculation is given in Section 3.4.2. #### 3.4.1 Number of States in the Command Controller

A dedicated command controller (i.e., FSM controller presented in Figure 3) generates control signals to execute, (i) affine-to-projective conversion, (ii) PM in projective coordinates and (iii) projective-to-affine conversions of Algorithm 1 and includes 60 states, as shown in Figure 3. The description of these states with respect to different parts of the Algorithm 1 follows:

**Affine-to-projective conversions:** State 0 is an idle state while state 1 to state 5 executes affine-to-projective conversions. * **PM in projective coordinates:** State 6 to State 20 generate control signals for the sequence of routines (from 1 to 15 in PM part), presented in Algorithm 1. State 21 is a conditional state and is responsible to check \(if(i=0\ and\ k_{i}=1)\) in Algorithm 1, where \(i\) counts the number of points on the ECC curve. Once the \(if\) statement becomes true, the next state is state 22, otherwise the next state is state 6. These states continue to repeat until the value of \(i\) becomes 0 (initially, the value of \(i\) is \(m-2\), see for statements in Algorithm 1). States 22 to 27 are for swapping purpose. Therefore, we have used 3 states (22 to 24) to execute the swap(\(X_{1}\), \(X_{2}\)) statement. The operations involved in these 3 states (22 to 24) are, (i) \(R_{1}=X_{1}\), (ii) \(X_{1}=X_{2}\), and (iii) \(X_{2}=R_{1}\). Similarly, in states 25 to 27, we have performed the swap(\(Z_{1}\), \(Z_{2}\)) statement. The operations involved in these 3 states (25 to 27) are (i) \(R_{1}=Z_{1}\), (ii) \(Z_{1}=Z_{2}\), and (iii) \(Z_{2}=R_{1}\). * **Projective-to-affine conversions:** As shown in Algorithm 1, the projective-to-affine conversions consist of 14 sequences of routines. Three are for inversion, 5 are for multiplications, 6 are for additions and there is only one instruction for squaring. To compute each inversion operation, states 28 to 47 are responsible to generate control signals. Finally, the states 48 to 59 are required to implement the remaining sequence of routines (multiplications, addition and squaring) in the projective-to-affine conversion part of Algorithm 1. #### 3.4.2 Clock Cycle Calculation

The affine-to-projective conversion is carried out by simply transferring (\(x_{p}\), 1) to (\(X_{1}\), \(Z_{1}\)) in two clock cycles. The \(X_{2}\) and \(Z_{2}\) contain \(x_{p}^{2}\) and \(x_{p}^{4}+b\), respectively. It is computed by using three clock cycles (see sequence of routines from 3 to 5 in the affine-to-projective conversion part of Algorithm 1). The point multiplication in projective coordinates contains 15 sequences of routines (see Algorithm 1). Out of these 15 routines, 6 are for multiplications, 6 are for squaring and the remaining 3 routines are for additions. Therefore, nine clock cycles are required for the computation of 9 squaring and addition routines. For multiplication, using a traditional schoolbook method, a total of \(6\times m\) clock cycles are needed.