# Elliptic Curve in the Homogeneous Coordinate ## Metadata **Status**:: #x **Zettel**:: #zettel/literature **Created**:: [[2024-03-29]] **Topic**:: [[♯ Cryptography]] **Parent**:: [[Elliptic Curve]], [[Homogeneous Coordinate]] ## Synopsis [[Homogeneous Coordinate]] simplifies [[Elliptic Curve Addition]] by eliminating expensive divisions. There's a similar coordinate system [[Jacobian Coordinate]] that also can be used in Elliptic Curve Addition. ## Adding Distinct Points For two distinct points $P_1 = (x_1, y_1, z_1)$ and $P_2 = (x_2, y_2, z_2)$ where $z_1, z_2 \neq 0$, the result of $P_1 + P_2$ is 0 if $x_1/z_1 = x_2/z_2$. Otherwise the result is $P_3 = (x_3, y_3, z_3)$. These points present $(\frac{x_1}{z_1}, \frac{y_1}{z_1}),(\frac{x_2}{z_2}, \frac{y_2}{z_2}),(\frac{x_3}{z_3}, \frac{y_3}{z_3})$ in the Cartesian coordinates. Substitute them into the following formulas for adding distinct points in the Cartesian coordinates. ![[Elliptic Curve Addition#^n4mj9n]] The substitution yields: $ \begin{align} \lambda &= \frac{\displaystyle\frac{y_2}{z_2} - \frac{y_1}{z_1}}{\displaystyle\frac{x_2}{z_2} - \frac{x_1}{z_1}} \\ \frac{x_3}{z_3} &= \lambda^2-\frac{x_1}{z_1}-\frac{x_2}{z_2} \\ \frac{y_3}{z_3} &= \lambda(\frac{x_1}{z_1}-\frac{x_3}{z_3}) - \frac{y_1}{z_1} \\ \end{align} $ Solve $x_3$ and $y_3$ using [[♯ Sympy|Sympy]] ([example code](https://github.com/doitian/sympy-playground/blob/main/recipes/elliptic-curve-addition/homogeneous-coordinate-adding-distinct-points.py)). The expressions are simplified by substituting $y_2 z_1 - y_1 z_2$ with $u$ and $x_2 z_1 - x_1 z_2$ with $v$. $ \begin{align} u &= - y_{1} z_{2} + y_{2} z_{1} \\ v &= - x_{1} z_{2} + x_{2} z_{1} \\ x_3 &= \frac{u^{2} z_{1} z_{2} z_{3} - v^{2} x_{1} z_{2} z_{3} - v^{2} x_{2} z_{1} z_{3}}{v^{2} z_{1} z_{2}} \\ y_3 &= - \frac{z_{3} \left(- u \left(- u^{2} z_{1} z_{2} + 2 v^{2} x_{1} z_{2} + v^{2} x_{2} z_{1}\right) + v^{3} y_{1} z_{2}\right)}{v^{3} z_{1} z_{2}} \\ \end{align} $ Let $z_3$ be the LCM (Least Common Multiple) of $x_3$ and $y_3$ to eliminate all divisions, which gives the final equations: $ \begin{align} u &= - y_{1} z_{2} + y_{2} z_{1} \\ v &= - x_{1} z_{2} + x_{2} z_{1} \\ x_3 &= u^{2} v z_{1} z_{2} - v^{3} x_{1} z_{2} - v^{3} x_{2} z_{1} \\ y_3 &= u \left(- u^{2} z_{1} z_{2} + 2 v^{2} x_{1} z_{2} + v^{2} x_{2} z_{1}\right) - v^{3} y_{1} z_{2} \\ z_3 &= v^{3} z_{1} z_{2} \\ \end{align} $ ## Doubling For a point $P_1 = (x_1, y_1, z_1)$, the result of $P_1 + P_1$ is 0 if $y_1 = 0$. Otherwise the result is $P_3 = (x_3, y_3, z_3)$. Recall the formulas in Cartesian coordinates. ![[Elliptic Curve Addition#^52zrdy]] Use the same method as adding distinct points to derive the equations ([example code](https://github.com/doitian/sympy-playground/blob/main/recipes/elliptic-curve-addition/homogeneous-coordinate-doubling.py)): $ \begin{align} w &= a z_{1}^{2} + 3 x_{1}^{2} \\ x_3 &= 2 w^{2} y_{1} z_{1} - 16 x_{1} y_{1}^{3} z_{1}^{2} \\ y_3 &= w \left(- w^{2} + 12 x_{1} y_{1}^{2} z_{1}\right) - 8 y_{1}^{4} z_{1}^{2} \\ z_3 &= 8 y_{1}^{3} z_{1}^{3} \\ \end{align} $ ## Implementations - [py_ecc/optimized_bn128/optimized_curve.py](https://github.com/ethereum/py_ecc/blob/main/py_ecc/optimized_bn128/optimized_curve.py) ## Known Issues - Using different equations to compute $\lambda$ is [[Mike Rosing - Defense Against Power Analysis Attacks Avoiding Elliptic Curve Side Channel Attacks (Highlights)|vulnerable to the side channel attacks]].