16
$\begingroup$

So let's assume I want to perform Ed448 or Ed25519 digital signatures or want to perform a DH key-exchange. Assume further that those curves (Curve448 or Curve25519) are required.

But the problem is, that I have only a constrained device given, which only allows for Weierstrass-Computations. Alternatively I have a software library that can perform Weierstrass-Operations but not Montgomery / Edwards operations. "Operations" here denote point addition and scalar multiplication. Note further that both devices / libraries support arbitrary (Weierstrass) curves.

So this provokes the question:
Is it possible to perform Edwards / Montgomery operations using a Weierstrass engine and if so, how?

$\endgroup$
17
$\begingroup$

If I understand your question correctly, you are essentially asking if points in Edwards and Montgomery curves can be represented in Weierstrass coordinates. This is true; in fact, any elliptic curve over a field of characteristic $\neq2,3$ can be represented in Weierstrass form $\mathcal{E}_{w}^{a, b} : y^2 = x^3 + ax + b$, and by extension its points can too.

The question, then, becomes “how easy is the conversion”?

For Montgomery curves of the form $\mathcal{E}_m^{A, B}: By^2 = x^3 + Ax^2 + x$, it is surprisingly straightforward. You can map the point $(x, y) \in \mathcal{E}_m^A$ to the Weierstrass curve $\mathcal{E}_w^{1/B^2-A^2/3B^2,A(2A^2 - 9)/27B^3}$ via the map $((x + A/3)/B, y/B)$. The inverse map is obvious, $(Bx - A/3, By)$. If $B=1$, which is the case for every Montgomery curve used in practice, this simplifies substantially.

For twisted Edwards curves $\mathcal{E}_{e}^{a, d} : ax^2 + y^2 = 1 + dx^2y^2$ (where Edwards curves are the subset where $a = 1$) there also is a simple map to a Weierstrass curve, which consists of converting the curve to Montgomery format first. In particular, we can map $\mathcal{E}_e^{a, d}$ to $\mathcal{E}_m^{2(a + d)/(a - d), 4/(a - d)}$ via $(x, y) \mapsto \left(\frac{1 + y}{1 - y}, \frac{1 + y}{x - xy}\right)$, with inverse $(x, y) \mapsto \left(\frac{x}{y}, \frac{x-1}{x+1}\right)$. Composing theses maps with the above, we get maps to the appropriate Weierstrass curve $\mathcal{E}_w^{a, b}$. None of these conversions are terribly expensive compared to the cost of a scalar multiplication.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.