RSA 暗号と中国剰余の定理による高速化についてのまとめ

RSA 暗号についての個人的なまとめ。

1. 教科書的な RSA 暗号

RSA 暗号は公開鍵暗号であり、公開鍵を利用して電文 $M$ を元にして作成した暗号化電文 $C$ が、秘密鍵の保持者にしか元の電文 $M$ を復号できなければ良い。

1.1 定義

$\lambda$ をカーマイケル関数とする。

ランダムに異なる2つの素数 $p$, $q$ を用意し、$N \coloncolonequals pq$ として $N$ を定義する。 適当な素数 $e$ も用意する。 このとき、$e$ と $\lambda(N)$ が互いに素になるようにする。(計算方法は後述) ならない場合は $p$, $q$ を生成しなおす。

こうして得られた $N$ と $e$ を公開鍵とし、 $p$, $q$ を秘密鍵とする。

なお、メッセージは適当に符号化すれば良いので、 $M$ と $C$ は自然数であるとする。 また、 RSA 暗号は $N$ を法として計算を行うので、 $M$ と $C$ は $N$ 未満であるとする。 (大きな $M$ を暗号化したい場合、それ以上に大きい $N$ を用いる)

1.2 暗号化

1.3 複合化($M$ が $p$ とも $q$ とも互いに素である場合の証明)

$\lambda(N)$ は、その素因数 $p$, $q$ を知っている秘密鍵保持者のみが、以下の計算で求めることができる。

この値を利用して、$e$ と $\lambda(N)$ は互いに素になるように $p$, $q$ を生成していたので、拡張ユークリッドの互除法によって、以下の条件を満たす自然数 $d$ を求める。

この時、適当な自然数 $n$ を用いて、 $ed = n\lambda(N) + 1$ であり、カーマイケル関数の定義より $M^{\lambda(N)} \equiv 1 \pmod{N}$ なので、

(算術はすべて $\mod N$ で行う)

として $C^d$ を計算することで、元の電文 $M$ を求めることができる。

1.4 $M$ が $1$ から $N-1$ の任意の値であった場合でも通用する証明

$M$ が $p$ ないし $q$ の倍数であった場合、上記の証明において利用した性質 $M^{\lambda(N)} \equiv 1 \pmod{N}$ は必ずしも成立するとは限らない。 この場合、中国剰余の定理を用いることで、 $M^{ed} \equiv M \pmod{N}$ を示すことができる。 以下、その場合を証明すると、

$p$, $q$ は互いに異なる素数であるとしたので、 $M$ は $p$ か $q$ のうち少なくとも一つと互いに素。 よって、 $M$ が $p$ と互いに素であったとして、証明の一般性を失わない。 このとき、 $\lambda(N) = \mathrm{LCM}(p-1, q-1)$ であったので、 $\lambda(N)$ は $p-1$ の倍数。 すると、 $ed = n\lambda(N) + 1$ であったことより、 $ed = m(p-1) + 1$ を見たす $m$ が存在する。 フェルマーの小定理により、 $M^{p-1} \equiv 1 \pmod{p}$。 よって、

ここで、もし $M$ が $q$ に対しても互いに素であれば、同様に $M^{ed} \equiv M \pmod{q}$ を得る。

そうでない場合、 $M$ は $q$ の倍数であるので、 $M \equiv 0 \pmod{q}$ であり、 $M^{ed} \equiv 0 \pmod{q}$。 よって、$M^{ed} \equiv M \pmod{q}$。

いずれにせよ、 $M^{ed} \equiv M \pmod{p}$ かつ $M^{ed} \equiv M \pmod{q}$ が示されたので、中国人剰余の定理により、 $M^{ed} \equiv M \pmod{N}$。

2. 中国剰余の定理による高速化

$p$, $q$, $e$ によって一意に計算される $d$ は、秘密鍵の生成時点で予め計算しておくことができる。 しかし、この値は $\mod{\mathrm{LCM}(p-1, q-1)}$ であるので、そこそこ大きな値であり、 $C^d$ の計算に割と時間がかかってしまう。 中国剰余の定理を活用する以下の計算方法によって、複合化処理を高速化できる。

まず、以下の値を予め、秘密鍵生成時に計算しておく。

暗号化電文 $C$ に対して、以下の計算を行うことで、 $M'$ が計算できるが、これがその実、 $M$ に一致する。

2.1 証明

2.1.1 $M \equiv M_1 \pmod{p}$ かつ $M \equiv M_2 \pmod{q}$

同様の証明になるので、$M \equiv M_1 \pmod{p}$ について示す。

今、$p$ は $N$ を割り切り、かつ $M \equiv C^d \pmod{N}$ であったので、 $M \equiv C^d \pmod{p}$

$C$ が $p$ の倍数の時、$M_1$($\coloncolonequals C^{d_p}$) も $C^d$ も $\mod p$ の基、$0$ なので等しい。

以降、$C$ が $p$ の倍数でない場合を考える。 $p$ は素数だったので、 $C$ と $p$ は互いに素。 フェルマーの小定理より、 $C^{p-1} \equiv 1 \pmod{p}$。 定義より、ある整数$k$ が存在して、 $d = k(p-1) + d_p$。

よって、

以上より $M \equiv C^d \equiv M_1 \pmod{p}$. 同様に $M \equiv M_2 \pmod{q}$

2.1.2 $M' \equiv M_1 \pmod{p}$ かつ $M' \equiv M_2 \pmod{q}$

一般に、整数 $p$ と $q$ があって(素数でなくとも良い)、$M \equiv M_1 \pmod{p}$, $M \equiv M_2 \pmod{q}$ であるとき、

$M_1 - M_2$ を $\mathrm{GCD}(p, q)$ は割り切るので、

として整数 $k$ と定義できる。 これを変形して、

また、ここで拡張ユークリッドの互除法によって、整数 $p_{\mathrm{inv}}'$, $q_{\mathrm{inv}}'$ が存在して、

この2式より、

を得る。

今、 $M'' \coloncolonequals kq_{\mathrm{inv}}'q + M_2 = M_1 - kp_{\mathrm{inv}}'p$ として $M''$ を定義すると、$M'' \equiv M_1 \pmod{p}$ かつ $M'' \equiv M_2 \pmod{q}$ が成立する。 つまり、このように $M''$ を構築することで、 $M$ が満たしていた合同条件を満たす $M''$ が構築できる。

またこの時、$q_{\mathrm{inv}}'$ はその満たすべき制約である $q_{\mathrm{inv}}'q + p_{\mathrm{inv}}'p = \mathrm{GCD}(p, q)$ において、 その値に $p$ の倍数を足し引きしても、 $p_{\mathrm{inv}}'$を適宜調整すればこの制約を満たす。 $q_{\mathrm{inv}}'$ のみ注目するのならば、なので、 $\mod p$ の中で好きな値を選択すれば良い。

次に、 $h \coloncolonequals kq_{\mathrm{inv}}' \pmod{p}$ を満たす $h$ が得られたとする。 このとき、 $M' \coloncolonequals hq + M_2$ とすると、まず $M' \equiv M_2 \pmod{q}$。 次に、ある整数 $n$ が存在して $h = kq_{\mathrm{inv}}' + np$ だから、

ここまで一般整数 $p$, $q$ を想定してきて議論してきたが、 $p$, $q$ を異なる素数とするならば、 $k = M_1 - M_2$ となり、また、 $q_{\mathrm{inv}}'$ の選択において $q_{\mathrm{inv}} \coloncolonequals q^{-1} \pmod{p}$ を採用することによって、以下を得る。

これは、証明するべき $M'$ の定義と示したい合同式に他ならない。

2.1.3 まとめ

2.1.1 と 2.1.2 そして中国剰余の定理により、 $M \equiv M'$ を得る。