rsa
差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| rsa [2025/07/12 05:03] – [証明] bokupi | rsa [2025/07/12 13:00] (現在) – bokupi | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== RSA公開鍵暗号 ====== | + | ====== RSA公開鍵暗号方式 |
| ===== 公開鍵暗号の概要 ===== | ===== 公開鍵暗号の概要 ===== | ||
| 行 33: | 行 33: | ||
| $(a^e)^d \equiv a \mod n$ | $(a^e)^d \equiv a \mod n$ | ||
| - | 最初に、$\mod p$とした場合について見ていきます。 | + | 最初に、$\mod n$ではなく$\mod p$とした場合について見ていきます。これはmodで作る法の世界を、素数にすることが、この先の証明で必要になるからです。($n$は素数ではないため) |
| - | $a$が$p$の倍数である場合、$a$を$p#で割った余りは0となるので、 | + | $a$が$p$の倍数である場合、$a$を$p$で割った余りは0となるので、 |
| $(a^e)^d \equiv 0 \equiv a \mod p$ | $(a^e)^d \equiv 0 \equiv a \mod p$ | ||
| 行 41: | 行 41: | ||
| となって、 | となって、 | ||
| - | $(a^e)^d \equiv a \mod n$ | + | $(a^e)^d \equiv a \mod p$ |
| は成り立ちます。 | は成り立ちます。 | ||
| 行 72: | 行 72: | ||
| となります。 | となります。 | ||
| - | 下記の式が成り立てば、暗号文を平文に復号出来ることを証明できます。 | + | 少し間が空いたので再掲しますが、下記の式が成り立つことを、証明します。。 |
| - | $(a^e)^d \equiv a \mod n$ | + | $(a^e)^d \equiv a \mod p$ |
| 以下、式変形していきます。 | 以下、式変形していきます。 | ||
| 行 102: | 行 102: | ||
| ここまで$p$について見てきましたが、$p$を$q$に置き換えても同様のことが言えます。 | ここまで$p$について見てきましたが、$p$を$q$に置き換えても同様のことが言えます。 | ||
| + | ということは、$k, | ||
| + | |||
| + | $(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:// | ||
| + | * 個人的にはこちらの説明が分かりやすかったです。自身のレベルによって読みやすいと感じる説明は変わると思います | ||
| + | |||
rsa.1752296615.txt.gz · 最終更新: 2025/07/12 05:03 by bokupi