RSA Encryption Explained: A Simple Step-by-Step Example
Quick answer: RSA is a public-key encryption system: a public key encrypts and a matching private key decrypts. Both keys come from a number n = p × q, where p and q are large secret primes. A message, encoded as a number m, is encrypted as c = m^e mod n and decrypted as m = c^d mod n. Finding d requires the primes, so security rests on how hard it is to factor n. Real RSA also needs randomized padding such as OAEP.
Facts checked November 22, 2026.
Every time you see the padlock in your browser, buy something online or sign in to your bank, number theory is working for you. For decades, much of that protection has relied on RSA, an encryption method built on one simple fact: multiplying two primes is easy, but splitting the product back into those primes is extremely hard. This guide explains the math step by step, works a complete example you can check by hand, and covers why RSA is now being replaced.
What Is RSA Encryption?
RSA is a public-key encryption method published in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman at MIT; the name comes from their initials. “Public key” means there are two keys:
- A public key that anyone can see and use to encrypt a message to you.
- A private key that only you have, used to decrypt it.
Think of a padlock you hand out freely: anyone can snap it shut, but only you have the key that opens it. RSA is also used for digital signatures, which prove a message really came from you. In practice, RSA usually protects a short secret key, and a faster method such as AES encrypts the actual data.
The One Math Idea Behind RSA
Multiply two primes: \(61 \times 53 = 3{,}233\). That takes seconds. Now go backward: which two primes multiply to 3,233? You have to search. For small numbers that is quick, but real RSA keys use a number \(n\) about 617 digits long (2,048 bits). No known method on ordinary computers can factor a properly generated RSA modulus of that size in any practical amount of time. This one-way difficulty is called a trapdoor: easy in one direction, hard in the other, unless you know the secret (the primes).
New to primes? See prime numbers and factoring numbers.
Modular Arithmetic in 60 Seconds
RSA uses modular arithmetic, or “clock math.” On a 12-hour clock, 5 hours after 9 o’clock is 2 o’clock, because \(9 + 5 = 14\) and 14 leaves remainder 2 when divided by 12. We write \(14 \equiv 2 \pmod{12}\), and “\(a \bmod n\)” means the remainder when \(a\) is divided by \(n\). For example, \(64 \bmod 33 = 31\), because \(64 = 1 \times 33 + 31\).
How RSA Works, Step by Step
| Step | What you do | Public or secret? |
|---|---|---|
| 1. Choose two primes | \(p\) and \(q\) | Secret |
| 2. Multiply | \(n = p \times q\) | Public |
| 3. Compute the totient | \(\varphi(n) = (p-1)(q-1)\) | Secret |
| 4. Choose the public exponent | \(e\), sharing no factor with \(\varphi(n)\) | Public |
| 5. Find the private exponent | \(d\) with \(e \times d \equiv 1 \pmod{\varphi(n)}\) | Secret |
| 6. Encrypt message \(m\) | \(c = m^e \bmod n\) | Anyone can do it |
| 7. Decrypt | \(m = c^d \bmod n\) | Only the key owner |
The public key is the pair \((n, e)\). The private key is \(d\). To find \(d\) you need \(\varphi(n)\), and to find \(\varphi(n)\) you need \(p\) and \(q\). That is why breaking RSA comes down to factoring \(n\).
A Worked RSA Example With Small Numbers
Real keys use huge primes, but the math is the same with tiny ones. Let’s encrypt the message \(m = 4\).
- Primes: \(p = 3\), \(q = 11\).
- Modulus: \(n = 3 \times 11 = 33\).
- Totient: \(\varphi(n) = (3-1)(11-1) = 2 \times 10 = 20\).
- Public exponent: \(e = 3\), since 3 and 20 share no common factor.
- Private exponent: we need \(3d \equiv 1 \pmod{20}\). Try \(d = 7\): \(3 \times 7 = 21 = 20 + 1\). So \(d = 7\).
- Encrypt: \(c = 4^3 \bmod 33 = 64 \bmod 33 = 31\). The ciphertext is 31.
- Decrypt: \(m = 31^7 \bmod 33\). A shortcut: \(31 \equiv -2 \pmod{33}\), so \(31^7 \equiv (-2)^7 = -128 \equiv -128 + 132 = 4 \pmod{33}\). We get back \(m = 4\).
Public key: \((n, e) = (33, 3)\). Private key: \((n, d) = (33, 7)\), because \(3 \times 7 = 21 = 1 + 20\). An attacker who sees \(n = 33\) can factor it instantly, which is exactly why real RSA uses primes hundreds of digits long. Want to check any step? Compute the powers and remainders on a calculator, or with Python’s pow(4, 3, 33) and pow(31, 7, 33).
Why Decryption Gives Back the Message
The key fact is Euler’s theorem: if \(m\) and \(n\) share no common factor, then \(m^{\varphi(n)} \equiv 1 \pmod{n}\). Because \(e d = 1 + k\,\varphi(n)\) for some whole number \(k\),
\[ c^d = (m^e)^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot \left(m^{\varphi(n)}\right)^k \equiv m \cdot 1^k = m \pmod{n}. \]In our example, \(ed = 21 = 1 + 1 \times 20\). (The result also holds when \(m\) shares a factor with \(n\), by a slightly longer argument using the Chinese remainder theorem.)
Real RSA vs the Classroom Version
| Feature | Our example | Real-world RSA |
|---|---|---|
| Primes | 3 and 11 | Each about 309 digits (1,024 bits) |
| Modulus \(n\) | 33 | 2,048 bits (about 617 digits) or more |
| Public exponent \(e\) | 3 | Usually 65,537 |
| Message handling | Raw number | Randomized padding (OAEP for encryption, PSS for signatures) so the same message never encrypts the same way twice |
“Textbook” RSA without padding is insecure even with huge keys, so never build your own crypto for real use; use a well-tested library.
How Hard Is It to Break RSA?
The best classical attack is the general number field sieve (GNFS). Public RSA Factoring Challenge records show how far attackers can get, and 2026 brought two new records in 16 days, both built with AI coding assistants:
| Number | Size | Factored | How |
|---|---|---|---|
| RSA-250 | 250 digits (829 bits) | February 2020 | Academic team (Boudot, Gaudry, Guillevic, Heninger, Thomé, Zimmermann); about 2,700 CPU core-years |
| RSA-260 | 260 digits (862 bits) | September 3, 2026 (announced September 9) | Eric Lu at Cognition, with GPU code written and run by the AI agent Devin; about 4,900 GPU-days over about 15.6 days |
| RSA-896 | 270 digits (896 bits) | September 19, 2026 | Stephen Weis at Anthropic, using Claude to port the CADO-NFS software to GPUs; about 30 GPU-years over 10 days on up to 2,048 GPUs |
| RSA-2048 | 617 digits | No public factorization known | Far beyond any classical computer |
Neither team made the GNFS algorithm itself faster; AI helped engineer fast GPU software. Weis wrote that his result does not affect RSA-2048 keys but shows that 1,024-bit RSA keys are within reach of anyone with a data-center fleet of GPUs. That is why 2,048 bits is today’s minimum. (CPU core-years and GPU-years measure different hardware, so the rows are not directly comparable.)
The Quantum Threat to RSA
A large, error-corrected quantum computer running Shor’s algorithm could factor \(n\) efficiently and break RSA. No such machine exists yet, but estimates of the machine size needed have dropped fast:
| Estimate | Physical qubits for RSA-2048 | Time |
|---|---|---|
| Gidney and Ekerå, 2019 | About 20 million | About 8 hours |
| Gidney (Google), May 2025 | Under 1 million | Under a week |
| Pinnacle architecture (Iceberg Quantum), Feb 2026, revised May 2026 | About 94,000, using quantum LDPC codes | One month or less |
| Alice & Bob and partners, Oct 2026 (preprint) | 22,593 cat qubits, assuming no bit flips | 3.14 days |
These are theoretical resource estimates, not demonstrations. Each assumes hardware that has not been built at scale, such as physical error rates of about 0.1% and error-correction cycles of 1 microsecond. Today’s experiments are far from that. The worry is “harvest now, decrypt later”: data stolen today could be decrypted once such machines exist. For the quantum basics, see the math of quantum computing.
What Replaces RSA: Post-Quantum Cryptography
On August 13, 2024, the US National Institute of Standards and Technology (NIST) published its first three post-quantum standards: FIPS 203 (ML-KEM) for key exchange, and FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) for signatures. ML-KEM and ML-DSA rely on hard problems about lattices, which no known quantum algorithm solves quickly. NIST’s final transition report, NIST IR 8547 (October 27, 2026), deprecates quantum-vulnerable public-key algorithms, including RSA, after 2030 and disallows them under NIST standards after 2035. Chrome and other major browsers already use a hybrid key exchange that combines classical X25519 with ML-KEM.
Common Misconceptions
“RSA has already been broken by quantum computers.” No. Quantum factoring demonstrations have used tiny numbers such as 15 and 21, often with simplified circuits that rely on knowing the answer’s structure.
“The 2026 records mean RSA-2048 is unsafe now.” No. Each extra digit makes factoring much harder; RSA-896 has 270 digits, far fewer than a 617-digit key.
“The public key reveals the private key.” Only if you can factor \(n\). That is the whole security idea.
Watch: RSA Encryption Explained
If you learn better by watching, these videos are worth your time.
Check Your Understanding
Five quick questions to see how much of this has stuck. Pick an answer and press Submit; you will see a short explanation either way.
Answer each question and press Submit to see your result right away.
Frequently Asked Questions
How does RSA encryption work in simple terms?
You multiply two large secret primes to make a public number n. Anyone can encrypt with the public key (n, e) using c = m^e mod n, but decrypting needs the private exponent d, which can only be computed if you know the primes. Factoring n to find them is extremely hard.
What is a simple RSA example?
With p = 3 and q = 11: n = 33, φ(n) = 20, e = 3 and d = 7. The message 4 encrypts to 4^3 mod 33 = 31, and 31^7 mod 33 = 4 decrypts it.
Why is RSA secure?
Its security rests on the difficulty of factoring a very large number that is the product of two primes. For 2,048-bit keys, no known classical method can do it in a practical time.
What is the largest RSA number ever factored?
RSA-896, a 270-digit (896-bit) number, factored on September 19, 2026 by Stephen Weis at Anthropic using Claude to port CADO-NFS to GPUs. Sixteen days earlier, Cognition had factored RSA-260 with its AI agent Devin; the previous record was RSA-250 in February 2020.
Can quantum computers break RSA?
A large error-corrected quantum computer running Shor’s algorithm could. None exists yet, but estimates of the size needed fell from about 20 million qubits (2019) to under 100,000 in 2026 designs, which is why NIST will deprecate RSA after 2030 and disallow it after 2035.
What will replace RSA?
Post-quantum algorithms such as ML-KEM (FIPS 203) for key exchange and ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) for signatures, published by NIST in August 2024.
Keep Exploring
- Shor’s Algorithm Explained: Example, RSA and Qubits
- The Math Behind Quantum Computing: A Beginner’s Guide
- Linear Algebra for AI: Vectors, Matrices and Examples
Sources and Further Reading
- Rivest, Shamir and Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (CACM, 1978)
- Cognition: Factoring RSA-260 (Sept 9, 2026)
- Stephen A. Weis: RSA-896 (Sept 2026)
- Zimmermann: RSA-250 factorization announcement (Feb 2020)
- Gidney, How to factor 2048 bit RSA integers with less than a million noisy qubits (arXiv 2505.15917)
- Webster et al., The Pinnacle Architecture (arXiv 2602.11457)
- The Quantum Insider: Alice & Bob estimates 22,593 qubits to break RSA-2048 (Oct 29, 2026)
- NIST IR 8547: Transition to Post-Quantum Cryptography Standards (final, Oct 27, 2026)
- NIST: First 3 finalized post-quantum encryption standards (Aug 13, 2024)
Related to This Article
More math articles
- How to Master the Concept of Continuity over an Interval
- CHSPE Math Formulas
- What Does the STAAR Test Stand For?
- Understanding an Author’s Implicit Purpose
- Six Hacks for ACT Math: Top Clues, Tricks, and Tactics
- Opioid Conversion Calculator
- Reciprocal Identities
- The Sociological Imagination and the Origins of Sociology
- The Best Grade 3 ELA Practice Tests for New Hampshire Students
- Conformity, Obedience, and Situational Influence


What people say about "RSA Encryption Explained: A Simple Step-by-Step Example - Effortless Math"?
No one replied yet.