RSA暗号は、公開鍵暗号の一種である。公開鍵暗号とは、暗号化と復号に異なる鍵を用いる暗号のことである。RSA暗号は、1977年にロナルド・リベスト、アディ・シャミア、レナード・アドルマンによって発明された。
RSA暗号は、以下の手順で暗号化と復号を行う。
- 2つの素数 $p$ と $q$ を選ぶ。
-
$n=pq$とする。
-
$\phi(n)=(p-1)(q-1)$とする。
-
$\phi(n)$と互いに素な $e$ を選ぶ。
-
$ed\equiv 1\pmod{\phi(n)}$となる$d$を求める。
$d\times e = x\times \phi(n) + 1$となる整数 $d,x$ が存在する。
このとき、 $(n,e)$ が公開鍵、 $d$ が秘密鍵である。
平文を $a$ とし、 $0\leq a< n$ の整数とする。
$a^e\equiv b\pmod{n}$となる $b$ を求める。このときの $b$ が暗号文である。ここで、 $b$ は $0\leq b< n$ を満たす整数である。
$b^d\equiv a^{\prime}\pmod{n}$となる $a^{\prime}$ を求める。このとき、 $a^{\prime}=a$ となり、平文に復号できる。この理由については、以下の証明を参照。
RSA暗号が完全性を持つことを証明する。
復号化の過程より
$a^{\prime}\equiv b^d \pmod{n} = (a^e)^d = a^{ed} = a^{1+x\phi(n)}$
となる。
(i) $a$と $n$ が互いに素のとき、 $a$ と $p,q$ も互いに素であるから、フェルマーの小定理より
$a^{\phi(n)} = (a^{p-1})^{q-1}\equiv 1^{q-1} = 1\pmod{p}$
$a^{\phi(n)} = (a^{q-1})^{p-1}\equiv 1^{p-1} = 1\pmod{q}$
となる。
よって、 $a^{\phi(n)}\equiv 1\pmod{n}$ である。
以上より
$a^{\prime}\equiv a^{1+x\phi(n)}\equiv a\times (a^{\phi(n)})^x\equiv a\times 1^x\equiv a\pmod{n}$
となり、 $0 \leq a^{\prime}, a < n$ であるから、 $a^{\prime}=a$ である。
(ii) $a$と $n$ が互いに素でないとき、 $a$ と $p,q$ も互いに素でない。よって、 $a$ は $p$ の倍数または $q$ の倍数である。つまり、 $a = kp$ または $a = kq$ となる整数 $k$ が存在する。
(ii-1) ここで、 $a$ が $p$ の倍数だが、 $q$ の倍数でないとする。このとき、 $a\equiv 0\pmod{p}$ であり、 $a\equiv a\pmod{q}$ である。
また、 $a$ と $q$ は互いに素であるから、フェルマーの小定理より
$a^{\prime} = a\times (a^{p-1})^{(q-1)x}\equiv a\times 1^{(q-1)x} = a\pmod{q}$
となる。さらに、
$a^{\prime} = a\times (kp)^{x\phi(n)}\equiv a\times 0^{p-1} = 0\pmod{p}$
となる。以上の結果より中国の剰余定理の条件を満たし、 $a^{\prime}$ と $a$ が $n(=pq)$ を法として一意に決まることがわかるので、 $a^{\prime}=a$ である。
(ii-2) $a$が $q$ の倍数だが、 $p$ の倍数でないとする。このとき、 $a\equiv a\pmod{p}$ であり、 $a\equiv 0\pmod{q}$ である。
(ii-1)と同様に、 $a^{\prime}=a$ である。
(ii-3) $a$が $p$ の倍数かつ $q$ の倍数であるとする。このとき、 $a=kpq$ となる整数 $k$ が存在する。つまり、 $a\equiv 0\pmod{n}$ である。
このとき、
$a^{\prime} = a\times (a^{p-1})^{(q-1)x}\equiv a\times 0^{(q-1)x} = 0\pmod{q}$
$a^{\prime} = a\times (a^{q-1})^{(p-1)x}\equiv a\times 0^{(p-1)x} = 0\pmod{p}$
であるから、 $a^{\prime}\equiv 0\pmod{n}$ である。よって、 $a^{\prime}=a$ である。
以上より、 $a^{\prime}=a$ である。