RSA暗号のアルゴリズム

概要

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

前提知識

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

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

RSA暗号の仕組み

• 公開鍵
  • n : 2つの素数の積
  • k₁ : $\phi (n)=(p-1)(q-1)$と互いに素な整数k₁ (ただし、$1<k_{1}<n$を満たすこと)
• 秘密鍵
  • 素数p
  • 素数q
  • φ(n) : $(p-1)(q-1)$の積
  • k₂ : $k_{1}k_{2}\equiv 1{\bmod {(}}p-1)(q-1)$となるk₂

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

大きな素数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とする時、暗号文をCは、以下の式で求められる。
ただし、$\,0\leq M\leq n\,$を満たす。
$C=M^{k_{1}}{\bmod {n}}$

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

受信した暗号文Cと秘密鍵k₂を使用して復号する時、以下の式から求められる。
$M=C^{k_{2}}{\bmod {n}}$

これが元のメッセージに一致する。(後述)

安全性

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

• 復号できる理由

  暗号化：$m^{k_{1}}{\bmod {n}}$

  復号　：$C^{k_{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を復号できる。