# Throughput/Area Optimized Architecture for Elliptic-Curve Diffie-Hellman Protocol
## 2 Related Mathematical Background  
Each associated layer in Figure 1a,b requires several algorithms or protocols for cryptographic computations. Layer 1 (ECDH protocol) is responsible for a shared key generation between two different parties. As given in Figure 2, each user, i.e., \(U_{A}\), and \(U_{B}\), uses common ECC parameters to initiate the setup for a shared key generation. Moreover, each user also generates his/her public key (i.e., \(Q_{A}\) and \(Q_{B}\)) by using a base-point \(P\) and his/her private key (i.e., \(d_{A}\) and \(d_{B}\)). The \(d_{A}\) and \(d_{B}\) are \(m\)-bit random numbers (also termed as scalar multipliers and secret keys in literature). After generating the public keys, both users exchange their public keys with each other. Thereafter, the \(U_{A}\) and \(U_{B}\) generate their shared key using \(d_{A}\times Q_{B}\) and \(d_{B}\times Q_{A}\), respectively. The \(A\) and \(B\) in the subscript of \(d\), \(Q\) and \(SK\) (shared key) determine the execution of a corresponding operation for the respective user A and B. In Figure 2, the \(d\times P\) and \(d\times Q\) determine the computation of ECPM operation for \(U_{A}\) and \(U_{B}\), respectively.  
The computation of ECPM operation, shown in Figure 1b, is the execution of \(d-1\) times the addition of an elliptic curve point (\(P\)) when generating the public key or (\(Q\)) when generating the shared key. To perform ECPM operations, there are several algorithms such as Double and Add, Montgomery, Lopez Dahab and many more. A comparative study over various ECPM algorithms is presented in [11]. Subsequently, the Montgomery (Algorithm 1) algorithm has been used in this work as (inherently) it provides resistance against simple power analysis (SPA) and timing attacks.  
```
Input:\(d=(d_{n-1},\ldots,d_{1},d_{0})\) with \(d_{n-1}=1\), \(P=(x_{p},y_{p})\in GF(2^{m})\) Output:\(Q=(x_{q},y_{q})=d\cdot P\) Affine to projective conversions:\(X_{1}=x_{p}\), \(Z_{1}=1\), \(Z_{2}=x_{p}^{2}\) and \(X_{2}=x_{p}^{4}+b\) PM in projective coordinates: for(i from m-2 down to 0)do if(\(d_{i}=1\))then \(PAdd(X_{1},Z_{1})=(X_{1},Z_{1},X_{2},Z_{2})\) and \(PDbl(X_{2},Z_{2})=(X_{2},Z_{2})\) else \(PAdd(X_{2},Z_{2})=(X_{2},Z_{2},X_{1},Z_{1})\) and \(PDbl(X_{1},Z_{1})=(X_{1},Z_{1})\) endif Reconversion from projective to affine:\(x_{q}=\frac{X_{1}}{Z_{1}}\) and \(y_{q}=x_{p}+(\frac{X_{1}}{Z_{1}})[(X_{1}+x_{p}\times Z_{1})(X_{2}+x_{p}\times Z _{2})+(x_{p}^{2}+y_{p})(Z_{1}\times Z_{2})](x_{p}\times Z_{1}\times Z_{2})^{-1 }+y_{p}\)
```  
**Algorithm 1**Montgomery ECPM Algorithm [12].  
Algorithm 1 contains an initial point \(P\) and a scalar multiplier \(d\) as an input. A sequence \(d_{n-1},\ldots,d_{1},d_{0}\) shows the bits (0 s and 1 s) of the scalar multiplier. The output of Algorithm 1 is the \(x\) and \(y\) coordinates of the generated public and shared keys. The \(PAdd()\) and \(PDbl()\) functions in Algorithm 1 show the instructions for point addition and double  
Figure 2: ECDH protocol for shared key generation or key agreement.  
computations respectively. For \(if\) and \(else\) statements of Algorithm 1, the corresponding sequence of instructions for \(\textit{PAdd}()\) and \(\textit{PDbl}()\) functions are given below.  
\[\textit{PAdd}(X_{1},Z_{1})=\left\{\begin{array}{l}\mathit{Inst}_{1}\longleftarrow Z _{1}=X_{2}\times Z_{1}\\ \mathit{Inst}_{2}\longleftarrow X_{1}=X_{1}\times Z_{2}\\ \mathit{Inst}_{3}\longleftarrow T_{1}=X_{1}+Z_{1}\\ \mathit{Inst}_{4}\longleftarrow X_{1}=X_{1}\times Z_{1}\\ \mathit{Inst}_{5}\longleftarrow Z_{1}=T_{2}^{2}\\ \mathit{Inst}_{6}\longleftarrow T_{1}=x_{p}\times Z_{1}\\ \mathit{Inst}_{7}\longleftarrow X_{1}=X_{1}+T_{1}\\ \mathit{Inst}_{1}\longleftarrow Z_{2}=Z_{2}^{2}\\ \mathit{Inst}_{2}\longleftarrow T_{1}=Z_{2}^{2}\\ \mathit{Inst}_{3}\longleftarrow T_{1}=b\times T_{1}\\ \mathit{Inst}_{4}\longleftarrow X_{2}=X_{2}^{2}\\ \mathit{Inst}_{5}\longleftarrow Z_{2}=X_{2}\times Z_{2}\\ \mathit{Inst}_{6}\longleftarrow X_{2}=X_{2}^{2}\\ \mathit{Inst}_{7}\longleftarrow X_{2}=X_{2}+T_{1}\\ \end{array}\right.\]