Missing elliptic curves

[tarcieri]

This is a tracking issue for additional elliptic curves we could potentially implement.

Note that we are presently focusing on short Weierstrass curves which can be implemented using the primeorder crate. There are many other Rust projects implementing newer curve forms, such as bls12_381, curve25519-dalek and ed448-goldilocks.

• [ ] Brainpool P-224 (brainpoolP224r1, brainpoolP224t1)
• [x] Brainpool P-256 (brainpoolP256r1, brainpoolP256t1)
• [ ] Brainpool P-320 (brainpoolP320r1, brainpoolP320t1)
• [x] Brainpool P-384 (brainpoolP384r1, brainpoolP384t1)
• [ ] Brainpool P-512 (brainpoolP512r1, brainpoolP512t1)
• [x] NIST P-192 (secp192r1)
• [x] NIST P-224 (secp224r1)
• [x] NIST P-521 (secp521r1)
• [ ] GOST 34.10-2018
• [ ] secp224k1
• [x] SM2

[tarcieri]

I added an initial set of Brainpool curves (bp256 and bp384) in #281 and #280 respectively.

Unfortunately I'm not a Brainpool user, so I was unclear around usage of brainpoolP256r1/brainpoolP384r1 vs brainpoolP256t1/brainpoolP384t1. The crates I added assume the former.

Happy to hear from Brainpool users about how the curves are used in practice. If it turns out *r1 is a mistake we can potentially transition over to *t1 or support both *r1 and *t1.

[tarcieri]

Circling back on Brainpool, I see a couple ways forward. We should decide which one makes sense.

First, for background:

• r1 curves are "verifiably pseudorandom" (or rather, were supposed to be but were erroneously generated)
• t1 curves are the "twist" curves and provide the same effective security properties but permit a slightly more efficient implementation due to the use of smaller parameters

So, it seems like we should probably support both r1 and t1, for both the 256-bit and 384-bit modulus sizes. Here are a couple of ways that could be done:

Include both r1 and t1 curves in the same crate

This would result in the following crates:

• bp256: brainpoolP256r1 and brainpoolP256t1
• bp384: brainpoolP384r1 and brainpoolP384t1

Separate crates for r1 and t1 curves

This would look like:

• bp256r1: brainpoolP256r1
• bp256t1: brainpoolP256t1
• bp384r1: brainpoolP384r1
• bp384r1: brainpoolP384t1

My vote would be for bp256 and bp384 crates for now, each containing both the r1 and t1 variants respectively.

They could be placed under r1 and t1 modules, e.g. bp256::r1 and bp256::t1

As it were, I went ahead and registered bp256r1, bp256t1, bp384r1, and bp384t1 just in case.

Edit: split r1 and t1 variants of bp256 and bp384 in #286

[kamulos]

I know it is not one of the most widespread curves, but is there any chance, that secp224r1 is supported at some point?

[tarcieri]

@kamulos it might be possible to support sometime after #218 lands

[pdeligia]

@tarcieri, I know that you mentioned in your original post that:

Note that we are presently focusing on "legacy" short Weierstrass curves. There are many other Rust projects implementing newer curve forms, such as curve25519-dalek and bls12_381.

But is there any chance (or are planning already) to implement the curve25519 natively in RustCrypto's elliptic-curves crate?

I know that someone can use curve25519-dalek, but I am mainly looking for a solution that plays along well with the RustCrypto elliptic_curve::PublicKey (and other related) APIs and especially the "parsing SPKI" feature. This would be super awesome, as I don't think with curve25519-dalek you can do something similar (i.e. parse from PEM/DER), nor that it interops with the elliptic-curves crate, unless I am missing something?

[tarcieri]

I assume you're specifically interested in Ed25519 and RFC 8410 support?

There's an open PR to add PKCS#8 and SPKI support to ed25519-zebra:

https://github.com/ZcashFoundation/ed25519-zebra/pulls

I'll also note that similar functionality is available through the signatory crate:

https://docs.rs/signatory/0.23.2/signatory/ed25519/struct.SigningKey.html#method.from_pkcs8_der

We do also maintain the ed25519 crate which is used by ed25519-dalek. I could potentially add support for decoding/encoding PKCS#8 and SPKI public keys and private keys to bytes:

https://github.com/RustCrypto/signatures/tree/master/ed25519

[tarcieri]

I added PKCS#8 support to the ed25519 crate in https://github.com/RustCrypto/signatures/pull/381

It now provides a KeypairBytes type which can be decoded from/encoded into PKCS#8.

Note it's still unreleased though

[diachedelic]

Deno, a popular JavaScript runtime, uses RustCrypto's implementation of the P-256 and P-384 curves. A lack of support for the P-521 curve is the only thing holding it back from full compliance the WebCrypto standard, implemented by all major browsers. I humbly request the P-521 curve. Thank you very much!

[tarcieri]

Now that p384 is mostly good to go and based on what are hopefully reusable wrappers around fiat-crypto (#586), it might be possible to wrap their implementation of P-521's fields, although first I'll probably take a look at migrating the field implementations in p256 to also use fiat-crypto.

[kamulos]

Has the secp224r1 come any closer with the work? The #218 you mentioned last time seems to be abandoned.

[tarcieri]

Do you have a real use case for it?

Note that there's quite a bit of duplication between p256 and p384, and more work is needed to extract things like the addition formulas and make them generic around the underlying field elements, so we're still not in great shape to start supporting more P-curves.

If it's just p256, p384, and p521, things are a bit more manageable until more of the implementation can be provided generically.

[kamulos]

Sounds reasonable :+1:

I need the curve for my company's product. Having this without importing one of the few C crypto libraries supporting it would be nice to have, but obviously I am aware that this is a quite exotic curve.

[tarcieri]

#607 added the initial boilerplate for a p521 crate.

However, implementing it properly will require some breaking changes to the elliptic-curve crate as various properties which can presently be computed/inferred, such as the size of a serialized field element, will require explicit configuration with p521.

[tarcieri]

#631 extracts a proper generic implementation of AffinePoint and ProjectivePoint, which eliminates a lot of code duplication and will make it much easier to implement p521 as well as adding arithmetic backends to bp256 and bp384.

[tarcieri]

@newpavlov we got a request on Zulip for a p224 crate. Can you grant ownership to the elliptic-curves team?

[newpavlov]

@tarcieri Done.

[tarcieri]

@newpavlov thank you!

[tarcieri]

p224 and p521 now have base and scalar field implementations, as well as curve parameter definitions, although none of it is properly tested and all gated under the wip-arithmetic-do-not-use crate feature.

[halvors]

Could you please add secp192r1 to this list?

[tarcieri]

@halvors added, although given its small modulus size it will probably be a fairly low priority (i.e. we should finish up P-224, P-521, and the Brainpool curves first, at least)

[tarcieri]

@newpavlov it looks like you're an owner of the sm2 crate. Do you know its status?

[newpavlov]

@tarcieri I have added @RustCrypto/elliptic-curves to owners of sm2 (though I don't remember exactly how I got it).

P.S.: I think it would be better to use the Zulip private chat for such questions, since I doubt other users are interested in these matters.

[halvors]

I see that secp256k1 is supported, and seems to be the most complete so far, is this generalized? Would it be easy to support other k1 curves, for example secp224k1 ?

[tarcieri]

@halvors supporting any given curve is a lot of work, as we need to synthesize field implementations (both base and scalar) for each curve, and plug in formulas for the parts of the field implementation which can't be synthesized.

The curve arithmetic implementation is generic; the field arithmetic implementations are not.

[tarcieri]

As of v0.13.1 (#820), p224 has an arithmetic feature as well as support for ECDH and ECDSA

[halvors]

@halvors supporting any given curve is a lot of work, as we need to synthesize field implementations (both base and scalar) for each curve, and plug in formulas for the parts of the field implementation which can't be synthesized.

The curve arithmetic implementation is generic; the field arithmetic implementations are not.

I fully understand that it is a lot of work, but would it still be possible to add it to the list to eventually be added in the future when the other curves are finished?

Also I can to the best of my ability help out, I don't think I am skilled enough to write the field arithmetic implementation myself, but still I can help out with other tedious work like adding test vectors etc that maybe isn't a lot of help but hopefully still can reduce the amount of work that has to be done.

[tarcieri]

Okay, I can add it, although I'd prefer to implement curves people are actually using

[halvors]

Okay, I can add it, although I'd prefer to implement curves people are actually using

Very understandable, in my use case i have to verify signature using P-192, P-224, and k224 (but not signing) this is due to the fact that i am verifying authentication tokens issued by an external provider (somewhat dated one of that). So me personally have a use case for it, but i understand that the curve is rather exotic and not much used in general.

Has there been any progress on generalizing k256? If so could generic implementations be reused for k224? Or is something that is yet to be done?

[fjarri]

Has there been any progress on generalizing k256? If so could generic implementations be reused for k224? Or is something that is yet to be done?

@halvors https://github.com/RustCrypto/elliptic-curves/tree/master/primeorder seems to be it? Have you tried applying it to your curves?

[tarcieri]

Yeah, primeorder should work fine for it, but there are other curves I'd like to work on first which are niche but more commonly used, like the Brainpool curves