RSA暗号のアルゴリズム

概要

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

前提知識

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

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

RSA暗号の仕組み

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

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

大きな素数pとqを生成して、 $n = p q$ とする。
$ϕ (n) = (p - 1) (q - 1)$ と互いに素な整数k₁を取る。
$k_{1} k_{2} \equiv 1 mod (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}} mod n$

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

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

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

安全性

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

復号できる理由
暗号化： $m^{k_{1}} mod n$

復号　： $C^{k_{2}} mod n$

証明
$m^{k_{1} k_{2}} \equiv m mod n$ を証明すればよい。
$m^{k_{1} k_{2}} \equiv m mod p$ を証明すれば十分である。(対称性より、 $mod 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} mod n = m$ となる。
(ただし、途中の $\equiv$ は $mod n$ であり、フェルマーの小定理を用いた)

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

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

RSA暗号が破られる理由

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

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

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