我在昨天的文章裡簡單講解了AES的加密原理，並且有提到對稱加密與非對稱加密，而今天要來講講最有名的現代非對稱加密算法: RSA。雖然較少被勒索軟體使用，但是有很多有趣的地方可以拿來講解和比較。
如果你不知道對稱與非對稱加密的差別，對稱加密就是只有一組密鑰，非對稱則是有一組公鑰和一組私鑰。換成現實中的物品形容，對稱加密就像使用傳統鑰匙的，上鎖和解所都要使用鑰匙；非對稱加密則是像一些電子門鎖一樣，關起來就上鎖，但是姐所需要輸入密碼，或是上鎖與解鎖使用不同密碼。
昨天提到的AES命名是直接以用途命名(進階加密標準)，但是RSA跟AES的原名RijnDael很像是取三位發明者名字的開頭而成。很巧的是，AES的前身DES被訂為標準的1977年剛好就是RSA被發明的那年。
RSA跟AES一樣有五個不同的步驟，不過相對於AES，邏輯都非常簡單，以下將講解各個步驟的執行方式:
- 選擇兩個相異的質數p與q。
- 計算 n = pq。這將是加密和解密過程中使用的模數。
- 計算卡邁克爾歐拉函數 λ(n)，用於確定與 n 互質的數字個數。計算 λ(n) 的方法是找到 p-1 和 q-1 的最小公倍數λ(n) = lcm(p − 1, q − 1)。
- 選擇公開金鑰的指數 e，也就是要找到一個小於 λ(n)且與之互質的數字。這個數字將被用來加密明文。
- 計算私密金鑰的指數 d。它會是公開金鑰指數 e 在模 λ(n) 下的反元素，也就是說，要找一個數字 d，使 (e × d) mod λ(n) = 1。
是不是比AES好理解很多? 有了公鑰(質數乘積n和指數e)和私鑰(質數乘積n和指數d)，要加密或解密，分別要將明文m(未加密的內容)與密文c(加密過的內容)乘自己e和d次，也就是如下面所示:
c(m) = m^e mod n
m(c) = c^d mod n
由於e, d, n都是被控制的，所以整數模n時一定是整數。
因為通常會挑選很大的數字作為p和q，所以要解密的時候要對非常大的乘積n(通常是二進位數字個位數，例如1024, 2048…)進行質因數分解，因此需要很強大的計算能力，但是不同於AES，是現代超級電腦有辦法在有限時間內破解的。