Why RSA and ECC are on the clock

If you completed Lesson 0.1, you know that Shor's algorithm breaks RSA and elliptic curve cryptography. But before that statement can feel real and urgent, you need to understand what those two things actually are, and why they appear on virtually every piece of digital infrastructure in existence.

RSA is a public-key cryptographic algorithm invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman, the initials give it its name. It is built on a simple mathematical observation: multiplying two very large prime numbers together is fast and easy, but working backwards, given the result, finding the two original prime numbers, is extraordinarily difficult. A 2048-bit RSA key involves prime numbers so large that factoring their product would take classical computers longer than the age of the universe. RSA is used to protect private keys, sign certificates, encrypt email, and authenticate servers.

ECC stands for Elliptic Curve Cryptography. It is a more modern approach that uses the mathematics of points on an elliptic curve. Like RSA, it depends on a one-way function, multiplying a point on a curve by a number is fast and easy, but reversing the process (finding the original number given the result) is computationally infeasible on classical hardware. ECC produces smaller, faster keys than RSA for equivalent security, which is why it became the default for TLS connections, mobile devices, and anything performance-sensitive. The specific curves you will encounter most often are secp256k1 (used by Bitcoin and Ethereum), P-256 and P-384 (used by most TLS certificates), and Ed25519 (used by Solana and modern SSH).

In Lesson 0.1 you learned that Shor's algorithm can factor large numbers efficiently on a quantum computer. Now let's be precise about what that means for RSA and ECC.

RSA's security depends entirely on the difficulty of factoring a large number, the public key, back into its two prime components. If you can factor it, you get the private key. On a classical computer, the best-known factoring algorithms for a 2048-bit RSA key would take roughly 300 trillion years. On a quantum computer running Shor's algorithm with sufficient qubits and error correction, the same factoring problem can be solved in a matter of hours or days. The one-way function that RSA depends on is no longer one-way.

ECC faces a slightly different but equally fatal problem. Its security depends on a related mathematical challenge called the discrete logarithm problem, given a point on a curve produced by multiplying a secret number with a base point, find the original secret number. Shor's algorithm, with a small modification, solves this problem efficiently too. The entire mathematical basis of ECC evaporates under quantum computation just as RSA's does.

It is important to note that we do not currently have a quantum computer capable of running Shor's algorithm at the scale needed to break real 2048-bit RSA keys. Estimates from NIST, the NSA, and independent researchers suggest that a cryptographically relevant quantum computer, one powerful enough to pose a genuine threat to current encryption, will require millions of physical qubits with low error rates. Current machines have hundreds to a few thousand noisy qubits. The gap is real. But it is closing, and closing faster than most people expected five years ago.

One of the most common misunderstandings about the quantum threat is the assumption that quantum computers break all cryptography. They do not. Different algorithms have different vulnerability profiles, and understanding this spectrum is essential for any migration planning.

The key takeaway from this table is that the quantum migration problem is primarily an asymmetric cryptography problem. Symmetric encryption like AES-256 and hash functions like SHA-384 are manageable with modest adjustments. The urgent and expensive work is replacing RSA, ECC, and Diffie-Hellman everywhere they appear, which is everywhere.

The most common objection to PQC urgency is: "quantum computers cannot break encryption today, so we have time." This objection misunderstands the threat model entirely. The threat is not only about what a quantum computer can do when it arrives. The threat is already active.

Harvest Now, Decrypt Later (HNDL) is a data collection strategy where an adversary, typically a well-resourced nation-state intelligence service, captures and stores encrypted network traffic today with the intention of decrypting it later, once a sufficiently powerful quantum computer exists. The adversary does not need to break the encryption now. They just need to save the ciphertext and wait.

Think carefully about what this means for your specific situation. Medical records that need to remain private for a patient's lifetime. Defense contracts that contain classified design specifications. Legal communications protected by privilege. Financial records subject to multi-decade regulatory retention. Intellectual property that gives a company its competitive advantage. Research data that will not be published for years. All of this is being encrypted with RSA or ECC today. All of it is potentially being harvested today. All of it will be readable when the quantum computer arrives.

NIST's guidance document SP 800-131A Revision 3, one of the Tier 1 must-reads on your course reading list, establishes the official transition timeline for cryptographic algorithms. Here is what it means in practice.