達人專欄 對我來說，這大概是我寫過有史以來最困難的一篇文了，畢竟 RSA 加密算法牽涉到即使已經修完高中數學都不見得能夠理解的前備知識，特地寫成一篇也是為了逼迫自己掌握它的觀念，試試看能不能成功讓一般人也能理解 RSA 加密算法。
本文算式圖片設計以深色模式為主，閱覽前建議切換為深色模式。由於手機 App 在切換樣式前需要強制重啟 App，若你是日間模式使用者，請在切換前利用「收藏」功能，避免切換完模式以後找不回本文。
。加密演算法的對稱性
以前我曾經在《壓縮檔如何幫你的檔案加密？有可能「繞」過去嗎？》提到，RC4 加密算法利用了邏輯閘 XOR 的基本性質：
「若計算 A XOR B 得到 C，則計算 C XOR B 必定會得到 A」
這樣的性質，讓我們能夠把一組數據和一組密鑰變換成無法直接解讀的密文，等到我們需要使用的時候，再用同樣一組密鑰把密文變換回來就可以了，這就是所謂的「對稱式加密」。
最常見的應用就是壓縮檔（AES-256 加密演算法）。我們向特定對象分享敏感資料的時候，為了避免這些檔案因為各種疏失而被其他人取得後輕易打開，通常都會用一組密碼把它加密，之後才把檔案傳過去。
然而，使用這種方式時，你和對方必須事先共同約定好一組密鑰，要是在決定並且分享密鑰給對方的過程中，被人竊聽了、散播出去了，那麼這些加密的保護也只是徒勞。
因此，在資訊領域裡發展出了「非對稱性加密」的技術——加密的時候使用一組密鑰、解密的時候使用另一組密鑰，我們甚至可以把其中一組密鑰公開出去給所有人知道也沒關係！這聽起來非常不可思議，而其中的代表正是今天的主角：1977 年發明的 RSA 加密演算法。
我們用特定的方法產生出一對存有一定關係的密鑰：公鑰（Public Key）、私鑰（Private Key），其中公鑰用來加密資料，私鑰拿來解密資料。
因為公鑰和私鑰之間的數學關係非常複雜，所以即使讓大家知道了公鑰，這些人也難以藉此推導出對應的私鑰，再加上私鑰只需要自己保管而不需要傳遞給任何人，自然也就保證了第三方無法輕易地破譯出原文內容。
。RSA 加解密的實例
先不要談公鑰和私鑰如何產生，因為那是 RSA 最複雜的部分。我們要先知道 RSA 的密鑰必須合乎 RSA 演算法的規範，經過特定的流程會產生出三個數字：N、e、d，各自作為密鑰的一部分。
其中數對 (N, e) 是公鑰，而 (N, d) 是私鑰。
先來講它的加解密過程吧，我們會需要用到。
假設我現在產生了一組密鑰，然後有一組數據需要被加密：
公鑰：(65, 35)
私鑰：(65, 11)
原文：[63, 34, 27, 14, 50, 2, 21, 17]
接下來我們計算：
63 的 35 次方，再除以 65，得到餘數為 32
34 的 35 次方，再除以 65，得到餘數為 44
27 的 35 次方，再除以 65，得到餘數為 53
14 的 35 次方，再除以 65，得到餘數為 14
50 的 35 次方，再除以 65，得到餘數為 45
2 的 35 次方，再除以 65，得到餘數為 33
21 的 35 次方，再除以 65，得到餘數為 31
17 的 35 次方，再除以 65，得到餘數為 23
那就得到密文是 [32, 44, 53, 14, 45, 33, 31, 23] 了
反過來，持有私鑰 (65, 11) 的我，可以用同樣的方法恢復原文，計算：
32 的 11 次方，再除以 65，得到餘數為 63
44 的 11 次方，再除以 65，得到餘數為 34
53 的 11 次方，再除以 65，得到餘數為 27
14 的 11 次方，再除以 65，得到餘數為 14
45 的 11 次方，再除以 65，得到餘數為 50
33 的 11 次方，再除以 65，得到餘數為 2
31 的 11 次方，再除以 65，得到餘數為 21
23 的 11 次方，再除以 65，得到餘數為 17
成功恢復出原文 [63, 34, 27, 14, 50, 2, 21, 17]。
也就是說，如果我打算接收對方傳來的敏感訊息，那麼我可以產生一對公鑰 (65, 35) 和私鑰 (65, 11)，並且事先告訴對方：「在你要傳達訊息給我以前，請先使用公鑰 (65, 35) 把訊息加密。」
在此同時，已經產生的私鑰 (65, 11) 就自行妥善保管，從頭到尾都不讓任何人知道。當對方把加密後的密文傳送過來，我們只要利用保留在身上的這對私鑰 (65, 11)，就可以還原出對方的訊息了。
當然，這個計算過程產生的數是非常恐怖的，像是計算 50 的 35 次方會得到一個 60 位數的超大數字，所以在電腦裡也通常會用一些方式去優化、簡化這些過程，避免在加密、解密的過程耗費太多時間。
。RSA 的密鑰產生過程
如果明文（Plaintext）是 P、密文（Ciphertext）是 C，我們可以表達為：
RSA 產生金鑰的步驟如下：
1. 自行挑選兩個質數 p、q，把兩數相乘得到 N
2. 計算 φ(N)，得到 r
3. 尋找一個同時符合以下兩條件的數 e：
(1) 1 < e < r
(2) e 與 r 互質
4. 尋找一個數 d，符合「ed ≡ 1 (mod r)」的條件
5. 得到的 (N, e) 為公鑰，(N, d) 為私鑰
我們可以實作一次：
1. 挑選兩個質數 p=5, q=13，相乘得到 N=65
2. 計算 φ(N)，φ(65) = φ(5)φ(13) = 4×12，取名為 r，得到 r=48
3. 找到一個 e=35 符合「1 < e < r」而且「公因數 (35, 48) = 1」
4. 找到一個 d=11，符合「ed 除以 r 得到餘數為 1」（385÷48=8...1）
5. 得到 (65, 35) 為公鑰，(65, 11) 為私鑰
。RSA 的前備知識
說到原理層面就開始複雜起來了，這也是我花最多時間消化的地方。在開始講原理以前，必須要有兩個前備知識，一個是歐拉函數，一個是費馬小定理。
首先講歐拉函數。數學家歐拉曾經研究了一個函數 φ(n)，這個函數簡單來說就是「求得 1~n 之間和 n 互質的數字個數」。比如在 6 這個數底下只有 1, 5 兩個數和 6 互質，所以 φ(6)=2；在 21 底下有 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20 一共 12 個數字跟 21 互質，所以 φ(21)=12。
但如果今天 n 是一個質數，我們知道像 13 這個數字，在它底下 1~12 每個數字都跟 13 互質，不可能會有其他的公因數，所以我們可以知道在 n 是質數的狀況下 φ(n) = n-1。
另一方面，歐拉函數有個特性，就是如果 m、n 互質，那麼 φ(mn) = φ(m)φ(n)，這也是為什麼產生金鑰的時候 φ(N) = φ(pq) = φ(p)φ(q) = (p-1)(q-1) 了。
接下來便是真正的核心。1636 年，費馬發現了當 p 是質數的狀況下：
換個講法也可以說 
可以被 p 整除，這正是費馬小定理。一百年後，歐拉正式把費馬小定理證明出來，並且把它拓展成：
可以被 p 整除，這正是費馬小定理。一百年後，歐拉正式把費馬小定理證明出來，並且把它拓展成： 當 a 和 n 互質的情況下，
當然同樣也可以換個說法：「若 a 和 n 互質，則 
可以被 n 整除」，這兩件事情是一樣的。
可以被 n 整除」，這兩件事情是一樣的。。實際的 RSA 加解密推導
那麼我們現在再回來看 RSA 的加解密流程：
明文 P、密文 C、公鑰 (N, e)、私鑰 (N, d)、某整數 K
在 RSA 的加密過程，首先我們透過公鑰 (N, e) 加密：
計算 
那我們自然可以把式子表達為：
現在，我們必須證明 
，因為只有在證明這件事之後才能確保「在使用 e 加密過後，還能使用 d 來順利解密」。
，因為只有在證明這件事之後才能確保「在使用 e 加密過後，還能使用 d 來順利解密」。 先把剛剛加密的式子變換一下，我們知道 
會得到 N 的某個倍數，那麼反過來說 
也會是 N 的某個倍數（只是差了一個負號而已）：
會得到 N 的某個倍數，那麼反過來說 也會是 N 的某個倍數（只是差了一個負號而已）： 我們要證明 ，於是兩邊同時作 d 次方：
，於是兩邊同時作 d 次方： 我們觀察二項式 (x+y) 的冪次展開，不難發現除了第一項以外，後面的每一項都有 y 的蹤影：
據此，我們可以知道 
這個式子展開以後，除了第一項會是 
以外，每一項因為都曾經乘過至少一次 
，這些第二項以後的東西既然每個都是 N 的倍數，那麼加起來就也一定會是 N 的倍數——所以我們可以乾脆把它寫成 
。
這個式子展開以後，除了第一項會是 以外，每一項因為都曾經乘過至少一次 ，這些第二項以後的東西既然每個都是 N 的倍數，那麼加起來就也一定會是 N 的倍數——所以我們可以乾脆把它寫成 。 接下來，我們回去看產生密鑰的過程，可以看到 ed ≡ 1 (mod r) 這件事情，也就是指 ed 除以 r 會得到餘數為 1，也就是說我們可以說 
，那麼剛剛的式子就可以改寫為：
，那麼剛剛的式子就可以改寫為： 提出一個 P：
再回頭對照一下，r 是怎麼來的呢？可以看到 r 是透過 φ(N) 得來的，所以又可以改寫成：
接下來就用到前面講到的費馬小定理了，我們知道 
會是 1 + (N的某個倍數)，所以就能再改成：
會是 1 + (N的某個倍數)，所以就能再改成： 整理：
我們證明了在遵守 RSA 密鑰產生程序得出 N、e、d 三個數的情況下：
當 
，則 
，則 也就有：
當 
，則 
，則 這過程的每個 K 都是某個整數，具體的數值是多少並不重要，因為我們只在乎計算完以後求得的餘數而已。
大概就是這樣。至於他們是如何想到可以這麼做，你大概就要去問 Ron Rivest、Adi Shamir、Leonard Adleman 這三個神人了。
。RSA 的安全性
我們從推導過程可以窺見，RSA 的安全性是建立在「質數」上面的。如果我們一開始在產生金鑰時選擇的兩個質數 p、q 非常小，那麼嘗試破解的駭客就可以自行產生出用來嘗試的公鑰、私鑰，並且試圖解開這些密文，所以為了避免這種狀況發生，我們必須在產生金鑰的時候選擇夠大的質數。
這些用來加密的 N、e、d 產生出來以後，如果其他人截取了密文 C，想要從 C 恢復成明文 P，那麼他們就得先知道 d；如果要取得 d，那麼就得知道 r 的值（也就是 φ(N)）；如果想取得 φ(N) 的值，就得要知道 p 和 q（因為 φ(N) = φ(p)φ(q) = (p-1)(q-1)）；要想知道 p 和 q 的值，就得成功把 N 質因數分解……
這正是 RSA 的安全基礎。想像一下，我們可以很輕鬆地把兩個質數 3389 和 2377 相乘得到 8055653，但要是反過來在你手上只有「8055653」的情況下，我們就難以把它短時間內分解成 3389 和 2377 了。
而且這還只是舉例，3389 和 2377 這兩個數對於電腦來說已經算是很小了。現行的業界標準是 RSA-2048，意思是 p 和 q 相乘以後得到的 N，大約有 2 的 2048 次方這麼大——利用高中所學的 log 位數估算法，我們可以從 2048×log 2 ≒ 616.51 得知，這個由 p 和 q 相乘得到的 N 可是一個多達 617 位數的天文數字！
以現在的技術而言，符合 RSA-2048 標準的 N 值是即使傾全球之力也無法短時間內成功分解的數，因為除了把合數篩選掉（然後一個一個往上嘗試是否能夠整除）的方式以外，現今的數學家還沒有想到可行的方法能夠讓現有的經典電腦快速地分解掉這種大型的半質數。
當然，這也不代表 RSA 未來不會在某個時間點被破解——也許將來量子電腦發展成熟，人類得以使用秀爾演算法快速地分解大型半質數，又或者某個超越 RSA 發明者的怪物出現，突然就發明出了能夠快速分解半質數的算法，使得金融、通訊體系的安全性一夕之間被打垮，這都不是不可能。
不過，這樣的可能性畢竟還是比較小的。即使量子電腦已經在邁向發展成熟的路上，現在世界上的科學家們也正相應地發展「基於量子電腦的量子密碼學」，我相信未來的通訊安全只會隨著時間而越來越牢固。我們平常在使用各類金融、資訊服務的同時，也別忘了這些科學家的偉大貢獻。
參閱：
維基百科相關條目：
