質因數分解造就的加密美學 - RSA 非對稱式加密演算法

在上一篇文章中 Base64? SHA? MD5? AES? 你搞得我好亂啊，我們介紹了編碼、雜湊、加密的基本概念，並且說明了它們之間的差異與應用場景，今天我們要更深入地探討加密這件事。加密這件事在人類歷史上已經存在了數千年。因為有著軍事和外交的需求，人們需要一種方法來保護訊息不被敵人窺探。即使訊息被截取，也要讓敵人無法理解內容。從古老的凱薩密碼（Caesar Cipher）談起，一直到現代的 RSA 非對稱式加密，並且解釋為什麼 RSA 如此廣泛的在現代電腦科學中應用。

一、古老的凱薩密碼（Caesar Cipher）

凱薩密碼是由古羅馬將軍凱薩（Julius Caesar）發明的一種簡單加密方法。它的原理是將字母表中的每個字母向後移動固定的位數來進行加密。例如，使用位移 3 的凱薩密碼：

• 明文：ABCDE
• 密文：DEFGH
• 加密過程：
  • A -> D
  • B -> E
  • C -> F
  • D -> G
  • E -> H

但是這樣的加密方式非常容易被破解。只要嘗試所有可能的位移（總共有 25 種可能性），就能輕易地還原出原始訊息。

二、德軍的恩尼格瑪密碼機（Enigma Machine）

在第二次世界大戰期間，德國軍隊使用了一種稱為恩尼格瑪密碼機的機械裝置來加密他們的通訊。恩尼格瑪密碼機利用了多個轉子和插頭板來進行複雜的字母替換，使得每次按下鍵盤時，輸出的字母都會不同。這種加密方式大大增加了破解的難度，讓同盟國的情報人員頭痛不已。然而，同盟國軍的密碼破譯專家，如艾倫·圖靈（Alan Turing），設計出了最早期的計算機來破解恩尼格瑪密碼，最終成功地解讀了大量德軍的通訊，對戰爭的勝利起到了關鍵作用。

INFO

艾倫·圖靈作為現代計算機科學和人工智慧的先驅，《圖靈獎》這個電腦科學界的最高榮譽是以他的名字命名的。私心推薦 模仿遊戲 這部電影，講述了艾倫·圖靈和他的團隊如何破解恩尼格瑪密碼的故事，非常精彩且富有啟發性。

三、現代的對稱式加密：AES

隨著計算機技術的發展，對稱式加密演算法如 AES（Advanced Encryption Standard）成為了現代加密的主流。對稱式加密使用相同的密鑰來進行加密和解密。AES 支持多種密鑰長度（128、192、256 位元），並且被廣泛應用於各種安全通訊協議中，如 HTTPS、VPN 等。

在上一篇文章中 Base64? SHA? MD5? AES? 你搞得我好亂啊，我們談到混合式加密，先透過非對稱式加密來交換對稱式加密的密鑰，然後使用對稱式加密來加密連線要傳送的資料，這個對稱式加密演算法就是 AES。

四、非對稱式加密的革命：RSA

RSA（Rivest-Shamir-Adleman）是由 Ron Rivest、Adi Shamir 和 Leonard Adleman 在 1977 年發明的一種非對稱式加密演算法。非對稱式加密使用一對密鑰：公鑰（public key）和私鑰（private key）。公鑰可以公開給任何人用來加密訊息，而私鑰則必須保密，用來解密訊息。

RSA 的數學基礎

RSA 其實是一個質因數分解的問題。它以歐拉函數（Euler's Totient Function）和模指數運算為基礎。

INFO

歐拉函數是一個為了尋找小於 n 的正整數中，與 n 互質（最大公因數為 1）的數量的函數。比如說 n = 11，11 是質數，所以小於 11 的正整數 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) 都與 11 互質，因此 φ(11) = 10。

而歐拉函數有一個重要的性質：如果 n 是由 p 和 q 兩個不同的質數相乘的，則 $p\ast q$ 的質數數量等於 $(p-1)(q-1)$。。

以下是 RSA 產生公私鑰的基本步驟：

1. 選擇兩個質數 p 和 q。例如，p = 3，q = 11。
2. 計算一個模數 $n=p\ast q$。例如，$n=3\ast 11=33$。
3. 計算歐拉函數 $\phi (n)=(p-1)(q-1)$。例如，$\phi (33)=(3-1)(11-1)=2\ast 10=20$。
4. 接著選擇一個質數當作公鑰指數 $e$，使得 $1<e<\phi (n)(\mathrm{這}\mathrm{裡}\mathrm{是}20)$ 且 $e$ 與 $\phi (n)$ 互質。例如，選擇 $e=3$。我們就可以說：公鑰是 $(e,n)=(3,33)$。
5. 接著要透過一個數字 $d$ 讓 $(d\ast e)\mathrm{對}\phi (n)$ 取餘數後等於 1。也就是 $(d\ast 3)mod20=1$。
6. 移向一下變成 $d\ast 3=20+1$，則 $d\ast 3=21$，所以 $d=7$。我們就可以說：私鑰是 $(d,n)=(7,33)$。
7. 現在我們有了公鑰 $(3,33)$ 和私鑰 $(7,33)$，我們可以用公鑰來加密訊息，用私鑰來解密訊息。

加密方式：$C=M^{e}modN$

以 明文訊息 $M=4$、$\mathrm{公}\mathrm{鑰}(e,N)=(3,33)、\mathrm{私}\mathrm{鑰}(d,N)=(7,33)$為例：

明文 M	指數 e	模數 N	密文 C = M^e mod N
4	3	33	31

則加密步驟為：

1. $C=4^{3}mod33=64mod33=1...\mathrm{餘}31$
2. 所以密文 $C=31$

解密方式：$M=C^{d}modN$

以 明文訊息 $M=4$、$\mathrm{公}\mathrm{鑰}(e,N)=(3,33)、\mathrm{私}\mathrm{鑰}(d,N)=(7,33)$為例：

密文 C	指數 d	模數 N	明文 M = C^d mod N
31	7	33	4

則解密步驟為：

1. $M={31}^{7}mod33=27512614111mod33=4$
2. 所以明文 $M=4$

逆推與破解

看到這裡你可能會想：

$C=4^{3}mod33=64mod33=1...\mathrm{餘}31$

就算把 $M=4$ 隱藏起來變成：

$C=M^{3}mod33=64mod33=1...\mathrm{餘}31$

只要移向

$M^3=33k+31(k\mathrm{為}\mathrm{任}\mathrm{意}\mathrm{商}\mathrm{數}，\mathrm{這}\mathrm{裡}k=1，\mathrm{因}\mathrm{為}\mathrm{只}\mathrm{除}\mathrm{了}\mathrm{一}\mathrm{次}\mathrm{就}\mathrm{找}\mathrm{到}\mathrm{餘}\mathrm{數}\mathrm{了})$

然後對 $M$ 進行開三次方根就能還原出 $M=4$ 了啊！明明很容易就能用公鑰就能逆推明文嘛？

是這樣，但不是這樣。

通常實際上在使用 RSA 時，指數 $e$ 會選擇一個比較大的質數（像是 65537）、模數 $N$ 也會選擇非常大的質數乘積（通常至少 2048 位元長度），這樣一來即使知道密文 $C$ 和公鑰 $(e,N)$，要逆推出明文 $M$ 會非常消耗算力跟時間。

就算只設定比較長的指數 $e$，像是 65537，公式套入上面的公鑰就會變成：

$31=M^{65537}mod33$

則逆推會變成：

$M^{65537}=(k\ast 33)+31(k\mathrm{為}\mathrm{任}\mathrm{意}\mathrm{商}\mathrm{數})$

然後把 65537 次方根轉移到右邊：

$M=((k\ast 33)+31{)}^{1/65537}$

即使用迴圈的方式遞增 $k=1,k=2,k=3...k=???$，然後每次都要算一次 $65537$ 次方根，這樣的計算量是非常龐大的。即使使用現代的超級電腦，也需要花費數百年才能破解。

然後你可能又想：哇，$e$ 值越大越安全，那這樣 $e$ 只要夠大，是不是 $p\mathrm{跟}q$ 值就不需要那麼大了？

回到我們前面的步驟 4：

明文 M	指數 e	模數 N	密文 C = M^e mod N
M=?	65537	33	31

則加密步驟為：

1. $C=M^{65537}mod33=(k\ast 33)+31$

如果要算出 $M^{65537}$ 看似很困難，但其實重點並不是 $e$ 值多大，而是 $N$ 的質因數分解難度，只要能夠破解 $N$ 就可以直接依靠質因數分解推導出私鑰，當然就能解開了。

而這裡的 $N$ 只有 $33$，光是用心算都能輕易地分解出 $p=3$ 和 $q=11$。一旦知道了 $p$ 和 $q$，就能輕易地計算出私鑰 $d$，從而破解整個加密系統。所以對於計算速度更快的現代電腦來說，破解這段加密只需要幾毫秒。

所以，RSA 的安全性主要依賴於大質數的選擇和質因數分解的困難度，選擇足夠長度的 $N$ 是確保 RSA 安全性的關鍵。

六、RSA 的安全性與位元長度

在 2048 bit 長度下的 RSA 使用暴力破解，就算以比特幣的全網算力(約 $600\text{ EH/s}$，即每秒 $6\times {10}^{20}$ 次運算)，大約也需要 27 萬年才有可能被破解。

在現代計算能力越來越強大的環境下，像是 RSA-1024（1024 位元長度的 $N$）在現代已經被認為不夠安全，建議至少使用 RSA-2048 或更高位元長度的 $N$ 來確保安全性。甚至有些機構已經開始使用 RSA-3072 或 RSA-4096 來應對未來的安全需求。

你可能很好奇，既然長度越長越安全，那為什麼不用一個超級長超級大的質數呢？因為數字越大、加密的運算量就越大，會導致加密和解密的速度變慢，會很影響系統的效能。就像每次你瀏覽網頁，都需要對網站憑證的簽章進行解密，如果每次都需要幾分鐘才能解密，那使用者體驗就會非常差。因此在實際應用中，需要在安全性和效能之間找到一個平衡點。

五、RSA 的應用 - 區塊鏈與數位簽章

在現代應用中，RSA 被廣泛應用於各種安全通訊協議和數位簽章中。而近年很火紅的區塊鏈技術也大量使用了非對稱式加密來確保交易的安全性和完整性。透過 RSA，使用者可以生成一對公私鑰，公鑰用於接收資產，而私鑰則用於簽署交易，確保只有擁有私鑰的人才能發起交易、簽署。也因此，保護私鑰的安全性成為了區塊鏈使用者的首要任務。

六、RSA 的挑戰與未來

儘管 RSA 在過去數十年中一直是非對稱式加密的主流，但隨著量子計算技術的發展，RSA 面臨著被破解的風險。量子電腦能夠利用 Shor 演算法在多項式時間內分解大質數，這將使得 RSA 的安全性大幅降低。因此，研究人員正在積極探索量子抗性加密演算法，如格基加密（Lattice-based Cryptography）和多變量多項式加密（Multivariate Polynomial Cryptography），以應對未來量子計算帶來的挑戰。

也許在不久的將來，我們會看到新的加密技術取代 RSA，成為保護數位世界安全的基石。但無論如何，理解 RSA 的原理和運作方式，對於我們理解現代加密技術的發展歷程和未來趨勢，都是非常重要的。