RSA暗号の仕組み 補足
目次
RSA暗号の仕組みの補足です。
はじめに #
こんにちは、IKです。
自分が学んだことを文書として記録しておこうと考え、記述します。
以前記述した、 RSA暗号の仕組み についての補足です。
目的 #
RSA暗号の仕組みで省略した部分を補完することが目的です。
具体的にはここを補完します、
「なぜ、上記の式を満たす時、\(x^{e \cdot d}\equiv x \bmod N\) が成り立つのかというのは今回は省略します。」
逆に RSA暗号の仕組み 内で紹介したことは省略します。
- ① $$e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)$$
- ② $$ x^{e \cdot d}\equiv x \bmod N$$
\(x\)が\(p\) \(q\) と互いに素であり、①の式を満たす時、②の式を満たす理由の説明をします。
説明 #
| 記号 | 説明 |
|---|---|
| \(x\) | 送信したい平文、\(p\) , \(q\) と互いに素、\(x \lt N\) |
| \(^d\) | 秘密鍵 |
| \(^e\) | 公開鍵 |
| \(\bmod\) | 剰余演算（プログラミングの%） |
| \(N\) | 公開されている法数 |
| \(p\) | \(N\)の素因数 |
| \(q\) | \(N\)の素因数 |
| \(\equiv\) | 合同 |
| \(k\) | 整数 |
上記の表を前提として進めます。
フェルマーの小定理において①の式が成立します。
- ① $$x^{\mathrm{lcm}(p-1,q-1)} \equiv 1 \bmod N$$
①の式の \(\mathrm{lcm}(p-1,q-1)\) に整数 \(k\) を掛けたとしても法数\(N\)上において\(1\)と合同です。
\(1^k \equiv 1 \bmod N\) だからです。
- ② $$x^{k \cdot \mathrm{lcm}(p-1,q-1)} \equiv 1 \bmod N$$
さらに、\(\mathrm{lcm}(p-1,q-1)\)の式に \(1\) を加算した場合、法数\(N\)上において、\(x\) と合同です。
③ $$x^{k \cdot \mathrm{lcm}(p-1,q-1) + 1} \equiv ｘ \bmod N$$
④ $$ x^{e \cdot d}\equiv x \bmod N$$
③と④の２つの式を加味すると、\(k \cdot \mathrm{lcm}(p-1,q-1) + 1\) と \(e \cdot d\) は下記の式に変形できます。
- ⑤ $$e \cdot d\ = k \cdot \mathrm{lcm}(p-1,q-1) + 1$$
⑤の式の両辺を \(\mathrm{lcm}(p-1,q-1)\)で剰余演算をします。
- ⑥ $$e \cdot d \equiv k \cdot \mathrm{lcm}(p-1,q-1) + 1 \bmod \mathrm{lcm}(p-1,q-1)$$
右辺の \(k \cdot \mathrm{lcm}(p-1,q-1)\) は \(\mathrm{lcm}(p-1,q-1)\) で剰余すると \(0\) になります。
\(0\) に \(+1\) しているので右辺は \(1\) と合同となります。
\(k \cdot \mathrm{lcm}(p-1,q-1) + 1 \equiv 1 \bmod \mathrm{lcm}(p-1,q-1)\)
よって、下記の式に変形することができます。
- ⑦ $$e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)$$
終わりに #
以前書いた記事の補足補完として記述しました。
備忘録としてこの文書を残しますが、誰かの学びの糧となれば幸いです。
最後までお読みいただきありがとうございました。