It appears that this algorithm specifically targets RSA and El-Gamel by crafting inputs that would produce different numbers of multiplications (among other ops) depending on the input.
This should be a wake-up call for the move to elliptic curves, as GPG and OpenSSH allegedly support them. Windows support is lacking for remoting into Linux hosts with elliptic curve based ciphers. I found that while PuTTY does not support this directly, evidently the Gpg4win agent can work with putty, and that might allow ECDSH/ECDSA. I haven't tested this, however. And another terminal client, Tera Term, purports to support elliptic curve algorithms.
Unfortunately for GnuPG, it looks like the only supported curves are those defined in NSA Suite B (the NIST recommended curves). That set is considered tainted by some community members. There's some discussion of GnuPG supporting Curve25519/Ed25519, of implementing it, but I can't tell if it's implemented or not.
Edit: I've played with Tera Term and can confirm that it works with Ed25519 along with OpenSSL 1.0.1f. I'm pleased with the result.
RSA is difficult to make constant time, but there are plenty of constant-time elliptic curve implementations out there. Curve25519/Ed25519 is one of them, and this paper suggests that they will be strongly resistant to these sort of attacks.
RSA is actually one of the easiest algorithm to protect from side-channel attacks (though nothing gives you 100% protection), thanks to the various kinds of blindings you can immediately apply.
Blinding techniques are not constant-time, but what you really want in the end is to reduce the Signal-to-Noise ratio on the radiated energy.
For ECC it is more difficult, and it becomes very hard for most symmetric ciphers.
Blinding ECC is as easy as RSA, if not easier. Coron's classic paper has 3 easy measures to blind a scalar multiplication, and more have appeared since then:
The problem with GnuPG is not that it's using RSA/ElGamal instead of ECC; it's that it's using a general-purpose large integer arithmetic package, MPI, whose purpose is to optimize speed for a wide range of input arguments.
On the specific case of RSA (or rather, CRT-RSA), I've mostly studied fault-injection attacks, which can be considered a kind of side-channel attack. And I agree with you that it is possible to protect RSA (see my most recent paper [1] on that subject, which will be published at FDTC 2014, the day just before CHES 2014, where the paper being discussed in this HN thread will appear).
I also agree with you on the fact that ECC is not immune to side-channel attacks at all: for proof this cool paper [2] by Barthe, Dupressoir, Fouque, Grégoire, and Zapalowicz, which will appear at CCS 2014 which shows working fault-injection attacks on both RSA and ECDSA.
Curve25519 was designed specifically to be leak-resistant, by one of the world's foremost experts in leak-resistant cryptography. Most elliptic curve software is not. Like RSA, elliptic curve also involves exponentiation and modular reduction.
This should be a wake-up call for the move to elliptic curves, as GPG and OpenSSH allegedly support them. Windows support is lacking for remoting into Linux hosts with elliptic curve based ciphers. I found that while PuTTY does not support this directly, evidently the Gpg4win agent can work with putty, and that might allow ECDSH/ECDSA. I haven't tested this, however. And another terminal client, Tera Term, purports to support elliptic curve algorithms.
Unfortunately for GnuPG, it looks like the only supported curves are those defined in NSA Suite B (the NIST recommended curves). That set is considered tainted by some community members. There's some discussion of GnuPG supporting Curve25519/Ed25519, of implementing it, but I can't tell if it's implemented or not.
Edit: I've played with Tera Term and can confirm that it works with Ed25519 along with OpenSSL 1.0.1f. I'm pleased with the result.