RSA

The idea is that each person has a public key known to the world and a private key that only they know. You encode messages using someones public key, and they decode them using their private key.

Invertible / Bijection

A function $f:\{0,1,\dots ,m\}\to \{0,1,\dots ,m\}$ is invertible if for every y in the span, there is an $x$ in the span such that $f(x)=y$.

Or every x in the domain has a mapping in the range.

Pick any two distinct prime numbers and let $N=p\ast q$. For any e relatively prime to $(p-1)(q-1)$ (or for an e, such that $gcd(e,(p-1)(q-1))=1$):

1. The mapping $x\to x^e\text{ mod }N$ is invertible on $\{0,1,\dots ,N-1\}$
2. The inverse mapping is defined as follows: let d be the multiplicative inverse of $e\text{ mod }(p-1)(q-1)$ Then, for $x\in \{0,\dots ,N-1\}$ → $(x^e{)}^d\text{ mod }N=x$

So for a given x, we can encode using $(x^e)\text{ mod }N$ computed with modexp, and decode using $(x^e{)}^d\text{ mod }N=x$ again using modexp.

The public key is $(N,e)$ with a secret key $d$. $p$ and $q$ which compute $N$ are very large primes.

This is secure since this would take forever to factor.