How to interpret this statement against 4096-bit RSA

Question

While I'd agree that double-sized RSA keys may pose more problems than the gain in security possibly justifies, I am having problems understanding the argument made here: https://gnupg.org/faq/gnupg-faq.html#please_use_ecc

They state that RSA2048 corresponds to about 112 bits of security and RSA4096 to about 140 bits, and they state that the 28 bits improvement is "marginal". But the way I understand this, is that the conversion from "key bits" to "security bits" is that it (as an estimate) takes ~2¹¹² operations to crack a 2048 bit RSA key and ~2¹⁴⁰ operations to crack a 4096 bit RSA key. So in my eyes that still means that if they™ routinely solve the RSA2048 problem in one seconds by throwing all their CPU power at it, it would still take several years for the RSA4096 key. (Or: be slightly less paranoid and replace "one second" with "one minute" and "several years" becomes "several centuries").

Why would such differences still be called "marginal"?

Maybe the answer is that 112 or 140 bits is only for some brute-forcing (even though the naive brute force would be something like 1024 vs 2048 bis) - but wouldn't that rather imply that these numbers are inadequate to begin with as a means to describe the complexity/security?

Answer 1

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 2²⁸ 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

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:

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 algorithm, 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 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 materialize 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 advise is that 4096‑bit RSA is a sound choice for long term security in PGP/GPG. It is safe, interoperable, simpler thus 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‑Qbit superconducting chip.

---

2019 addition: 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.

---

2022 addition: The answer remains accurate. Notably, the acronym CRQC (for Cryptographically Relevant Quantum Computer) has caught for this answer's quantum computer usable for cryptanalysis. The NSA (or is it the NIST) published a readable FAQ defining the term. I find it rather balanced, even if I'm a tad more skeptical than they admit they are about if and when CRQC will ever be available to mankind.