RSA (Rivest-Shamir-Adleman) is a public-key cryptosystem that allows two parties $X$ and $Y$ to exchange secrets. Given any large [[Integers|integer]] $n$, the secret can be represented as a number [[Congruence Modulo|modulo]] $n$. To generate the keys, $X$ first chooses two large [[Prime Number|prime numbers]] $p < q$, and calculates $n = pq$, $k = (p - 1)(q - 1)$. $X$ then chooses an integer $d$ such that $\gcd(d, k) = 1$. $X$ finds an integer $e$ such that $ed \equiv 1$, mod $k$. $X$ **publishes** $e$ and $n$ as the **public key**, and keeps $d$ as the **private key**, while destroying all other numbers. To send a secret, $Y$ writes it as $b \mod n$ where $b$ and $n$ are coprime, then sends $b^e$ (mod $n$) to $X$. This creates a *discrete log problem*, where it is difficult to find $b$ even with knowledge of $b^e$ and $n$. Therefore, it is difficult to extract $b$ from $b^e \mod n$. Upon receiving the message $b^e$, $X$ calculates $\paren{b^{e}}^{d}$. Then, since $ed \equiv 1$, mod $k$, it can be written as $ed = 1 + vk$. Using [[Fermat's Little Theorem]], $ \begin{align*} b^{ed} &= b^{1 + vk} \\ &= b \cdot b^{(p - 1)(q - 1)v} \\ &= b \cdot 1^{(q - 1)v} \\ &= b \end{align*} $ Which gives back the original secret.