up:: Breaking Today’s Cryptography MOC
Post-Quantum RSA
Post-quantum RSA, or pqRSA, is a 2017 proposal by Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta that asks a tempting question directly: if Shor’s algorithm breaks RSA by factoring the modulus, can you just make the key so enormous that even a quantum computer cannot factor it in reasonable time? The answer they build is a technically valid yes and a practical no. Their construction uses a modulus roughly 1 terabyte in size, assembled from billions of small primes, which pushes all known quantum attacks above a huge work threshold while keeping legitimate encryption and decryption barely feasible on classical hardware. It works as a proof of concept at a cost of roughly a dollar per operation and a terabyte per public key, which is why it teaches a lesson rather than offering a migration path.
Source: Daniel J. Bernstein, Nadia Heninger, Paul Lou, Luke Valenta, “Post-quantum RSA,” PQCrypto 2017, cr.yp.to/papers/pqrsa-20170419.pdf.
The short version:
- pqRSA is a real proposal, not a strawman: it shows that RSA parameters can, in principle, be chosen so all known quantum attacks are infeasible while encryption and decryption stay feasible on today’s computers.
- The construction reaches that by making the modulus about 1 terabyte and building it from many billions of small primes instead of two large ones.
- The security argument is that the paper’s version of RSA has an attack cost roughly quadratic in the usage cost, so an attacker’s work scales far faster than the legitimate user’s as the key grows.
- The reason it is impractical is cost: each encryption or decryption runs on the scale of a dollar of compute time, and the public key is a terabyte, which is many orders of magnitude worse than ordinary RSA.
- The paper also introduces GEECM, a new quantum factorization algorithm faster than Shor’s for finding the small primes, which is one of the main constraints on how the parameters have to be chosen.
- The lasting lesson is that making the key bigger is not the post-quantum answer, because the classical costs explode long before the security margin becomes comfortable, which is why the transition moved to new math families instead.
What is post-quantum RSA actually proposing?
The proposal is to keep the RSA algorithm exactly as it is and defeat the quantum attack purely by scale. Ordinary RSA builds its modulus from two large secret primes, and its security rests on the difficulty of factoring that modulus back into them. Shor’s algorithm destroys that difficulty, factoring an RSA public key on a quantum computer almost as fast as the legitimate owner can decrypt, which is why RSA at normal sizes is finished once a cryptographically relevant quantum computer exists. The paper’s move is not to change the math but to change the size, asking whether the parameters can be pushed so far that even Shor’s runs out of room.
The abstract states the goal precisely: choose RSA parameters for which key generation, encryption, decryption, signing, and verification are feasible on today’s computers, while all known attacks are infeasible even assuming highly scalable quantum computers. The authors are explicit that under the assumption of a cheap, scalable quantum computer, Shor’s algorithm easily breaks RSA as used on the internet today, so the question is only whether a much larger RSA can move the attack out of reach. Their answer is a construction that lives at the extreme edge of what standard RSA speedup techniques allow, which is what makes it interesting and what makes it impractical at the same time.
Source: Bernstein, Heninger, Lou, Valenta, “Post-quantum RSA,” PQCrypto 2017, abstract and §1, cr.yp.to/papers/pqrsa-20170419.pdf.
How big does the key have to be, and why so many primes?
The headline number is a modulus of about 1 terabyte, and it is built from billions of small primes rather than the two large primes of ordinary RSA. That many-small-primes structure is the engineering trick that keeps the legitimate operations feasible at such an enormous size. Standard RSA speedup methods (working modulo each prime separately and recombining with the Chinese Remainder Theorem, and using fast multiplication) scale much better when the primes are small and numerous, so decomposing a terabyte modulus into a vast number of small factors is what lets a classical machine encrypt and decrypt with it at all, rather than choking on arithmetic over a monolithic terabyte number.
Section 4 of the paper reports actually generating a 1-terabyte public key as the most expensive operation in post-quantum RSA, at parameters large enough to push all known quantum attacks above roughly 2^100 qubit operations, which is the security threshold they target. The choice of many small primes is not free, because it opens a specific attack surface: a quantum computer can try to find those small primes directly with the elliptic-curve method rather than running full Shor factorization, which is precisely why the paper has to introduce a new quantum algorithm to analyze that route. So the parameter selection is a tug-of-war between using small primes for classical feasibility and using primes large enough that a quantum small-prime search stays too expensive.
Source: Bernstein, Heninger, Lou, Valenta, “Post-quantum RSA,” PQCrypto 2017, §4 (1-terabyte key generation), cr.yp.to/papers/pqrsa-20170419.pdf.
What is GEECM, and why does it constrain the design?
GEECM is a new quantum factorization algorithm the authors introduce, and it is one of the main forces shaping how pqRSA’s parameters must be chosen. Ordinary quantum analysis of RSA assumes the attacker runs Shor’s algorithm on the full modulus, but pqRSA’s many-small-primes structure invites a different attack: instead of factoring the whole terabyte number at once, an attacker can hunt for its small prime factors one route at a time. GEECM (a Grover-accelerated variant of the elliptic-curve method of factorization) is the paper’s tool for that route, and it is often much faster than both Shor’s algorithm and pre-quantum factorization methods for finding small primes.
The consequence is that GEECM, not Shor’s, becomes the binding constraint on parameter selection. The primes cannot be too small, or GEECM finds them and the whole modulus unravels, so the design has to balance small-enough primes for classical speed against large-enough primes to keep GEECM above the target work threshold. This is the detail that makes pqRSA a serious analysis rather than a naive “just use a bigger key” sketch. The authors did the adversarial work of finding the strongest quantum attack against their own structure and sizing around it, which is what an honest cryptographic proposal looks like even when the conclusion is that the scheme is impractical.
Source: Bernstein, Heninger, Lou, Valenta, “Post-quantum RSA,” PQCrypto 2017, §2 (GEECM quantum factorization), cr.yp.to/papers/pqrsa-20170419.pdf.
Why is pqRSA impractical despite being secure?
Because the classical costs are extreme, and every legitimate user pays them on every single operation while the attacker pays only once. The paper is candid about this in its own evaluation. A public key is about 1 terabyte, so distributing and storing keys becomes a serious burden on its own. Worse, the cost of each new encryption or decryption is on the scale of a dollar of computer time, which the authors state is many orders of magnitude more expensive than ordinary pre-quantum RSA. A cryptographic operation that costs a dollar and a data structure that costs a terabyte are simply out of range for the billions of TLS handshakes, signatures, and key exchanges the internet runs every day.
The gap between pqRSA and a real post-quantum scheme is easiest to see side by side:
| Approach | Public key size | Cost per operation | Attacker vs honest-user gap | Deployable? |
|---|---|---|---|---|
| Ordinary RSA (3072-bit) | ~384 bytes | Milliseconds | Broken by Shor’s at any size | No, once a CRQC exists |
| Post-quantum RSA (pqRSA) | ~1 terabyte | ~$1 of compute | Quadratic in usage cost | No, cost is prohibitive |
| ML-KEM (lattice) | ~1-2 kilobytes | Microseconds | Exponential, no known quantum attack | Yes, a finalized standard |
The security argument that makes pqRSA work at all also caps how good it can be. The paper’s version of RSA achieves an attack cost that is essentially quadratic in the usage cost, meaning the attacker’s work grows as the square of the honest user’s work. That is a real advantage over pre-quantum RSA, but a quadratic gap is a weak lever compared with the exponential gap that lattice, code-based, and hash-based post-quantum schemes offer between honest use and attack. The authors themselves note that code-based and lattice cryptography appear to provide secure encryption at far less expense, and they frame pqRSA’s appeal as resting on the faint possibility of dramatic future improvements in attacks against all the other families. So pqRSA is secure and buildable and still not something to deploy, which is the whole point of the exercise.
Source: Bernstein, Heninger, Lou, Valenta, “Post-quantum RSA,” PQCrypto 2017, “Evaluation and comparison,” cr.yp.to/papers/pqrsa-20170419.pdf.
What does pqRSA teach about “just make the key bigger”?
It teaches that scaling the key is a losing strategy against a quantum computer, because the honest user’s costs explode long before the security margin becomes comfortable. The intuition many people carry from classical cryptography is that when an attack gets stronger, you respond by lengthening the key, the way RSA moved from 1024-bit to 2048-bit to 3072-bit moduli over the years. pqRSA follows that instinct to its logical extreme and shows where it breaks. To keep Shor’s algorithm and GEECM out of reach, the key has to grow to a terabyte and each operation to a dollar, which is a size and cost the internet cannot absorb. The lever exists, and it is far too expensive to pull.
The contrast with the standardized post-quantum algorithms is the lesson. ML-KEM, ML-DSA, and the rest do not defend by scaling a broken assumption. They rest on entirely different hard problems (lattices, codes, hashes) that have no known efficient quantum attack at all, so they buy an exponential gap between honest use and attack while keeping keys and operations at practical sizes. That is why the transition is a move to new math families rather than a move to bigger RSA, and pqRSA is the clean demonstration of why: the number-theoretic assumptions Shor’s algorithm breaks stay broken no matter how large you make them, so the answer had to come from somewhere else.
Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016 (public-key algorithms fall to Shor’s; the response is new families, not larger keys), csrc.nist.gov/pubs/ir/8105/final.
Common misconceptions
- “You can make RSA quantum-safe by using a bigger key.” pqRSA shows the price of trying. To hold off Shor’s and GEECM, the key grows to about 1 terabyte and each operation to roughly a dollar of compute, which is far outside what real systems can use.
- “Post-quantum RSA is a joke paper.” It is a serious analysis that produces a genuinely secure construction and introduces a new quantum factorization algorithm to attack its own design. Its value is precisely in showing where the scaling approach hits a wall.
- “pqRSA is one of the NIST post-quantum options.” It is not. The NIST standards are ML-KEM, ML-DSA, SLH-DSA, and others built on different math families. pqRSA is a research curiosity, not a standardized algorithm.
- “If Shor’s algorithm has overhead, ordinary RSA just needs a moderate size bump.” Shor’s factors an RSA modulus about as fast as the owner can decrypt it, so the overhead is tiny. Closing the gap requires the extreme sizes pqRSA describes, which is why moderate increases do nothing.
- “pqRSA proves RSA survives the quantum era.” It proves a terabyte-scale, dollar-per-operation RSA can survive in theory, which is the opposite of survival in practice. Deployable RSA at internet sizes is broken by a quantum computer, and the practical answer is the new standards.
Questions people ask
What is post-quantum RSA? Post-quantum RSA (pqRSA) is a 2017 proposal by Bernstein, Heninger, Lou, and Valenta to resist a quantum computer by scaling RSA to a roughly 1-terabyte modulus built from billions of small primes, keeping encryption and decryption barely feasible while pushing all known quantum attacks above a huge work threshold.
Can you just use a bigger RSA key to beat quantum computers? In theory, at absurd cost. pqRSA is the worked example: the key has to reach about a terabyte and each operation about a dollar of compute to hold off Shor’s and the paper’s GEECM attack, which is far too expensive for real systems, so scaling is not the practical answer.
Is post-quantum RSA a NIST standard? No. It is a research proposal, not a standardized algorithm. The NIST post-quantum standards (ML-KEM, ML-DSA, SLH-DSA, and others) rest on different math families and stay at practical sizes.
Why is pqRSA impractical? The public key is about 1 terabyte and each encryption or decryption costs on the scale of a dollar of computer time, many orders of magnitude more than ordinary RSA. Its attack cost is only quadratic in usage cost, a far weaker margin than the exponential gap the new post-quantum families provide.
What is GEECM? GEECM is a quantum factorization algorithm the pqRSA paper introduces, a Grover-accelerated elliptic-curve factoring method that finds small primes faster than Shor’s algorithm. Because pqRSA’s modulus is built from small primes, GEECM is the binding constraint that sizes how large those primes must be.
What is the real lesson of post-quantum RSA? That defeating a quantum attack by scaling a broken assumption is a dead end, because the honest user’s costs explode before security becomes comfortable. The number-theoretic problems Shor’s breaks stay broken at any size, which is why the transition moved to new math families rather than bigger keys.
Everything here is the map, given freely. When your team needs the genuine post-quantum options sized and sequenced into your own architecture, rather than a scaling trick that cannot ship, that’s what an alignment briefing is for.
Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.