Use of Curve25519 in ECDSA

I'm currently investigating the use of curve25519 for signing. Original distribution and a C implementation (and a second C implementation).

Bernstein suggests to use ECDSA for this but I could not find any code.

ECDSA is specified by ANSI X9.62. That standard defines the kind of curves on which ECDSA is defined, including details curve equations, key representations and so on. These do not match Curve25519: part of the optimizations which make Curve25519 faster than standard curves of the same size rely on the special curve equation, which does not enter in X9.62 formalism. Correspondingly, there cannot be any implementation of ECDSA which both conforms to ANSI X9.62, and uses Curve25519. In practice, I know of no implementation of an ECDSA-like algorithm on Curve25519.

To be brief, you are on your own. You may want to implement ECDSA over the Curve25519 implementation by following X9.62 (there a draft from 1998 which can be downloaded from several places, e.g. there, or you can spend a hundred bucks and get the genuine 2005 version from Techstreet). But be warned that you are walking outside of the carefully trodden paths of analyzed cryptography; in other words I explicitly deny any kind of guarantee on how secure that kind-of-ECDSA would be.

My advice would be to stick to standard curves (such as NIST P-256). Note that while Curve25519 is faster than most curves of the same size, smaller standard curves will be faster, and yet provide adequate security for most purposes. NIST P-192, for instance, provides "96-bit security", somewhat similar to 1536-bit RSA. Also, standard curves already provide performance on the order of several thousands signature per second on a small PC, and I have trouble imagining a scenario where more performance is needed.

To use Curve25519 for this, you'd have to implement a lot of functions that AFAIK aren't currently implemented anywhere for this curve, which would mean getting very substantially into the mathematics of elliptic curve cryptography. The reason is that the existing functions throw away the "y" coordinate of the point and work only with the "x" coordinate. Without the "y" coordinate, the points P and -P look the same. That's fine for ECDH which Curve25519 is designed for, because |x(yG)| = |x(-yG)|. But for ECDSA you need to calculate aG + bP, and |aG + bP| does not in general equal |aG - bP|. I've looked into what would be involved in extending curve25519-donna to support such calculations; it's doable, but far from trivial.

Since what you need most of all is fast verification, I recommend Bernstein's Rabin-Williams scheme.

I recently shared the curve25519 library that I developed awhile back. It is hosted at https://github.com/msotoodeh and provides more functionality, higher security as well as higher performance than any other portable-C library I have tested with. It outperforms curve25519-donna by a factor of almost 2 on 64-bit platforms and a factor of almost 4 on 32-bit targets.

Today, many years after this question was asked, the correct answer is the signature scheme Ed25519.