# 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 $\phi(n)=(p-1)(q-1)$.

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

• Computes private key $d$ such that $de\equiv 1\quad\textrm{mod }\phi(n)$.

To encrypt a message $M$ (where $M) the user Bob forms $C=M^{e}\quad\textrm{mod }n$.

To decrypt the message, Alice forms $d(C)=C^{d}\quad\textrm{mod }n$.

This recovers message $M$ because:

 $\displaystyle d(C)$ $\displaystyle=C^{d}\quad\textrm{mod }n$ $\displaystyle=(M^{e}+rn)^{d}\quad\textrm{mod }n\qquad\textrm{for some }r$ $\displaystyle=(M^{(p-1)})^{t(q-1)}M\quad\textrm{mod }n\qquad\textrm{for some }t$ $\displaystyle\equiv(1+sp)^{t(q-1)}M\quad\textrm{mod }p\qquad\textrm{for some }s$ $\displaystyle\equiv M\quad\textrm{mod }p$

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

Title RSA RSA 2013-03-22 15:14:50 2013-03-22 15:14:50 aoh45 (5079) aoh45 (5079) 5 aoh45 (5079) Definition msc 94A60 RSA cryptosystem