RSA暗号の仕組み

RSA 暗号とは

公開鍵暗号方式の 1 つ。

• $m$: 平文
• $c$: 暗号文
• $e$: 公開鍵
• $d$: 秘密鍵

とする。

メッセージ送信者と受信者間で暗号化通信を行う際、送信者側で平文 $m$ を暗号化（これを $E(m)$ と書く）する。一方受信者側で暗号文 $c$ を復号（これを $D(c)$ と書く）する。このとき $D(E(m)) = m$ は、平文を暗号化し、その暗号文から元の平文を復号できたことを意味する。

RSA 暗号は大きな素数 $p,\ q$ を用いて $n = pq$ の mod 計算で暗号化・復号を行う。平文 $m$ を

$$
E(m) = (m \bmod n)^e
$$

で暗号化し、暗号文 $c$ を

$$
D(c) = (c \bmod n)^d
$$

で復号する。すなわち RSA 暗号において平文を暗号化し、その暗号文から元の平文を復号できることは

$$
m^{ed} \equiv m \pmod{n}
$$

を意味する。

RSA 暗号で使われる数学

以下、$(a,\ b)$ で整数 $a,\ b$ の最大公約数を表す。$\phi(n)$ を $n$ と互い素であるような $n$ 以下の自然数の個数とする。$\phi$ をオイラー関数という。RSA 暗号で使われる数学ではオイラーの定理「 $(a,\ b) = 1$ ならば

$$
a^{\phi(b)} \equiv 1 \pmod{b}
$$

が成り立つ」が重要である。

参考:

$\phi$ をオイラー関数、 $p,\ q$ を異なる奇素数とし、$n := pq$ とおく。$(e,\ \phi(n)) = 1,\ 1\lt e \lt \phi(n)$ となる $e$ を選ぶ（※）。また

$$
ed \equiv 1 \pmod{\phi(n)},\ 1\lt d \lt \phi(n)
$$

となる $d$ を選ぶ（※）。このとき $1\le m \lt n$ に対して

$$
m^{ed} \equiv m \pmod{n}
$$

が成り立つ。

【証明】

• $(m, n) = 1$ の場合

オイラーの定理により $m^{\phi(n)} \equiv 1 \pmod{n}$ だから成り立つ。

• $(m, n) = p$ の場合

$m\equiv 0 \pmod{p}$ だから $m^{ed} \equiv m \pmod{p}$ となる。また、オイラーの定理より $m^{q - 1} \equiv 1 \pmod{q}$ だから $m^{\phi(n)} \equiv 1 \pmod{q}$ となる。よって $m^{ed} \equiv m \pmod{q}$ となる。$(p,\ q) = 1$ だから $m^{ed} \equiv m \pmod{n}$ となる。

• $(m, n) = q$ の場合

$(m, n) = p$ の場合において $p$ と $q$ を入れ替える。

※このような $e,\ d$ は必ず存在する。$e,\ d$ の候補は $\phi(\phi(n)) - 1$ 個ある。ここで $p,\ q$ は奇素数だから

$$
\displaystyle
\phi(\phi(n)) = \phi((p-1)(q-1)) = 2^k\left(1 - \frac{1}{2}\right)l,\ (k \ge 2,\ l \ge 1)
$$

と表せる。よって $\phi(\phi(n)) - 1\ge 1$ である。

例

ステップ1: 素数 p と q を決める

$p = 5,\ q = 3$ とする。このとき $n = 15$ 、$\phi(n) = (p - 1)(q - 1) = 8$ である。

ステップ2: 公開鍵 e と秘密鍵 d を生成する

まずは公開鍵 $e$ を決める。 $1 \lt e \lt 8$ を満たし、かつ $(e, 8) = 1$ となるように決める。そこで $e = 3$ とする。

このとき秘密鍵は $ed\equiv 1 \pmod 8$ を解いて $d = 7$ と決まる。

ステップ3: 暗号化と復号

平文を $m = 2$ とする。このとき暗号文は

$$
E(2) = 2^3 \mod 15 = 8 \mod 15
$$

となる。これを復号すると

$$
D(8) = 8^7 \mod 15 = 2 \mod 15
$$

となる。

第三者が秘密鍵を知るには

メッセージ受信者は $n,\ e$ を送信者に送信する。$n$ と $e$ は意図しない第三者に知られても問題ない。なぜなら $n,\ e$ から $d$ を計算することは難しいからだ。$d$ を知るためには $\bmod{\phi(n)}$ の世界を考える必要があるが、$\bmod{\phi(n)}$ の世界は $n$ を素因数分解しない限りわからない。そして大きな自然数 $n$ の素因数分解は難しい。

$n$ を素因数分解できた場合、簡単に秘密鍵 $d$ を知ることができる。$n$ の素因数分解から $\phi(n)$ がわかり、第三者はすでに $n,\ e$ を知っているため、次の式から $d$ を求めることができる。

$$
ed \equiv 1 \pmod{\phi(n)}
$$

ユークリッドの互除法を繰り返し使うことでこの式から $d$ を求めるのは素因数分解よりもはるかに簡単である（Wikipedia ユークリッドの互除法 計算量）。

参考