# RSA/Intuitive

## Intuitive Proof

The algorithm is based on a Fermat's little theorem

$a^{(p-1)} \equiv 1 \pmod{p}$

p prime, a & p coprime.

So, if we choose d such that

$e d \equiv 1 \pmod{p-1}$

i.e.

$e d - 1 = k(p-1)$

Then for a message m

$m^{e^d} \equiv m^{e d} \equiv m^{(e d - 1)} \cdot m^1 \equiv m^{k(p-1)}m \equiv 1^km \equiv m \pmod{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 calculates

$n = p q$

(p, q prime) and then d such that

$e d \equiv 1\pmod{(p-1)(q-1)}$

so

$e d - 1 = k(p-1)(q-1)$

We can then continue to calculate

$m^{e^d} \equiv m^{e d} \equiv m^{(e d - 1)}m \equiv m^{k(p-1)(q-1)}m \equiv 1^{k(q-1)}m\equiv m \pmod{p}$

And likewise for q

$m^{e^d} \equiv m^{e d} \equiv m^{(e d - 1)}m \equiv m^{k(p-1)(q-1)}m \equiv 1^{k(p-1)}m\equiv m \pmod{q}$

Now if $a\equiv b \pmod{p}$ and $a\equiv b \pmod{q}$ then $a\equiv b \pmod{pq}$, p, q coprime.

so

$m^{e^d} \equiv m \pmod{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

$e f \equiv 1 \pmod{n-1}$

that

$m^{e^f} \equiv m^{k(n-1)}m \neq m \pmod{n}$

because n is not prime.