RSA

The setting is that Alice wants to send a message to Bob while making sure that the message cannot be read by an eavesdropper (Eve).

Let $p$ and $q$ be two large primes and $N= pq$. Moreover, take $e$ to be a number such that ${\sf gcd}(e,(p-1)(q-1)) = 1$. We write $d = e^{-1} \pmod{(p-1)(q-1)}$ (recall that such an inverse exists). The values of $N$ and $e$ are made public by Bob (i.e., anyone who wants to send a message to him can use these values to encrypt the message). The rest of the numbers are private and known only to Bob.

• Encryption: Alice sends message $x$ to Bob by computing the value $E(x) \equiv x^e \pmod{N}$.

• Decryption: Upon receiving the message $y$, Bob computes $D(y) \equiv y^d \pmod{N}$.

The correctness of this protocol relies on a simple fact in number theory. The next subsection takes a small detour to cover that fact.

We remark that RSA is not provably secure. Indeed, it seems that the only way for Eve to recover the message $x$ is trying all numbers from $0$ to $N$ (which is infeasible when $N$ is, e.g., 512 bits long). Let us try to understand this more systematically. One potential attempt by Eve might be to factor $N$ into $p\cdot q$, which would allow her to construct $d = e^{-1} \pmod{(p-1)(q-1)}$. But factoring is also believed to be computationally hard, and this is a standard assumption in computation.

More precisely, the security of RSA depends on the following assumption:

Given $N,e$ and $y = x^e \pmod{N}$, no efficient algorithm can determine $x$.