RSA Algorithm

• Let $n$ be a number known by sender and receiver.
• Plaintext is encrypted in blocks, with each block having a binary value less than $n$. Block size must be less than or equal to ${\log }_2(n)+1$. Each block represents a number $M$ such that $M<n$.

We define RSA encryption and decryption of $M$ for some (properly) chosen values of $e$ and $d$

$$\begin{array}{rl}C& =M^e\text{ mod }n\\ M& =C^d\text{ mod }n\\ & =(M^e{)}^d\text{ mod }n\\ & =M^{ed}\text{ mod }n\end{array}$$

It is a public-key encryption algorithm with:

• public key $PU=(e,n)$
• private key $PR=(d,n)$

For the algorithm to work, the following requirements must be met:

1. It is possible to find values of $e$, $d$, $n$ such that $M^{ed}\text{ mod }n=M$ for all $M<n$.
2. It is relatively easy to calculate $M^e\text{ mod }n$ and $C^d\text{ mod }n$ for all values of $M<n$.
3. It is infeasible to determine $d$ given $e$ and $n$.