RSA暗号 - 知識メモ

A:送信者、B:受信者

（１）B は大きな素数 p , q を選び秘密鍵とする。
m = pq とおき、e を (p - 1)(q - 1)と互いに素な自然数とする。
m と e は公開鍵。

（２）A は情報を x ∈ Z_m で表し、x^e mod m を B に送る。

（３）e と (p - 1)(q - 1) は互いに素なので、


（拡張ユークリッド互除法）
この s を使って、

と復元できる。（s は (p-1)(q-1) が分からないと生成できず、そのためには秘密鍵 p , q が必要）

（３）の最後の等式の成り立つ理由

いま、x は「p の倍数でも q の倍数でもない」「p の倍数であって q の倍数でない」「p の倍数でなくて q の倍数」
のいずれかになっている。

• x が「p の倍数でも q の倍数でもない」とき

が成立するため、（３）の最後の等式が成り立つ。

（証明）
命題を示すには、

が m = pq の倍数であること、すなわち p の倍数かつ q の倍数であることを示せばよい。

x は p の倍数でない（このとき p:素数 より x と p は互いに素）ので、
フェルマーの小定理より、

よって、両辺を -t(q-1) 乗（t ≦ 0 に注意）すれば

よって

は p の倍数になる。
同様に、x は q の倍数でもないので、

は q の倍数になる。

以上より、上の命題が示せたこととなる。

• x が「p の倍数であって q の倍数でない」とき

の両辺を 1-t(p-1)(q-1) 乗すれば

を得る。
一方、x は q の倍数でないので、上の議論より


となる。
これらの結果より

は p の倍数かつ q の倍数となるので、pq（= m ） の倍数となる。
よって（３）の最後の等式が成り立つ。

• x が「p の倍数でなくて q の倍数」とき

上の議論と同様である。

（注意）
一般に

である。なぜなら

より



となるため。

（例）
p = 11, q = 13, m = pq = 143, (p - 1)(q - 1) = 120, e = 7 とする。
送信情報を 1, 7, 4, 5 とすれば x^e mod m は

（暗号化された情報）

103×7 - 6×120 = 1 より s = 103 なので、

とすれば情報を復元できる。