Redux crypto guides · RSA

RSA: a lock anyone can close, but only one person can open

RSA: textbook encryption, two classical attacks, and Shor's algorithm

RSA (named after its three inventors, Rivest, Shamir and Adleman) is a way of sending secret messages that has protected online shopping, banking and email for decades. This guide shows how it works with numbers small enough to check by hand, how an eavesdropper breaks it when the numbers are small, and why quantum computers are a big deal for it. Every example matches what you will see on the RSA page in Redux.

How Redux's RSA problem models textbook RSA on toy keys: the instance formats, the two classical attacks (factoring N, and searching the plaintext), the verifier, how to read the step table, and where Shor's algorithm enters. Every number on this page comes from the default instance (55,3,"Hello World").

Alice's message, on its way to Bob

The default instance, symbol by symbol

Top: the message. Middle: each letter as a number (A = 1, B = 2, ..., space = 27). Bottom: what actually travels, and all an eavesdropper sees.

Each symbol is encoded as m (A = 1 ... Z = 26, space = 27) and encrypted on its own as c = m³ mod 55.

Three people and a padlock

The setting: the attacker's view

Alice wants to send Bob a message. Eve can read everything they send each other. With older ways of keeping secrets, Alice and Bob had to meet first and agree on a secret key. RSA skips that step.

Bob hands out an open padlock to anyone who asks. Anyone can snap it shut on a message, but only Bob has the key that opens it. In RSA the padlock is two numbers anyone can see, and the key is a third number that Bob keeps to himself.

Redux models each cipher from the eavesdropper's side. Eve is passive: she knows the public key (N, e) and the intercepted ciphertext, and wants the plaintext. The instance is what Eve sees, the solvers are her attacks, and the verifier checks a proposed plaintext.

In message mode the instance string also contains the plaintext, so Redux can encrypt it for you. That is a teaching convenience: the problem keeps only the ciphertext, and the table treats everything except N, e and c as secret until an attack recovers it.

Bob puts out an open padlock with the numbers 55 and 3 on it. His key, 27, stays in his pocket.Public key (N, e) = (55, 3); private key d = 27.

Alice turns her message into numbers and locks each one with Bob's padlock.Each symbol m is encrypted independently: c = m^e mod N.

Eve sees the padlock numbers and every locked number. She does not have the key, 27.Eve's knowledge: N, e and c. The attacks recover d (or m directly).

Locking a message

Encryption, symbol by symbol

Computers lock numbers, not letters, so first each letter becomes a number: A = 1, B = 2, and so on up to Z = 26, with 27 for a space.

Then each number is locked with Bob's two padlock numbers, 55 and 3. Multiply the number by itself so it appears 3 times (8 × 8 × 8 = 512), divide by 55, and keep only the remainder, the amount left over (512 ÷ 55 is 9 with 17 left over). That 17 is what Alice sends.

Type your own message below to see each letter locked.

Encoding: A = 1 ... Z = 26, space = 27, so message mode requires N > 27. Each symbol is encrypted separately, c = m^e mod N. Redux also accepts a single number, (N,e,c), for example the Encryption Lesson's (55,3,52), which decrypts to 13.

Instance checks: N ≥ 3, 1 < e < N, 0 ≤ c < N in number mode, and only letters and spaces in a message (lower case is accepted; the answer comes back in upper case).

Your message (letters and spaces)Plaintext (letters and spaces)

This is textbook RSA, not real RSA. Encrypting one symbol at a time makes RSA a substitution cipher on 28 symbols: equal letters give equal ciphertexts (the two L's in HELLO are both 23), and the plaintext space is so small that Eve can skip the key altogether (section 6). Real RSA encodes the whole message as one large number and randomizes it with padding (OAEP) before encrypting. Redux keeps per-symbol encryption because it makes every step visible with numbers you can check by hand.

Bob's secret key, and where it comes from

Key generation and decryption

To unlock, Bob does the same kind of step with his secret number, 27: multiply the locked number by itself so it appears 27 times, divide by 55 and keep the remainder. The 17 Alice sent comes back as 8, which is H. Every letter comes back the same way.

Tip: 27 copies of 17 multiplied together make a 34-digit number, but you never need it. Take the remainder after every multiplication and the numbers stay small.

Bob doesn't pick 27 out of thin air. He builds it from two prime numbers, numbers that only divide evenly by 1 and themselves, like 2, 3, 5, 7 and 11:

N = pq for primes p and q. φ(N) = (p − 1)(q − 1) counts the numbers below N that share no factor with N. The private exponent is d = e⁻¹ mod φ(N), which exists exactly when gcd(e, φ(N)) = 1.

Decryption m = c^d mod N works because ed = 1 + kφ(N), so m^ed = m · (m^φ(N))^k ≡ m (mod N) by Euler's theorem, and by the Chinese remainder theorem also for the m that share a factor with N.

Bob picks two primeschoose primes5 and 11

Multiplies them: the padlock numberN = pq (public)55

Takes 1 off each, multipliesφ = (p − 1)(q − 1)4 × 10 = 40

Finds the number that, times 3, leaves 1 over when divided by 40d = e⁻¹ mod φ3 × 27 = 81 = 2 × 40 + 1

That is the key (Redux calls it d)private exponentd = 27

Why these steps give a working key is a famous piece of math you don't need here. To find the key, Bob just tries 3 × 1, 3 × 2, 3 × 3, ... until one leaves 1 over when divided by 40. The first one is 3 × 27 = 81, which is 2 × 40 with 1 left over.

The whole secret rests on one fact: Bob knows that 55 = 5 × 11. Eve only sees 55. If she can split 55 back into 5 and 11, she can follow the same steps and get 27 too.

Extended Euclid for d = 3⁻¹ mod 40

40 = 13 · 3 + 1
 1 = 40 − 13 · 3
 so  3 · (−13) ≡ 1   (mod 40)
     d = −13 mod 40 = 27
check: 3 · 27 = 81 = 2 · 40 + 1

Redux's table records this step as "Extended Euclid: d = e⁻¹ mod φ, since 3 × 27 = 81 ≡ 1 (mod 40)".

Square-and-multiply: c²⁷ mod 55

Decrypt intercepted symbol

27 = 11011 in binary. Read the bits from the left: square every time, and also multiply by c when the bit is 1. Five squarings instead of 26 multiplications; for real keys this is the difference between milliseconds and never.

How Eve picks the lock

Attack 1: factor N (RSA Factoring Attack)

Eve's plan: split 55 into its two primes. The simplest way is to try dividing 55 by 2, then by 3, then 4, and so on, until one divides evenly. This is called trial division. Try it on other numbers:

The default solver. Trial division finds the smallest factor p, then q = N / p, φ = (p − 1)(q − 1), d = e⁻¹ mod φ by extended Euclid, and finally m = c^d mod N for each symbol.

Trial division costs up to √N divisions, about 2^b/2 for a b-bit modulus: exponential in the size of the input. Better classical algorithms (Pollard's rho, the quadratic sieve, the general number field sieve) are far faster but still super-polynomial. No polynomial-time classical factoring algorithm is known.

Number to splitN

With 5 and 11, Eve rebuilds Bob's key exactly as Bob did and unlocks every letter. Press play to watch her notebook fill in. It is the same table Redux shows, with the same words.

Reading Redux's shorthand. Redux writes its notebook in math shorthand. Here is what it means:

Letters: N is the padlock number (55), e the padlock power (3), c the locked numbers, p and q the two primes, φ ("phi") the 40 Bob made in section 3, d Bob's key (27), and m the message.
mod 55: the remainder after dividing by 55.
m³ or m^3: three m's multiplied together, m × m × m.
≡ 1 (mod 40): leaves 1 over when divided by 40.
e⁻¹ mod φ: the number that, times e, leaves 1 over when divided by φ. That is how Bob found his key in section 3; Extended Euclid is a quick way to find it.
Public key means the padlock numbers, and ciphertext means the locked numbers.

The step table below replays the solver's recorded steps for the default instance, with Redux's own text. Switch to the plaintext search to compare (section 6).


Value	Number	Can Eve see it?Visible to the attacker?	How Eve knows itHow the attacker knows it

Blue: the row Eve just worked out. Green appears when the message is found.Blue is Redux's ElementHighlight (the value found in this step); green is Solution (the answer).

Run it in Redux

Here is the RSA page in Redux, and what each part does.

The RSA page (/RSA in Redux_Frontend). The parts below map onto Redux's problem interface: the instance, the chosen solver, the chosen visualization, and the verifier.

The RSA page in Redux before running: details panel on the left, the instance box, solver menu and Run solve button at the top, and the attacker table below

1Details. The problem in words. It uses some technical terms; this guide explains the same ideas in plain words. Close it with × for more room.problemDefinition, input and output descriptions, source and contributors.
2Instance. The puzzle: Bob's padlock numbers and Alice's message. Press Edit to type your own.(N,e,"TEXT") or (N,e,c). Edit to change it; it is checked as you type.
3Solver. Which attack Eve uses: RSA Factoring Attack, or RSA Brute Force Plaintext Search. The small tags (like NP or Brute Force) and the Reduce button are for other parts of Redux; you can ignore them.The two ISolver classes, tagged Brute Force and Exponential.
4Run solve. Runs the attack.Runs the solver and records its steps for the picture.
5Visualization Type. How the attack is drawn. RSA has one picture: the Attacker Knowledge Table.RSA Attacker Knowledge Table, a DynamicTable with one frame per step.
6The table. What Eve knows. Before running, only the public numbers are filled in.Public rows N, e, c; secret rows p, q, φ, d, m shown as "?".
7Result. The answer, and a box where you can check any answer yourself.Answer (certificate), timing, and the verifier.

Step through the factoring attack

Frames of the factoring attack

After Run solve, use the player under the table: ▶ plays the steps, the arrows move one step, and the slider jumps. Its counter includes the starting picture, so it always reads one more than the table's own step number.The player's count includes the initial frame (visualize), so it runs to 16 while the frame titles from StepsVisualization run to 15.

Checking an answer

The verifier

The Result panel shows the answer and lets you check any answer you type. Redux calls a proposed answer a certificate, and its format line uses the shorthand from section 4. Checking is quick even when finding the answer is hard: Redux locks your answer with the public numbers and compares it with what Eve intercepted.

The Default RSA Verifier re-encrypts the proposed certificate (one modular exponentiation per symbol) and compares it with c. Checking is cheap; finding is the hard direction. That asymmetry is why the problem is declared in NP: RSA = {<N, e, c> | some m with 0 <= m < N has m^e = c (mod N)}.

Result and Verify panel showing the answer HELLO WORLD — The answer after Run solve.

Checking HELLO WORLD: valid certificate — HELLO WORLD: accepted.

Checking HELLO WORLE: not a valid certificate — HELLO WORLE: rejected.

The instance (55,3,"Hi!") outlined in red, with Run solve grayed out

If Redux can't read the instance

The box turns red and Run solve is grayed out. A message may only use letters and spaces, so "Hi!" fails because of the "!". The padlock number must also be bigger than 27, so every letter's number fits under it.

A ProblemParseException (HTTP 400) disables Run. The backend's reason for (55,3,"Hi!") is that '!' cannot be encrypted; for (21,5,"HI"), that a message needs N > 27 so every letter code is below N.

Eve's shortcut: guess each letter

Attack 2: search the plaintext (RSA Brute Force Plaintext Search)

There is a second way in that doesn't need Bob's key at all. The padlock is public, so Eve can lock every possible letter herself and see which one comes out as the number she intercepted.

Pick an intercepted number and watch her tries:

For each ciphertext, try m = 0, 1, 2, ... until m^e mod N = c, and reuse the answer when a ciphertext repeats. The solver never learns p, q, φ or d; they stay "?" in the table.

In general that is up to N encryptions per symbol. In message mode, though, m is at most 27, so it never needs more than 28 tries per distinct symbol whatever the size of N. Determinism plus a tiny message space breaks per-symbol textbook RSA without touching the key.

Intercepted numberCiphertext c

Each box is one try. "4³ → 9" means 4 × 4 × 4 = 64, and 64 divided by 55 leaves 9.

There are only 27 possible symbols (26 letters and a space), and Redux also tries 0 first, so Eve never needs more than 28 tries. And when a number shows up twice, she already knows its letter. That is why this guide calls Redux's RSA a toy version: real RSA locks the whole message as one giant number, so there is nothing small to guess.

Plaintext search, letter 4: ciphertext 23 already appeared as letter 3, so it is L again — Letter 4 is another 23, so it must be L again: no tries needed. (The shorthand is explained in section 4.)Repeated ciphertext reused (no search).

Plaintext search final step: HELLO WORLD recovered while p, q, φ and d are still unknown — The message is found, yet Bob's key is still "?".Answer recovered with p, q, φ, d still unknown.

How big does the padlock number have to be?

Key size and the cost of factoring

55 has 2 digits, so Eve splits it in 4 tries. Real padlock numbers have hundreds of digits. Eve only has to try dividers up to the number that, times itself, makes the padlock number: for 55 that is about 7, since 7 × 7 = 49. Two extra digits make the padlock number 100 times bigger, and that limit 10 times bigger, so every 2 extra digits make trial division about 10 times slower. Slide to see what that means for a computer doing a billion tries every second.

Rough operation counts against the size of N in bits, constants ignored: trial division ~2^b/2; the general number field sieve, the best known classical method, ~exp(1.923 (ln N)^1/3 (ln ln N)^2/3); Shor's algorithm ~b³ quantum gates. The vertical axis is logarithmic: each gridline is 10²⁰ times the one below.

Digits in the padlock number:

Tries needed (about)

At a billion tries a second

Names like RSA-512 and RSA-2048 count binary digits, the 0s and 1s computers write numbers with: 512 binary digits is about 155 ordinary digits.

This counts the slow method from this guide. Researchers use much smarter methods: a 250-digit number (RSA-250) was split in 2020 using about 2,700 computer-years of work (one computer would have needed 2,700 years; many computers shared the job). Numbers with 617 digits, the size used today, are still far out of reach.

RSA-250 (829 bits) was factored with the number field sieve in 2020, about 2,700 core-years. RSA-2048 is a common key size today. Shor's curve assumes a large, error-corrected quantum computer, which does not exist yet.

Why quantum computers matter here

Shor's algorithm: factoring by finding a period

A quantum computer works by the rules of very tiny particles. For most jobs it isn't faster than a normal computer, but for a few special puzzles it is enormously faster. Splitting a big number into its primes is one of them.

In 1994 Peter Shor found the method, now called Shor's algorithm (an algorithm is a step-by-step method). A big enough quantum computer running it could split the padlock numbers used today, and with them RSA. Today's quantum computers are much too small and make too many errors to break real RSA, but people are already switching to new kinds of locks that quantum computers can't pick easily.

Shor's algorithm (1994) factors N in polynomial time, roughly O(b³) gates for a b-bit N. The quantum part finds the period r of a^x mod N with the quantum Fourier transform; if r is even and a^r/2 ≢ −1 (mod N), then gcd(a^r/2 ± 1, N) are proper factors. Resource estimates have been falling: a 2025 estimate put RSA-2048 within reach of under a million noisy physical qubits running for under a week, far beyond today's machines.

Quantum computer guides are in progress. They will cover Shor's and Grover's algorithms step by step.

Things to try in Redux

Exercises

Instances are written (padlock number, padlock power, "message"). Copy an instance, press Edit on the RSA page, paste it, then Run solve. Redux allows about 10 runs a minute; if it says "Too many runs in a row", wait a few seconds.

Lock your own name

(55,3,"YOUR NAME")

Swap in your name (letters and spaces only). Watch the last row (m, the message) fill in one letter at a time.

Letters that don't change

(55,3,"AJKU")

Look at the c row (the locked numbers) before you run anything. What do you notice?

What's going on

The locked numbers are 1, 10, 11, 21: exactly the letters' own numbers. For example 1 × 1 × 1 = 1. A, J, K and U pass through this padlock unchanged, which is one more reason tiny padlocks are weak.

Unlock a single number

(55,3,52)

Instead of a message, Eve intercepts one number, 52. What was the original number? Hint: use Eve's shortcut from section 6.

Answer

13. Check it: 13 × 13 × 13 = 2197, and 2197 ÷ 55 = 39 with 52 left over.

Catch a wrong answer

After running the default, open Result and type HELLO WORLE in the certificate box, then press Check.

What happens

"Not a valid certificate." Redux locked HELLO WORLE, and the last number came out different from what Eve intercepted.

A bigger padlock

(3233,17,"HELLO WORLD")

Same message, padlock 3233 = 53 × 61. How many tries does Eve need now to find the first prime? What is Bob's key?

Answer

52 tries to find 53. The key is 2753; read it from the d row. Check: (53 − 1) × (61 − 1) = 3120, and 17 × 2753 = 46801, which is 15 × 3120 with 1 left over. The locked numbers change completely, but the answer is still HELLO WORLD.

Break the rules

(21,5,"HI")

Why won't Redux run this one?

Answer

21 is smaller than 27. The letter numbers go up to 27, and a padlock number has to be bigger than every number it locks.

1. Fixed points

(55,3,"AJKU")

How many m in [0, 55) satisfy m³ ≡ m (mod 55)? Which letters are they? Predict, then check the c row.

Answer

Nine: by CRT, m ≡ 0, ±1 (mod 5) and m ≡ 0, ±1 (mod 11), giving {0, 1, 10, 11, 21, 34, 44, 45, 54}. In the alphabet range: A = 1, J = 10, K = 11, U = 21. In general an RSA key has (1 + gcd(e − 1, p − 1))(1 + gcd(e − 1, q − 1)) fixed points.

2. An exponent with no inverse

(55,5,"HI")

The instance parses, but what does the factoring attack report, and why? Does the plaintext search still succeed?

Answer

"No solution: e = 5 has no inverse mod φ = 40, so there is no private key." gcd(5, 40) = 5, so m ↦ m⁵ is not a permutation of Z₅₅ and some ciphertexts have several preimages. Try the plaintext search to see whether it still recovers HI.

3. Which attack scales?

(3233,17,"HELLO WORLD")

Run both solvers. Count trial divisions for the factoring attack and tries for the plaintext search. How does each grow as N grows?

Answer

Factoring: 52 trial divisions to find p = 53 (then d = 2753); it grows like √N. Plaintext search: at most 28 tries per distinct symbol for any N, because the message space is fixed. The "weaker" attack wins here, which is the case for padding in real RSA.

4. Decrypt by hand

Use square-and-multiply to compute 48²⁷ mod 55 (letter 6). Check yourself with the table in section 3.

Answer

27, which is a space.

5. Unlucky choices of a

Find every a coprime to 55 (2 to 54) for which Shor's classical post-processing fails (odd r, or a^r/2 ≡ −1).

Answer

9 of the 39 values fail: 16, 19, 24, 26, 29, 31, 36, 39, 54. Shor's algorithm picks a at random, so it succeeds with good probability and simply retries otherwise.

6. Number mode

(55,3,52)

The Encryption Lesson example. What certificate does the verifier accept, and what range check does it apply?

Answer

13, since 13³ = 2197 ≡ 52 (mod 55). The verifier also requires 0 ≤ m < N.

Words to know

Reference card

Plaintext: The message before it is locked: HELLO WORLD.
Ciphertext: The locked message, the numbers that travel: 17, 15, 23, ...
Public key: Bob's padlock numbers, which everyone may see: 55 and 3.
Private key: Bob's secret unlocking number: 27.
Prime: A whole number above 1 that divides evenly only by 1 and itself: 2, 3, 5, 7, 11, 13, ...
Factor: A number that divides another evenly. 5 and 11 are the factors of 55. Splitting a number into its factors is called factoring.
Remainder: What is left over after dividing: 512 ÷ 55 is 9 with 17 left over.
Eavesdropper: Someone who listens in on a conversation without being part of it. Here, Eve.
Solver: In Redux, a method for solving the problem. For RSA, each solver is one of Eve's attacks.
Certificate: In Redux, a proposed answer that can be checked. For RSA, the message.
Quantum computer: A computer that uses the rules of tiny particles. It is much faster at a few special puzzles, including splitting big numbers into primes.

Problem	RSA (`Problems/NPComplete/NPC_RSA/`), page `/RSA`. Declared complexity class NP; problem type AlgebraAndNumberTheory.
Instance	`(N,e,c)` or `(N,e,"TEXT")`; N ≥ 3, 1 < e < N, 0 ≤ c < N; text of letters and spaces needs N > 27. Default `(55,3,"Hello World")`.
Certificate	The plaintext: m with 0 ≤ m < N and m^e mod N = c, or the message text (any case).
Solvers	RSA Factoring Attack (default): trial division, then φ, d, decrypt; O(√N) divisions. RSA Brute Force Plaintext Search: m = 0, 1, 2, ... per ciphertext, repeats reused; O(N) per symbol, at most 28 in message mode.
Verifier	Default RSA Verifier: re-encrypts the certificate and compares with c.
Visualization	RSA Attacker Knowledge Table (DynamicTable): rows N, e, c (public) and p, q, φ, d, m (secret); one frame per recovered value; blue = found in this step, green = answer.
Quantum	Shor's algorithm; in Redux, PRIMEFACTOR's ShorsQuantumSolver (N < 10 bits, Qiskit Aer simulator).
Source	Rivest, R. L., Shamir, A., and Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.