I guess the canonical of public key crypto is RSA.
RSA is the consequence of a piece of number theory called Euler's Theorem, which says:
$a^{\varphi(n)} \equiv 1 \mod n$
where $\phi(n)$ is Euler's totient function. You can check the Wikipedia article for more information on it, but the important piece regarding RSA is that if $n = pq$, then $\varphi(n) = (p-1)(q-1)$.
The RSA cryptosystem consists of 3 values:
- Public exponent $e$
- Private exponent $d$
- Public modulus $n = pq$ where $p$ and $q$ are primes
To encrypt with RSA, we compute:
$C = M^e \mod n$
To decrypt we compute:
$M = C^d \mod n$
That is, $M = C^d = (M^e)^d \mod n$
To see why this works, we need to look at the relationship between $e$, $d$, and $n$
We choose $e$ and $d$ such that:
$ed \equiv 1 \mod \varphi(n)$
$e$ and $d$ are multiplicative inverses $\mod \varphi(n)$.
That is, $ed$ is some multiple of $\varphi(n)$, plus $1$.
All we're really doing is taking advantage of Euler's theorem:
if
$a^{\varphi(n)} = 1 \mod n$
then
$a^{k\varphi(n)} = 1 \mod n$
$a^{k\varphi(n)+1} \equiv a \mod n$
$ed = k\varphi(n) + 1 \mod \varphi(n)$
$ed \equiv 1 \mod \varphi(n)$
Given $M^e \mod n$ it is difficult to compute $M$. This is known as the RSA problem and there is no known efficient solution.
Given $n$ and $e$, it is difficult to compute $d$. This is because to compute $d$, we need to know $\varphi(n)$. We cannot compute $\varphi(n)$ without knowing the factors of $n$.
The most efficient solution to these problem is integer factorization. This is where RSA gets its security.