13
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ I would argue that my answer you cited says that curve25519 allows for a faster variable base scalar multiplication than ed25519. And key exchange requires a variable base scalar multiplication. Even the library you cited, internally, performs the key exchange on curve25519. $\endgroup$
    – Ruggero
    Mar 19, 2019 at 11:25
  • $\begingroup$ Hey Ruggero, thanks for your answer. You said in your answer "the fixed-base algorithm of Ed25519 is, on most platform, faster than the variable-base of X25519." (line 24 of your answer), also how do you know the library internally performs the key exchange on Curve25519? (as far as I know Curve25519 uses 32 bytes private keys and the library uses 64 bytes private keys) $\endgroup$ Mar 19, 2019 at 11:44
  • $\begingroup$ @OughToPrevail there is a relationship between the curves and if you look at the source you may see the conversion from edwards to montgomery. $\endgroup$
    – Ruggero
    Mar 19, 2019 at 11:48
  • $\begingroup$ Oh, so as long as I stick to the library I will be using Curve25519 with Ed25519? $\endgroup$ Mar 19, 2019 at 11:51
  • $\begingroup$ btw @Ruggero I am not so good in math so I don't really understand crypto.stackexchange.com/questions/26966/… but thank you $\endgroup$ Mar 19, 2019 at 13:12

1 Answer 1

34
$\begingroup$

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.
$\endgroup$
11
  • $\begingroup$ Hello, I came back here to try to understand this again but I do have a few questions relating to this answer: What do you mean by always choosing a positive point, and also what do you mean redeploy them? $\endgroup$ Apr 23, 2019 at 20:00
  • 1
    $\begingroup$ @OughtToPrevail Positive point: It is an arbitrary choice which subset of points you label positive and which subset of points you label negative, as long as $-x$ is negative whenever $x$ is positive (and nonzero). $\endgroup$ Apr 23, 2019 at 20:26
  • 1
    $\begingroup$ @OughtToPrevail Redeploy them: If you have already published the telephone book with everyone's public key in it, and you don't want throw them all out and publish a new one to replace the old telephone book, then you can use XEd25519. But if you haven't published a telephone book at all yet, you don't need XEd25519. $\endgroup$ Apr 23, 2019 at 20:29
  • $\begingroup$ Ok... positive I mostly understand and I guess redeploy too, thank you. But when does the redeploy occur for Curves unlike XEd25519 and why does the redployment occur? $\endgroup$ Apr 23, 2019 at 21:17
  • 1
    $\begingroup$ @OughtToPrevail You can use XEd25519 if you have already published a telephone book with X25519 public keys (the $x$ coordinates) and you don't want to republish it with Ed25519 public keys ($x$ and $y$ coordinates). This literally happened with Signal's book mapping telephone numbers to public keys! $\endgroup$ Apr 24, 2019 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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