概要
この記事では、RSA暗号の数学的原理を解説している。
目次
1. はじめに
インターネット通信は、私たちの日常生活から社会基盤まで広く利用されている。そこでは、個人情報や金融取引、企業の機密データなど多様な情報がやり取りされるため、安全性を確保する仕組みが欠かせない。その中心的な役割を担うのが暗号技術である。その中でも、広く利用されている公開鍵暗号方式の１つがRSA暗号である。
本記事では、RSA暗号の仕組みと、その高速化技術について解説する。
2. RSA暗号の数学的基礎
2.1. 剰余演算
ここでは剰余演算について説明する。
剰余演算というのは、つまり割り算の余りに着目した演算のことである。プログラミング言語では % がよく用いられる。
例えば、10 % 3 について計算すると、答えは1となる。これは、10を3で割ると商は3で、余りは1となることから分かる。
以下のように、Python で実際に計算して結果を確認してみる：
print(10 % 3) # 出力: 1（10 ÷ 3 = 3 余り 1）
print(5 % 3) # 出力: 2（5 ÷ 3 = 1 余り 2）
print(12 % 3) # 出力: 0（12 ÷ 3 = 4 余り 0）
剰余演算において、10 と 1 は法3の元で合同であるという。これは10と1を3で割った余りはともに1であることから。式で表すと、
$$
10 \equiv 1 \pmod{3}
$$
と表す。
ここまでの話を一般化すると、$n$ を2以上の整数とする。整数 $a, b$ が法 $n$ の元で合同であるとは、 を で割った余りと、 を で割った余りが等しいことを意味する。これを合同記号（$\equiv$）を使って次のように表す。
$$
a \equiv b \pmod{n}
$$
この時、$a - b$ は $n$ の倍数である。
2.2. オイラーのトーシェント関数
2.2.1. 定義と性質
ここではオイラーのトーシェント関数について説明する。
初めに、1から10の中で、10と互いに素である数の集合について考える。10と互いに素である数とは、$\gcd(10, n) = 1$ （=10との最大公約数が1）となる $n$ のことを指す。これは、
$$
{1, 3, 7, 9 }
$$
である。この集合のいずれの値も、10との最大公約数が1となるので、互いに素であるという条件を満たす。この時の集合の個数は4である。
ここまでの話を一般化すると、整数 $n$ について、$1, 2, ..., n$ までの整数と互いに素である者の個数を $\phi(n)$ という記号で表し、これをオイラー関数という。先ほどの例（ $n = 10$ のとき）では、
$$
\phi(10) = 4
$$
である。
2.2.2. 素数に対するオイラー関数
$p$ を素数とすると、$1$ から $p - 1$ までの全ての整数が $p$ と互いに素になるため、
$$
\phi(p) = p - 1
$$
が成立する。このとき、 $p$ は含まない。$\gcd(p, p) = p$ となり、互いに素ではないためである。
2.2.3. 素数の積に対するオイラー関数
さらに、2つの異なる素数 $p, q$ に対して、$pq$ に対するオイラー関数は以下のようになる。
\begin{align*}
\phi(pq) &= \phi(p) \cdot \phi(q) \\
&= (p - 1) (q - 1)
\end{align*}
たとえば、$p = 3$、$q = 5$ のとき、
\phi(3) = 2, \quad \phi(5) = 4
より、
\begin{align*}
\phi(15) &= \phi(3) \cdot \phi(5) \\
&= (3 - 1) (5 - 1) \\
&= 2 \cdot 4 \\
&= 8
\end{align*}
と求めることができた。15と互いに素となる集合について考えると、${ 1, 2, 4, 7, 8, 11, 13, 14}$ となり、8個であることが確認できた。
この性質は、RSA暗号で公開モジュラスと呼ばれる値を生成するのに使われる性質である。この公開モジュラスとは、公開鍵・秘密鍵に含まれる値で、暗号の根幹をなす。
2.3. オイラーの定理
ここではオイラーの定理について説明する。
オイラーの定理は、$\gcd(a, n) = 1$ となる $a, n$ について以下の式が成立する。
$$
a ^ {\phi(n)} \equiv 1 \pmod{n}
$$
この式は、互いに素となる $a, n$ について $a ^ {\phi(n)}$ と $1$ が法 $n$ の元で合同であることを示している。
例として、$a = 11$、$n = 7$ について考える。$\gcd(11, 7) = 1$ である。また、$\phi(7) = 6$ である。上記の式に当てはめて、
$$
11 ^ 6 \bmod 7 = 1 \quad (= 右辺)
$$
となる。
上記の例を計算したPythonコードを以下に示す。
mod = 7 # 法 n
a = 11 # 底 a
phi = 6 # トーシェント関数 φ(n)
res = 1 # 結果初期化
while phi > 0:
if phi & 1:
res = (res * a) % mod
a = (a * a) % mod
phi >>= 1
print(res) # 1
2.4. フェルマーの小定理
2.3. 節にて、オイラーの定理について説明した。
オイラーの定理において、$n$ が素数 $p$ となるとき、フェルマーの小定理と呼ばれている。
$$
a ^ {p - 1} \equiv 1 \pmod{p}
$$
これは 2.3. 節で説明したオイラーの定理に、2.2.1. 素数に対するオイラーの関数で説明した $\phi(p) = p - 1$ を代入すれば求めることができる。
2.5. 拡張ユークリッドの互除法
ここでは拡張ユークリッドの互除法について説明する。
拡張ユークリッドの互除法とは、2つの整数 $a, b$ の最大公約数を効率的に求めるアルゴリズムである。これを少し拡張すると、次のような式を満たす整数 $x, y$ を同時に求められる。
$$
ax + by = \gcd(a, b)
$$
特に、$\gcd(a, b) = 1$ のとき、$ax + by = 1$ となり、$x$ が $a$ の法 $b$ における逆元となる。
RSA暗号では、秘密鍵指数 $d$ を求めるのに次の合同式を説く必要がある。
$$
ed \equiv 1 \pmod{\phi(n)}
$$
これは、拡張ユークリッドの互除法を用いて
$$
ed + k\phi(n) = 1
$$
を満たす整数 $d, k$ を求めることで、$d$ を得ることができる。
Pythonコードは以下の通り。
def extended_gcd(a, b):
if b == 0:
return 1, 0, a
x, y, g = extended_gcd(b, a % b)
return y, x - (a // b) * y, g
x, y, gcd = extended_gcd(7, 120) # ここでは a = 7, b = 120 としている。
print(x, y, gcd)
3. RSA暗号の全体像
ここでは、RSA暗号の暗号化から復号の一連の流れを説明する。
3.1. 鍵生成
2つの相異なる大きな素数 $p, q$ を用いて
- $n = pq$
- $\phi(n) = (p - 1)(q - 1)$
を計算する。
次に、公開鍵指数 $e$ を選ぶ。
- $gcd(e, \phi(n)) = 1$
最後に、秘密鍵指数 $d$ を以下のように計算する。
- $ed \equiv 1 \pmod{\phi(n)}$
以上の手順で鍵が定まる。そこで、次のように区別する。
- 公開鍵: $(e, n)$
- 秘密鍵: $(d, n)$
公開鍵は誰でも利用可能で、秘密鍵は所有者のみが保持する。
3.2. 暗号化
暗号化されていないメッセージ（これを平文という）$m$ を数値化して、暗号文（=$C$）を以下のように計算する。ここで、平文 $m$ は $0 < m \leq n - 1$ である必要がある。
$$
C = m ^ {e} \pmod{n}
$$
3.3. 復号
3.2. 暗号化で計算した暗号文Cを受け取ったら、$C ^ {d} \pmod{n}$ を計算することで、平文 $m$ を得ることができる。
\begin{align*}
C ^ {d} &\equiv (m ^ {e}) ^ {d} \pmod{n} \\
&\equiv m ^ {ed} \pmod {n} \\
&\equiv m ^ {1 + k \phi(n)} \pmod{n} \\
&\equiv m \times (m ^ {\phi(n)}) ^ k \\
&\equiv m \pmod{n}
\end{align*}
$m ^ {ed}$ までは単純な計算で求めることができる。
2行目から3行目への変形では、秘密鍵指数 $d$ が $ed \equiv 1 \pmod{\phi(n)}$ を満たすことを使っている。この合同式は、$ed - 1$ が $\phi(n)$ の倍数であるという意味なので、整数 $k$ を用いて、
$$
ed = 1 + k \phi(n)
$$
と書き表せる。
4行目から5行目への変換は、オイラーの定理（2.3. オイラーの定理）を使っている。
すなわち、$gcd(m, n) = 1$ であれば、
$$
m ^ {\phi(n)} \equiv 1 \pmod{n}
$$
が成立する。したがって、
$$
(m ^ {\phi(n)}) ^ k \equiv 1 ^ k \equiv 1 \pmod{n}
$$
となり、式は
$$
m \times (m ^ {\phi(n)}) ^ k \equiv m \pmod{n}
$$
と簡約できる。
実際には $\gcd(m, n) \neq 1$ となる場合（たとえば $m$ が $p$ や $q$ の倍数のとき）もあるが、その場合でも中国剰余定理を用いることで復号が正しく成立することが保証されている。ここでは説明を簡単にするため、$\gcd(m, n) = 1$ と仮定して議論した。
3.4. RSA暗号の具体的な計算例
ここでは、RSA暗号を簡単な例を用いて実際に計算していく。
3.4.1. 鍵生成
2つの素数を選ぶ。ここでは、$p = 11, q = 13$ を選ぶ。ここから、
- $n = pq = 143$
- $\phi(n) = (p - 1)(q - 1) = 10 \times 12 = 120$
と計算することができる。
次に、公開鍵指数 $e = 7$ を選ぶ。（$\gcd(7, 120) = 1$）
最後に秘密鍵指数 $d$ を、拡張ユークリッドの互除法より求める。
def extended_gcd(a, b):
if b == 0:
return 1, 0, a
x, y, g = extended_gcd(b, a % b)
return y, x - (a // b) * y, g
x, y, gcd = extended_gcd(7, 120) # ここでは a = 7, b = 120 としている。
print(x, y, gcd)
d = x % 120
print(d) # 103
RSAでは 法 $\phi(n)$ の範囲に収めた正の値を使うので、求める秘密鍵指数 $d$ は 103である。
したがって、
- 公開鍵 $(e,n) = (7,143)$
- 秘密鍵 $(d,n) = (103,143)$
3.4.2. 暗号化
平文 $m = 9$ を暗号化する。
$$
C = m ^ {e} \pmod {n} = 9 ^ 7 \pmod{143} = 48
$$
よって暗号文は $C = 48$ となる。
Pythonコードは次の通り。
C = pow(9, 7, 143)
print(C) # 48
3.4.3. 復号
暗号文 $C = 48$ を秘密鍵で復号する。
$$
m = C ^ {d} \pmod{n} = 48 ^ {103} \pmod{143} = 9
$$
元の平文 $m = 9$ を正しく復元できた。
Pythonコードは次の通り。
m = pow(48, 103, 143)
print(m) # 9
3.5. RSA暗号の安全性
ここまで、RSA暗号の暗号化から復号までの流れを説明した。ここでは、RSA暗号の安全性の根拠について説明する。
単純な式から構成されるRSA暗号がなぜ幅広く使われているのかというと、「大きな整数の素因数分解が困難である」ことに基づいている。
復号の流れからわかるように、秘密鍵指数 $d$ が分かれば、公開されている公開鍵 $(e, n)$ と組み合わせることで、平文 $m$ を復元できてしまう。
秘密鍵指数の定義は、次の通りであった。
$$
ed \equiv 1 \pmod{\phi(n)}
$$
ここで $e$ は公開されているが、$d$ を求めるためには $\phi(n)$ が必要になる。$\phi(n)$ は定義より、 $\phi(n) = (p - 1)(q - 1)$ であり、これを計算するには $n$ を素因数分解して $p, q$ を得る必要がある。
したがって、RSA暗号は公開鍵 $(e, n)$ の $n$ を素因数分解できれば解読可能である。逆に言えば、十分大きな $n$ の素因数分解が現実的に不可能である限り、RSA暗号は安全に利用できる。
現在安全なRSA暗号として一般的に使われている素数 $p, q$ の大きさは約1024ビットであり、$n = pq$ より、$n$ のビット長は約2048ビットである。これは10進数にして617桁である。
この規模の桁数を実用的な時間内で因数分解できるアルゴリズムはまだ解明されていない。そのため、RSA暗号は現代の計算機環境において、依然として安全に利用できると考えられている。
4. RSA暗号の高速化
3節では、RSA暗号の全体像について述べた。
RSA暗号ではべき乗剰余計算が頻繁に登場する。特に秘密鍵指数 $d$ は非常に大きな数になる為、復号処理（$C ^ {d}$）は計算のボトルネックとなりやすい。
この計算コストを現実的な時間で処理する為、RSAの実装には様々な高速化技術が用いられている。ここでは、その代表的な手法である
- 中国剰余定理（CRT）
- k-ary 法
について解説する。
4.1. 計算量
本格的な解説に入る前に、べき乗剰余計算のコストについて触れておく。
ある数 $n$ （ビット長を $k$ とする）を法とするべき乗剰余計算の全体の計算量は、およそビット長 $k$ の3乗、すなわち $O(k ^ {3})$ に比例する。つまり扱うビット長が2倍になると、計算量は $2 ^ {3} = 8$ 倍に膨れ上がる。
この事実は、これから説明する高速化の鍵となる。
4.2. 中国剰余定理（CRT）
4.2.1. 中国剰余定理の主張とRSAへの適用
中国剰余定理（以下CRT）は、次のようなものである。
主張
整数 $n_i\ (i = 1, 2, \dots, k)$ たちがどの2つも互いに素である時、$k$ 本の連立合同式を満たす $x$ が $0 \leq x < n_1n_2 \dots n_k$ の範囲にただ1つ存在する。
$$
\begin{align*}
x &\equiv a_i \pmod{n_i}
\end{align*}
$$
これは言い換えると、大きな数で割った余りを知りたいとき、その数を互いに素な小さな数たちに分解し、それぞれで割った余りから元の答えを復元できるという定理である。
これをRSA暗号に適用する。RSA暗号では、復号の時に
$$
m \equiv C ^ {d} \pmod{n}
$$
を計算した。このとき、$n$ （$= pq$ ）は非常に大きな数であった。これにCRTを適用すると、
\begin{align*}
m_{p} &\equiv C ^ {d} \pmod{p} \\
m_{q} &\equiv C ^ {d} \pmod{q}
\end{align*}
となる。ここで、
\begin{aligned}
C_p &\equiv C \pmod{p},\quad
C_q \equiv C \pmod{q},\\
d_p &\equiv d \pmod{p-1},\quad
d_q \equiv d \pmod{q-1}
\end{aligned}
であるので、
\begin{align*}
m_p &\equiv C_p ^ {d_p} \pmod{p} \\
m_q &\equiv C_q ^ {d_q} \pmod{q}
\end{align*}
となる。ここで得られた2つの $m_p, m_q$ を合成して、元の平文 $m$ を復元する。この再結合の計算には、拡張ユークリッドの互除法や、ガーナーの公式などが使われる。
\begin{align*}
h &\equiv (m_p - m_q) \cdot q^{-1} \pmod{p} \\
m &\equiv m_q + h \cdot q
\end{align*}
ここで、$q ^ {-1}$ は $q$ の $p$ における逆元である。（拡張ユークリッドの互除法で求められる）
4.2.2. 中国剰余定理による高速化
中国剰余定理を使うことで、大きな法 $n$ を分割して計算することができた。具体的には、$n$ を構成する2つの素数 $p, q$ に分けて計算を行った。
ではなぜ法を分割することで、高速化されるのだろうか??
$m \equiv C ^ {d} \pmod{n}$ の計算量は、$n$ のビット長を $k$ としたときおおよそ $k ^ 3$ に比例する。$p, q$ は $n$ のビット長の半分（=$\dfrac{k}{2}$）になるので、コストは $(\dfrac{k}{2}) ^ {3} = \dfrac{k ^ 3}{8}$ に比例する。つまり、元の計算量の $\dfrac{1}{8}$ になる。このコストの計算を mod p と mod q の2回行う。したがって、合計のコストは $\dfrac{1}{4}$ となる。
CRT によって法を分割して計算することで、計算コストを削減できることが分かった。
4.3. k-ary 法
べき乗剰余計算の高速化する手法として、繰り返し2乗法があるが、これは指数ビット長を $m$ とすると、平方が約 $m-1$ 回、乗算が平均で $m/2$ 回発生する。
これをさらに高速化するために、指数を幅 $k$ ビットごとに分割し、底 $a$ の小さな冪を事前計算しておくことで高速化を図る。これを k-ary 法という。
4.3.1. k-ary 法の計算例
ここでは k-ary 法を利用して、$7 ^ {59} \pmod{29}$ の計算を、$k = 3$ で計算する。k-ary 法では、$a^{1}, a^{2}, ..., a ^ {2 ^ {k} - 1}$ を前計算する。（今回は $2 ^ 3 - 1 = 7$ 個）
事前計算を行った結果は以下の通りとなる。
\begin{aligned}
a^1 &= 7 &\mod 29 &= 7 \\
a^2 &= 49 &\mod 29 &= 20 \\
a^3 &= 343 &\mod 29 &= 24 \\
a^4 &= 2401 &\mod 29 &= 23 \\
a^5 &= 16807 &\mod 29 &= 16 \\
a^6 &= 117649&\mod 29 &= 25 \\
a^7 &= 823543&\mod 29 &= 1
\end{aligned}
指数59の2進表現は $111011_{2}$。これを上位から幅 $k = 3$ で区切ると $111$ $011$ なので、
\begin{align}
b_3[1] = 111_{(2)} = 7 \\
b_3[0] = 011_{(2)} = 3
\end{align}
となる。現在までの答えを $S$ （初期値 $S = 1$）として、最初に$b_3[1]$ を使い計算すると、
\begin{align}
S &= S \times 7 ^ 7 \pmod{29}\\
&= 1
\end{align}
次に $2 ^ {k}$ ビット分ずらす。今回は$k = 3$ なので $2 ^ 3$ 乗をして、
\begin{align}
S ^ {2 ^ 3} &= 1 ^ 8 \\
&= 1
\end{align}
次に、$b_3[0]$ を使い計算すると、
\begin{align}
S &= S \times 7 ^ 3 \pmod{29} \\
&= 1 \times 7 ^ 3 \pmod{29} \\
&= 24
\end{align}
となる。Pythonで計算を行うと、
print(pow(7, 59, 29)) # 24
となり、答えが一致しているのが分かる。
4.3.2. k-ary 法の計算量
事前計算に $O(2 ^ {k} - 1)$ 回の計算コストを払うので、べき乗指数が大きい時に有用な方法である。
必要なモジュラ乗算の平均回数は、指数のビット長を $m$ とする。
- 事前計算： $2^k-1$ 回
- 平方（square）：指数のビット長が $m$ のとき、$m$ ビット処理する計算回数は、厳密には $m - 1$ 回であるが、見積もり式なので定数1の差を無視して、$m$ 回とする。
- 乗算（multiply）：固定ウィンドウ幅を $k$ とすると、指数を上位から $k$ ビットごとに分ける。この時それぞれのまとまりについて、事前計算表と1回だけ乗算が行われる。ただし、そのまとまりが全て0の場合には、乗算は発生しない。（上記の例で $000_{2}$ の時）すべて0になる確率は $\dfrac{1}{2 ^ k}$ なので、1まとまりあたりの乗算回数は平均すると $1 - \dfrac{1}{2 ^ k}$ 。このまとまりが $\dfrac{m}{k}$ 個あるので、平均乗算回数は $\dfrac{m}{k}(1 - \dfrac{1}{2 ^ k})$ 回となる。
これらをまとめると、k-ary 法の計算回数は、
$$
T(m, k) = (2 ^ k - 1) + m + \dfrac{m}{k}(1 - \dfrac{1}{2 ^ {k}})
$$
である。この式の最小値が、k-ary 法における最適な分割数（=$k$）となる。この式を $k$ について最小化することで、計算回数がを削減することができる。
4.3.3. 最適な分割数 k の導出
$T(m, k)$ を微分したものを $f(m, k)$ とすると、
$$
f(m, k) = 2 ^ {k} \log2 - \dfrac{m}{k ^ 2} + \dfrac{m(1 + k \log2)}{k ^ {2} \times 2 ^ {k}}
$$
最適条件は $f(m, k) = 0$。
Newton 法で解くために、導関数 $f'(k)$ を求めて整理をすると、
$$
f'(k) = 2 ^ {k} (\log2) ^ 2 + \dfrac{2m}{k ^ {3}} - \dfrac{m}{k ^ {3} \times 2 ^ {k}}(2 + 2k \log2 + k ^ {2} (\log2) ^ 2)
$$
この導関数を用いて Newton 法を実装し、最適な $k$ を求める Python コードを以下に示す。
import math
ln2 = math.log(2)
def guess_initial_k(m):
# Newton 法の初期値
# f(k) = 0となるような解を近似することで、Newton法の収束を早める
return math.log2(m) - math.log2(math.log2(m))
def T(k, m):
# Tを得るための関数
return 2 ** k + m / k - m / (k * pow(2, k)) + m - 1
def f(k, m):
# fを得るための関数
return pow(2, k) * ln2 - m / pow(k, 2) + (m * (1 + k * ln2)) / (pow(k, 2) * pow(2, k))
def df(k, m):
# f'を得るための関数
return pow(2, k) * pow(ln2, 2) + 2 * m / pow(k, 3) - (m * (2 + 2 * k * ln2 + pow(k, 2) * pow(ln2, 2))) / (pow(k, 3) * pow(2, k))
def newton(m):
# Newton 法を使って最適な k を求める。
guess = guess_initial_k(m)
eps = 1e-9
max_iter = 100
for _ in range(max_iter):
f_val = f(guess, m)
df_val = df(guess, m)
delta = f_val / df_val
guess_next = guess - delta
guess = guess_next
if abs(delta) < eps:
break
return guess
def find_optimal_k(m):
k_best = newton(m)
# 最も最適な k (小数)を表示する
print(k_best)
# k_best は小数なので、前後の整数値を見て最小値を取る方を答えにする。
best_low = math.floor(k_best)
best_high = best_low + 1
best_values = T(best_low, m)
if best_values > T(best_high, m):
best_values = T(best_high, m)
return best_high, f"{best_values:.2f}"
return best_low, f"{best_values:.2f}"
# 指数 m
m_vals = [1024, 1536, 2048, 4096]
for m in m_vals:
best_k, best_T = find_optimal_k(m)
print(f"m = {m}, k = {best_k}, T = {best_T}")
print()
実行結果は次の通り。
5.463457724523712
m = 1024, k = 5, T = 1253.40
5.874394689380678
m = 1536, k = 6, T = 1851.00
6.168877632630228
m = 2048, k = 6, T = 2447.00
6.888353182810514
m = 4096, k = 7, T = 4803.57
例えば、RSA暗号において秘密鍵指数 $d$ のビット長が $m = 2048$ ビットである場合、k-ary 法では分割数 $k = 6$ が最も効率的な設定になることが分かる。このとき、べき乗剰余演算に必要なモジュラ乗算の平均回数 $T(m, k)$ は約2447回に抑えられる。
単純な繰り返し2乗法でのべき乗剰余計算は、指数を $m$ ビットとすると、
- 平方：$m - 1$ 回（各ビットごとに実行し、最上位ビットを除く）
- 乗算：$\dfrac{m}{2}$ 回（各ビットが1のときのみ行われ、平均で半分が1）
したがって、モジュラ演算の合計回数はおよそ
$$
(m - 1) + \dfrac{m}{2} \approx \dfrac{3m}{2}
$$
$m = 2048$ の時、$\dfrac{3}{2} \times 2048 = 3072$ となり、625回の計算を削減することができた。
k-ary 法は、RSAのような大きな指数を扱う暗号アルゴリズムにおいて、単純な繰り返し2乗法に比べて大きな高速化をもたらす有力な手法である。
5. さいごに
本記事では、RSA暗号の仕組みとその高速化技術について解説した。
6. 参考資料
[1]. Pythonで学ぶ暗号理論
[2]. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
[3]. RSA暗号