この記事の目的

RSA 暗号という暗号方式があります¹。RSA 暗号は非常に強力であるため様々な場所で使われており、暗号方式の中でもかなり有名な部類に入ると思います。ちなみに "RSA" という名前は開発者三名の名前 (Ronald Linn Rivest, Adi Shamir, Leonard Max Adleman) からとられたそうです。

しかしそのアイデアにはなかなか高度な数学が用いられており、難解を極めます。そんなわけで、RSA 暗号の原理と正しさを私が納得できるまで徹底的に証明していきます。

証明の概略

ユークリッドの互除法、及びその拡張の正しさを証明する
フェルマーの小定理を証明する
中国剰余定理を証明する
オイラーのトーシェント関数の性質を証明する
RSA 暗号の正しさと解読困難性を証明する

ユークリッドの互除法

ユークリッドの互除法は、与えられた二整数の最大公約数 (Greatest Common Divisor, 略して GCD) を求めるアルゴリズムです。名前からもわかる通りユークリッドというおじさんが考えました。

その主張は以下の通りになります。

定理:
$a, b \in \mathbb{Z}$ の最大公約数を $\gcd(a, b)$ と表記する。ここで

\mathrm{gcd}(a, b) = \left\{
    \begin{array}{ll}
        a & (b = 0) \\
        \mathrm{gcd}(b, a \bmod b) & (b \neq 0)
    \end{array}
\right.

が成り立つ。

証明:
$a, b \in \mathbb{Z}\ (b \neq 0)$ に対し、$a = bq + r$ かつ $0 \le r < \lvert b \rvert$ を満たす $q, r$ が一意に定まる（商と剰余の定義）。ここで $d_0$ を $b$ と $r$ の任意の公約数とする。このとき $d_0$ は $bq + r = a$ を割り切る。よって $b$ と $r$ の公約数は全て $a$ と $b$ の公約数である。次に $d_1$ を $a$ と $b$ の任意の公約数とする。このとき $d_1$ は $a - bq = r$ を割り切る。よって $a$ と $b$ の公約数は全て $b$ と $r$ の公約数である。以上より、$a$ と $b$ の公約数の集合と $b$ と $r$ の公約数の集合は等しい。よって $\gcd(a, b) = \gcd(b, r)$ である。

ここで $r$ の定義より $0 \le r < \lvert b \rvert$ である。従って $\gcd(\cdot, \cdot)$ の第二引数の絶対値は毎回かならず小さくなるため、高々 $\lvert b \rvert$ 回以内に $0$ になる²。よって $a$ と $b$ の最大公約数が求められた。（証明終）

この定義だと $\gcd(0, 0) = 0$ になりますが、これについてはこちらの記事もご覧ください。

プログラムとして実装するとこのようになります。

def euclidean_algorithm(a, b):
    return a if b == 0 else euclidean_algorithm(b, a % b)

プログラムで計算するときは上に書いた定義をそのまま再帰関数として定義するだけですが、手計算の時はこんな感じでやるとやりやすいです。例として $1071$ と $1029$ の最大公約数を求めます。

\displaylines{
  1071 = 1029 \times 1 + 42 \\
  1029 = 42 \times 24 + 21 \\
  42 = 21 \times 2 + 0 \\
  \therefore \gcd (1071, 1029) = 21
}

拡張ユークリッドの互除法

このユークリッドの互除法をつよくした拡張ユークリッドの互除法というものがあります。拡張ユークリッドの互除法はベズーの補題の解を求めることができます。

定理:
$a, b \in \mathbb{Z}$ に対し、ベズーの等式

ax + by = \gcd(a, b)

には整数解が存在する。

証明:
表記の便宜のため $r_0 := a, r_1 := b$ とする。ユークリッドの互除法を用いて $\gcd(r_0, r_1)$ を計算する過程で以下のような等式群が得られたとする。

\displaylines{
  r_0 = r_1q_0 + r_2 \\
  r_1 = r_2q_1 + r_3 \\
  \vdots \\
  r_{n - 1} = r_nq_{n - 1} + 0
}

この等式群は以下のように表せる。

\displaylines{
  \begin{pmatrix}
    r_0 \\
    r_1
  \end{pmatrix}
  =
  \begin{pmatrix}
    q_0 & 1 \\
    1 & 0
  \end{pmatrix}
  \begin{pmatrix}
    r_1 \\
    r_2
  \end{pmatrix} \\
  \begin{pmatrix}
    r_1 \\
    r_2
  \end{pmatrix}
  =
  \begin{pmatrix}
    q_1 & 1 \\
    1 & 0
  \end{pmatrix}
  \begin{pmatrix}
    r_2 \\
    r_3
  \end{pmatrix} \\
  \vdots \\
  \begin{pmatrix}
    r_{n - 1} \\
    r_n
  \end{pmatrix}
  =
  \begin{pmatrix}
    q_{n - 1} & 1 \\
    1 & 0
  \end{pmatrix}
  \begin{pmatrix}
    r_n \\
    0
  \end{pmatrix}
}

すなわちこのようになる。

\begin{pmatrix}
  r_0 \\
  r_1
\end{pmatrix}
=
\begin{pmatrix}
  q_0 & 1 \\
  1 & 0
\end{pmatrix}
\begin{pmatrix}
  q_1 & 1 \\
  1 & 0
\end{pmatrix}
\cdots
\begin{pmatrix}
  q_{n - 1} & 1 \\
  1 & 0
\end{pmatrix}
\begin{pmatrix}
  r_n \\
  0
\end{pmatrix}

また、任意の $k\ (0 \le k < n)$ に対し

\begin{pmatrix}
  q_k & 1 \\
  1 & 0
\end{pmatrix}^{-1}
=
\begin{pmatrix}
  0 & 1 \\
  1 & -q_k
\end{pmatrix}

であるので、

\begin{pmatrix}
  0 & 1 \\
  1 & -q_{n - 1}
\end{pmatrix}
\begin{pmatrix}
  0 & 1 \\
  1 & -q_{n - 2}
\end{pmatrix}
\cdots
\begin{pmatrix}
  0 & 1 \\
  1 & -q_0
\end{pmatrix}
\begin{pmatrix}
  r_0 \\
  r_1
\end{pmatrix}
=
\begin{pmatrix}
  r_n \\
  0
\end{pmatrix}

となる。ここで

\begin{pmatrix}
  x & y \\
  * & *
\end{pmatrix}
:=
\begin{pmatrix}
  0 & 1 \\
  1 & -q_{n - 1}
\end{pmatrix}
\begin{pmatrix}
  0 & 1 \\
  1 & -q_{n - 2}
\end{pmatrix}
\cdots
\begin{pmatrix}
  0 & 1 \\
  1 & -q_0
\end{pmatrix}

と置くと、上式は

\displaylines{
  \begin{pmatrix}
    x & y \\
    * & *
  \end{pmatrix}
  \begin{pmatrix}
    r_0 \\
    r_1
  \end{pmatrix}
  =
  \begin{pmatrix}
    r_n \\
    0
  \end{pmatrix}\\
  \therefore
  r_0x + r_1y = r_n
}

となり、さらに $r_0 = a, r_1 = b, r_n = \gcd(r_0, r_1)$ であったので

ax + by = \gcd(a, b)

となる。よって、$x, y$ は条件を満たす解になっている。（証明終）

さらに明らかに以下が成り立ちます。

\begin{align}
  \begin{pmatrix}
    x & y
  \end{pmatrix}
  & =
  \begin{pmatrix}
    1 & 0
  \end{pmatrix}
  \begin{pmatrix}
    x & y \\
    * & * \\
  \end{pmatrix} \\
  & =
  \begin{pmatrix}
    1 & 0
  \end{pmatrix}
  \begin{pmatrix}
    0 & 1 \\
    1 & -q_{n - 1}
  \end{pmatrix}
  \begin{pmatrix}
    0 & 1 \\
    1 & -q_{n - 2}
  \end{pmatrix}
  \cdots
  \begin{pmatrix}
    0 & 1 \\
    1 & -q_0
  \end{pmatrix}
\end{align}

よって拡張ユークリッドの互除法はこのように実装できます。

def extended_euclidean_algorithm(a, b):
    if b == 0:
        return 1, 0
    else:
        q = a // b
        x, y = extended_euclidean_algorithm(b, a % b)
        return y, x - y * q

さてかなりの労力を割いて拡張ユークリッドの互除法の正しさを証明しましたが、それはモジュラ逆数を求めるためです。

定義:
合同式 $xy \equiv 1 \pmod{m}$ が満たされるとき、$y$ を「法 $m$ における $x$ のモジュラ逆数」といい、

x^{-1} \pmod{m}

と表記する。

要するに「掛け算したら $1$ と等しくなる（合同になる）」から逆数と呼ばれるわけです。これが拡張ユークリッドの互除法で求まることを証明します。

証明:
$a, m$ は互いに素である、すなわち $\gcd(a, m) = 1$ であるとする。このときベズーの補題より、不定方程式 $ax + my = 1$ には解が存在する。このとき

\displaylines{
  ax + my = 1 \\
  \therefore ax + my \equiv 1 \pmod{m} \\
  \therefore ax \equiv 1 \pmod{m}
}

が成り立つので、モジュラ逆数の定義より $x = a^{-1} \pmod{m}$ である。（証明終）

ここからわかるように、「$a$ と $m$ が互いに素であること」は「$a^{-1} \pmod{m}$ が定義できること」の十分条件です。実際には必要条件であることも証明できます。

証明:
合同式の定義より、$ax \equiv 1 \pmod{m}$ ならば $ax - 1$ は $m$ の倍数である。つまり適当な整数 $k$ が存在し $ax - 1 = km$ が満たされる。ここで $g := \gcd(a, m)$ とし、$a' := \frac{a}{g}, m' := \frac{m}{g}$ とする。これを代入すると $ga'x - 1 = kgm' \therefore g(a'x - km') = 1$ となる。この等式が成り立つには少なくとも $g = 1$ でなければならないので、「$a$ と $m$ が互いに素であること」は「$a^{-1} \pmod{m}$ が定義できること」の必要条件である。（証明終）

結局「$a$ と $m$ が互いに素であること」は「$a^{-1} \pmod{m}$ が定義できること」と同値ということになります。よってモジュラ逆数を求める関数はこのように実装できます。

# 本当は拡張ユークリッドの互除法を計算するときに一緒に最大公約数も求めた方が
# 計算も減ってよいのですが、各関数の実装が煩雑になるのを避けるため、
# 今回はそのような実装は行いません。

def euclidean_algorithm(a, b):
    return a if b == 0 else euclidean_algorithm(b, a % b)

def extended_euclidean_algorithm(a, b):
    if b == 0:
        return 1, 0
    else:
        q = a // b
        x, y = extended_euclidean_algorithm(b, a % b)
        return y, x - y * q

def modular_inverse(a, m):
    if euclidean_algorithm(a, m) != 1:
        raise Exception(f'{a}^-1 mod {m} is undefined')
    return extended_euclidean_algorithm(a, m)[0]

フェルマーの小定理

フェルマーの小定理はその名の通りフェルマーというおじさんに由来します。フェルマーの最終定理で有名な人ですね。

フェルマーの小定理は以下を主張します。

定理:
$p$ が素数で $a$ と $p$ が互いに素であるとき、

a^{p - 1} \equiv 1 \pmod{p}

が成り立つ。

証明:
集合 $S, S'$ を以下のように定める。

\displaylines{
  S := \{ 1, 2, \ldots, p - 1 \} \\
  S' := \{ a, 2a, \ldots, (p - 1)a \}
}

ここで $S$ の要素が全て $p$ を法として互いに非合同であることは言うまでもないが、同様に $S'$ の要素も全て $p$ を法として互いに非合同である。なぜならもし $S'$ のある異なる要素 $ka, la\ (k \neq l)$ について $ka \equiv la \pmod{p}$ であるならば、$a, p$ が互いに素であることから両辺を $a$ で割って $k \equiv l \pmod{p}$ となり、かつ $k, l$ はともに $p$ 未満であることから $k = l$ となり、矛盾するためである。

このことから $S$ と $S'$ はともに「$p$ で割ったあまりが $1$ である数」、「$p$ で割ったあまりが $2$ である数」・・・「$p$ で割ったあまりが $p-1$ である数」のみをすべて含むので、$S$ の要素の総乗と $S'$ の要素の総乗は $p$ を法として合同である。よって以下が成り立つ。

(p - 1)! \equiv a^{p - 1} (p - 1)! \pmod{p}

$p$ は素数であるから $p$ と $(p - 1)!$ は互いに素であり、従って両辺を $(p - 1)!$ で割って $a^{p - 1} \equiv 1 \pmod{p}$ を得る。（証明終）

これでフェルマーの小定理も証明できました。お次は中国剰余定理です。

中国剰余定理

中国剰余定理は、整数の剰余に関する定理です。南北朝時代の中国で書かれた算術書「孫子算経」に由来するため、このような名前が付いたそうです。定理の名前に国名が入っているのは珍しいですね。

中国剰余定理は以下を主張します。

定理:
整数 $m_1, m_2, \ldots, m_n$ がすべて互いに素ならば、任意の整数 $a_1, a_2, \ldots, a_n$ に対し

\displaylines{
  x \equiv a_1 \pmod{m_1} \\
  x \equiv a_2 \pmod{m_2} \\
  \vdots \\
  x \equiv a_n \pmod{m_n}
}

を満たす整数 $x$ が $m_1m_2 \cdots m_n$ を法として一意に定まる。

証明:
まず各 $k\ (1 \le k \le n)$ について

M_k := \frac{m_1m_2 \cdots m_n}{m_k}

とする。このとき各 $m$ が全て互いに素であることから、任意の $k$ について $m_k$ と $M_k$ も互いに素である。従って $M_k^{-1} \pmod{m_k}$ が定義できるのでこれを $t_k$ と置く。このとき

x := a_1M_1t_1 + a_2M_2t_2 + \cdots + a_nM_nt_n

は中国剰余定理に対する解になっている。

例として $x \equiv a_1 \pmod{m_1}$ が満たされるかを確認する。$x$ の第 $2$ 項から第 $n$ 項は全て $m_1$ の倍数であるので、$x \equiv a_1 M_1 t_1 \pmod{m_1}$ である。さらに各 $t_k$ の定義より $M_1 t_1 \equiv 1 \pmod{m_1}$ なので、$x \equiv a_1 \pmod{m_1}$ である。同じように全ての $k$ に対し $x \equiv a_k \pmod{m_k}$ を証明できる。

次にこの $x$ が法 $m_1m_2 \cdots m_n$ のもとで一意に定まることを証明する。$x, y$ をそれぞれ中国剰余定理に対する解とすると、各 $k$ に対し $x - y \equiv 0 \pmod{m_k}$ が成り立つ。従って $x - y$ は各 $k$ に対し $m_k$ で割れる。また、$m_1, m_2, \ldots, m_n$ はすべて互いに素なので、従って $x - y$ は $m_1m_2 \cdots m_n$ で割れる。よって $x \equiv y \pmod{m_1m_2 \cdots m_n}$である。（証明終）

ちなみにこの証明はガウスという数学つよつよおじさんの証明だそうです。³

ガウスの証明には解の構成法まで書いてあるので、そのまま簡単に実装することができます。

import math

def euclidean_algorithm(a, b):
    return a if b == 0 else euclidean_algorithm(b, a % b)

def extended_euclidean_algorithm(a, b):
    if b == 0:
        return 1, 0
    else:
        q = a // b
        x, y = extended_euclidean_algorithm(b, a % b)
        return y, x - y * q

def modular_inverse(a, m):
    if euclidean_algorithm(a, m) != 1:
        raise Exception(f'{a}^-1 mod {m} is undefined')
    return extended_euclidean_algorithm(a, m)[0]

def chinese_remainder_theorem(*equiv_to):
    """
    @param equiv_to 可変個のタプル(合同な値, 法)
    """
    M = math.prod([m for _, m in equiv_to])
    return sum([a * M // m * modular_inverse(M // m, m) for a, m in equiv_to])

これで中国剰余定理も証明できました。最後にオイラーのトーシェント関数を見ていきます。

オイラーのトーシェント関数

オイラーのトーシェント関数もやはりオイラーというおじさんに由来します。

オイラーのトーシェント関数の定義を確認した後、その計算法について見ていきます。

定義:
オイラーのトーシェント関数 $\varphi(n)$ は、$n$ 以下の正整数で $n$ と互いに素なものの個数を表す。

定理:
素数 $p$ と任意の正整数 $k$ に対し

\varphi(p^k) = p^k - p^{k - 1}

が成り立つ。

証明:
$p$ は素数であるので、$p$ と互いに素でないことは $p$ の倍数であることと同値である。また、$p^k$ 以下の正整数の中に $p$ の倍数は $p, 2p, \ldots, p^{k - 1}p$ の $p^{k - 1}$ 個存在するため、$p^k$ 以下の正整数の中に $p$ と互いに素であるものは $p^k - p^{k - 1}$ 個存在する。（証明終）

定理:
正整数 $m, n$ が互いに素であるとき

\varphi(mn) = \varphi(m)\varphi(n)

が成り立つ。

証明:
$\varphi(1) = 1$ であるので、$m$ と $n$ のどちらか片方以上が $1$ であるならば与命題が成り立つことは言うまでもない。以降、$m$ と $n$ がともに $2$ 以上である場合を考える。

まず集合 $M$ を $m$ 以下で $m$ と互いに素な正整数の集合とする。同様に集合 $N$ を $n$ 以下で $n$ と互いに素な正整数の集合とする。

\displaylines{
  M = \{ m_1, m_2, \ldots, m_{\varphi(m)} \} \\
  N = \{ n_1, n_2, \ldots, n_{\varphi(n)} \}
}

$m, n$ は互いに素であるので、中国剰余定理より任意の $k, l\ (1 \le k \le \lvert M \rvert, 1 \le l \le \lvert N \rvert)$ に対し連立合同式

\left\{
  \begin{align}
    \gamma_{k, l} &\equiv m_k \pmod{m} \\
    \gamma_{k, l} &\equiv n_l \pmod{n}
  \end{align}
\right.

を満たす $\gamma_{k, l}$ が $mn$ を法として一意に定まる。すなわち $1 \le \gamma_{k, l} \le mn$ という条件を課せば $\gamma_{k, l}$ はただ一つ存在する。

ここで $m_k < m$ であることから $\gamma_{k, l} \bmod m = m_k$ である。したがってユークリッドの互除法より

\begin{align}
  \gcd(\gamma_{k, l}, m) &= \gcd(m, \gamma_{k, l} \bmod m) \\
  &= \gcd(m, m_k) \\
  &= 1
\end{align}

であるから、$\gamma_{k, l}$ は $m$ と互いに素である。同様にして $n$ とも互いに素である。したがって $mn$ とも互いに素である。

また、逆に $\gamma\ (1 \le \gamma \le mn)$ が $mn$ と互いに素であるならば $\gamma$ に対し上の連立合同式を満たす $M, N$ の要素は一意に定まる。まず $\gamma$ が $mn$ と互いに素であるならば $\gamma$ は $m$ とも互いに素であるので、

\begin{align}
  \gcd(\gamma, m) &= 1 \\
  \therefore \gcd(\gamma, m) &= \gcd(m, \gamma \bmod m) \\
  &= 1
\end{align}

が成り立つ。すなわち $\gamma \bmod m$ は $m$ と互いに素である。さらにこの $\gamma \bmod m$ は $1$ 以上 $m$ 以下であるので、これは $M$ の要素である。同様にして $\gamma \bmod n$ も $N$ の要素である。ここで $M, N$ はそれぞれ $m, n$ 以下の正整数しか含まないことを考えると $M, N$ の要素はそれぞれ $m, n$ を法として互いに非合同であるので、$\gamma$ に対し要求を満たす $M, N$ の要素はそれぞれ $\gamma \bmod m $ と $\gamma \bmod n$ のみで全てであることがわかる。

従って $mn$ 以下で $mn$ と互いに素であるような正整数の集合と $M \times N$ は互いに他方に対し単射を持つが、このことは二者の間に全単射が存在することと同値である（ベルンシュタインの定理）。よって二者の大きさは等しい。よって $mn$ 以下で $mn$ と互いに素であるような正整数は $\lvert M \times N \rvert = \varphi(m)\varphi(n)$ 個存在する。（証明終）

定理:
正整数 $a$ が $p_1^{e_1} p_2^{e_2} \cdots p_n^{e_n}$ と素因数分解されるとき、

\varphi(a) = a \left(1 - \frac{1}{p_1} \right) \left(1 - \frac{1}{p_2} \right) \cdots \left(1 - \frac{1}{p_n} \right)

が成り立つ。

証明:
$p_1^{e_1}$ と $p_2^{e_2} \cdots p_n^{e_n}$ は互いに素である。従って

\begin{align}
  \varphi(a) & = \varphi(p_1^{e_1} p_2^{e_2} \cdots p_n^{e_n}) \\
  & = \varphi(p_1^{e_1}) \varphi(p_2^{e_2} \cdots p_n^{e_n})
\end{align}

である。以下再帰的に

\varphi(a) = \varphi(p_1^{e_1}) \varphi(p_2^{e_2}) \cdots \varphi(p_n^{e_n})

である。従って

\begin{align}
  \varphi(a) & = \varphi(p_1^{e_1}) \varphi(p_2^{e_2}) \cdots \varphi(p_n^{e_n}) \\
  & = (p_1^{e_1} - p_1^{e_1 - 1}) (p_2^{e_2} - p_2^{e_2 - 1}) \cdots (p_n^{e_n} - p_n^{e_n - 1}) \\
  & = p_1^{e_1} \left(1 - \frac{1}{p_1} \right) p_2^{e_2} \left(1 - \frac{1}{p_2} \right) \cdots p_n^{e_n} \left(1 - \frac{1}{p_n} \right) \\
  & = p_1^{e_1} p_2^{e_2} \cdots p_n^{e_n} \left(1 - \frac{1}{p_1} \right) \left(1 - \frac{1}{p_2} \right) \cdots \left(1 - \frac{1}{p_n} \right) \\
  & = a \left(1 - \frac{1}{p_1} \right) \left(1 - \frac{1}{p_2} \right) \cdots \left(1 - \frac{1}{p_n} \right)
\end{align}

となる。（証明終）

さて、それでは満を持して本題である RSA 暗号に入ります。

RSA 暗号

RSA 暗号での暗号化・復号は以下のように行われます。

定義:
$p, q$ をそれぞれ異なる素数とし、$n := p q$ とする。さらに $e$ を $\varphi(n)$ 以下⁴で $\varphi(n)$ と互いに素であるような適当な正整数とする。また、$e$ と $\varphi(n)$ が互いに素であることから $e^{-1} \pmod{\varphi(n)}$ が定義できるので、これを $d$ とする。RSA 暗号は $\{e, n\}$ を公開鍵、$d$ を秘密鍵として用いる。

$n$ 未満の平文 $a$ を暗号化して暗号文 $b$ を得るには以下のようにする。

b = a^e \bmod{n}

また、暗号文 $b$ を復号して平文 $a$ を得るには以下のようにする。

a = b^d \bmod{n}

それでは RSA 暗号の復号が常に正しく行われることを証明します。つまり、$(a^e)^d \bmod n$ が $a$ に戻ることを証明します。

証明:
まず $a$ が $p$ の倍数であると仮定する。このとき $(a^e)^d$ も明らかに $p$ の倍数であるので、

(a^e)^d \equiv 0 \equiv a \pmod{p}

となる。

次に $a$ が $p$ の倍数でないと仮定する。$p$ は素数であるので、この条件は $a$ と $p$ が互いに素であることと同値である。

$d$ の定義より $e d \equiv 1 \pmod{\varphi(n)}$ なので、適当な整数 $k$ を用いて $ed - 1 = k\varphi(n)$ と表せる。さらに $p, q$ が素数であることと $n = pq$ であることから $\varphi(n) = (p - 1)(q - 1)$ が成り立つので、$ed - 1 = k(p - 1)(q - 1)$ と表せる。よって以下の式が成り立つ。

\begin{align}
  (a^e)^d & = a^{e d} \\
  & = a^{e d - 1} a \\
  & = a^{k(p - 1)(q - 1)} a \\
  & = (a^{p - 1})^{k(q - 1)} a \\
  & \equiv 1^{k(q - 1)} a \\
  & \equiv a \pmod{p}
\end{align}

従って $(a^e)^d$ は $a$ が $p$ の倍数であるか否かにかかわらず、常に $p$ を法として $a$ と合同である。同様に $q$ を法としても $a$ と合同である。よって $(a^e)^d - a$ は $p$ の倍数であるとともに $q$ の倍数であり、さらに $p, q$ は互いに素なので、$(a^e)^d - a$ は $pq = n$ の倍数である。よって $(a^e)^d \equiv a \pmod{n}$ である。定義より平文 $a$ は $n$ 未満であったので、$(a^e)^d \bmod{n}$ は $a$ に一致する。（証明終）

RSA 暗号の安全性

さてめでたく RSA 暗号がきちんと復号できることが証明できました。それでは安全性はどうなのでしょうか。RSA 暗号を解読する方法としては二つ思いつきます。

暗号化することで暗号文と一致する文を見つけ出す。つまり、$x^e \bmod n$ が暗号文と等しくなるような $x$ を計算する。
公開鍵から秘密鍵を割り出す。

まず一つ目の方法ですが、これは離散対数問題として知られています。今まで見てきたとおり RSA 暗号では暗号化にも復号にも「冪の剰余」を計算します。この「冪の剰余」は別名離散冪乗とも呼ばれます。その逆関数なので離散対数というわけですね。この離散対数を計算するのは非常に難しいことが知られています。

EDIT: 記事公開から一年近くたって気づきましたが、$x^e \bmod n$ に対し $x$ を求めるのでこれは対数ではなく冪根でした。この問題になにか名前がついているのかは調べてはみたのですがよくわからなかったです。

では公開鍵から秘密鍵を割り出すのはどうでしょうか。公開鍵を $\{e, n\}$ として、秘密鍵 $d$ の定義は $e^{-1} \pmod{\varphi(n)}$ でした。よって、秘密鍵を求めるのがどれくらい難しいかは $\varphi(n)$ を求めるのがどれくらい難しいかにかかっています。任意の正整数について $\varphi(n)$ が計算できる方法は上に書いた通りですが、この方法を実行するには $n$ の素因数が全てわかる必要があります。従って、$p, q$ が十分に大きいとき $\varphi(n)$ を求めるのは非常に難しくなります。

よって、どちらの方法をとるにしても非常に難しい問題を解く必要があります。逆に言えば上の二つのどちらかでも高速に解く方法が発見されてしまえば、RSA 暗号の安全性は瓦解します。

RSA 暗号の高速化

さっき見た通り RSA 暗号は暗号文 $b$ に対し $b^d \pmod{n}$ で復号できるのですが、ここでさっきも出てきた中国剰余定理を用いるとこの計算を高速化することができます。

定理:
RSA 暗号の生成に用いた素数を $p, q$、秘密鍵を $d$、暗号文を $b$ とする。ここで

\displaylines{
  d_p := d \bmod (p - 1) \\
  d_q := d \bmod (q - 1)
}

と定義すると、

\displaylines{
  x \equiv b^{d_p} \pmod{p} \\
  x \equiv b^{d_q} \pmod{q}
}

を満たす $x$ は $pq$ を法として平文 $b^d$ に合同である。

証明:
まず $b$ が $p$ の倍数であると仮定する。このとき言うまでもなく

b^d \equiv 0 \equiv b^{d_p} \pmod{p}

である。

次に $b$ が $p$ の倍数でないと仮定する。$p$ は素数であるので、この条件は $b$ と $p$ が互いに素であることと同値である。

$d_p$ の定義より $d - d_p = k (p - 1)$ となる整数 $k$ が存在するので、以下が成り立つ。

\begin{align}
  b^d & = b^{(d - d_p)} b^{d_p} \\
  & = b^{k (p - 1)} b^{d_p} \\
  & = (b^{p - 1})^k b^{d_p} \\
  & \equiv 1^k b^{d_p} \\
  & \equiv b^{d_p} \pmod{p}
\end{align}

よって、$b^{d_p}$ は $b$ が $p$ の倍数であるか否かにかかわらず $p$ を法として $b^d$ と合同である。同じことが $q$ についてもいえるので、中国剰余定理より

\displaylines{
  x \equiv b^{d_p} \pmod{p} \\
  x \equiv b^{d_q} \pmod{q}
}

を満たす $x$ は $pq$ を法として $b^d$ と合同である。（証明終）

定義より平文は $pq = n$ 未満だったので、上記のような $x$ を求めてそれを $pq$ で割った剰余を求めれば平文が得られます。$d_p, d_q$ は $p, q$ それぞれより小さくなるのでこっちの方が計算が速くなるそうです。

最後に実装してテストしてみます。

実装

import math

def euclidean_algorithm(a, b):
    return a if b == 0 else euclidean_algorithm(b, a % b)

def extended_euclidean_algorithm(a, b):
    if b == 0:
        return 1, 0
    else:
        q = a // b
        x, y = extended_euclidean_algorithm(b, a % b)
        return y, x - y * q

def modular_inverse(a, m):
    if euclidean_algorithm(a, m) != 1:
        raise Exception(f'{a}^-1 mod {m} is undefined')
    return extended_euclidean_algorithm(a, m)[0]

def chinese_remainder_theorem(*equiv_to):
    """
    @param equiv_to 可変個のタプル(合同な値, 法)
    """
    M = math.prod([m for _, m in equiv_to])
    return sum([a * M // m * modular_inverse(M // m, m) for a, m in equiv_to])

def rsa_generate_key(p, q):
    """
    @todo 素数p, qをこの関数内で自動で生成するようにする
    """
    n = p * q
    phi_n = (p - 1) * (q - 1)
    # ビット長が短くてハミング重みが小さいeだと効率がいいらしい。
    # だから65537がよく用いられる。
    e = 65537
    # dが負になると正常に動作しない場合がある。
    # Pythonでは剰余演算子の評価結果の符号は右側引数のものと等しくなるので、
    # これで必ず正のdが得られる。
    d = modular_inverse(e, phi_n) % phi_n
    return e, n, d

def rsa_encrypt(plain_text, e, n):
    return pow(plain_text, e, n)

def rsa_decrypt(cipher_text, d, n):
    return pow(cipher_text, d, n)

def rsa_decrypt_with_crt(cipher_text, d, p, q):
    dp, dq = d % (p - 1), d % (q - 1)
    return chinese_remainder_theorem(
        # pow(cipher_text, dp) としても数学的には問題はないが、途中計算の結果がデカくなりすぎるので
        # pow(cipher_text, dp, p) として p の剰余を取る。当然だがこれでも数学的に問題はない。
        # q に関しても同様。
        (pow(cipher_text, dp, p), p),
        (pow(cipher_text, dq, q), q)
    ) % (p * q)

if __name__ == '__main__':
    def encode_string_to_int(string, encode='utf_8'):
        '''
        @brief 文字列 string をバイト列へ変換したものを「一塊のビッグエンディアン符号なし整数」とみなして返却する。
        '''
        return int.from_bytes(string.encode(encode), byteorder='big', signed=False)

    def decode_int_to_string(integer, encode='utf-8'):
        '''
        @brief 符号なし整数 integer をビッグエンディアンでバイト列へ切り出したものを文字列へデコードして返却する。
        '''
        return integer.to_bytes((integer.bit_length() + 7) // 8, byteorder='big', signed=False).decode(encode)

    # 暗号界隈では有名なフレーズです。詳しくはググってください。
    plain_text = 'The Magic Words are Squeamish Ossifrage'
    plain_text_in_integer = encode_string_to_int(plain_text)
    # 某映画にのっとって公開鍵 N が 2056 桁になるようにしました。
    p = 89368787611031235520145142340845151884433560524610689750869054596948683850345765088572349720440712241733172594177617961851909087505398854952643366217794504830442233604857036725122257591122777899046541469651798110665002411718350284621810599974409372470841994803013799173244269772447531850604001195335485060074399319295119406587064988459290668116945663768318226054968328375312808613605992207104962556230449115158877309504562169745883137010042296487328020882634402909399982528020971775546018891630218543836133779648987442639345299173781958077078832921557771976562115763743090435306703839760947989047621935201677629042027796471106061751294624275832369444075494710571133829462714104707434806755389741539126984367887090842027723315428578278582800114494168195222102589277286567376884402401935732979032638146554890215014680611829798016608239674092958852188873134161548291576758224247727480998820448086857571744934346067258488139566016245229128284296829609369041758627924586513898278951837383349698299759978823591737005357793405023813633
    q = 52048137929018049294826461400270402689981496361269072262129908663316054180437402787258971200757167260363866763223592090394628127743795494083040982230639313491467565597255001055893753319101222561423949077163908013832482564822744599148433985140790671070747733643273783792635934734529374443349067097411367383202721400800911288124643565011979891455567956603871954204628220250999753175221121012413184505946241941659428616483817239766690932630901926121441145106678588698550025371075487045732474531511072821776312236803945839150311009273860814230454636381808583647687526663568019445553401204217082215395295249273794747199514112278723250564576630418414841054689964405065378228933971780679828405414669557168971576255709039835727518667487453479570276056354451301327594482368840301546782638120213378440535505270641065172462392598564172617678749589297953128420363243752822934208982197436950931344633734515889771701448832890878158782521098132498939969136828808602459552823987698339845203133686093528308218042974703618016461618469459751600127
    e, n, d = rsa_generate_key(p, q)
    cipher_text_in_integer = rsa_encrypt(plain_text_in_integer, e, n)
    decrypted_text_in_integer_without_crt = rsa_decrypt(cipher_text_in_integer, d, n)
    decrypted_text_in_integer_with_crt = rsa_decrypt_with_crt(cipher_text_in_integer, d, p, q)

    print(f'''\
plain text                : {plain_text}
plain text in integer     : {plain_text_in_integer}
public key                : {{
                              e = {e},
                              n = {n}
                            }}
private key               : {d}
cipher text in integer    : {cipher_text_in_integer}

--- without CRT ---
decrypted text in integer : {decrypted_text_in_integer_without_crt}
decrypted text            : {decode_int_to_string(decrypted_text_in_integer_without_crt)}

--- with CRT ---
decrypted text in integer : {decrypted_text_in_integer_with_crt}
decrypted text            : {decode_int_to_string(decrypted_text_in_integer_with_crt)}''')

plain text                : The Magic Words are Squeamish Ossifrage
plain text in integer     : 2751067378439211100332616590463301037463658559722050145674855065594989971250155545264362973029
public key                : {
                              e = 65537,
                              n = 4651478984128073191875673340418213829230850743117452999073972505929143708053677395344051930758390806875389653868797474638145001829702021797075349872072463229184428444301271674456773024195352193676507051030283742940898719618301800187990342960962550079614666896902604453527316053764809932487689931246426244160452636625000082134850576200096606593947495492167141685077465910504791997687473128126318671919025775137727557268174333730259386030138109794575612564066264334586483813075172862714755427590854942311892200368838290554416460224575688724441873177284125115392770903860636260698145058560747559511904050724879389114801967297184522868647363287743098655586863910168144391391672859894446006812682217514372851220784117863263359099060693096839670429774798728374720952582568345946604696494124175708087308911081181004584092874404509953240641170079170415301661110898112448523109989595702036129001128931268102297918165192177984449683432636566105122513640590339772849249036531109084656763523608943780957187252585060770397235451542711608624624005536094349998006728523221590817472107567055700579207150110006617304166987089190877548022938134110852091380413057867615255463108029579253360573471558942513243932845881480251971961158198128052546118189943447482549217824129665569312481547453085532011706046676996942734216083179913076134499564926268620971126069518839823443533015264554806544573714541532625487249874944122318904959711968899551039202874872884487602393910587404756122158446597094689422440059098561380830314272120254467872506399421752762390135299381566520595955774351581280210501845642362272105809579916602796338824666877540096821449089580895403993199547208882969389070693797523100940134125152136109672132435312602843847854721991301209032391407033530310592121712212695270194526176744641890382654589371116683130822523318037084078752975152624120768407677910279182158378974074664993408793308485523376947789869617917331838070688416476956240343013082779629970863502661359307330258757601448307454009550069719312154474301413150614076787650257639206575916373995311587131391
                            }
private key               : 433088557015876567691919964649464284083291136831144211672023135498720339755306765130985624631699661314274801530546137147595416347480686284171594441603768415162173770040227043617120542497215909880129484495579465026250270642703779311642538913099371051250571393333532086842908319881484813281655918953655079449274180824354952182535944824648511427686156178848648832908779727267043666476783512028728756825150606220767101857735321794132211934569826906426909804628413643737838537427479207291841823994985990478465083947245849656881597270097210012611872837142190387935466805855586957944063371032205954012872705761985047108938791895378487854868031963346024200015121894194821506572958600349053352054121898946743109055178367749540458324648188798341634022956281517929452786252938523993563664159286292020854612798501874765246687134284699020929770853408350975390553978648706565159955706799410620328351387593856874135555436532076080093870154354766412461015582569880423179671294397253881541351771076823396728577087985016720645802077075753028607146997203131091489569191460131984376065454929231674422486819816248016286350658655841195234413763508149940084645992619365692355749400103950055514599769460144770366676587184050810347944037919619856979194651545927915022531910767741250334600759024456066811795623446965660822228443957798747400201637585756898111859473054456789650934702741215370501861197919052153382718993526852261023635942130237263846496521664182254879641229554498786580564229245980521478649898131308219084114767050539405763411007236574384594007354691708806066741525259713334074246807641798573055990947686950239876199700265626985222042077970657100915920438047841866743188701453474246081728412421179042788390859876104031616941404884097216239654476715977425875011674446011272265696140134237585595445424312340934835162774555144550546505727196081338254031135845075294272243302124271700640474529014154296853924793572415759818175802726629238791657586335552722160957787473758054177895791487257138867866453987162443584904321243859028297004541072214037942087465476957908434945
cipher text in integer    : 1387009359049412476767789343504113977253753206009457061187488554841535958200186405333133874856288713718528040936150463937818627589681594448382807295011217513630750559731742414867342984438378826904949552940563746608395151141580388416709353499225123965024300730074345716893116479115833774192218884136139479788506110008214895068169269361170630353122803198581408892977429009420724398857180409672141146128968537148682603184930403147838159898559911878802537906551023131755368846931658085519314001664209077348254050053786880060442661802070052608664661689028427744160027685086089554313146060189621188349292285147017688755971645726884711846451875585869894665173557442843891280423137010593804869339889954957708217656369919348119550748471704355399048650693671461009700931315759529325406887556690883203480249822801617480858683011545999526777565201029106214732062429200815453070407846320719332239657558967050465890291475345485566604814962637409576707659721131889167626936608694344164529990321254437238284375150186585683366327020284801873880112128783049979625089388259054522966416259910836464966734263733916504029856366285808886047314424977093677253617982192597228503127179951445371124489804458902409192059235942719859204809026606645320542807325417518840672270085357089496432495645101115128157404640372118732099278390301797270467526537236398271748079427412633460203506696145838460192511826980701306455888172182121601547576799208357540045609714745451801395424582095140169972903065310377348136268099470429332308694100280972479302652656709995257060660243409410437547982734140598355679586078902228593083858139100424131119771501727675756680373421707819047259459490323735178733558574701857441793295790400690859007960477480285491641733203119579608945246252383901001672108472750309483986989767806380919793851344934924131937491345606102424244412534789242325309892528090485110942971855597625804014660942503882821045176428214745391867455329579581345807765466110928356090892231097720917963744691184515147354462022436137504693303562562270997845343044887704992457972710346545187812076

--- without CRT ---
decrypted text in integer : 2751067378439211100332616590463301037463658559722050145674855065594989971250155545264362973029
decrypted text            : The Magic Words are Squeamish Ossifrage

--- with CRT ---
decrypted text in integer : 2751067378439211100332616590463301037463658559722050145674855065594989971250155545264362973029
decrypted text            : The Magic Words are Squeamish Ossifrage

そんなわけで無事ちゃんと計算できていました。

課題

今の実装では RSA 暗号の使用者が適当な素数を決めて入力しなければなりません。これでは不便すぎるので、適当な大きさの素数を自動で生成する仕組みが必要です。実際にはミラー–ラビン素数判定法などの様々な方法で素数が生成されているようです。また余力のある時に調べてみたいと思います。

EDIT: angel_p_57さんから情報をいただきました。FIPS186-4（デジタル署名のための連邦情報処理標準）に素数判定・素数生成についての情報がまとめられています。全編英語でページ数も多いのでなかなか手ごわそうですね...

また、RSA 暗号の原論文¹では上の説明の通り $\varphi(n)$ を計算に用いるのですが、現在ではカーマイケル関数 $\lambda(n)$ を用いるのが一般的なようです。カーマイケル関数 $\lambda(n)$ は $n$ と互いに素な全ての正整数 $a$ に対し $a^m \equiv 1 \pmod{n}$ が成り立つような最小の $m$ を返してくれる関数です。こちらもまたいつか調べたいと思います。

R. L. Rivest, A. Shamir, L. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM, Vol. 21, No. 2, p. 120–126, 1978. ↩ ↩²
実際には「$a, b$ のうち小さい方を十進表記したときの桁数を $m$ として、$5m$ 回以内に計算が終わる」ことが証明できます（ラメの定理）。 ↩
Johann Carl Friedrich Gauß. Disquisitiones Arithmeticae. Gerhard Fleischer, 1801. ↩
$e$ が $\varphi(n)$ 超であったとしても計算自体は正しく行われます。これは計算時間を短くするための取り決めです。(参考1)(参考2) ↩

RSA 暗号の正しさを徹底的に証明する

この記事の目的

証明の概略

ユークリッドの互除法

拡張ユークリッドの互除法

フェルマーの小定理

中国剰余定理

オイラーのトーシェント関数

RSA 暗号

RSA 暗号の安全性

RSA 暗号の高速化

実装

課題