Comparison of RSA vs elliptical keys

[Grzegorz Kulewski]

W dniu 12.05.2020 o 17:04, Sylvain Besençon via Gnupg-users pisze:
> In the FAQ, it is written:
>> Will GnuPG ever support RSA-3072 or RSA-4096 by default?
>> Probably not. The future is elliptical-curve cryptography, which will bring a level of safety comparable to RSA-16384. Every minute we spend arguing about whether we should change the defaults to RSA-3072 or more is one minute the shift to ECC is delayed. Frankly, we think ECC is a really good idea and we’d like to see it deployed as soon as humanly possible. 
> (https://www.gnupg.org/faq/gnupg-faq.html#default_rsa2048)
> 
> So, I guess the key size is not the only criteria to evaluate the strength of a cipher and ECC still provides better results despite shorter keys.
> 
> However, I would be interested to know which ECC cipher would you recommend to replace RSA. I am not a cryptographer and I don't find any information (or more honestly: information that I can understand) about Curve 25519, NIST P-256 (and greater), Brainpool, or secp256k1.

Disclaimer: I am not a cryptographer either, let's just say I am an advisor. So, anybody, please correct me, if needed.

1. In terms of key size Curve 25519 and P-256 should have same strength: ~128 bits (== comparing with good symmetric cipher, like AES). Generally decent ECC strength = ~0.5 * key_length_in_bits.
2. Curve 25519 is very easy to implement in such a way that the implementation is fast. Implementations of other curves are usually slower.
3. Curve 25519 is generally easier to implement and easier to implement in such a way that avoids many common security pitfalls, like vulnerability to timing attacks.
4. The design of Curve 25519 is public, (is believed to be) software patent free and all constants in it are derived in an easily explainable ways. There are no "magic numbers" out of nowhere that may be just random or maybe were chosen by designers to make some kind of backdoor - but you can never prove that they are innocent since obviously you can't prove that random number was indeed chosen truly randomly.
5. Curve 25519 was designed by DJB, an (mostly) independent security expert while others were designed/standardized by big organizations that (given indirect evidence and rumors) may not be that trustworthy.
6. This is why many new (and not only, see SSH) protocols tend to choose Curve 25519. But in PGP you should be careful because many implementations (and/or older versions) don't support it. So if you want portability/interoperability you may want some other curve or RSA, especially for the main and signing key.
7. If you want something stronger than Curve 25519 that (is believed to) share similar benefits try Curve 448 (~224 bits of security). But I am not sure if PGP implements it (yet?).

-- 
Grzegorz Kulewski