RSA暗号のアルゴリズムのソースを表示

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

== 前提知識 ==
以下の初等整数論の知識を用いる。<br>
<br>
* [[合同式の基礎]]
* [[フェルマーの小定理]]
* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。<br>
<br><br>

== RSA暗号の仕組み ==
* 公開鍵
** n : 2つの素数の積
** k<sub>1</sub> : <math>\phi(n) = (p - 1)(q - 1)</math>と互いに素な整数k<sub>1</sub> (ただし、<math>1 < k_{1} < n</math>を満たすこと)
* 秘密鍵
** 素数p
** 素数q
** φ(n) : <math>(p - 1)(q - 1)</math>の積
** k<sub>2</sub> : <math>k_1k_2 \equiv 1 \bmod (p - 1)(q - 1)</math>となるk<sub>2</sub>
<br>
===== メッセージを受け取る側の準備 =====
大きな素数pとqを生成して、<math>n = pq</math>とする。<br>
<math>\phi(n) = (p - 1)(q - 1)</math>と互いに素な整数k<sub>1</sub>を取る。<br>
<math>k_1k_2 \equiv 1\,\bmod\,(p - 1)(q - 1)</math>となるk<sub>2</sub>を取る。<br>
<br>
'''※注意'''<br>
'''上記の有名な定理により、<math>0 \le k_2 \le (p - 1)(q - 1)</math>とすると、k<sub>2</sub>は一意に定まる。'''<br>
'''また、ここまでの操作は高速にできることが知られている。'''<br>
* nとk<sub>1</sub>を公開する(公開鍵)
* k<sub>2</sub>は非公開にする(秘密鍵)
<br>

===== メッセージを送る側の暗号化方法 =====
送信するメッセージをMとする時、暗号文をCは、以下の式で求められる。<br>
ただし、<math>\,0 \le M \le n \,</math>を満たす。<br>
<math>C = M^{k_1} \bmod n</math><br>
<br>

===== メッセージを受け取る側の復号方法 =====
受信した暗号文Cと秘密鍵k<sub>2</sub>を使用して復号する時、以下の式から求められる。<br>
<math>M = C^{k_2} \bmod n</math><br>
<br>
これが元のメッセージに一致する。(後述)
<br>

===== 安全性 =====
暗号文Cと公開鍵n、k<sub>1</sub>が分かっても、(現実的な時間では)mを復元することはできない。<br>
<br>
* 復号できる理由
*: 暗号化：<math>m^{k_1} \bmod n</math>
*: 復号　：<math>C^{k_2} \bmod n</math>
<br>
証明<br>
<math>m^{k_1k_2} \equiv m\,\bmod\,n</math>を証明すればよい。<br>
<math>m^{k_1k_2} \equiv m\,\bmod\,p</math>を証明すれば十分である。(対称性より、<math>\bmod q</math>も同様)<br>
<br>
mがpの倍数のとき、両辺ともにpの倍数よりOK。<br>
mがpの倍数でないとき、<math>k_1k_2 - 1</math>が<math>p - 1</math>の倍数となるように設定したので、<br>
整数Nを用いて、<math>k_1k_2 = 1 + N(p - 1)</math>とおける。<br>
よって、<math>m^{k_1k_2} = m * (m^{p - 1})N \equiv m * 1^N \bmod n= m</math>となる。<br>
(ただし、途中の<math>\equiv</math>は<math>\bmod n</math>であり、フェルマーの小定理を用いた)<br>
<br><br>

== RSA暗号の安全性と素因数分解 ==
素因数分解が簡単に(短時間で)計算できれば、RSA暗号は破られる。<br>
<br>
* RSA暗号が破られる理由<br>
*: 暗号文C、公開鍵k<sub>1</sub>、nは誰でも見ることができる。
*: ここで、nを素因数分解することでpとqが求まる。
*: すると、"メッセージを受け取る側の準備"と同じ方法で秘密鍵k<sub>2</sub>が求まり、元のメッセージMを復号できる。
<br><br>

__FORCETOC__
[[カテゴリ:暗号理論]]