Article 6YYG3 Equivalence between commonly used elliptic curves

Equivalence between commonly used elliptic curves

by
John
from John D. Cook on (#6YYG3)

The elliptic curves Curve25519 and Ed25519 are both commonly used in applications. For example, Curve25519 is used in Proton Mail and Ed25519 is used in SSH.

The two curves are related, as the numerical parts in their names suggest. The two curves are equivalent in some sense that we will describe below.

An algebraic geometer would say that Curve25519 and Ed25519 arenot isomorphic, but a cryptographer would say that they are isomorphic. That's because the algebraic geometer cares about more structure than the cryptographer does.

Curve25519 is given by

M: v^2 =u^3 + 486662u^2 +u

over the field Fq where q = 2255 - 19.

Ed25519 is given by

E: y^2 - x^2 = 1 - (121665/121666) x^2 y^2

over the same field. The 25519" part of both names comes from q.

We use M for Curve25519 because it is a Montgomery curve, named after Peter Montgomery. We use E for Ed25519 because it is a twisted Edwards curve, named after Harold Edwards.

The algebraic geometer would say M and E are not isomorphic as algebraic curves [1] because the curves are not the same in all their structure. However, the cryptographer isn't interested in elliptic curvesper se, only the additive group that is defined on elliptic curves, and these groupsare isomorphic. The isomorphism can be given by

x = 486664u/v

y = (u - 1)/(u + 1)

Here 486664 is a square root mod q and division means multiplication by the multiplicative inverse mod q.

Even though the group isomorphism is simple and explicit, it's not simple to prove that it is a group isomorphism. For a proof, see [2].

So if the additive groups of the two curves are isomorphic, why use one in some applications rather than the other? Each is used where its implementation is more efficient. Ed25519 is typically used in digital signatures (for example, in Monero) and Curve25519 is typically used in key exchange (for example, in secure web pages).

Related posts

[1] The map between (u,v) and (x,y) does serve as an isomorphism between the group structures. But it is a birational equivalence" rather than an isomorphism because it has singularities at (-1, 0) and (0, 0).

[2] Daniel J. Bernstein, Tanja Lange, Faster addition and doubling on elliptic curves, in Asiacrypt 2007 [49] (2007), 29-50. URL: http://eprint.iacr.org/2007/286.

The post Equivalence between commonly used elliptic curves first appeared on John D. Cook.
External Content
Source RSS or Atom Feed
Feed Location http://feeds.feedburner.com/TheEndeavour?format=xml
Feed Title John D. Cook
Feed Link https://www.johndcook.com/blog
Reply 0 comments