A comparison of different elliptic curves: which to use
curve25519: I don’t trust it. It’s not used in any major protocols (eg TLS) because the equation’s of the wrong form (x² term rather than x), so implementations won’t be widely reviewed. Of course he’s right it’s fast, but it’s happened before that’s someone’s tried to optimise some arithmetic in major libraries like OpenSSL and introduced subtle calculation errors. Therefore, I don’t trust any implementations, especially Bernstein’s which is written in his own programming language no-one else has ever heard of. The best implementation looks to be curve25519-donna. Also non-standard, so no marketing or certification possible (“US Government-approved!”). Finally, regarding speed, Käsper points out (“Fast Elliptic Curve Cryptography in OpenSSL”) that Bernstein’s curve25519 implementation isn’t constant-time, and the best constant-time implementation is in fact slightly slower than P-224, so the speed issue might be moot anyway. Avoid.
NIST P-192: why bother? P-224 is faster and stronger.
NIST P-384: why bother? P-521 is faster and stronger.
NIST P-224: we have a winner. Recognized by all bodies (ANSI, NIST) and approved for use everywhere, and blazingly fast. Rather stronger than RSA-2048. (Adam Langley claims it’s well over twice as fast as P-256, but I only get 16% faster on my machine, so you might need to take care to ensure you’re using a fast implementation.)
NIST P-256: somewhat stronger than P-224 (about RSA-3000 equiv), but honestly why do you need that much? A security level of 128 bits (ie 2¹²⁸ operations to crack) is apparently approved for use until 2060, but which point it’s possible that quantum cryptography will be around. I’m serious: there are working machines now, just not big enough, as a result of twenty years of research. The difference between P-224 and P-256 isn’t worth it: if you want really long-term protection, either (1) be paranoid and use P-521 in the hope that throwing another 2¹²⁸ operations at the attacker will slow him down even in 2060 (hardly an improbable prediction); or, (2) use 256-bit hashing methods that aren’t susceptible to quantum methods and can’t ever be cracked by anything in the universe. Unfortunately, deploying hash-based signature and key exchange schemes is a total pain and vastly vastly slower than anything you want to do. My conclusion: forget P-256, go for P-521. This is the same logic that justifies the existence of AES-256 in the face of AES-196, ie, it’s a completely stupidly large level of security that can only be justified by absurd paranoia, and since it’s only 40% slower than AES-128 who cares? Note that P-521 matches the security level of AES-256, so if you’re planning to use AES-256 you have to go for 500-bit elliptic curves anyway; if the links in your chain don’t have comparable strength, you’re wasting computation on all the algorithms that are stronger than the weakest function you use.
NIST P-521: a winner. The natural match to AES-196 or AES-256. In my mind, the only curve worth using to secure data beyond 2070 or 2080, because computers of the future are just too unpredictable to use the Moore’s law projections.
Koblitz curves/binary fields: It’s good that we don’t have a complete monoculture, but by and large standards bodies have avoided recommending these, and across the various protocols (IPSec, TLS) they seem to be less used. I don’t have a good reason not to use them, and I haven’t studied the way the arithmetic is optimised at all, but my suggestion is to avoid them. Why use something I don’t understand?