RSA Encryption

The Rivest-Shamir-Adleman (RSA) encryption system relies on the ease of multiplication and hardness to factor large semi-primes. Let $n$ $=$ $pq$ be such a semi-prime with $p$ and $q$ being distinct primes. The multiplicative group $\mathbb{Z}_n^*$ has exactly $(p-1)(q-1)$ elements. Then $a^{(p-1)(q-1)+1}$ $\equiv$ $a$ $\pmod{n}$.

Find $e$ such that $\gcd(e,(p-1)(q-1))$ $=$ $1$. Compute $d$ $\equiv$ $e^{-1}$ $\pmod{(p-1)(q-1)}$ by the extended Euclid's algorithm. So we have $E(w)$ $\equiv$ $w^e$ $\pmod{n}$ for encryption and $D(w)$ $\equiv$ $w^d$ $\pmod{n}$ for decryption. Note that $D(E(w))$ $\equiv$ $w^{ed}$ $\equiv$ $w$ $\pmod{n}$.

For example let us encode the word "AT" using the primes $73$ and $101$ or $n$ $=$ $7373$. We choose $e$ to be $7$, noting that the requirement $\gcd(7,7200)$ $=$ $1$ is met. We compute the inverse $d$ as $5143$. We have to translate "AT" to numbers. Let's do that with "0120" where "01" is "A" and "20" is "T". We encode the message as $120^7$ $\equiv$ $2852$ $\pmod{7373}$. To decode it we take the cypher number and raise it to $d$. That is $2852^{5143}$ $\equiv$ $120$ $\pmod{7373}$ and translate back the number "120" to English as "AT".