The reasoning in the quoted advice is poor:
The United States’ National Institute of Standards and Technology (NIST) states that RSA‑2048 gives roughly 112 bits of security and RSA‑3072 gives roughly 128. There is no formal recommendation on where RSA 4096 lies, but the general consensus is that it would come in somewhere around 140 bits — 28 bits of improvement over RSA‑2048. This is an improvement so marginal that it’s really not worth mentioning.
If you need more security than RSA‑2048 offers, the way to go would be to switch to elliptical curve cryptography — not to continue using RSA. As stated in the question, even the 28‑bit (or 228 times) improvement in resistance to brute force from 2048‑bit RSA to 4096‑bit RSA is large (not marginal), enough for decades of brute-force computing progress, and could well make the difference between secure and insecure in say half a century. Also, the 28‑bit figure quoted is significantly below general consensus, which would be more like 36±4‑bit. Factoring the public modulus of a properly drawn RSA key n with classical (non-quantum) computers is, as far as we know, best done by GNFS with effort
GNFS asymptotic formula
While the speed at which the o(1) term goes to zero is not known, projections on computing effort customarily neglect that o(1). Taking 3072‑bit RSA as baseline, that tells 4096‑bit RSA would be ≈18‑bit (not 12‑bit) harder, 7680‑bit RSA ≈64‑bit harder, and 15360‑bit ≈131‑bit harder. This nicely matches the figures starting from the 128‑bit security level in NIST SP 800-57 Pt 1 implicitly referenced by the citation:
- NIST comparable strengths table
- If there is a consensus, it is that
If 4096‑bit RSA is broken in the next three decades, that will be by some groundbreaking progress in factorization algorithms, or (and) the advent of quantum computers usable for cryptanalysis (which currently do not exist, and remain highly hypothetical).
There is no compelling reason to believe that ECC would be less susceptible to such hypothetical progress; there are even convincing arguments that at the same security level (and increasingly at higher levels), ECC would fall before RSA to quantum computers usable for cryptanalysis.
One correct argument to be made against 4096‑bit RSA is that currently 2048‑bit RSA is more than safe enough, thus 4096‑bit RSA is way overkill. But a reasonable argument to use 4096‑bit RSA is the possibility of quantum computers usable for cryptanalysis; or/and, the need to repel those considering such devices might materialise in the usable lifespan of the key. 4096‑bit RSA is fast enough to be usable from most applications of PGP/GPG involving a post-2010 general-purpose computer; key and ciphertext size is bearable; so why not?
My advice is that 4096‑bit RSA is a sound choice for long term security in PGP/GPG. It is safe, interoperable, simpler and better audited than ECC, and there is some credibility in the arguments that it gives a better level of security against hypothetical quantum computers usable for cryptanalysis. Note: I use quantum computer usable for cryptanalysis rather than quantum computer, because devices performing Adiabatic Quantum Computing (as in D‑Wave's 2000Q) are increasingly referred to as quantum computers, while I have not seen any serious claim that their technology could lead to something usable for cryptanalysis, contrary to the Intel/QuTech 17‑Qubit superconducting chip. Addition: And now (2019) there are indisputably quantum computers competitive with classical computers on some simulation problems (even if their claim to quantum supremacy in this area is disputed), but still useless for any exact, deep, combinatorial problem like cryptanalysis.
