Public-Key Cryptography

RSARivest · Shamir · Adleman

Learn it, compute it, and test yourself — the whole algorithm in one place, built for your exam.

The core idea

What problem does RSA solve?

RSA is an asymmetric (public-key) cryptosystem. Instead of one shared secret key, every person has a pair of keys that are mathematically linked:

Public key — share freely

(e, n)

Anyone can use it to encrypt a message to you, or verify your signature.

Private key — keep secret

(d, n)

Only you hold it. It's used to decrypt incoming messages, or sign.

The magic: what one key locks, only the other can unlock. You never have to share a secret in advance.

Why it's secure — the trapdoor

RSA rests on a one-way "trapdoor" function. Multiplying two large primes is easy:

p × q = n (fast, even for 300-digit numbers)

But going backwards — factoring n back into p and q — is believed to be computationally infeasible for huge numbers. Without the factors you can't find φ(n), and without φ(n) you can't find the private exponent d. That asymmetry of effort is the whole security argument.

Key vocabulary

Prime numbers (p, q): two large, distinct primes — the secret seeds of everything.
Modulus (n): n = p·q. Public, and shared by both keys. Its bit-length is the "key size" (e.g. 2048-bit RSA).
Euler's totient φ(n): the count of integers below n coprime to it. For two primes, φ(n) = (p-1)(q-1).
Public exponent (e): chosen so 1 < e < φ(n) and gcd(e, φ(n)) = 1. Often a fixed value like 65537.
Private exponent (d): the modular inverse of e, i.e. e·d ≡ 1 (mod φ(n)).
Coprime: two numbers whose greatest common divisor is 1 (no shared factors).

The five phases at a glance

1 · Key generation — pick p, q → compute n, φ(n) → choose e → derive d.
2 · Distribute — publish (e, n); lock away (d, n).
3 · Encrypt — sender computes c = mᵉ mod n using your public key.
4 · Transmit — only the ciphertext c travels over the wire.
5 · Decrypt — you recover m = cᵈ mod n with your private key.

Formulas & theory

Everything you must memorise

Step 1 — Key generation

n = p · qModulus. p and q are large distinct primes.

φ(n) = (p − 1)(q − 1)Euler's totient of n.

choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1Public exponent — must be coprime to φ(n).

d ≡ e⁻¹ (mod φ(n)) ⟺ e·d ≡ 1 (mod φ(n))Private exponent — the modular multiplicative inverse of e. Found via the Extended Euclidean Algorithm.

Step 2 — Encryption & decryption

Encrypt: c = m^e mod nm is the plaintext, must satisfy 0 ≤ m < n.

Decrypt: m = c^d mod nRecovers the original plaintext exactly.

Why decryption works

Because e·d ≡ 1 (mod φ(n)), we have e·d = kφ(n)+1 for some integer k. Then by Euler's theorem:

c^d = (m^e)^d = m^ed = m^kφ(n)+1 ≡ m (mod n)The exponents cancel modulo n, returning the original message.

Quick-reference table

Symbol	Name	Computed as	Secret?
p, q	primes	chosen	secret
n	modulus	p·q	public
φ(n)	totient	(p−1)(q−1)	secret
e	public exp.	gcd(e,φ)=1	public
d	private exp.	e⁻¹ mod φ	secret
c	ciphertext	mᵉ mod n	public

Computational tools you'll need

Fast modular exponentiation (square-and-multiply) — to compute mᵉ mod n without astronomically large intermediates.
Extended Euclidean Algorithm — to find d, the inverse of e mod φ(n).
Euclid's GCD — to verify gcd(e, φ(n)) = 1 before accepting e.

Live RSA calculator

Type values — every step recomputes instantly

p (prime)

q (prime)

e (public exp.)

m — message as a number, 0 ≤ m < n

A full worked example

Tiny primes so you can follow every digit by hand

We'll send the message m = 4 using small primes p = 3, q = 11. Trace it from key generation to recovery.

📝

Plaintext

m = 4

🔒encrypt
c = mᵉ mod n

📦

Ciphertext

c = 31

🔑decrypt
m = cᵈ mod n

📝

Recovered

m = 4

Key generation

① Choose primes

p = 3, q = 11

② Modulus

n = p·q = 3 × 11 = 33

③ Totient

φ(n) = (3−1)(11−1) = 2 × 10 = 20

④ Public exponent

choose e = 3 → gcd(3, 20) = 1 ✓

3 shares no factors with 20, so it's a valid choice.

⑤ Private exponent

d = 3⁻¹ mod 20 = 7

Check: 3 × 7 = 21 = 20 + 1 ≡ 1 (mod 20) ✓

Public key

(e, n) = (3, 33)

Private key

(d, n) = (7, 33)

Encrypt the message

Encryption

c = mᵉ mod n = 4³ mod 33 = 64 mod 33 = 31

64 − 33 = 31, so the ciphertext sent over the wire is 31.

Decrypt to recover

Decryption

m = cᵈ mod n = 31⁷ mod 33

Using 31 ≡ −2 (mod 33): (−2)⁷ = −128, and −128 + (4×33) = −128 + 132 = 4

We recovered m = 4 — exactly the original message. The round-trip works.

Want to verify with different numbers? Hop over to the Calculator tab and type these in.

Test yourself

6 questions · instant feedback · explanations

Score

0 / 6

Answer the questions to see how you're doing.