↓メインコンテンツへスキップ
  1. Blog/

RSA暗号の仕組み 補足

目次

RSA暗号の仕組みの補足です。

はじめに #

こんにちは、IKです。

自分が学んだことを文書として記録しておこうと考え、記述します。

以前記述した、 RSA暗号の仕組み についての補足です。

目的 #

RSA暗号の仕組みで省略した部分を補完することが目的です。

具体的にはここを補完します、

「なぜ、上記の式を満たす時、xe⋅d≡x mod Nx^{e \cdot d}\equiv x \bmod N が成り立つのかというのは今回は省略します。」

逆に RSA暗号の仕組み 内で紹介したことは省略します。

  • ① e⋅d≡1 mod lcm(p−1,q−1)e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)
  • ② xe⋅d≡x mod N x^{e \cdot d}\equiv x \bmod N

xxがpp qq と互いに素であり、①の式を満たす時、②の式を満たす理由の説明をします。

説明 #

記号説明
xx送信したい平文、pp , qq と互いに素、x<Nx \lt N
d^d秘密鍵
e^e公開鍵
 mod \bmod剰余演算（プログラミングの%）
NN公開されている法数
ppNNの素因数
qqNNの素因数
≡\equiv合同
kk整数

上記の表を前提として進めます。

フェルマーの小定理において①の式が成立します。

  • ① xlcm(p−1,q−1)≡1 mod Nx^{\mathrm{lcm}(p-1,q-1)} \equiv 1 \bmod N

①の式の lcm(p−1,q−1)\mathrm{lcm}(p-1,q-1) に整数 kk を掛けたとしても法数NN上において11と合同です。

1k≡1 mod N1^k \equiv 1 \bmod N だからです。

  • ② xk⋅lcm(p−1,q−1)≡1 mod Nx^{k \cdot \mathrm{lcm}(p-1,q-1)} \equiv 1 \bmod N

さらに、lcm(p−1,q−1)\mathrm{lcm}(p-1,q-1)の式に 11 を加算した場合、法数NN上において、xx と合同です。

  • ③ xk⋅lcm(p−1,q−1)+1≡ｘ mod Nx^{k \cdot \mathrm{lcm}(p-1,q-1) + 1} \equiv ｘ \bmod N

  • ④ xe⋅d≡x mod N x^{e \cdot d}\equiv x \bmod N

③と④の２つの式を加味すると、k⋅lcm(p−1,q−1)+1k \cdot \mathrm{lcm}(p-1,q-1) + 1 と e⋅de \cdot d は下記の式に変形できます。

  • ⑤ e⋅d =k⋅lcm(p−1,q−1)+1e \cdot d\ = k \cdot \mathrm{lcm}(p-1,q-1) + 1

⑤の式の両辺を lcm(p−1,q−1)\mathrm{lcm}(p-1,q-1)で剰余演算をします。

  • ⑥ e⋅d≡k⋅lcm(p−1,q−1)+1 mod 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⋅lcm(p−1,q−1)k \cdot \mathrm{lcm}(p-1,q-1) は lcm(p−1,q−1)\mathrm{lcm}(p-1,q-1) で剰余すると 00 になります。

00 に +1+1 しているので右辺は 11 と合同となります。
k⋅lcm(p−1,q−1)+1≡1 mod lcm(p−1,q−1)k \cdot \mathrm{lcm}(p-1,q-1) + 1 \equiv 1 \bmod \mathrm{lcm}(p-1,q-1)

よって、下記の式に変形することができます。

  • ⑦ e⋅d≡1 mod lcm(p−1,q−1)e \cdot d \equiv 1\bmod \mathrm{lcm}(p-1,q-1)

終わりに #

以前書いた記事の補足補完として記述しました。

備忘録としてこの文書を残しますが、誰かの学びの糧となれば幸いです。

最後までお読みいただきありがとうございました。

↑