RSA暗号のアルゴリズム

概要

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

前提知識

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

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

RSA暗号の仕組み

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

大きな素数pとqを生成して、$n=pq$とする。
$(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}}$であり、フェルマーの小定理を用いた)

RSA暗号の安全性と素因数分解

素因数分解が簡単に(短時間で)計算できれば、RSA暗号は破られる。

• RSA暗号が破られる理由
  

  暗号文C、公開鍵k₁、nは誰でも見ることができる。

  ここで、nを素因数分解することでpとqが求まる。

  すると、"メッセージを受け取る側の準備"と同じ方法で秘密鍵k₂が求まり、元のメッセージMを復号できる。