How Does RSA Encryption Work? A Beginner's Guide

RSA was the first practical public-key cryptosystem and still secures a vast share of the internet — yet it is the algorithm most threatened by quantum computers. Understanding RSA is essential to understanding the post-quantum transition.

The Core Idea: Asymmetric Keys

RSA uses a key pair: a public key anyone can use to encrypt to you, and a private key only you hold to decrypt. This solves the key-distribution problem that symmetric encryption cannot.

The Math: Factoring

RSA's security rests on a single fact: it is easy to multiply two large prime numbers, but hard to factor their product back into the primes.

• Pick two large primes p and q.
• Compute n = p × q.
• The public key includes n; the private key depends on knowing p and q.
• Anyone can encrypt using n; only someone who can factor n can decrypt.

For classical computers, factoring a 2048-bit number is infeasible. For a large quantum computer, it is not.

Key Sizes and Security

• RSA-1024: broken — do not use.
• RSA-2048: currently secure against classical attacks, the common minimum.
• RSA-3072/4096: higher margin, used where long-term security matters.

Larger keys buy time against classical attacks but do not help against quantum computers — Shor's algorithm factors any RSA key efficiently regardless of size.

Where RSA Is Used

• TLS certificates and handshakes (being phased out for ECDH/ECDSA and now post-quantum).
• Code signing.
• Email encryption (PGP/S-MIME).
• SSH keys (legacy).
• JWT signing and API authentication.

The Quantum Threat

In 1994, Peter Shor showed that a quantum computer can factor integers in polynomial time. A cryptographically relevant quantum computer would break RSA-2048 in hours. This is the single biggest driver of the post-quantum migration.

Harvest Now, Decrypt Later

Even if no quantum computer exists today, adversaries record encrypted RSA handshakes. When a quantum computer arrives, those recorded sessions can be decrypted retroactively. Any data that must stay confidential beyond the expected arrival of a quantum computer is already at risk if protected only by RSA.

Migrating Away From RSA

The transition involves:

1. Replacing RSA key exchange with ECDH (classical) and then hybrid ECDH + ML-KEM (post-quantum).
2. Replacing RSA signatures with ECDSA, then ML-DSA (post-quantum).
3. Keeping RSA only for legacy compatibility, with short-lived keys.

What RSA Still Teaches Us

RSA's elegance — security from a simple mathematical asymmetry — defined modern cryptography. Its coming obsolescence is not a failure; it is the natural evolution of a field that must always stay ahead of computing power. The lesson is to build systems that are crypto-agile enough to move on when the time comes.

Bottom Line

RSA remains everywhere, but its days are numbered by quantum computing. If you rely on RSA for anything that must stay confidential for more than a few years, you should already be planning its replacement.