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}


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)}


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.


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}


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

because n is not prime.

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.