RSA暗号 なぜ暗号化，復号できるか
- もはや枯れた技術といってもよいRSA暗号ですが，そもそも何故異なる鍵(公開鍵，秘密鍵)で暗号化，復号ができるのか気になります。
- そこで私なりに証明を与えました。
- しかしこの内容が確実に正しいことであるかどうかは保証しかねますので，その点はご了承ください。
証明について
前提
| 鍵の種類 | 値 |
|---|---|
| 共通鍵 | $e$および$N$ |
| 秘密鍵 | $d$および$N$ |
-
ただし$d,e,N$は以下のように決める。
- $p,q$を素数とし，$N=p \times q$とする。
- $L$を$(p-1),(q-1)$の最小公倍数とする。
- $e \times d \equiv 1 (mod\ L)$となる2つの自然数e,dを巧く取る。
- 通常eは65537とする。
-
暗号化対象のデータをMとすると，暗号化，復号は以下の式で実施する。
- 暗号化 $C \equiv M^{e} (mod\ N)$
- 復号 $M \equiv C^{d} (mod\ N)$
証明
- 証明は以下の通りです。
- Qiitaで対応していない数式を使う都合上すべて画像になっています。
具体例
-
直観的にわかるように図で説明すると以下のようになります。
-
$p=3,q=11$とする。
-
$Lはp-1=2,q-1=10$の2つの最小公倍数なので$L=10$。
-
$N=p \times q=33$となる。
-
$e=3$とすると，$e \times d = L \times k + 1(k \in \mathbb{N})$を満たせばよいので，仮に$k=2$とする。
-
$e \times d = 21$となる数値を考えると，$d=7$となる。
-
$p=3,q=11,L=10,N=33,e=3,d=7$というパラメータから1から17のデータに対して21乗までのべき乗を計算。ただし計算結果は$33(=N)$で割った余り。
- 吹き出しや枠線で多少見えない数値がありますが、ご了承ください。
- 実際のRSA暗号では$N=p \times q$は300桁程度の数値、$e=65537$を使うためこのような小さな数値ではない。
補足
- 証明自体は既存の定理を駆使するので，特に面白みのない技巧的なものです。
- メルセンヌ・ツイスターやAESのほうが数学としては面白いと思います。
- 以前RSA暗号について図を駆使したわかりやすい解説があったのですが，失われてしまったようです。