# Overview

**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!Last modified 1yr ago