RSA/Intuitive

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Intuitive Proof[edit]

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.