2015/06/13

RSA暗号の仕組みと安全性


公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について解説します。数学がまあまあ得意な高校生なら理解できるレベルの内容です。

前提知識

公開鍵暗号方式についてなんとなくでも知っていると読みやすいと思います。共通鍵暗号と公開鍵暗号の仕組みをどうぞ。

また,以下の初等整数論の知識を用います。

RSA暗号の仕組み

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

  • 大きな素数 $p,q$ を生成し,$n=pq$ とする
  • $(p-1)(q-1)$ と互いに素な整数 $k_1$ を取ってくる
  • $k_1k_2\equiv 1\:\mathrm{mod}\:(p-1)(q-1)$ なる $k_2$ を取ってくる

注:「有名な定理」により $0\leq k_2\leq (p-1)(q-1)$ とすると $k_2$ は一意に定まります。また,ここまでの操作は高速にできることが知られています。
・ $n$ と $k_1$ を公開する(公開鍵),$k_2$ は公開しない(秘密鍵)

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

  • 送りたいメッセージを $m$(ただし $0\leq m <n$ を満たす)とする
  • 公開鍵を用いて $m^{k_1}\:\mathrm{mod}\:n$ を計算し,これを暗号文($C$ とおく)とする

3.メッセージを受け取る側の復号方法
・暗号文 $C$ と秘密鍵 $k_2$ を用いて $C^{k_2}\:\mathrm{mod}\:n$ を計算すると,実はこれがもとのメッセージに一致する(後述)!

4.安全性
暗号文 $C$ と公開鍵 $n,k_1$ が分かっても(現実的な時間では)$m$ を復元することはできない(と信じられている)

復号がうまくいく理由

暗号化:$m^{k_1}\:\mathrm{mod}\:n$
復号:$C^{k_2}\:\mathrm{mod}\:n$
でうまく復号できていることの確認をします。

証明

$m^{k_1k_2}\equiv m\:\mathrm{mod}\:n$ を証明すればよい。

$m^{k_1k_2}\equiv m\:\mathrm{mod}\:p$ を証明すれば十分(対称性より $\mathrm{mod}\:q$ も同様)。

  • $m$ が $p$ の倍数のときは両辺ともに $p$ の倍数よりOK。
  • $m$ が $p$ の倍数でないとき,

$k_1k_2-1$ が$(p-1)$ の倍数となるように設定したので,整数 $N$ を用いて $k_1k_2=1+(p-1)N$ とおける。よって,
$m^{k_1k_2}=m\cdot (m^{p-1})^N\equiv m\cdot 1^N=m$
ただし,途中の $\equiv$ は $\mathrm{mod}\:n$ であり、フェルマーの小定理を用いた。

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

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

(説明)
暗号文 $C$,公開鍵 $k_1,n$ は誰でも見ることができる。
ここで $n$ を素因数分解することで $p,q$ が求まる。すると「メッセージを受け取る側の準備」と同じ方法で秘密鍵 $k_2$ が求まり,もとのメッセージ $M$ を復号できる。

幸い,大きな数の素因数分解の計算は難しいです。→素因数分解の難しさと素数判定

厳密には($p$ などに)もっといろいろ条件があります。興味を持った方は暗号の本を読んでみてください!