3
$\begingroup$

According to this page, Curve25519 and Ed25519 are not isomorphic, because the birational equivalence equation has singularities:

What does "birational equivalence" mean in a cryptographic context?

But... Curve25519 and Ed25519 are both cyclic groups, right? Both have order of $2^3 * (2^{252}+27742317777372353535851937790883648493)$. Doesn't that make them isomorphic?

$\endgroup$
4
  • 2
    $\begingroup$ Maybe someone writes it, Theorem 2.1 eprint.iacr.org/2007/286.pdf $\endgroup$
    – kelalaka
    Jun 7 at 20:20
  • 2
    $\begingroup$ And, $$a = P(-121665/121666)$$ $$print(kronecker(a,2^{255}-19)==1)$$ returns false from Sagemath. $\endgroup$
    – kelalaka
    Jun 7 at 20:38
  • $\begingroup$ @kelalaka Yeah, that link had what I needed; thanks! I worked out the same answer using the curve equations: the only singularities you run into with converting Edwards to Curve are $\mathcal{O}=(0, 1)$ and $(0, -1)$, the latter being the sole point of order $2$. Those two exceptions map to Curve points $\infty$ and $(0, 0)$ respectively, completing the isomorphism. $\endgroup$
    – Myria
    Jun 7 at 20:58
  • 1
    $\begingroup$ Write an answer, don't forget the choices due to the security issues... $\endgroup$
    – kelalaka
    Jun 7 at 21:01

2 Answers 2

3
$\begingroup$

The word "isomorphism" is always relative to a particular structure your mathematical objects carry. Sometimes this is obvious from context, but in many cases clarification is needed.

Here's an example to illustrate the core issue: $\mathbb Z$ is isomorphic to $\mathbb Q$ as a set (because there exists a bijection between them, in other words, an isomorphism of sets). But they clearly aren't isomorphic as rings: one is a field and the other isn't. In many cases, there are either special names for specific types of isomorphisms (bijection, homeomorphism, diffeomorphism, etc.), or it's clear from context which structure is meant.

Elliptic curves feature two major kinds of structure: They are algebraic curves with a group structure on them. One source of complication is that neither of these structures has a special word for its isomorphisms, so we have to distinguish by saying "isomorphism of algebraic curves" or "isomorphism of groups" or "isomorphism of abelian varieties" (which combines the two).

The Montgomery curve $M\colon\; y^2=x^3+486662x^2+x$ is not isomorphic to the Edwards curve $E\colon\; x^2 + y^2 = 1 + (121665/121666)x^2y^2$ as an algebraic curve. One simple reason is that $M$ is smooth whereas $E$ has a singular point at infinity — but smoothness is preserved under isomorphism of algebraic curves, so they cannot be isomorphic.

However, the groups of (regular) points on these curves are isomorphic: The isomorphism is given by the birational equivalence between $M$ and $E$. Note that this does not imply that the birational equivalence is an isomorphism of curves! Indeed, there exist plenty of other elliptic curves with a cyclic group of order $2^3\cdot (2^{252}+27742317777372353535851937790883648493)$ on them, and this group is certainly isomorphic to the group of the same order on $E$, but none of those other curves has a reason to be isomorphic as a curve to $E$.

$\endgroup$
1
  • $\begingroup$ I definitely meant that the groups are isomorphic, since this is ultimately related to particular cryptosystems (especially given the names with "25519" in them, referring to the particular field over which the curves are evaluated). $\endgroup$
    – Myria
    Jun 14 at 18:22
1
$\begingroup$

Looking at this problem in more detail, and looking at Bernstein and Lange's PDF kelalaka linked in a comment above, the answer is yes, Curve25519/X25519 and Ed25519 groups are isomorphic to each other.

This paragraph explains the isomorphism, with the proof of correctness in earlier sections of the paper:

The point at $\infty$ on Curve25519 corresponds to the point $(0,1)$ on the Edwards curve; the point $(0,0)$ on Curve25519 corresponds to $(0,-1)$; any other point $(u,v)$ on Curve25519 corresponds to $(\sqrt{486664}u/v,(u-1)(u+1))$; a sum of points on Curve25519 corresponds to a sum of points on the Edwards curve. One can therefore perform a sequence of group operations on points of the elliptic curve $v^2=u^3+486662u^2+u$ by performing the same sequence of group operations on the corresponding points of the Edwards curve.

So it is possible to convert between Curve25519 points and Ed25519 points. However, in X25519, the $y$ coordinate is ignored, so an X25519 point corresponds to two Ed25519 points, which could be a problem.

$\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.