10

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.

1
  • Since this was asked, Bernstein developed Ed25519 as a means to use this curve for signing. ed25519.cr.yp.to Oct 11, 2016 at 17:08

4 Answers 4

13

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.

6
  • Thank you very much. My goal was to get compact signatures and preferably fast to verify. I red in the mean time some articles reporting that an rsa signature may be 5 time faster to verify than an ECDSA signature. This is problematic for my type of application where signatures must be checked by message relay servers. Any code for NIST P-192 to suggest I could use and benchamrk ?
    – chmike
    Mar 27, 2010 at 11:50
  • Try OpenSSL (openssl.org). It is both a library and a command-line tool. The command-line tool (included in every decent version of Linux) has a "speed" option which runs a benchmark. Mar 27, 2010 at 13:14
  • If you want fast verification, use Bernstein's Rabin-based signature scheme and probabilistic verification - blazingly fast. Apr 8, 2010 at 16:30
  • 1
    By now there is a signature scheme called Ed25519 which works on the same curve, but in a different representation. Jul 13, 2012 at 21:23
  • Does this also apply to ECDH; i.e., could Curve25519 be used as a custom curve in protocols like TLS that allow specifying one?
    – lxgr
    Sep 12, 2013 at 18:22
9

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.

4

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.

2

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

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.