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(\mathrm{mod}p)$

p prime, a & p coprime.

So, if we choose d such that

$ed\equiv 1(\mathrm{mod}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(\mathrm{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 calculates

$n=pq$

(p, q prime) and then d such that

$ed\equiv 1(\mathrm{mod}(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(\mathrm{mod}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(\mathrm{mod}q)$

Now if $a\equiv b(\mathrm{mod}p)$ and $a\equiv b(\mathrm{mod}q)$ then $a\equiv b(\mathrm{mod}pq)$, p, q coprime.

so

$m^{e^d}\equiv m(\mathrm{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\equiv 1(\mathrm{mod}n-1)$

that

$m^{e^f}\equiv m^{k(n-1)}m\ne m(\mathrm{mod}n)$

because n is not prime.