Table of costs of operations in elliptic curves

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

$ed\equiv 1{\pmod {p-1}}$

i.e.

$ed-1=k(p-1)$

Then for a message m

$m^{e^{d}}\equiv m^{ed}\equiv m^{(ed-1)}\cdot m^{1}\equiv m^{k(p-1)}m\equiv 1^{k}m\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=pq$

(p, q prime) and then d such that

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

so

$ed-1=k(p-1)(q-1)$

We can then continue to calculate

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

$ef\equiv 1{\pmod {n-1}}$

that

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

because n is not prime.