# 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:

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