Earlier this year, Cendyne published A Deep Dive into Ed25519 Signatures, which covered some of the different types of digital signature algorithms, but mostly delved into the Ed25519 algorithm. Truth in advertising.
This got me thinking, “Why isn’t there a better comparison of different elliptic curve signature algorithms available online?”
Most people just defer to SafeCurves, but it’s a little dated: We have complete addition formulas for Weierstrass curves now, but SafeCurves doesn’t reflect that.
For the purpose of simplicity, I’m not going to focus on a general treatment of Elliptic Curve Cryptography (ECC), which includes pairing-based cryptography, Elliptic-Curve Diffie-Hellman, and (arguably) isogeny cryptography.
Instead, I’m going to focus entirely on elliptic curve digital signature algorithms.
Note: The content of this post is a bit lower-level than most programmers ever need to be concerned with. If you’re a programmer and interested in learning cryptography, start here. If you’re looking for library recommendations, libsodium is a good safe default.
Compliance Rules Everything Around Me
If you have to meet some arbitrary compliance requirements (i.e. FIPS 140-3, CNSA, etc.), your decision is already made for you, and you shouldn’t waste your time reading blogs like this that will only get your hopes up about the options available to you.
Choose the option your compliance officer demands, and hope it’s good enough.
Art: LvJ
Elliptic Curves for Signature Algorithms
Let’s start with the same curve Cendyne analyzed: Ed25519.
Ed25519 (EdDSA, Curve25519)
Ed25519 is one of the two digital signature algorithms today that use the EdDSA algorithm framework. The other is Ed448, which targets a higher security level (224-bit vs 128-bit) but is also slower and uses SHAKE256 (which is overkill and not great for performance).
Ed25519 is a safe default choice for most applications where a digital signature is appropriate, for many reasons:
- Ed25519 uses deterministic nonces, which means you’re severely unlikely to ever reproduce the Sony ECDSA k-reuse bug in your system.
The deterministic nonce is calculated from the SHA512 hash of the secret key and message. Two invocations tocrypto_sign_ed25519()with the same message and secret key will produce the same signature, but the intermediate nonce value is never revealed to an attacker. - Ed25519 includes the public key in the data hashed to produce the signature (more specifically s from the (R,s) pair). This offers a property that ECDSA lacks: Exclusive Ownership. I’ve written about this property before.
Without Exclusive Ownership, it’s possible to create a single signature value that’s valid for multiple different (message, public key) pairs.
Years ago, there would have an additional list item: Ed25519 uses Edward Curves, which have complete addition formulas and are therefore safer to implement in constant-time than Weierstrass curves (i.e. the NIST curves). However, we now have complete addition formulas for Weierstrass curves, so this has become a moot point (assuming your implementation uses complete addition formulas).
Ed25519 targets the 128-bit security level.
Why Not Use Ed25519?
There is one minor pitfall of Ed25519 that makes it unsuitable for esoteric uses (say, Ring Signature Schemes or zero-knowledge proofs): Ed25519 is not a prime-order group; it has a cofactor h = 8. This detail famously created a double-spend vulnerability in all CryptoNote-based cryptocurrencies (including Monero).
For systems that want the security of Ed25519 and its various well-studied implementations, but still need a prime-order group for their protocol, cryptographers have developed the Ristretto Group to meet your needs.
If you’re working on embedded systems, the determinism inherent to EdDSA might be undesirable due to the possibility of fault attacks. You can use a hedged variant of Ed25519 to mitigate this risk.
Additionally, Ed25519 is not approved for many government applications, although it did make the latest draft revision of FIPS 186 in 2019. If you care about compliance (see above), you cannot use Ed25519. Yet.
Guidance for Ed25519
Unless legally prohibited, Ed25519 should be your default choice, unless you need a prime-order group. In that case, build your desired protocol atop Ristretto255.
If you’re not sure if you need a prime-order group, you probably don’t. It’s a specialized requirement for uncommon use cases (ring signatures, password authenticated key exchange protocols, zero-knowledge proofs, etc.).
The Bitcoin Curve (ECDSA, secp256k1)
Secp256k1 is a Koblitz curve, which is a special case of Weierstrass curves that are more performant when used in binary fields, of the form, 
There is no specified reason why Bitcoin chose secp256k1 over another elliptic curve at the time of its inception, but we can speculate:
The author was a pseudonymous contributor to the Metzdowd mailing list for cypherpunks, and probably didn’t trust the NIST curves. Since Ed25519 didn’t exist at the time, the only obvious choice for a hipster elliptic curve parameter selection was to rely on the SECG recommendations, which specify the NIST and Koblitz curves. If you cross the NIST curves off the list, only the Koblitz curves remained.
Therefore, the selection of secp256k1 is likely an artefact of computer history and not a compelling reason to select secp256k1 in new designs. Please look elsewhere.
Secp256k1 targets the 128-bit security level.
Guidance for secp256k1
Don’t bother, there are better options. (i.e. Ed25519)
If you’re writing software for a cryptocurrency-related project, and you feel compelled to use secp256k1 for the sake of reducing your code footprint, please strongly consider the option of burning everything to the proverbial ground.
Art: Swizz
Cryptocurrency Aside, Why Avoid Secp256k1?
As we noted above, secp256k1 isn’t widely used outside of cryptocurrency.
As a direct consequence of this (as we’ll discuss in the NIST P-256 section), most cryptography libraries don’t offer optimized, side-channel-resistant implementations of secp256k1; even if they do offer optimized implementations of NIST P-256.
(Meanwhile, Ed25519 is designed to be side-channel and misuse-resistant, partly due to its Schnorr construction and constant-time ladder for scalar multiplication, so any library that implements Ed25519 is overwhelmingly likely to be constant-time.)
Therefore, any secp256k1 library for most programming languages that isn’t an FFI wrapper for libsecp256k1 will have worse performance than the other 256-bit curves.
Additionally, secp256k1 implementations are often a source of exploitable side-channels that permit attackers to pilfer your secret keys.
The previously linked article was about BouncyCastle’s implementation (which covers Java and .NET), but there’s still plenty of secp256k1 implementations that don’t FFI libsecp256k1.
From a quick Google Search:
- Python (uses EEA rather than Binary GCD for modular inverse)
- Go (uses Numbers, which weren’t designed for cryptography)
- PHP (uses GMP, which isn’t constant-time)
- JavaScript (calls here, which uses bn.js, which isn’t constant-time)
If you’re using secp256k1, and you’re not basing your choice on cybercash-interop, you’re playing with fire at the implementation and ecosystem levels–even if there are no security problems with the Koblitz curve itself.
You are much better off choosing any different curve than secp256k1 if you don’t have a Bitcoin/Ethereum/etc. interoperability requirement.
Art: LvJ
NIST P-256 (ECDSA, secp256r1)
NIST P-256 is the go-to curve to use with ECDSA in the modern era. Unlike Ed25519, P-256 uses a prime-order group, and is an approved algorithm to use in FIPS-validated modules.
Most cryptography libraries offer optimized assembly implementations of NIST P-256, which makes it less likely that your signing operations will leak timing information or become a significant performance bottleneck.
P-256 targets the 128-bit security level.
Why Not Use P-256?
Once upon a time, P-256 was riskier than Ed25519 (for signatures) and X25519 (for Diffie-Hellman), due to the incomplete addition formulas that led to timing-leaky implementations.
If you’re running old software, you may still be vulnerable to timing attacks that can recover your ECDSA secret key. However, there is a good chance that you’re on a modern and secure implementation in 2022, especially if you’re outsourcing this to OpenSSL or its derivatives.
ECDSA requires a secure randomness source to sign data. If you don’t have one available, and you sign anything, you’re coughing up your secret key to any attacker capable of observing multiple signatures.
Guidance for P-256
P-256 is an acceptable choice, especially if you’re forced to cope with FIPS and/or the CNSA suite requirements when using cryptography.
Of course, if you can get away with Ed25519, use Ed25519 instead.
If you use P-256, make sure you’re using it with SHA-256. Some implementations may default to something weaker (e.g. SHA-1).
If you’re also going to be performing ECDH with P-256, make sure you use compressed points. There used to be a patent; it died in 2018.
If you can afford it, make sure you use deterministic ECDSA (RFC 6979) or hedged signatures (if fault attacks are relevant to your threat model).
NIST P-384 (ECDSA, secp384r1)
NIST P-384 has a larger field than the curves we’ve previously examined, which allows P-384 to target the 192-bit security level. That’s the primary reason why anyone would choose P-384.
Naturally, elliptic curve security is more complicated than merely security against the Elliptic Curve Discrete Logarithm Problem (ECDLP).
P-384 is most often paired with SHA-384, which is the most widely used flavor of the SHA-2 family hash functions that isn’t susceptible to length-extension attacks. (There are also truncated SHA-512 variants specified later, but that’s also what SHA-384 is under-the-hood.)
If you’re aiming to build a “secure-by-default” tool for a system that the US government might one day become a customer of, with minimal cryptographic primitive choice, using NIST P-384 with SHA-384 makes for a reasonably minimalistic bundle.
Why Not Use P-384?
Unlike P-256, most P-384 implementations don’t use constant-time, optimized, and/or formally verified assembly code. (Notable counter-examples: AWS-LC and Go x/crypto.)
Like P-256, P-384 also requires a secure randomness source to sign data. If you aren’t providing one, expect your signing key to end up on fail0verflow one day.
Guidance for P-384
If you use P-384, make sure you’re using it with SHA-384.
The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.
NIST P-521 (ECDSA, secp521r1)
Biggest curve is best curve! — the clueless
Systems that choose P-521 often have an interesting threat model, even though said threat model is rarely formally specified.
It’s overwhelmingly likely that what eventually breaks the 256-bit elliptic curves will also break P-521 in short order: Cryptography Relevant Quantum Computers.
The only thing P-521 does against CRQCs that P-256 doesn’t is require more quantum memory. If you’re worried about QRQCs, you might want to look into hybrid post-quantum signature schemes.
If you’re choosing P-521 in your designs, you’re basically saying, “I want to have 256 bits of asymmetric cryptographic security, come hell or high water!” even though the 128-bit security level is likely just fine for your actual threats.
Aside: P-521 and 512-bit ECC Security
P-521 is not a typo, although people sometimes think it is. P-521 uses the Mersenne prime 
This has led to an unfortunate trend in cryptography media to map ECC key sizes to symmetric security levels that misleads people as to the relationship between the two. For example:
Regrettably, this is misleading, because plotting the ECC Key Size versus equivalent Symmetric Security isn’t a how ECDLP security works. The ratio of the exponents involved is totally linear; it doesn’t suddenly increase beyond 384-bit curves for a mysterious mathematical reason.
- 256-bit Curves target the 128-bit security level
- 384-bit Curves target the 192-bit security level
- 512-bit Curves target the 256-bit security level
- 521-bit Curves actually target the 260-bit security level, but that meets or exceeds the 256-bit security level, so that’s how the standards are interpreted
The reason for this boils down entirely to the best attack against the Elliptic Curve Discrete Logarithm Problem: Pollard’s Rho, which recovers the secret key from an 
Taking the square root of a number is the same as halving its exponent, so the security level is half: 
Takeaway: If someone tells you that you need a 521-bit curve to meet the 256-bit security level, they are mistaken and it’s not their fault.
Why Not Use P-521?
It’s slow. Much slower than P-256 and Ed25519. Modestly slower than P-384.
Unlike P-384, you’re less likely to find an optimized, constant-time P-521 implementation.
Guidance for P-521
First, make a concerted effort to figure out the motivation for P-521 in your designs. Chances are, someone is putting too much emphasis on the wrong things for security.
If you use P-521, make sure you’re using it with SHA-512.
The standard NIST curve advice of RFC 6979 and point compression and/or hedged signatures applies here too.
Ed448 (EdDSA, Curve448)
Ed448 is the P-521 of the Edwards curves: It mostly exists to give standards committees a psychological comfort for the unlikely event that 256-bit ECC is desperately broken but ECC larger than 384 bits is somehow still safe.
The very concept of having multiple “security levels” for raw cryptography primitives is mostly an artefact of the historical military roots of cryptography, rather than a serious consideration in the modern world.
Unfortunately, this leads to implementations that prioritize runtime algorithm selection negotiation, which maximizes the risk of protocol-level vulnerabilities. See also: JWT.
Ed448 was specified to use SHAKE256, which is a needlessly conservative decision which leads to an unnecessary performance bottleneck.
Why Not Use Ed448?
Aside from the performance hit mentioned previously, there’s no compelling reason to avoid Ed448 that isn’t also true of either Ed25519 or P-384.
Guidance for Ed448
If you want more speed, go with Ed25519. In addition to being faster, Ed25519 is also very widely supported.
If you need a prime-order field, use Decaf with Ed448 or consider P-384.
The Brainpool Curves
The main motivation for the Brainpool curves is that the NIST curves were not generated in a “verifiable pseudo-random way”.
The only reasons you’d ever want to support the Brainpool curves include:
- You think the NIST curves are somehow backdoored by the NSA
- You don’t appreciate small attack surfaces in cryptography libraries
- The German government told you to (see: compliance)
Most of the advice for the NIST Curves at each security level can be copy/pasted for the Brainpool curves, with one important caveat:
When considering real-world implementations, Brainpool curves are more likely to use the general purpose Big Number procedures (which aren’t always constant-time), rather than optimized assembly code, than the NIST curves are.
Therefore, my general guidance for the Brainpool curves is simply:
- Proceed at your own peril
- Consider hiring a cryptography engineer to study the implementation you’re relying on, especially with regard to timing attacks
Art: LvJ
Re-Examining the SafeCurves Criteria
Here’s a 2022 refresh of the SafeCurves criteria for all of the curves considered by this blog post.
| SafeCurve Criteria | Relevance to the Curves Listed Above |
|---|---|
| Fields | All relevant curves satisfy the requirements |
| Equations | All relevant curves satisfy the requirements |
| Base Points | All relevant curves satisfy the requirements |
| Rho | All relevant curves satisfy the requirements |
| Transfers | All relevant curves satisfy the requirements |
| Discriminants | Only secp256k1 doesn’t satisfy the requirements (out of the curves listed in this blog post) |
| Rigidity | The NIST curves do not meet this requirement. If you care about whether or not the standards were manipulated to insert a backdoor, rigidity matters to you. Otherwise, it’s not a deal-breaker. |
| Ladders | While a Montgomery ladder is beneficial for speed and implementation security, it isn’t strictly speaking required. This is an icing-on-the-cake consideration. |
| Twists | The only curve listed above that doesn’t meet the requirement is the 256-bit Brainpool curve (brainpoolp256t1). |
| Completeness | All relevant curves satisfy the requirements, as of 2015. SafeCurves is out of date here. |
| Indistinguishability | All relevant curves satisfy the requirements, as of 2014. |
SafeCurves continues to be a useful resource, especially if you stray from the guidance on this page.
For example: You wouldn’t want to use pairing-friendly curves for general purpose ECC digital signatures, because they’re suitable for specialized problems. SafeCurves correctly recommends not using BN(2,254).
However, SafeCurves is showing its age in 2022. BN curves still end up in digital signature protocol standards even though BLS-12-381 is clearly a better choice.
The Internet would benefit greatly for an updated SafeCurves that focuses on newer elliptic curve algorithms.
TL;DR
Ed25519 is great. NIST P-256 and P-384 are okay (with caveats). Anything else is questionable, and their parameter selection should come with a clear justification.
19 replies on “Guidance for Choosing an Elliptic Curve Signature Algorithm in 2022”
Hi,
This is the first time I’m commenting, so first of all, thank you for all the great content on this blog!
If I may nit-pick a bit:
– I think “a special case of Weierstrass curves that can be used in binary fields” is a bit misleading, I think it would be more accurate to say that they have special properties that can be used to boost performance especially over binary fields (which is what the linked source says, btw). One point is, working on binary fields is nothing specific to Koblitz curves. The other point is Koblitz curves on prime fields use a different equation than Koblitz curves on binary fields, so they’re not that directly related (Koblitz curves on prime fields just try to transfer to the prime field case one trick that happens to be quite important in the case of binary fields, that’s all). In particular, it would be wrong to think you can somehow take secp256k1 and “use it in binary fields”, while I think that’s one reasonable intepretation of your wording.
– I’m not seeing anything wrong with the table you show at the beginning of section “Aside: P-521 and 512-bit ECC Security”. I don’t think it’s “plotting the ECC Key Size versus equivalent Symmetric Security”, but ECC key size vs equivalent RSA key size. The ratio explodes because “The ratio of the exponents [between ECDLP and symmetric] is totally linear” as you say, but it famously isn’t the case for RSA, where sub-exponential attacks exist. I agree with the general point that the reason we have 521 instead of 512 here is because of the Mersenne prime, which was chosen for performance and not because we would need the extra 9 bits to reach the 512-bit level for some mysterious reason. But I just don’t see what that has to do with the quoted table.
– “Unlike Ed25519, P-256 uses a prime-order field” I think that’s a typo an you mean group here.
That’s it, sorry for picking on details, and again thanks for al the great content!
Thanks for the nit-picks. I’ll make corrections so nobody gets confused.
With regards to FIPS it is possible to include non-NIST curvs. There is an Implementation Guidance (https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Module-Validation-Program/documents/fips140-2/FIPS1402IG.pd and https://csrc.nist.gov/CSRC/media/Projects/cryptographic-module-validation-program/documents/fips%20140-3/FIPS%20140-3%20IG.pdf) that allows the use of non-NIST curves for FIPS 140-2 and FIPS 140-3 under the CMVP. IG A.2 (-2) and IG C.A (-3) explicitly permit the use of non-NIST-recommended curves in a module’s Approved mode of operation.
There are also two draft publications (FIPS 186-5 and SP 800-186) that (when published) will formally recognize the curves in Section 3.5 as FIPS Approved. Public comment period closed in January 2020. Section 7.1 in the draft of FIPS 186-5 (https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5-draft.pdf) identifies Edwards-curve Digital Signature Algorithms and considers them Approved (as long as the “shall” statements are met). Curve25519 is identified in Section 4.2 of SP 800-186 (https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-186-draft.pdf). ACVP validation testing (https://usnistgov.github.io/ACVP/) for these algorithms should follow once FIPS 186-5 and SP 800-186 are published. Until ACVP testing is available a these functions can be included in the module’s Approved mode of operation as “vendor affirmed”.
I know it’s, strictly speaking, “possible”. But in practice, nobody I’ve ever worked with wanted to rock the compliance boat by deviating from the well-tread path. FIPS certifications are already severely backlogged due to COVID-19 (by at least 3 months).
Fair enough đ
Additional nitpick: the following is incorrect.
“Indistinguishability: Only Ed25519 and Ed448 satisfy this requirement.”
All curves satisfy this requirement, at least as of 2014. See the Elligator Squared paper (eprint 2014/043) and its follow-ups.
I actually hadn’t had a chance to read these papers. Will do so and then update the post. Thanks!
[…] 2022-05-19): I’ve published a more in-depth treatment of the Elliptic Curve Digital Signature Algorithms a few years after this post was created. A lot of the topics covered by EdDSA and ECDSA are focused […]
[…] Dhole Moments â Guidance for Choosing an Elliptic Curve Signature Algorithm in 2022 […]
One thing I didn’t see mentioned is how curve/signature algorithm affects privacy. NIST curves and ECDSA allow the public key to be recovered from the signature (section 4.1.6 of http://www.secg.org/sec1-v2.pdf), which can act as a tracking identifier. I’m not aware of Ed25519 having this vulnerability. But, this info is from several years ago so it may no longer be relevant.
You need one additional bit to recover the public key from a signature, otherwise you recover two candidate public keys and cannot distinguish one from the other. I’ve not heard of this “feature” existing in EdDSA, either, but I could be missing something.
I love that the Tl;Dr is at the end đ hahaha
Great post, as usual! Keep up the good work!
[âŠ] Comment choisir un algorithme de courbes elliptiques [âŠ]
Very interesting and very much applicable to my requirements, which include FIPS compliance. I was wondering if you could comment on the âsectâ (versus âsecpâ) curves as well? My requirements dictate 384-bit or better, so Iâm thinking that Iâll stick with just secp384r1 and potentially allow secp521r1 but from your article, it seems like I donât really gain much from doing so. But this morning I saw âsectâ curves mentioned (on the ActiveMQ mailing list) and so I was wondering if you had any thoughts on that? Thanks.
I would advise against binary curves unless you have a specific need to support them. “sect” are elliptic curves over binary fields rather than prime fields.
[…] Less obviously, you need a specific list of non-goals for your design: Properties that you will not prioritize. A lot of security engineering involves trade-offs. For example: elliptic curve choice for digital signatures is largely a trade-off between speed, theoretical security, and real-world implementation security. […]
[…] frameworks support NIST P-256, but CPace supports X25519 and OPAQUE supports Ristretto255; these are currently not FIPSable […]
Just an update as I stumbled upon this, it seems EdDSA was approved by FIST in february 2023! This makes choosing ed25519 a much more reliable option for companies now.
https://csrc.nist.gov/publications/detail/fips/186/5/final
[…] The security of the elliptic curve being used. […]