RSA暗号とは
RSA暗号とは、公開鍵暗号（非対象鍵暗号）の一種で、桁数が大きい合成数の素因数分解が困難であることを安全性の根拠とした暗号化方式です。RSAは、発明者であるリベスト（Rivest）、シャミア（Shamir）、エーデルマン（Adleman）の３人の頭文字をつなげたものです。
暗号化と複合化
送信者は受信者の公開鍵（暗号化鍵）で平文から暗号文を作成し、受信者は自分の秘密鍵（複合化鍵）で暗号文を平文に戻します。平文と暗号文、及び、暗号化鍵と複合化鍵の関係は以下で表されます。
| 送信者（暗号化） | 受信者（複合化） |
| 平文（$M$）→ 暗号文（$C$） | 暗号文（$C$）→ 平文（$M$） |
| 暗号化鍵（$e,n$） | 複合化鍵（$d,n$） |
| $C=M^e\pmod{n}$ －① | $M=C^d\pmod{n}$ －② |
鍵の作成
暗号化鍵と複合化鍵は以下のように作成します。
- ２つの大きな素数 $p$ と $q$ を適当に選択し、$n=pq$ を計算する。
このとき、$M\lt n$ とする。 - $(p-1)(q-1)$ より小さく、互いに素である奇数 $e$ を適当に選択する。
- $ed$ を $(p-1)(q-1)$ で割って余りが１になる数 $d$ を求める。
これを式で書くと、$ed\pmod{(p-1)(q-1)}=1$ となります。 - 暗号化鍵（$e,n$）を公開する（公開鍵）。
暗号化鍵の（$e,n$）は公開されているので、$p$ と $q$ が求めることができれば、複合化鍵 $d$ を得ることができます。しかし、$n$ から$p$ と $q$ を求めること（$n=pq$）は計算量的に困難とされています。
複合化できることの証明
暗号化鍵と複合化鍵で、以下の条件を仮定し、
$$ed\pmod{(p-1)(q-1)}=1 －③$$
①で求めた暗号文（$C$）に対し、②により平文（$M$）に戻せること（次式）を証明します。
$$C^d\pmod{n}=M^{ed}\pmod{n}=M －④$$
１つ目のイコール
④の１つ目のイコールが成り立つことを示します。①より、
$$C^d\pmod{n}=(M^e\pmod{n})^d\pmod{n}$$
任意の整数 $\alpha,\beta$ に対し、$M^e\equiv\alpha n+\beta$ と置くと、この右辺は、
$$((\alpha n+\beta)\pmod{n})^d\pmod{n}=\beta^d\pmod{n}$$
一方、
$$M^{ed}\pmod{n}=(\alpha n+\beta)^d\pmod{n}$$$$=\beta^d\pmod{n}$$
であることから、１つ目のイコールは成り立つことが分かります。
２つ目のイコール
④の２つ目のイコールが成り立つことを示します。③より、ある整数 $k$ に対し $ed=1+k(p-1)$ であるため、
$$M^{ed}\pmod{p}=MM^{k(p-1)}\pmod{p}$$$$=MM^{p-1}\cdots M^{p-1}\pmod{p}$$$$=M\pmod{p}$$
となります。最後の項で、フェルマーの小定理 $M^{p-1}\pmod{p}=1$ を使っています。従って、以下が得られます。
$$(M^{ed}-M)\pmod{p}=0$$
$q$ についても同様に考えると以下になります。
$$(M^{ed}-M)\pmod{q}=0$$
$p$ と $q$ は素数であるため以下が成り立つことが分かります。
$$(M^{ed}-M)\pmod{pq}=0$$
②より $M\lt pq$ であるため、
$$M^{ed}\pmod{pq}=M$$
となり、２つ目のイコールが成り立つことが分かります。
