Is it bad that my ed25519 key is so short compared to a RSA key?

Question

I recently generated a new SSH key in the ed25519 format. The public key is only 69 bytes long while my old RSA key is 373 bytes.

From my perception ed25519 is the more recent and secure format.

So why isn't longer better here?

Answer 1

No, longer is not better.

Let me explain. In symmetric cryptography, keys are just bunches of bits, and all sequences of bits are valid keys. They have no internal structure. Provided that you use decent algorithms, the best possible attack on a key for symmetric encryption is brute force: the attacker tries all possible keys until he finds the right one. If the key has n bits, then there are 2ⁿ possible keys, and the attacker, on average, will find the right one after trying half of them, i.e. 2^n-1. Longer keys thus make brute force harder; in that case, longer is better.

(Note that there is a limit to that; when keys are sufficiently long that brute force is no longer feasible, increasing the key length does not make things "more secure" in any meaningful way. So, for symmetric keys, longer is better until they are long enough, at which point longer is just longer.)

RSA and EdDSA relate to asymmetric cryptography where things are completely different. A key for asymmetric cryptography is a mathematical object that has a specific internal structure; breaking the key consists in unravelling that structure, and can be done a lot more efficiently than trying out all possible private keys. Note the two points:

• Against brute force, what matters is not the length of the public key, but that of the private key, since what the attacker wants is the private key, not the public key.

• Brute force is not the most efficient attack against keys used in asymmetric cryptography.

For RSA keys, attack succeeds by factoring the modulus. Integer factorization is a long-studied problem; with the best known algorithm, breaking a 2048-bit RSA key (i.e., a RSA public key whose modulus is a 2048-bit integer) requires about 2¹¹⁰ or so elementary operations.

For EdDSA keys, the public key is a point P on an elliptic curve, such that P = xG where x is the private key (a 256-bit integer) and G is a conventional curve point. The best known algorithm for recovering x from P and G requires about 2¹²⁸ elementary operations, i.e. more than for a 2048-bit RSA key. In general, to break a n-bit elliptic curve public key, the effort is 2^n/2.

Breaking either key is way beyond that which is feasible with existing or foreseeable technology. But in an "academic" viewpoint, the EdDSA key is somewhat stronger than the RSA key; also, elliptic curves give you more security per bit (technically, we say that integer factorization is a sub-exponential problem).

See this site for more information on that subject.

Answer 2

I'm not satisfied with my previous answer that lead to confusing assumption about compression method used in ed25519, so I will try one more time for those who won't to jump on EC (Elliptic Curve further) math to be able to understand why EC keys is so short to compare with RSA keys.

Since my English is far from perfect, I better drop here IMHO pretty good links to this subject.

For those who really want to understand "magic" of EC (but still want to avoid to fall deeply in love with math) and be able to understand - "why EC can manage more stronger encryption than RSA using much smaller keys", - I advise to read full article on arstechnica.com "A relatively easy to understand primer on elliptic curve cryptography"

Author illustrate there gist of EC with images that helps to understand concept in a few steps.

BTW, interesting excerpt about EC:

You can compute how much energy is needed to break a cryptographic algorithm and compare that with how much water that energy could boil. This is a kind of a cryptographic carbon footprint. By this measure, breaking a 228-bit RSA key requires less energy than it takes to boil a teaspoon of water. Comparatively, breaking a 228-bit elliptic curve key requires enough energy to boil all the water on earth. For this level of security with RSA, you'd need a key with 2,380 bits.

For those, who don't want to dig internals of EC under the hood, I advise at least to read and follow pretty good practical summarization on encryption in SSH that worth of spending time on reading that. Link is here: secure-secure-shell

Ready to copy/paste solutions (provided by community of github) for various OS is here: WiKi of Secure-Secure-Shell (but I highly advise to read previuos article on github before you go there)

---

Previous answer:

Q: "The public key is only 69 bytes long while my old RSA key is 373 bytes. So why isn't longer better here?"

In addition to Tom's explanation "why the keys are shorter while at least equally secure" - according to original paper from those who created ed25519 from here: http://ed25519.cr.yp.to/ed25519-20110926.pdf :

Besides of "equally secure" ed25519's short keys are "internally" compressed. Uncompressed ed25519 key would be almost twice longer.

P.S.

To avoid confuse or misinterpretation of point compression used in ed25519, it is NOT regular compression like in a zip archive(!!!). Thanks to @diagprov for helping correct my answer in the comments with good and simple explanation of point compression and for the link describing point compression

Reference from document above (Page#2):

• Small keys. Public keys consume only 32 bytes. The times for compression and decompression are again included.