暗号化だけ出来る鍵と、復号だけ出来る鍵が、ペアで存在します。暗号化だけ出来る鍵は公開して、復号だけ出来る鍵を自分だけが持つようにします。暗号化と復号を出来る鍵が共通の場合、やり取りをしたい相手に渡す際に、第三者に盗まれると困ります。一方で暗号化だけ出来る鍵の場合は、第三者に盗まれても困りません。これが公開鍵暗号の利点です。

暗号化だけ出来る鍵と、復号だけ出来る鍵のペアは、数学の理論に基づいて実現されています。

異なる2つの素数$p$と$q$を用意します。そして$n=pq$とします。

それから、$\varphi(n)$と互いに素(最大公約数が1であることと同じ)な数値を$e$とします。 なお$\varphi(n)$はトーシェント関数で、n以下の整数で、nと互いに素となるものの個数です。 ここで求めた${e, n}$を公開鍵とします。

そして、$ed \equiv 1 \mod \varphi(n)$となるモジュロ逆数$d$を求めて、この値を秘密鍵とします。 なおモジュロ逆数$d$ですが、$x \mod y$で$x$と$y$が互いに素である場合は、必ずモジュロ逆数が存在することが証明されています。

ここまでで必要な数字が用意できました。これらを用いて暗号化と復号を行ないます。 平文をaとして、暗号化された文をbとします。

$b = a^e \mod n\\
a = b^d \mod n$

上記の式で、暗号化と復号が出来ます。

なぜ上記のようなことが成り立つのか、説明します。

まず $ed \equiv 1 \mod \varphi(n)$なので、任意の整数$k$を用いて、$ed - 1 = k\varphi(n)$で表せます。$ed$を$\varphi(n)$で割った余りが$1$になるので、$ed$から$1$を引いた値は、$\varphi(n)$で割り切れる任意の値になる、という意味です。

$n = pq$であることから、

$\varphi(n) = \varphi(pq)\\
\varphi(n) = \varphi(p)\varphi(q)$

となります。そして$p$と$q$は素数であることから、 それぞれ自身より小さい整数は全て互いに素となりますので、

$\varphi(p) = p - 1\\
\varphi(q) = q - 1$

となり、

$\varphi(n) = (p - 1)(q - 1)$

となります。

ここまでの式をまとめると、

$ed - 1 = k(p - 1)(q - 1)$

となります。

下記の式が成り立てば、暗号文を平文に復号出来ることを証明できます。

$(a^e)^d \equiv a \mod n$