# 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
```
0:\((k,l)\)
0:\(C_{i}^{(1)},C_{i}^{(2)},C_{i}^{(3)}\)
1:\(n=max(\lceil log_{2}k\rceil,\lceil log_{2}l\rceil)\)
2:\(D=k\ mod\ 2\)
3:\(C_{i}^{(1)}=(k+(k+1)\ mod\ 2,l+(l+1)\ mod\ 2)\)
4:\(C_{n}^{(2)}=(k+k\ mod\ 2,l+l\ mod\ 2)\)
5:\(C_{n}^{(3)}=(k+(k+D)\ mod\ 2,l+(l+D+1)\ mod\ 2)\)
6:for\(i=n-1\) to \(0\)do
7: Set \((k^{\prime},l^{\prime})=(\lfloor k/2\rfloor,\lfloor l/2\rfloor)\)
8:if\((k+k^{\prime},l+l^{\prime})\ mod\ 2=(0,0)\)then
9:\(D=d\)
10:endif
11:if\((k+k^{\prime},l+l^{\prime})\ mod\ 2=(0,1)\)then
12:\(D=0\),
13:endif
14:if\((k+k^{\prime},l+l^{\prime})\ mod\ 2=(1,0)\)then
15:\(D=1\),
16:endif
17:if\((k+k^{\prime},l+l^{\prime})\ mod\ 2=(1,1)\)then
18:\(D=\bar{d}\),
19:endif
20: Set \(C_{i}^{(1)}=(k^{\prime}+(k^{\prime}+1)\ mod\ 2,l^{\prime}+(l^{\prime}+1)\ mod\ 2)\),
21: Set \(C_{i}^{(2)}=(k^{\prime}+k^{\prime}\ mod\ 2,l^{\prime}+l\ mod\ 2)\),
22: Set \(C_{i}^{(3)}=(k^{\prime}+(k^{\prime}+D)\ mod\ 2,l^{\prime}+(l^{\prime}+D+1)\ mod\ 2)\),
23:endfor Return:\(C_{i}^{(1)},C_{i}^{(2)},C_{i}^{(3)}\). ```  
**Algorithm 3** The Proposed Two-Dimensional DAC Generation Algorithm  
With flag signals precomputed, the proposed ECDSM algorithm is shown in Algorithm 5. \(C_{0}^{(3)}\) also needs to be precomputed to determine the data strobing for the initialization of the two-dimensional DAC. For ECSM, we employed the Montgomery ladder, as shown in Appendix B. Indeed, the Montgomery ladder also involves computation through constructing a DAC, but the DAC built in the Montgomery ladder is one-dimensional. Therefore, this method does not require precomputing the parameters of the DAC. Instead, it iteratively calculates and scans each bit of \(k\) during the process. Moreover, whether it is the proposed two-dimensional DAC computation method or the traditional one-dimensional DAC computation method (the Montgomery ladder), the operational steps in each round of iteration are uniform (PA-PD for the Montgomery ladder and PA-PA-PD for the proposed method). Consequently, both of these computation methods can enhance the resistance against some power and timing analysis attacks. For the Montgomery ladder, each loop contains 6 multiplication operations, while our proposed ECDSM method consumes 10 multiplication operations in each loop. Hence, when executing ECDSM, our proposed method reduces the computational burden by \(\frac{12-10}{12}=16.7\%\) compared to executing the Montgomery ladder twice. ```
0:\(C_{i}^{(1)},C_{i}^{(2)},C_{i}^{(3)},(k,l)\)
0:\(A_{i},B_{i},D_{i}\). 1:\(n=max(\lceil log_{2}k\rceil,\lceil log_{2}l\rceil)\)
2:for\(i=n\) to \(0\)do
3:if\((C_{i+1}^{(2)}/2)\ mod\ 2=(1,1)\)then
4: Set \(B_{i}=0\)
5:elseif\((C_{i+1}^{(2)}/2)\ mod\ 2=(0,0)\)then
6: Set \(B_{i}=1\)
7:else
8: Set \(B_{i}=2\)
9:endif
10:if\((C_{i+1}^{(3)}\ mod\ 2\ \oplus\ C_{i}^{(3)}\ mod\ 2)=(1,1)\)then
11:\(A_{i}=0\)
12:if\(C_{i}^{(3)}-C_{i}^{(1)}=(0,1)\)then
13:\(D_{i}=0\)
14:elseif\(C_{i}^{(3)}-C_{i}^{(1)}=(1,0)\)then
15:\(D_{i}=1\)
16:endif
17:elseif\((C_{i+1}^{(3)}\ mod\ 2\ \oplus\ C_{i}^{(3)}\ mod\ 2)=(0,0)\)then
18:\(A_{i}=1\)
19:if\(C_{i}^{(3)}-C_{i}^{(2)}=(0,1)\)then
20:\(D_{i}=0\)
21:elseif\(C_{i}^{(3)}-C_{i}^{(2)}=(1,0)\)then
22:\(D_{i}=1\)
23:endif
24:endif
25: Set \(k=k^{\prime},l=l^{\prime},d=D\)
26:endfor Return:\(A_{i},B_{i},D_{i}\). ```  
**Algorithm 4** The Proposed Flag Signal Generation Algorithm  
```
0:\(A,B,C_{0}^{(3)},P,Q\). 0:\(kP+lQ\). 1:Set \(n=max(\lceil log_{2}k\rceil,\lceil log_{2}l\rceil)\),
2:Set \(C_{1}=P+Q,C_{2}=0\),
3:if\(C_{0}^{(3)}=(0,1)\)then
4: Set \(\subseteq\)\(Q\)
5:elseif\(C_{0}^{(3)}=(1,0)\)then
6: Set \(C_{3}=P\)
7:endif
8:for\(i=1\) to \(n\)do
9:\(C_{1}\gets PA(C_{1},C_{2})\)
10:if\(A_{i}=0\)then
11:\(C_{3}\gets PA(C_{1},C_{3})\)
12:elseif\(A_{i}=1\)then
13:\(C_{3}\gets PA(C_{2},C_{3})\)
14:endif
15:if\(B_{i}=0\)then
16:\(C_{2}\gets PD(C_{1})\)
17:elseif\(B_{i}=1\)then
18:\(C_{2}\gets PD(C_{2})\)
19:elseif\(B_{i}=2\)then
20:\(C_{2}\gets PD(C_{3})\)
21:endif
22:endfor Return:\(kP+lQ\). ```  
**Algorithm 5** The Proposed ECDSM Algorithm