69
$\begingroup$

NaCl and libsodium libraries use Curve25519 for authenticated encryption (actually for sharing a key which is used for encryption) and Ed25519 for signatures. What is the purpose of using different primitives for these operations? Why just not to use the same primitive for both key-sharing and signatures?

Are there some security or performance considerations? But both key-sharing and signing rely on multiplication of curve point by scalar so I guess you can't gain anything here by using different curves. If one of the curves is faster it should be faster in both cases.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
63
$\begingroup$

While it is true that Elliptic Curve Diffie Hellman (ECDH), Elliptic Curve Signature Generation (ECDSA), and Elliptic Curve Signature Verification rely on scalar multiplications, these are usually implemented as different types of scalar multiplication for both security and efficiency reasons.

In fact, there are three types of scalar multiplications used in practice for these schemes:

  • Fixed-Base: when the input point of the scalar multiplication is known at design time
  • Variable-Base: when the input point of the scalar multiplication is not known in advance
  • Double-Base: when the protocol actually requires to compute two scalar multiplications and then to add both results. (e.g. $kP+rB$ )

Variable-Base is what is usually needed in ECDH, as you receive the input point of the scalar multiplication from another peer.

Fixed-Base is used in key generation and signature generation. Here the fixed-base is always the "generator point", which is the point that generates the prime-order subgroup that is provided together with the curve's equation.

Double-Base is used for signature verification (both ECDSA and EdDSA and Schnorr) require to compute something of the form $kP+rB$. Note that unlike ECDH or Signature Generation the Signature Verification doesn't make use of any secret values and therefore there are no requirements for constant time execution.

X25519 provides a very simple, constant time, and fast variable-base scalar multiplication algorithms. This is very good for ECDH and this is why it is used specifically for ECDH.

Ed25519 instead provides a very fast fixed-base and double-base scalar multiplications, thanks to the fast and complete twisted Edwards addition law. In fact, the fixed-base algorithm of Ed25519 is, on the most platforms, faster than the variable-base of X25519.

And using X25519 for signature verification is just a bad idea because you need to execute it twice (to compute $kP$ and $rB$) and then to add a new function to perform the full addition of the two resulting points. Furthermore, you are using constant-time computation where it's not needed. Instead, you can achieve much faster implementations using interleaved NAF methods and the twisted Edwards addition law.

Note: for the purpose of this answer I'm not distinguishing between different elliptic curve signature algorithms such as ECDSA and EdDSA.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ In certain circumstances it may be worthwhile to use X25519 with a Montgomery ladder even for signatures: qDSA seems to outperform EdDSA on microcontrollers, at substantially less memory and code size than other Edwards alternatives like FourQ. $\endgroup$
    – Squeamish Ossifrage
    Commented Mar 19, 2019 at 14:44
  • 1
    $\begingroup$ Unfortunately this and all the answers seem to be from a perspective where you only care about performance, not fitting code in very small text space. $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Commented Sep 20, 2021 at 14:56
40
$\begingroup$

The old terminology was confusing, so they've rebranded a bit.

  • X25519 is Elliptic Curve Diffie-Hellman (ECDH) over Curve25519
  • Ed25519 is Edwards-curve Digital Signature Algorithm (EdDSA) over Curve25519

Libsodium's ref10 curve25519 code is actually used both by crypto_scalarmult()/crypto_box() as well as crypto_sign().

Improve this answer
$\endgroup$
3
  • 20
    $\begingroup$ To be nitpicky, Ed25519 is EdDSA over a twisted Edwards curve birationally equivalent to—but not isomorphic as an algebraic group, and thus not usually considered the ‘same as’—Curve25519. $\endgroup$
    – Squeamish Ossifrage
    Commented Sep 16, 2017 at 18:40
  • 7
    $\begingroup$ You are technically correct, the best kind of correct. $\endgroup$
    – Scott Arciszewski
    Commented Sep 17, 2017 at 19:02
  • 6
    $\begingroup$ Woo! Do I get a prize? Also, are you sure that libsodium's crypto_sign_ed25519 uses crypto_scalarmult_curve25519? That would be weird because crypto_scalarmult_curve25519 is $x$-only, whereas crypto_sign_ed25519 needs the $y$ coordinate even if it's only a single bit. A constant crypto_scalarmult_curve25519_BYTES seems to appear in crypto_sign/ed25519/keypair.c in a routine to convert an Ed25519 secret to an X25519 secret by hashing the seed and clamping bits of the scalar, but that's all. $\endgroup$
    – Squeamish Ossifrage
    Commented Sep 17, 2017 at 21:10
18
$\begingroup$

Curve25519 makes use of a special x-coordinate only form to achieve faster multiplication. Ed25519 uses Edwards curve for similar speedups, but includes a sign bit. While it could have been done differently, doing it this way simplifies implementations that only need one of encryption or signing.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I think Ed25519 uses a twisted Edwards curve, not a (plain) Edwards curve. $\endgroup$
    – étale-cohomology
    Commented Nov 9, 2017 at 22:47
  • $\begingroup$ I think your answer is most clear! $\endgroup$
    – user3130782
    Commented Mar 25, 2022 at 11:08

Your Answer

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