RSA

RSA is an example of public key cryptography. It is a widely used system, relying for its security on the difficulty of factoring a large number.

Alice forms her public and private keys as follows:

• Chooses large primes $p$ and $q$, then form $n=pq$.

• Chooses e coprime with $\varphi (n)=(p-1)(q-1)$.

• Publishes $(n,e)$ as her public key.

• Computes private key $d$ such that $de\equiv 1\mathit{\hspace{1em}}\text{mod }\varphi (n)$.

To encrypt a message $M$ (where ) the user Bob forms $C=M^e\mathit{\hspace{1em}}\text{mod }n$.

To decrypt the message, Alice forms $d(C)=C^d\mathit{\hspace{1em}}\text{mod }n$.

This recovers message $M$ because:

$d(C)$$=C^d\mathit{\hspace{1em}}\text{mod }n$

$={(M^e+rn)}^d\mathit{\hspace{1em}}\text{mod }n\mathit{\hspace{1em}\hspace{1em}}\text{for some }r$

$={(M^{(p-1)})}^{t(q-1)}M\mathit{\hspace{1em}}\text{mod }n\mathit{\hspace{1em}\hspace{1em}}\text{for some }t$

$\equiv {(1+sp)}^{t(q-1)}M\mathit{\hspace{1em}}\text{mod }p\mathit{\hspace{1em}\hspace{1em}}\text{for some }s$

$\equiv M\mathit{\hspace{1em}}\text{mod }p$

So $d(C)\equiv M\mathit{\hspace{1em}}\text{mod }p$ and similarly, $d(C)\equiv M\mathit{\hspace{1em}}\text{mod }q$ so by the Chinese remainder theorem, $d(C)\equiv M\mathit{\hspace{1em}}\text{mod }n$, and since we know we know that $M=d(C)$.