差分

このページの2つのバージョン間の差分を表示します。

--- rsa [2025/07/12 02:30] – bokupi
+++ rsa [2025/07/12 13:00] (現在) – bokupi
@@ 行 1: / 行 1: @@
-====== RSA公開鍵暗号 ======
+====== RSA公開鍵暗号方式 ======
 ===== 公開鍵暗号の概要 =====
@@ 行 29: / 行 29: @@
 なぜ上記のようなことが成り立つのか、説明します。
-まず $ed \equiv 1 \mod \varphi(n)$なので、$e$
+下記の式が成り立てば、暗号文を平文に復号出来ることを証明できます。
+$(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$
+と言えます。
+===== 参考サイト =====
+  * [[https://qiita.com/reika727/items/215d23bf18e21e3cbc52|RSA 暗号の正しさを徹底的に証明する]]
+    * 個人的にはこちらの説明が分かりやすかったです。自身のレベルによって読みやすいと感じる説明は変わると思います