RSA Algorithm
RSA (Rivest–Shamir–Adleman) is a widely-used asymmetric public-key cryptosystem. It uses a mathematically linked key pair — a public key for encryption and a private key for decryption. This guide covers the full algorithm, a worked example, and an interactive exercise.
Overview
RSA is built on a simple mathematical fact: multiplying two large prime numbers together is easy, but reversing the process (factorising the result) is computationally infeasible. This asymmetry is what makes RSA secure.
Asymmetric cryptography means encryption and decryption use different keys. Anyone can encrypt a message using the recipient's public key, but only the recipient — who holds the private key — can decrypt it. This contrasts with symmetric cryptography (e.g. AES) where both parties must share the same secret key.
Key Concepts
Prime Numbers
A number greater than 1 with no divisors other than 1 and itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. RSA requires two distinct large primes.
Modular Arithmetic
The remainder after integer division. Written as a mod n. For example, 17 mod 5 = 2 because 17 = 3 × 5 + 2. All RSA operations are performed in modular arithmetic.
Relatively Prime (Coprime)
Two numbers are coprime when their greatest common divisor (gcd) equals 1 — they share no common factors other than 1. Example: gcd(3, 40) = 1, so 3 and 40 are coprime.
Euler's Totient — Φ(n)
Counts how many integers from 1 to n are coprime to n. For n = p × q (distinct primes), Φ(n) = (p − 1)(q − 1). This value is the bridge that mathematically links e and d.
Algorithm Steps
Select two prime numbers p and q
Choose two distinct prime numbers. The security of RSA depends on how difficult it is to factorise n = p × q, so real-world implementations use extremely large primes (hundreds of digits). For exam and study purposes, small primes such as 3, 5, 7, 11, 13 are used.
Note: A prime number is divisible only by 1 and itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23.
Calculate n = p × q
n is the modulus. It appears in both the public key and the private key, and all RSA arithmetic is performed modulo n. Because n is the product of two primes, factorising it (to recover p and q) is computationally infeasible for large values.
Note: n is made public. It does not directly reveal p or q.
Calculate Euler's Totient Φ(n)
Euler's Totient counts how many integers from 1 to n are coprime to n. For n = p × q where p and q are distinct primes, this simplifies neatly to (p − 1)(q − 1). This value links e and d mathematically.
Note: Φ(n) must be kept secret. An attacker who learns Φ(n) can compute d and decrypt everything.
Select e that is relatively prime to Φ(n)
e is the public exponent. It must be greater than 1, less than Φ(n), and share no common factor with Φ(n) — i.e. gcd(e, Φ(n)) = 1. Common textbook values are 3, 7, or 17. In practice, e = 65537 is the industry standard.
Note: Use the Euclidean algorithm to verify gcd(e, Φ(n)) = 1. If gcd > 1, choose a different e.
Calculate d — the private exponent
d is the modular multiplicative inverse of e with respect to Φ(n). This means (e × d) mod Φ(n) = 1. For exam questions with small numbers, find d by trying d = 1, 2, 3, … until the condition is met. For large numbers, the Extended Euclidean Algorithm is used.
Note: d is the most sensitive value in RSA. Exposing d means exposing your private key — never share it.
Identify the keys
The public key {e, n} is shared openly. Anyone who wants to send you a confidential message uses it to encrypt. The private key {d, n} is kept secret and is used only by you to decrypt messages intended for you.
Note: Both keys share the same n. The security of the scheme depends entirely on d remaining secret.
Encryption
The sender uses your public key {e, n} to convert plaintext (PT) into ciphertext (CT). Anyone who has your public key can encrypt, but the result can only be reversed by the holder of d.
Note: PT must satisfy 0 < PT < n. If PT ≥ n, the decrypted result will not match the original.
Decryption
The receiver uses their private key {d, n} to recover the original plaintext from the ciphertext. Thanks to the mathematical relationship between e, d, and Φ(n), this always produces the original message.
Note: This is the foundation of asymmetric (public-key) cryptography — only the key owner can decrypt.
Worked Example
Given: p = 3, q = 11, e = 3, PT = 5
Step 7 (Encrypt): 5³ = 125. Then 125 ÷ 33 = 3 remainder 26, so 125 mod 33 = 26. Ciphertext CT = 26.
Step 5 (Finding d by trial): Try d = 1, 2, 3, … and compute (3 × d) mod 20 each time until the result is 1. 3×1=3, 3×2=6, 3×3=9, 3×4=12, 3×5=15, 3×6=18, 3×7=21 → 21 mod 20 = 1. So d = 7.
Interactive Exercise
Work through the RSA steps yourself. Type your answer and click Check.
Given: p = 5, q = 11, e = 3, Message (PT) = 9
Step 2 — Calculate n
n = p × q = 5 × 11 = ?
Step 3 — Calculate Φ(n)
Φ(n) = (p−1) × (q−1) = (5−1) × (11−1) = ?
Step 4 — Verify e is coprime to Φ(n)
e = 3 is given. Confirm: gcd(3, 40) = 1 ✓ — so e = 3 is a valid public exponent.
Step 5 — Find d (private exponent)
3 × d ≡ 1 (mod 40)
Hint: try d = 1, 2, 3, … and compute (3 × d) mod 40 until the result is 1.
Step 6 — Keys
Public Key: {3, n} — share openly.
Private Key: {d, n} — keep secret.
Step 7 — Encrypt
CT = PT^e mod n = 9^3 mod 55 = ?
Step 8 — Decrypt
PT = CT^d mod n = 14^d mod 55 = ?
Euclidean Algorithm Reference
The Euclidean Algorithm is used twice in RSA: first to verify that e and Φ(n) are coprime (Step 4), and then — in its extended form — to find d (Step 5).
How to read mod notation
Every line in the Euclidean Algorithm is a division equation with a remainder. Once you can read one line, you can read them all.
Anatomy of one division row
Golden rule: larger ÷ smaller
In every mod operation, the larger number is divided by the smaller one — never the other way around. If you see gcd(3, 40), swap to put the bigger number first: gcd(40, 3), then compute 40 mod 3. (Computing 3 mod 40 just gives 3, which goes nowhere useful.)
Mental process — how to compute 40 mod 3 (larger ÷ smaller):
So 40 mod 3 = 1. The remainder is always between 0 and (divisor − 1).
Quick examples to build intuition
Basic Euclidean Algorithm — finding gcd
Repeatedly replace the larger number with the remainder of dividing the two numbers, until the remainder is 0. The last non-zero remainder is the gcd.
Example: Verify gcd(40, 3) = 1 — confirming e = 3 is coprime to Φ(n) = 40 (from the exercise).
We write gcd(40, 3) — larger first — so the division in each row is always larger ÷ smaller.
Last non-zero remainder = 1. So gcd(40, 3) = 1 — they are coprime, e = 3 is valid. ✓
Extended Euclidean Algorithm — finding d
The extended form not only finds gcd(e, Φ(n)) but also back-substitutes through the division steps to express 1 as a linear combination of e and Φ(n). The coefficient of e gives d (take mod Φ(n) if negative).
Example: Find d where 3 × d ≡ 1 (mod 40) — i.e. e = 3, Φ(n) = 40 (exercise values).
Step A — run the basic EA and record each division
Step B — back-substitute to express 1 in terms of e and Φ(n)
Step C — read off d
The coefficient of e (= 3) is −13. Since d must be positive, add Φ(n):
Verify: 3 × 27 = 81 = 2 × 40 + 1, so 81 mod 40 = 1. ✓ d = 27 is correct.
Second example — worked example values
Find d where 3 × d ≡ 1 (mod 20) — e = 3, Φ(n) = 20.
Step A
Step B — back-substitute
Step C
Verify: 3 × 7 = 21 = 1 × 20 + 1, so 21 mod 20 = 1. ✓ d = 7 is correct.
Trial method — shortcut for small numbers
When Φ(n) is small (as in exam questions), simply try d = 1, 2, 3, … and compute (e × d) mod Φ(n) each time until you get 1. This avoids the back-substitution entirely. The Extended EA is only necessary when the numbers are too large to trial.