Curve25519 over Ed25519 for key exchange? Why?

Question

I've been reading up on the Signal Protocol (in this PDF) and it seems to be using Curve25519 for ECDH and EdDSA (with Ed25519) for signatures.

My question is why not use only Ed25519?

This implementation supports Ed25519 and key exchange so what is Curve25519 needed for?

Are there any security considerations where it beats Ed25519 key exchange?

This question from CryptoSE answered why to use Ed25519 over Curve25519 for signatures but why not to use Ed25519 for key exchange?

Answer 1

There's a few different related parts here, and the nomenclature of the library you've cited is a little confusing.

• Curve25519 is an elliptic curve over the finite field $\mathbb F_p$, where $p = 2^{255} - 19$, whence came the 25519 part of the name. Specifically, it is the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, but you don't need to know the details other than that it was designed to admit fast computation of $x([n]P)$ given $n$ and $x(P)$ which is useful for Diffie–Hellman key agreement.

  ^{(Side note: Sometimes the Montgomery form is written with the letters $u$ and $v$ as in $v^2 = u^3 + 486662 u^2 + u$, especially when drawing a contrast to another form like Weierstrass or Edwards.)}

• X25519 is a Diffie–Hellman function built out of Curve25519. An X25519 public key is the encoding of the $x$ coordinate of a point on Curve25519, hence the name X25519.

  ^{(Historical note: Originally, X25519 was called Curve25519, but now Curve25519 just means the elliptic curve and X25519 means the cryptosystem.)}

• Edwards25519 is an elliptic curve over the same field, with a different shape, the twisted Edwards shape $-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$, which admits fast computation of $P + Q$ given the $x$ and $y$ coordinates of $P$ and $Q$. It is related to Curve25519 by a birational map, so most points on Curve25519 can be mapped to edwards25519 and vice versa.

• Ed25519 is a public-key signature scheme built out of edwards25519, using the EdDSA construction. An Ed25519 public key is the encoding of the $x$ and $y$ coordinates of a point on edwards25519.

Curve25519 and X25519 were developed first; then Harold Edwards came along and blew the minds of Dan Bernstein and Tanja Lange by inventing Edwards curves which let you compute $P + Q$ in constant time faster than any other curve shapes and competitively with variable-time (i.e., leaky) formulas for other curve shapes. Fortuitously, it turned out that Curve25519 was birationally equivalent to a (twisted) Edwards curve, leading to Ed25519. Under the birational equivalence of Curve25519 and edwards25519, each X25519 public key corresponds to two possible Ed25519 public keys. As Ruggero explained, Curve25519 admits faster variable-base scalar multiplication, while edwards25519 admits faster fixed-base scalar multiplication and double-base scalar multiplication.

So what do you do if you want to use the same key material for key agreement and signature? There are a few options:

• The library you cited uses edwards25519 points as public keys, and converts them on the fly to Curve25519 $x$ coordinates for key agreement. This is simple and works if you have full control over the public key format and can choose to use edwards25519 points. It's confusing to call the function ed25519_key_exchange, but such is life.
• XEd25519 as used by Signal uses Curve25519 $x$ coordinates as public keys, and for signatures, always chooses the ‘positive’ point on edwards25519 as a corresponding Ed25519 public key. This is useful if you already have a lot of public keys deployed and you really don't want to redeploy them just to determine which ones are positive and which ones are negative.
• The signature scheme qDSA, following an idea used in Mike Hamburg's Strobe, uses Curve25519 $x$ coordinates as public keys, and uses a variant of the EdDSA signature equation to take advantage of the Montgomery ladder and avoid the Edwards shape and point addition altogether. This is useful if you want very small code like on a microcontroller, where there is a high cost to having several different scalar multiplication routines, e.g. for fixed-base vs. double-base.