Upgrade your SSH keys

.keys" rel="nofollow">https://github.com/.keys

A better comparison exists between multiplicative group crypto (DH/DSA) and their Elliptic Curve variants. In multiplicative group crypto there is a trivial, obvious mapping to the ring of integers (in less mathematical terms, "factorization makes sense"), so you can use techniques like Pohlig-Hellman (https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorit...) and Index Calculus (https://en.wikipedia.org/wiki/Index_calculus_algorithm). In Elliptic Curve groups we use, such a trivial mapping does not exist, although there are some special cases where you can achieve this (http://crypto.stackexchange.com/a/8344). Consequently, larger numbers are needed for security in these cases (along with strong primes).

The "bad press" RSA gets is likely due to the fact that in however many years of existence there have been a number of attacks on implementations - for example, side channel attacks, Bleichenbacher's attack on RSA PKCS#1_5 padding etc. Here's a survey: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf . A simple explanation is that implementing RSA is a fun exercise for personal experimentation, but implementing RSA for use in the wild is fraught with difficulties.

Ed25519 has some nice properties aside from the size of keys and signatures. It is deterministic, removing the requirement for cryptographically random (and therefore almost unique) k - if you forget this with plain ECDSA you end up in the Sony PS3 scenario. The provided software does not rely on indexes or branch instructions, removing timing issues in those cases and making the code constant time. It has what Bernstein calls "twist security" (https://safecurves.cr.yp.to/twist.html). Ordinarily, an ECC algorithm should check that a calculated or received point, particularly where point compression is used, exists on the curve in question - however with DJB's "twist security" and in particular in ed25519 this is unnecessary, simplifying the job of the implementer.

In other words, it is harder to get an implementation of ed25519 wrong.

As for the NSA pushing ECC, more intelligent people than may have different views, but I believe that ECC in general is sound, taking into account the sum of our knowledge so far. As with any algorithm there are specific choices of curves and constants which weaken the setup and we have a case study where NSA pushed poor choices deliberately: https://en.wikipedia.org/wiki/Dual_EC_DRBG . It comes down, therefore, to whether you believe the constants chosen for the NIST curves are "cooked" or not. I can't see any evidence to support this, but this doesn't mean it hasn't happened. However, Curve25519, Ed-448, Curve41717, FourQ and Brainpool curves are all curves designed outside the NIST system and not endorsed by the NSA and Bernstein includes in his security evaluations the concept of "rigidity", i.e. a full explanation of how curve parameters are generated (see https://safecurves.cr.yp.to/rigid.html) (although, apparently, there are some issues with Brainpool curve generation: https://bada55.cr.yp.to/brainpool.html).

If you want to measure "time of life" as a measure of safety, using the general assumption that the longer something remains unbroken the safer it is, RSA certainly scores better in that sense (although ECC goes back to the 90s and Curve25519 to 2005, so have been around a while too) and for a correct, good, well vetted implementation of RSA I see no reason personally to stop using it, with the caveat that, as you've noticed, if you have a high throughput system, you get equivalent security more efficiently with ed25519.

An interesting recommendation in the original article is to use smart cards for high assurance environments. I personally use an OpenPGP card (v2.1) and an authentication subkey on it acts as my SSH key. For this I use 4096-bit RSA keys - the OpenPGP v2.1 spec as implemented by this card does not support ECC at all, even though the actual hardware chip (http://www.basiccard.com/overview.htm) is capable of 512-bit ECC curves. The OpenPGP Card 3.0 standard includes ECC support but so far as I am aware no cards implementing it are available. The same is actually true in the JavaCard world; hardware support exists, but most JavaCard implementations you can buy are "limited" to 2048-bit RSA (If anyone knows differently I would love to know, please yell), which should be good enough for the moment but it would be nice to have some wiggle room.

So to summarise, the "hate" that RSA gets is likely due to the number of times people have seen mistakes in implementations. That said, the article makes a good point regarding the strength of brute forcing your key passphrase if you are not storing your keys on smartcards. If you are going to regenerate your key, I see no reason not to use ed25519 as you will likely be using it for host authentication anyway (modern remote hosts likely generate ed25519 keys by default, rather than RSA). I'd use it on my smartcards if I could, since there the timing difference for a signature would be noticeable. I have multiple ssh keys and those not stored on a smartcard are all ed25519. If you are considering embedded environments or high throughput ones, or many signature checks, ed25519 makes even more sense.