# Secure ECDSA SRAM-PUF Based on Universal Single/Double Scalar Multiplication Architecture
## 3 The Proposed Secure SRAM-PUF Scheme Based on Custom ECDSA
### The Proposed Universal Algorithm for ECSM and ECDSM  
For the construction of a two-dimensional DAC, we consider two scalars in ECDSM as an input vector \((k,l)\). The two-dimensional DAC is illustrated in Appendix C. The initial values of a two-dimensional DAC are zero \((0,0)\), the point \(P(1,0)\), and the point \(Q(0,1)\). Then, we precompute the PA results of \(P+Q\) and \(P-Q\). Note that point subtraction is as efficient as PA since, given \(Q(x_{Q},y_{Q})\), the coordinate of \(-Q\) is \(x_{Q},x_{Q}+y_{Q}\). The algorithm of single PA in LD coordinates is shown in Appendix B. For each loop in a two-dimensional DAC, the existence of the current vector \((k_{i},l_{i})\) allows the calculation of four intermediate values \((k_{i},l_{i})\), \((k_{i},l_{i}+1)\), \((k_{i}+1,l_{i})\), and \((k_{i}+1,l_{i}+1)\). We only preserve three values out of four to reduce the computation burden. The parities of these intermediate values are \((odd,odd)\), \((even,even)\), \((odd,even)\), and \((even,odd)\). As illustrated in Figure 11, values in \(C^{(1)}\) and \(C^{(2)}\) are always \((odd,odd)\) and \((even,even)\), respectively. The missing values can be \((odd,even)\) or \((even,odd)\). Only one of them is preserved in \(C^{(3)}\). The omitted value is determined by \((k_{i},l_{i})\) and \((k_{i-1},l_{i-1})\), where \((k_{i-1},l_{i-1})=([k_{i}/2],[l_{i}/2])\):  
1. When \((k_{i-1}+k_{i},l_{i-1}+l_{i})=(odd,odd)\), the choice is the same as the previous iteration;
2. When \((k_{i-1}+k_{i},l_{i-1}+l_{i})=(even,even)\), the choice is the opposite of the previous iteration;
3. When \((k_{i-1}+k_{i},l_{i-1}+l_{i})=(odd,even)\), the choice is \((even,odd)\);
4. When \((k_{i-1}+k_{i},l_{i-1}+l_{i})=(even,odd)\), the choice is \((odd,even)\). Hence, we can generate all elements in the proposed two-dimensional DAC, as shown in Algorithm 3. Furthermore, we also need to determine the flag signals to control the accumulation for the final ECDSM results. It is obvious that \(C_{i}^{(1)}\) is always calculated through the PA of \(C_{i-1}^{(1)}\) and \(C_{i-1}^{(2)}\). Further, \(C_{i}^{(2)}\) is always calculated through the PD with one of \(C_{i-1}^{(1)}\), \(C_{i-1}^{(2)}\), or \(C_{i-1}^{(3)}\). Finally, \(C_{i}^{(3)}\) is calculated through the PA of \(C_{i-1}^{(3)}\) and either \(C_{i-1}^{(1)}\) or \(C_{i-1}^{(2)}\). The relations in the proposed two-dimensional DAC are given as:  
\[ \begin{cases}C_{i}^{(1)}=C_{i-1}^{(1)}+C_{i-1}^{(2)}\\ C_{i}^{(2)}=2C_{i-1}^{(n)}\\ C_{i}^{(3)}=C_{i-1}^{(3)}+C_{i-1}^{(m)}\end{cases} , \tag{2}\]  
where \(n=1,2,3\) and \(m=1,2\). To establish the two-dimensional DAC, we need to determine the data strobing for each loop. \(C_{i}^{(1)}\) is always obtained through \(C_{i-1}^{(1)}\) and \(C_{i-1}^{(2)}\). For \(C_{i}^{(3)}\), one of the adders is fixed as \(C_{i-1}^{(3)}\), and the other adder can be \(C_{i-1}^{(1)}\) or \(C_{i-1}^{(2)}\). For \(C_{i}^{(2)}\), the input of the PD can be \(C_{i-1}^{(1)}\), \(C_{i-1}^{(2)}\), or \(C_{i-1}^{(3)}\). Meanwhile, we also need to determine the differences \(x_{diff}\) between two adders within two PAs for each loop. The possible values for \(x_{diff}\) can be \((1,1)\), \((0,1)\), \((1,0)\), \((1,0)\), or \((1,-1)\), which stand for \(P+Q\), \(Q\), \(P\), and \(P-Q\), respectively. The proposed flag signal generation algorithm is shown in Algorithm 4. In this algorithm, \(A_{i}\) and \(B_{i}\) denote the values of \(m\) and \(n\), respectively, in Equation (2). The difference between \(C_{i-1}^{(1)}\) and \(C_{i-1}^{(2)}\) can be \(P+Q\) or \(P-Q\). When the \(Y\)-coordinates are omitted, the \(X\)-coordinates and \(Z\)-coordinates of \(P+Q\) and \(P-Q\) are the same. Therefore, we only determine \(D_{i}\) to denote the difference between \(C_{i-1}^{(3)}\) and \(C_{i-1}^{(m)}\) in Equation (2).