RSA暗号のアルゴリズム

概要

公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について記載する。

前提知識

以下の初等整数論の知識を用いる。

合同式の基礎
フェルマーの小定理
有名な定理 : aとbが互いに素なとき、 $ax\equiv 1\,{\bmod {\,}}b$ となるxが、 $1\leq x\leq b-1$ の間でただ1つ存在する。

RSA暗号の仕組み

メッセージを受け取る側の準備

大きな素数pとqを生成して、 $n=pq$ とする。
$\phi (n)=(p-1)(q-1)$ と互いに素な整数k₁を取る。
$k_{1}k_{2}\equiv 1\,{\bmod {\,}}(p-1)(q-1)$ となるk₂を取る。

※注意
上記の有名な定理により、 $0\leq k_{2}\leq (p-1)(q-1)$ とすると、k₂は一意に定まる。
また、ここまでの操作は高速にできることが知られている。

nとk₁を公開する(公開鍵)
k₂は非公開にする(秘密鍵)

メッセージを送る側の暗号化方法

送りたいメッセージをm(ただし、 $0\leq m\leq n$ を満たす)とする。
公開鍵を用いて $mk_{1}\,{\bmod {\,}}n$ を計算し、これを暗号文(Cとおく)とする。

メッセージを受け取る側の復号方法

暗号文Cと秘密鍵k₂を用いて、 $Ck_{2}\,{\bmod {\,}}n$ を計算すると、
これが元のメッセージに一致する。(後述)

安全性

暗号文Cと公開鍵n、k₁が分かっても、(現実的な時間では)mを復元することはできない。

復号できる理由
暗号化： $mk_{1}\,{\bmod {\,}}n$

復号　： $Ck_{2}\,{\bmod {\,}}n$

証明
$m^{k_{1}k_{2}}\equiv m\,{\bmod {\,}}n$ を証明すればよい。
$m^{k_{1}k_{2}}\equiv m\,{\bmod {\,}}p$ を証明すれば十分である。(対称性より、 ${\bmod {q}}$ も同様)

mがpの倍数のとき、両辺ともにpの倍数よりOK。
mがpの倍数でないとき、 $k_{1}k_{2}-1$ が $p-1$ の倍数となるように設定したので、
整数Nを用いて、 $k_{1}k_{2}=1+N(p-1)$ とおける。
よって、 $m^{k_{1}k_{2}}=m*(m^{p-1})N\equiv m*1^{N}{\bmod {n}}=m$ となる。
(ただし、途中の $\equiv$ は ${\bmod {n}}$ であり、フェルマーの小定理を用いた)