Cryptography/RSA

Fermat's Little Theorem

The theorem states that for any prime p and any number $a \in \{1, ... p-1\}$ we have that $a^{p - 1} \equiv 1 \text{ mod }p.$

RSA

RSA starts off with two primes, $p$ and $q.$

We have $N:= pq$ and a number $e$ such that $\text{gcd}(e, (p - 1)(q-1)) = 1.$ Our private key is $d:= e^{-1}(\text{mod} (p - 1)(q - 1))$

Encryption

$$E(x) = x^e \text{mod } N$$

Decrpytion

$$D(x) = y^d \text{mod } N$$