RSA加密演算法

參考資料
Proof of the RSA Algorithm https://sites.google.com/site/danzcosmos/proof-of-the-rsa-algorithm
RSA算法原理 http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

資料加密(Data encryption)，如同替家門或金庫上鎖一樣，都是為了防止外人輕易窺知裡頭的東西。加密可分為「對稱式」與「非對稱式」。「對稱式」是指用同一把鑰匙進行加密和解密動作，「非對稱式」則是指加解密時採用不同的鑰匙。

對稱式的加解密方法比較直觀，也比較方便，但這也是它的致命傷。因為對稱式加密系統，加解密都是用同一把鑰匙，萬一鑰匙在某個環節被破解，等於宣告整個系統瓦解，因此有必要改進這種加密系統模式。

非對稱式加密系統是利用公開鑰匙(Public Key)和私密鑰匙(Private Key)進行加密解密動作。公開鑰匙是公開資訊，用於加密資料時使用；私密鑰匙是隱藏資訊，只有解密者擁有，用於解密時使用。

關鍵：加密用公鑰，解密用私鑰。

RSA加密演算法於1973年，由Ron Rivest、Adi Shamir 和 Leonard Adleman 三人提出，1977年正式對外發表。

RSA演算法的關鍵技術仰賴「(質)因數分解的困難度」。數字越大，因數分解需要耗費的時間就越長，資料受到保護的機率就越高。因此RSA演算法的重點不在於是否被破解(只要時間夠久，總有一天必能破解)，而是破解它所需耗費的成本是否值得。

RSA演算法會用的數論工具主要有二：Euler's theorem(歐拉定理)及Modular inverse(模反元素)。

Euler's theorem 會在製作公鑰時用到，modular inverse 用於製作私鑰。公私鑰製作流程如下圖。

有了公鑰和私鑰元素，接著我們來看如何進行加解密的操作，並針對RSA的安全性做討論。

加解密的流程如下圖，我們限制$m<n$：

我們必須證明 $c^{d}\equiv m$ (mod $\varphi (n)$) 這條同餘式的正確性。

<pf> $c^{d}\equiv (m^{e})^d \equiv m^{ed}\equiv m^{k \cdot \varphi (n)+1}$ (mod $\varphi (n)$), where $k$ is an integer.

CASE 1. If $(m,n)=1$, according to Euler's theorem, we have $m^{\varphi (n)}\equiv 1$ (mod $n$), so $m^{k\cdot \varphi (n)}\equiv 1$ (mod $n$). Therefore, $m^{k\cdot \varphi (n)+1}\equiv m$ (mod $\varphi (n)$)

CASE 2. If $m$ and $n$ are not coprime, you can try to prove it yourself. The answer is written in the 2nd reference.

透過上式證明，我們可以確定加解密的算法是正確的，但它的安全性呢？我能否光憑 $n$, $e$ 兩數，就可以算到 $d$ 呢？

$d$ 從何而來？$d$ 是在上述的步驟5出現，由 $e$ 而來；而 $e$ 是步驟4中由 $\varphi (n)$，也可以說由 $n$ 而來；而 $n$ 是兩個質數的乘積。因此$d$ 的破解與否，$n$ 的質因數分解扮演莫大的角色。如同我們在一開始提到到這段話：

RSA演算法的關鍵技術仰賴「(質)因數分解的困難度」。數字越大，因數分解需要耗費的時間就越長，資料受到保護的機率就越高。因此RSA演算法的重點不在於是否被破解(只要時間夠久，總有一天必能破解)，而是破解它所需耗費的成本是否值得。