アルゴリズム論特論（塩田）第13回 (3) RSA暗号の復号の工夫
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
RSA暗号のおさらい
- $p$, $q$ はほぼ同じビット数の素数
- $n = p \times q$
- $e$ は暗号化指数, $d$ は復号指数
- 平文 $x$ の暗号化は $y=x^e\, \%\, n$
- 暗号文 $y$ の復号は $z=y^d\, \%\, n$
この復号計算を CRA を用いて少し高速化しましょう。
CRA を用いた復号
Algorithm
- $y_p = y\,\%\,p$, $y_q = y\,\%\,q$,
$d_p = d\,\%\,(p-1)$, $d_q = d\,\%\,(q-1)$
とおく。
- $z_p = y_p^{d_p}\,\%\,p$, $z_q = y_q^{d_q}\,\%\,q$ を求める。
- $z \equiv z_p \pmod{p}$ かつ $z \equiv z_q \pmod{q}$ の解 $z$ を CRA を用いて求める。
このアルゴリズムを実行すると
$$
\left\{
\begin{array}{l}
z \equiv z_p \equiv y_p^{d_p} \equiv y^d \pmod{p} \\
z \equiv z_q \equiv y_q^{d_q} \equiv y^d \pmod{q} \\
\end{array}
\right.
$$
ですから通常の復号と同じ計算結果が得られます。
$n$ を $k$ ビットとすると $p$, $q$, $y_p$, $y_q$, $d_p$. $d_q$ は
おおよそ $\frac{k}{2}$ ビットですから、
このアルゴリズムの主要な部分 $2^{\circ}$ の
法べき乗計算 ( $k^3$ オーダー ) の計算時間は、
$y^d \,\%\, n$ に比べて
$$2 \times \left(\frac{1}{2}\right)^3 = \frac{1}{4}$$
倍、つまり 4 倍の高速化になります。