# On the Performance Analysis for CSIDH-Based Cryptosystems
## 2 Montgomery Curve and Tweaked Montgomery Curve
### Elliptic Curve Arithmetic on \(M_{a}\) and \(M_{a}^{t}\)  
Let \(P=(x_{P},y_{P})\) and \(Q=(x_{Q},y_{Q})\) be a point on a Montgomery curve \(M_{a}\) such that \(x_{P}\
eq x_{Q}\). Let \(P-Q=(x_{P-Q},y_{P-Q})\) be given. Then the \(x\) coordinates of their sum \(P+Q\) and the doubling of \(P\), \(x_{[2]P}\) can be computed as follows:  
\[x_{P+Q} =(x_{P}x_{Q}-1)^{2}/(x_{P-Q}(x_{P}-x_{Q})^{2})\] \[x_{[2]P} =(x_{P}^{2}-1)^{2}/(4x_{P}(x_{P}^{2}+ax_{P}+1))\]  
For a tweaked Montgomery curve \(M_{a}^{t}\), let \(P=(x_{P},y_{P})\) and \(Q=(x_{Q},y_{Q})\) be a point on \(M_{a}^{t}\) such that \(x_{P}\
eq x_{Q}\). Let \(P-Q=(x_{P-Q},y_{P-Q})\) be given. Then the \(x\) coordinates of their sum \(P+Q\) and the doubling of \(P\), \(x_{[2]P}\) can be computed as follows [14]:  
\[x_{P+Q} =(x_{P}x_{Q}+1)^{2}/(x_{P-Q}(x_{P}-x_{Q})^{2})\] \[x_{[2]P} =(x_{P}^{2}+1)^{2}/(4x_{P}(x_{P}^{2}+ax_{P}-1))\]  
At a glance, the computational costs of the differential addition and doubling on both curves are the same. However, when projective \(x\)-coordinate (\(XZ\)-coordinate) and projective curve coefficients are used, the computational costs are slightly different for both curves.  
Now let \(P=(X_{P}:Z_{P})\) and \(Q=(X_{Q},Z_{Q})\) be a point on a Montgomery curve \(M_{a}\) such that \(x_{P}=X_{P}/Z_{P}\) and \(x_{Q}=X_{Q}/Z_{Q}\) for \(x_{P}\
eq x_{Q}\). Let \(P-Q=(X_{P-Q}:Z_{P-Q})\) be the given difference of \(P\) and \(Q\) in projective coordinates such that \(x_{P-Q}=X_{P-Q}/Z_{P-Q}\). Then the addition formula in projective coordinates can be decomposed as follows [16]:  
\[X_{P+Q} =Z_{P-Q}(X_{P}X_{Q}-Z_{P}Z_{Q})^{2}=Z_{P-Q}((X_{P}-Z_{P})(X_{Q}+Z _{Q})+(X_{P}+Z_{P})(X_{Q}-Z_{Q}))^{2},\] \[Z_{P+Q} =X_{P-Q}(X_{P}Z_{Q}-Z_{P}X_{Q})^{2}=X_{P-Q}((X_{P}-Z_{P})(X_{Q}+Z _{Q})-(X_{P}+Z_{P})(X_{Q}-Z_{Q}))^{2}.\]  
The computational cost is \(4\mathbf{M}+2\mathbf{S}\), where the \(\mathbf{M}\) and \(\mathbf{S}\) refers to a field multiplication and squaring, respectively. The doubling of \(P\) gives \([2]P=(X_{[2]P}:Z_{[2]P})\), where \(X_{[2]P}\) and \(Z_{[2]P}\) are defined as:  
\[X_{[2]P} =C(X_{P}^{2}-Z_{P}^{2})^{2},\] \[Z_{[2]P} =4X_{P}Z_{P}(CX_{P}^{2}+CZ_{P}^{2}+AX_{P}Z_{P}),\]  
where \(a=A/C\). The computational cost is \(4\mathbf{M}+2\mathbf{S}\).  
On the other hand, for a tweaked Montgomery curve, let \(P=(X_{P}:Z_{P})\) and \(Q=(X_{Q},Z_{Q})\) be a point on \(M_{a}^{t}\) such that \(x_{P}=X_{P}/Z_{P}\) and \(x_{Q}=X_{Q}/Z_{Q}\) for \(x_{P}\
eq x_{Q}\). Let \(P-Q=(X_{P-Q}:Z_{P-Q})\) be the given difference of \(P\) and \(Q\) in projective coordinates such that \(x_{P-Q}=X_{P-Q}/Z_{P-Q}\). Then the sum \(P+\[X_{[2]P} =C(X_{P}^{2}+Z_{P}^{2})^{2},\] \[Z_{[2]P} =4X_{P}Z_{P}(CX_{P}^{2}-CZ_{P}^{2}+AX_{P}Z_{P}),\]  
where \(a=A/C\). Moreover, the concrete computation process is presented as below:  
\[t_{0}=X_{P}^{2},\quad t_{1}=Z_{P}^{2},\quad t_{2}=t_{0}+t_{1}, \quad t_{3}=t_{2}^{2},\quad X_{[2]P}=C\cdot t_{3},\quad t_{2}=t_{0}-t_{1},\quad t _{3}=X_{P}\cdot Z_{P},\] \[t_{0}=C\cdot t_{2},\quad t_{1}=A\cdot t_{3},\quad t_{2}=t_{0}+t_ {1},\quad t_{0}=t_{2}\cdot t_{3},\quad t_{1}=t_{0}+t_{0},\quad Z_{[2]P}=t_{1}+t _{1}.\]  
The computational cost of the doubling formula in the tweaked Montgomery curves is \(5\mathbf{M}+3\mathbf{S}\).