Mathematical foundation of the RSA asymmetrical cryptosystem.

# Key Generation

- Choose two prime numbers \(p\) and $q$
- Compute $n=p q$
- Choose $a$ such that $\textrm{gcd}(a,\,\varphi(n))=1$
- Compute $b$ such that $\textrm{mod}(a b,\,\varphi(n)) = 1$
**Public key:**$(n,\,a)$**Private key:**$(p,\,q,\,b)$

# Encryption With Public Key

Let $(n,\,a)$ be the public key, $x$ the plain text and $y$ the ciphertext:

# Decryption With Private Key

Let $(p,\,q,\,b)$ be the private key, $y$ the ciphertext, and $x$ the plain text:

# Decryption With Public Key (Cracking RSA)

Let $(n,\,a)$ be the public key, $y$ the ciphertext and $x$ the plain text:

Calculating the plain text $x$ requires to calculate $\varphi(n)$, which is equivalent to calculating the prime factors $p$ and $q$ of $n$, which is an NP problem (that is, not doable for large $n$).