アルゴリズム論特論(塩田)第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
  1. $y_p = y\,\%\,p$, $y_q = y\,\%\,q$, $d_p = d\,\%\,(p-1)$, $d_q = d\,\%\,(q-1)$ とおく。
  2. $z_p = y_p^{d_p}\,\%\,p$, $z_q = y_q^{d_q}\,\%\,q$ を求める。
  3. $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 倍の高速化になります。