up:: Classical Cryptography MOC

RSA

RSA is a public-key cryptosystem, named for its inventors Rivest, Shamir, and Adleman, whose security rests on the difficulty of factoring a very large number back into the two primes that were multiplied to create it. For nearly 50 years it has done two of the internet’s core jobs: carrying keys securely between parties (key transport) and proving who signed something (digital signatures). It sits inside TLS, PKI and X.509 certificates, code signing, secure email, smart cards, and firmware trust. In the post-quantum era RSA is the textbook casualty: a large enough quantum computer running Shor’s algorithm factors the key and breaks RSA completely, at every key size, which is why NIST has slated it for replacement rather than resizing.

The short version:

• RSA rests on one hard problem: factoring. Multiplying two big primes is easy; pulling the product back apart is what protects the private key. That single assumption is also its single point of failure.
• RSA does two jobs. Key transport and key wrapping (a confidentiality role) and digital signatures and certificates (a trust role). A quantum computer breaks both.
• Shor’s algorithm is the threat, not Grover’s. Shor factors the modulus in polynomial time on a cryptographically relevant quantum computer, which recovers the private key. This is a total break, not a weakening.
• Bigger keys do not save it. Moving from RSA-2048 to RSA-4096 buys a little runway against the machine but not safety, because Shor’s cost grows only polynomially with key size. That’s why the answer is to replace RSA, not enlarge it.
• The replacements are already standardized. ML-KEM takes over key establishment; ML-DSA and SLH-DSA take over signatures, all finalized by NIST in August 2024.

Picture a padlock that anyone can snap shut but only the owner can open. RSA’s public key is the open padlock, handed out freely, and the private key is the only thing that opens it. The security comes from a one-way street in arithmetic: multiplying two large prime numbers together is quick, but taking the result and working backward to find those two primes is so slow that a classical computer would need longer than the age of the universe at the right key size. A quantum computer running Shor’s algorithm knows a shortcut down that one-way street, and once it can walk backward from the product to the primes, the padlock opens for anyone.

What is RSA?

RSA is an asymmetric (public-key) cryptosystem published in 1978 by Ron Rivest, Adi Shamir, and Leonard Adleman, built on a key pair whose two halves are mathematically linked but computationally hard to derive from each other. The public key is a modulus n (the product of two secret primes p and q) together with a public exponent e. The private key is a private exponent d derived from the primes. Anyone can use the public key to encrypt to you or to verify your signature; only the holder of the private key can decrypt or sign. Its security basis is integer factorization: if an attacker could factor n back into p and q, they could reconstruct the private key and everything RSA protected would fall.

Source: R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communications of the ACM, 1978, ACM.

RSA belongs to the quantum-vulnerable family of public-key algorithms, alongside Diffie-Hellman, ECDH, and ECDSA. It is the oldest and most deeply embedded of them, which is exactly what makes it both easy to find in certificate-heavy systems and painful to root out of the older corners where it hides.

How does RSA work?

RSA runs on modular arithmetic with a public and a private exponent. The mechanism has three moving pieces, and the security lives in the gap between how easy the setup is and how hard reversing it is without the private key.

1. Key generation. Pick two large random primes p and q and multiply them to get the modulus n = p × q. Choose a public exponent e (commonly 65537). Compute the private exponent d as the modular inverse of e, so that e × d ≡ 1 (mod φ(n)), where φ(n) = (p − 1)(q − 1). The public key is (n, e); the private key is d. The primes p and q are then discarded or protected, because anyone who recovers them recovers d.
2. Encryption or verification (public key). To encrypt a value m, compute c = m^e mod n. To verify a signature, apply the public exponent to the signed value and check that it matches.
3. Decryption or signing (private key). To decrypt, compute m = c^d mod n. To sign, apply the private exponent d to a structured representation of the message.

The whole scheme stands on one asymmetry. Computing n from p and q is a single multiplication. Recovering p and q from n is factoring, and no efficient classical algorithm for it is known at the sizes RSA uses. Break that asymmetry and you break RSA.

One caution matters in practice: “textbook” RSA, the bare m^e mod n, is not safe to deploy. Real systems wrap it in a padding or encoding scheme, RSAES-OAEP for encryption and RSASSA-PSS for signatures in modern designs, with the older PKCS #1 v1.5 modes still lingering in legacy systems. The padding closes attacks that have nothing to do with factoring, and getting it wrong has caused real-world breaks independent of the quantum question.

Source: NIST, “Digital Signature Standard (DSS),” FIPS 186-5, 2023, NIST; NIST SP 800-56B Rev. 2, “Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography,” 2019, NIST.

What is RSA used for?

RSA does two of cryptography’s core jobs, and the distinction between them decides how urgent its failure is:

1. Key transport and key wrapping (a confidentiality role). RSA can carry or wrap a symmetric key so two parties end up sharing a secret. Older TLS used RSA key transport directly; many systems still use RSA to wrap the AES keys that actually protect bulk data.
2. Digital signatures and certificates (a trust role). RSA signs software releases, firmware, documents, and above all the X.509 certificates that anchor web and enterprise trust. When your browser trusts a site, an RSA (or elliptic-curve) signature chain is often what it is checking.

Where it actually lives in an enterprise:

• PKI and X.509 certificate chains, from public roots down to machine and user certificates
• TLS server authentication and legacy key transport
• code signing and software-release signing
• firmware signing and device trust anchors
• secure email (S/MIME and older OpenPGP)
• smart cards, hardware tokens, and HSM-backed signing services

Because RSA sits inside certificates and signing infrastructure, it is often invisible at the application layer. A team can believe they run “modern crypto” while RSA still anchors an intermediate certificate, a firmware signer, or a vendor appliance. That hidden footprint is what makes RSA both consequential and easy to under-count in a cryptographic inventory.

Is RSA quantum-vulnerable?

Yes, completely, and the threat is Shor’s algorithm, not Grover’s. This distinction is worth getting exactly right, because the two quantum algorithms do very different things to different kinds of cryptography.

Shor’s algorithm, published by Peter Shor in 1994 and detailed in 1997, solves integer factorization and the discrete logarithm in polynomial time on a fault-tolerant quantum computer. RSA’s entire security rests on factoring being hard, so a large enough quantum machine factors the modulus n, recovers the primes, reconstructs the private key d, and can then decrypt anything RSA protected and forge any RSA signature. This is a structural break of the core assumption, not a gradual erosion of margin.

Source: P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing, 1997, SIAM.

Grover’s algorithm, the other famous quantum attack, only speeds up brute-force search quadratically. That matters for symmetric ciphers like AES, where it roughly halves effective strength, but it does nothing to rescue RSA, whose weakness is the factoring shortcut Shor provides, not a searchable keyspace. Blurring Shor and Grover is one of the most common mistakes in this topic, so the clean rule is: Shor breaks public-key algorithms including RSA, Grover only dents symmetric ones.

The catch that makes this urgent today rather than in some distant future is harvest now, decrypt later. An adversary can record RSA-protected traffic and archives today and simply wait for a cryptographically relevant quantum computer. Anything that must stay confidential past the machine’s arrival is already exposed the moment it crosses the wire.

Why doesn’t a bigger RSA key like RSA-4096 fix the quantum problem?

Because Shor’s algorithm scales gently with key size, so enlarging the key raises the classical attacker’s cost enormously while raising the quantum attacker’s cost only modestly. Against classical factoring, RSA’s security grows fast enough that doubling the modulus buys a real jump in strength, which is the whole logic behind moving from RSA-2048 to RSA-3072 over the years. Against a quantum computer running Shor’s, the resource requirement grows only polynomially with the number of bits, so a bigger key adds qubits and runtime to the eventual attack but does not put it out of reach.

The published resource estimates make the shape of this concrete. Gidney and Ekerå estimated in 2021 that factoring a 2048-bit RSA key would take on the order of 20 million noisy qubits running for about 8 hours, and a 2025 estimate brought the figure to under a million qubits. A larger key pushes those numbers up, but along a curve that better hardware keeps eroding, not a wall that resizing can build.

Source: C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum 5, 433, 2021, Quantum; C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits,” 2025, arXiv.

So resizing costs you the worst of both worlds: larger keys and slower operations everywhere in your systems today, in exchange for runway measured against a threat that keeps getting cheaper. That is precisely why NIST’s transition guidance treats RSA as an algorithm to replace on a schedule rather than a parameter to keep tuning upward.

What replaces RSA?

The replacement depends on which of RSA’s two jobs you are replacing, and NIST finalized both replacements on August 13, 2024.

Source: NIST, “NIST Releases First 3 Finalized Post-Quantum Encryption Standards,” August 13, 2024, NIST.

1. For key transport and key establishment, use ML-KEM. ML-KEM is a lattice-based key-encapsulation mechanism, NIST’s primary standard for agreeing on a shared secret in a way that survives a quantum adversary. Where RSA wrapped or transported a key, ML-KEM is the direct successor.
2. For digital signatures and certificates, use ML-DSA, with SLH-DSA as the conservative backup. ML-DSA is the general-purpose post-quantum signature standard. SLH-DSA is a stateless hash-based signature, valued where the most conservative security assumptions matter, such as long-lived firmware and root trust anchors.

During the transition, most enterprises will not cut over instantly. Hybrid key establishment runs a classical algorithm and ML-KEM together so the result holds if either survives, and dual-signature or composite certificate approaches let PKI carry both a classical and a post-quantum signature while the ecosystem catches up. Getting there without re-touching every system later is the case for crypto-agility, designing so the algorithm can change without rebuilding the plumbing around it.

Note the asymmetry with symmetric cryptography: RSA gets fully replaced, but the AES that protects the actual data plane stays, typically at AES-256. The quantum transition is overwhelmingly a public-key migration, and RSA is the largest single piece of it.

What are the RSA key sizes and their security strengths?

RSA key size is the bit length of the modulus n, and NIST maps each size to a “security strength,” the equivalent number of bits of a symmetric key. The table below pairs each size with its classical security strength and its post-quantum verdict. The verdict column is the important one: every RSA size collapses to zero effective strength against Shor’s algorithm, regardless of how strong it looks classically.

RSA key size	Classical security strength	Against Shor’s algorithm	NIST transition status
RSA-2048	112 bits	Broken	Deprecated after 2030, disallowed after 2035
RSA-3072	128 bits	Broken	Disallowed after 2035
RSA-7680	192 bits	Broken	Disallowed after 2035
RSA-15360	256 bits	Broken	Disallowed after 2035

Sources: NIST SP 800-57 Part 1 Rev. 5, “Recommendation for Key Management,” 2020, Table 2, NIST; NIST IR 8547 (initial public draft), “Transition to Post-Quantum Cryptography Standards,” 2024, NIST.

The pattern reads top to bottom as the argument of this whole note. The classical column rewards bigger keys; the Shor column does not care about them at all; and NIST’s schedule deprecates the smallest size first while disallowing every quantum-vulnerable public-key size by 2035, which aligns with the 2035 government-wide migration target set by National Security Memorandum 10.

Source: The White House, National Security Memorandum 10 (NSM-10), 2022, whitehouse.gov.

Has this happened before?

RSA has a hidden origin worth knowing, because it shows how long a cipher’s real story can stay buried. The algorithm the world calls RSA was invented twice. Rivest, Shamir, and Adleman published it at MIT in 1977, but a British cryptographer named Clifford Cocks had already devised the same mathematical idea in 1973 while working at GCHQ, Britain’s signals-intelligence agency, building on James Ellis’s earlier concept of “non-secret encryption.” Because it was classified government work, Cocks’s invention stayed secret until GCHQ declassified the history in December 1997, twenty-four years later, by which point the public RSA had already reshaped the internet.

Source: Simon Singh, The Code Book, 1999, chapter on public-key cryptography (Ellis, Cocks, and Williamson at GCHQ).

The lesson carries straight into the quantum transition. Cryptographic knowledge can exist in secret long before it becomes public, and a capability you assume is years away may already sit in a classified lab. That is the exact logic of harvest now, decrypt later: you do not get to see the adversary’s quantum computer arrive, so the safe assumption is that your RSA-protected secrets need to outrun a machine whose timeline you cannot observe.

Common misconceptions

• “RSA is fine, we just need bigger keys.” Enlarging the key defends against classical factoring, not against Shor’s algorithm, whose cost grows only polynomially with size. NIST is deprecating and disallowing RSA at every size, which is why the guidance is to replace it.
• “Quantum breaks all encryption equally.” It doesn’t. Shor’s algorithm destroys public-key algorithms like RSA outright, while Grover’s only halves the strength of symmetric ciphers like AES, which survive with a larger key. RSA is on the catastrophic side of that line.
• “We moved to modern TLS, so RSA is gone.” Modern TLS often still relies on RSA somewhere in the certificate chain, and RSA hides in intermediate certificates, firmware signers, code-signing systems, and vendor appliances that a surface glance misses.
• “RSA and AES are the same kind of problem.” They aren’t. RSA is public-key and gets fully replaced by post-quantum standards; AES is symmetric and carries forward at a larger key. Conflating them leads teams to migrate the wrong things.
• “RSA signatures are safe even if RSA encryption isn’t.” Both fall to the same break. Once Shor’s algorithm recovers the private key, an attacker can forge signatures just as easily as they can decrypt, so certificates and code signing are exposed too.
• “We have until 2035, so there’s no rush.” For signatures and live trust, 2035 is the outer bound. For anything confidential that must stay secret for years, harvest-now-decrypt-later means the clock started the day the data first crossed an RSA-protected channel.

Questions people ask

Is RSA still safe to use today? Against classical attackers at proper key sizes with correct padding, yes, RSA-2048 and above remain secure right now, and no working quantum computer can factor those keys yet. The concern is forward-looking: any RSA-protected data that must stay confidential into the era of a CRQC is already at risk through harvest-now-decrypt-later, and NIST has set the replacement clock running.

Do I have to replace RSA? Yes, for anything that must remain secure past the quantum transition. NIST IR 8547 sets RSA-2048 to deprecated after 2030 and disallowed after 2035, with the larger sizes disallowed after 2035, so RSA has a defined end of life in NIST-aligned environments rather than an open-ended future.

What’s the difference between RSA and ECC? Both are quantum-vulnerable public-key algorithms, but they rest on different hard problems: RSA on factoring, elliptic-curve algorithms on the elliptic-curve discrete logarithm. ECC gives equivalent classical security with much smaller keys, which is why many systems migrated from RSA to ECC over the last decade. Both fall to Shor’s algorithm, so neither is a post-quantum answer.

What key size should I use if I’m staying on RSA for now? NIST maps RSA-2048 to 112 bits of security and RSA-3072 to 128 bits, and RSA-2048 is deprecated after 2030, so RSA-3072 or larger is the floor for anything meant to last through this decade classically. That said, the durable move is to plan the migration to ML-KEM and ML-DSA rather than to invest further in RSA sizing.

Does a quantum computer break RSA, and how big does it need to be? Yes. Published estimates put factoring an RSA-2048 key at roughly 20 million noisy qubits for about 8 hours in a 2021 analysis, brought down to under a million qubits in a 2025 estimate. No machine at that scale exists yet, but the trend of those estimates is the reason the migration is happening now rather than after the hardware appears.

Is RSA approved by NIST for the post-quantum era? No. RSA is a legacy quantum-vulnerable algorithm on a NIST deprecation and disallowance schedule. The NIST-approved post-quantum replacements are ML-KEM for key establishment and ML-DSA and SLH-DSA for signatures, all finalized in August 2024.

Which is more urgent, RSA encryption or RSA signatures? It depends on your data. RSA in a confidentiality role is urgent for anything with a long secrecy lifetime because of harvest-now-decrypt-later, since the exposure exists today even though the decryption comes later. RSA in a signing or certificate role becomes a forgery risk only once a quantum computer actually exists, so its hard deadline tracks the 2035 disallowance, though high-value signing keys warrant an early move.

Where is RSA hiding that I’m likely to miss? The usual blind spots are intermediate and root certificates, firmware and device trust anchors, code-signing systems, secure email, and vendor-managed appliances and SaaS trust workflows where the algorithm choice is out of your direct control. A cryptographic inventory built from runtime and certificate evidence, not documentation, is what surfaces them.

---

Everything here is the map, given freely. When your team needs its own RSA footprint found, classified, and sequenced for replacement, that’s what an alignment briefing is for.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.