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

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

異なる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$

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

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

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

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

最初に、$\mod n$ではなく$\mod p$とした場合について見ていきます。これはmodで作る法の世界を、素数にすることが、この先の証明で必要になるからです。($n$は素数ではないため)

$a$が$p$の倍数である場合、$a$を$p$で割った余りは0となるので、

$(a^e)^d \equiv 0 \equiv a \mod p$

となって、

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

は成り立ちます。

続いて、$a$が$p$の倍数でない場合を見ていきます。$p$は素数なので、$a$が$p$の倍数でない場合、$a$と$p$は互いに素となります。この条件が後ほどフェルマーの小定理を使う際に必要になります。$a$が$p$の倍数である場合、この条件は成立しないので、前述の通り個別に証明しています。

まず $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 p$

以下、式変形していきます。

$\begin{align} (a^e)^d &= a^{ed}\\ &= a^{ed - 1}a\\ &= a^{k(p - 1)(q - 1)}a\\ &= (a^{(p - 1)})^{k(q - 1)}a \end{align}$

となります。 ここで、フェルマーの小定理

$a^{p-1} \equiv 1 \mod p$

を活用して、さらに式変形を進めます。 ($p$が素数で且つ$a$と$p$が互いに素である)

$\begin{align} (a^e)^d &\equiv (a^{(p - 1)})^{k(q - 1)}a \mod p\\ &\equiv 1^{k(q - 1)}a \mod p\\ &\equiv a \mod p\\ \end{align}$

となります。

ここまで$p$について見てきましたが、$p$を$q$に置き換えても同様のことが言えます。 ということは、$k, l$を任意の整数とすると、

$(a^e)^d - a = kp\\
(a^e)^d - a = lq$

となります。 剰余が同じ値なら、それらの差は割った値の倍数です。

さらに$p$と$q$はそれぞれ素数なので、互いに素です。 $m$を任意の整数とすると、

$\begin{align} (a^e)^d - a &= m(pq)\\ &=mn \end{align}$

となります。

従って、

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

と言えます。

• RSA 暗号の正しさを徹底的に証明する
  • 個人的にはこちらの説明が分かりやすかったです。自身のレベルによって読みやすいと感じる説明は変わると思います