# Overview

## Encryption

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.

## Decryption

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

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!