Score:4

Converting elliptic curve equations

kz flag

I'm implementing a digital signature algorithm for academic purposes using elliptic curves. I am familiar with equations of the form $$y^2 = x^3 + ax + b$$, but the paper I am reading for implementing point addition and doubling uses the equation $$Y^2Z = X^3 +aXZ^2 +bZ^3$$.

I guess the $Z$ comes from representing the points using projective coordinates, but I'm not sure.

I'm not sure if I understood correctly, but I think I can rewrite one equation as the other. Can someone explain the process of converting an equation of the form $y^2 = x^3 + ax + b$ to the equation $Y^2Z = X^3 +aXZ^2 +bZ^3$?

I appreciate any guidance on this matter. Thanks in advance!

swineone avatar
ru flag
[In Standard Projective Coordinates the triple (X, Y, Z) represents the affine point (X / Z, Y / Z)](https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Standard_Projective_Coordinates)
Gareth Ma avatar
ng flag
If you just want to understanding transforming the equation, then the process is just (1) look at the highest degree monomial that appears (in this case, $X^3$), and then *homogenise* the equation by multiplying each monomial $X^iY^j$ by an extra monomial $Z^k$ such that $i+j+k=3$ is the highest degree you found. So here $X \to XZ^2$, $Y^2\to Y^2Z$, etc. Then now every term is of degree 3: $Y^2Z, X^3,XZ^2,Z^3$. And moreover, as you noted, it's in projective coordinates now, meaning if you map $(X:Y:Z)\to(\alpha X:\alpha Y:\alpha Z)$, the equation still holds. This helps with $\infty=(0:1:0)$
Score:2
ng flag

Explain the process of converting an equation of the form $y^2=x^3+a\,x+b$ to the equation $Y^2\,Z=X^3+a\,X\,Z^2+b\,Z^3$

This is projective coordinates. The idea is to express $x$ and $y$ as ratios $\frac XZ$ and $\frac YZ$ (with $x$, $y$, $X$, $Y$, $Z$ all in the base field). This has the beneficial effect that during point multiplication, we can defer to the end the expensive step of modular inversion that occurs for each point addition and doubling when we use Cartesian coordinates $(x,y)$.

Starting from from $y^2=x^3+a\,x+b$, changing $x$ to $\frac XZ$ and $y$ to $\frac YZ$ yields $\frac{Y^2}{Z^2}=\frac{X^3}{Z^3}+a\frac XZ+b$. And then multiplying by $Z^3$ yields $Y^2\,Z=X^3+a\,X\,Z^2+b\,Z^3$.

To obtain explicit point addition and doubling formulas, we can transform the standard formulas by making the same change of variable. There are many ways to arrange the computations, see the Explicit-Formulas Database.

To convert from $(x,y)$ to $(X,Y,Z)$, set $X=x$, $Y=y$, and $Z=1$.

To convert from $(X,Y,Z)$ to $(x,y)$ when $Z\ne0$, compute the inverse $Z^{-1}$ of $Z$, then set $x={Z^{-1}}X$ and $y={Z^{-1}}y$.

Note: We can initially represent the neutral/point at infinity $\mathcal O$ as $(X,Y,Z)=(0,1,0)$, and these formulas yield correct results, including when $\mathcal O$ is obtained as an intermediary value. At the end of a sequence of operations, we can convert back $(X,Y,Z)$ to $\mathcal O$ when $Z=0$.

fgrieu avatar
ng flag
Another popular option for fast point multiplication with deferred modular inversion is [Jacobian coordinates](https://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html), which express $x$ and $y$ as ratios $\frac X{Z^2}$ and $\frac Y{Z^3}$.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.