RSA/Intuative

The algorithm is based on a Fermat's little theorem

a^(p−1) ≡ 1 (mod  p)

p prime, a & p coprime.

So, if we choose d such that

ed ≡ 1 (mod  p − 1)

i.e.

ed − 1 = k(p−1)

Then for a message m

m^ed ≡ m^ed ≡ m^(ed−1) ⋅ m¹ ≡ m^k(p−1)m ≡ 1^km ≡ m (mod  p)

So a message that is encrypted by raising m to e can be decrypted by raising the result to d.

In order to provide security, RSA actually calulates

n = pq

(p, q prime) and then d such that

ed ≡ 1 (mod  (p−1)(q−1))

so

ed − 1 = k(p−1)(q−1)

We can then continue to calculate

m^ed ≡ m^ed ≡ m^(ed−1)m ≡ m^{k(p−1)(q−1)}m ≡ 1^k(q−1)m ≡ m (mod  p)

And likewise for q

m^ed ≡ m^ed ≡ m^(ed−1)m ≡ m^{k(p−1)(q−1)}m ≡ 1^k(p−1)m ≡ m (mod  q)

Now if a ≡ b (mod  p) and a ≡ b (mod  q) then a ≡ b (mod  pq), p, q coprime.

so

m^ed ≡ m (mod  pq)

An attacker would need to factor n into p and q in order to determine d, and this is a hard problem.

Note that while an attacker could easily calculate f as

ef ≡ 1 (mod  n − 1)

that

m^ef ≡ m^k(n−1)m ≠ m (mod  n)

because n is not prime.