# Overview

Last updated

Last updated

**Alice **first generates primes $p$ and $q$ and $N$ such that $N=pq$. This is half of the public key, with the other half being the **public exponent** $e$, which should be **coprime** to $\phi (N)$ (meaning $gcd(\phi (N), e) = 1$). These two values are then made public.

If **Bob** wants to send a message $M$ to Alice using RSA, he calculates:

$c = M^e \mod N$

Where $c$ is now the ciphertext and is sent to **Alice**.

Alice calculates $\phi (N) = (p-1)(q-1)$ and then calculates the **modular multiplicative inverse** $d$ of $e \mod \phi (N)$. $d$ is the **private key** used for the decryption which is known only to **Alice**.

To decrypt, the Alice calculates $M$ again:

$M = c^d \mod N$

The proof for this is based on Euler's Formula. Because we calculated $d$ such that $de \equiv 1 \mod \phi (N)$, then we know that there is an integer $k$ such that $de = k\phi (N) + 1$. Also note that $c^d \equiv (M^e)^d \equiv M^{de}$:

$M^{de} \equiv M ^ {k\phi (N) + 1} \equiv M^{k\phi (N)} \times M \equiv (M^{\phi (N)})^k \times M \equiv 1^k \times M \equiv M \mod N$

Attacks on RSA generally fall into several categories, including weak public exponent or a poor choice of $p,q$ which results in a value of $N$ which can be factorised or attacked in another way. Remember that the trapdoor function in RSA is the difficulty of factoring $N$ into the primes that make it up so only Alice is able to compute $\phi(N)$ efficiently!