RSA 加密是什麼，其運作原理為何？

Sep 12, 2023

12 分鐘閱讀

RSA（Rivest-Shamir-Adleman）加密是最古老的公開金鑰加密系統之一，但至今仍然被廣泛使用。從建立 VPN 連線到加密電子郵件，RSA 密碼系統的應用非常廣泛。但 RSA 加密是如何運作的，演算法是否真的安全？讓我們仔細深入探討。

內容

RSA 加密的定義
RSA 加密的運作原理為何？
RSA 加密用於何處？
RSA 加密的優點和缺點
RSA 演算法漏洞
針對 RSA 加密的攻擊
RSA 加密是否安全？
RSA 加密的未來

RSA 加密的定義

RSA 是一種公開金鑰加密系統，用於建立安全連線和創立數位簽章。

RSA 加密的名字由來為其創立者李維斯特（Rivest）、薩莫爾（Shamir）和阿德曼（Adleman）的姓氏開頭字母所組成，他們於 1977 年在麻省理工學院工作時提出了該演算法。

RSA 使用公鑰加密訊息，使用私鑰解密訊息。RSA 加密演算法背後的數學原理包含一個單向函數——計算容易，但逆轉卻非常具有挑戰性。這使得 RSA 成為一種幾乎不可能使用蠻力攻擊破解的安全加密演算法。

RSA 加密的運作原理為何？

RSA 是一種需要使用公鑰和私鑰的非對稱式密碼學（公開金鑰密碼學）。

您需要公鑰來加密訊息——把明文訊息轉變為密文。公鑰可以公開共用和存取。
您需要私鑰來解密加密訊息——將密文轉換為明文訊息。私鑰必須隨時維持保密狀態。

小明使用公鑰加密明文訊息，而小華使用私鑰解密密文。

另一方面，對稱加密使用相同的私鑰來加密和解密訊息。當可以事先與訊息接收者安全共用私鑰時，對稱加密即可很好地發揮作用。而如果情況不允許時，包含 RSA 在內的公開金鑰加密就非常實用。

非對稱加密演算法包含四個部分：公鑰和私鑰的產生、（公開）金鑰交換（透過金鑰交換演算法）、加密和解密。

金鑰產生

金鑰產生是計算 RSA 金鑰（一對私鑰和公鑰）的過程。此過程包含以下步驟：

1. 選擇兩個質數（p 和 q）

為了確保加密安全性，必須選擇兩個大且不同的質數。

例如，2048 位元 RSA 加密使用 308 位數大小的質數。由於得出如此大的數字並不容易，因此需要進行質數測試。

2. 計算模數（n）

私鑰和公鑰的前半部分是模數（n），即 p 和 q 的乘積：

n = p x q

雖然計算起來很容易，但實際上要估算出是哪個數字相乘才能得到乘積是不可能的。

舉例來說，如果 p 為 6,637，q 為 8,971，手機上的計算機應用程式可以得出兩數相乘為 59,540,527。但是，如果此一數字 59,540,527 擺在眼前，您能判斷或使用同個計算機來確定乘積是由精確的哪些數相乘而得的嗎？

可能無法。這就是 RSA 加密背後的理念——演算法需要容易計算，但又不能被逆轉。

對於因數分解計算機來說，上面例子中的數字很容易分解。然而，如前所述，RSA 加密使用 308 位大小的質數，因此要大得多，計算起來也更加困難。

3. 產生公鑰（e）

RSA 公鑰由模數（n）和公鑰指數值（e）組成。在得到 e（公鑰後半部分）之前，需要先計算 φ（n 的總和）：

φ (n) = (p − 1) x (q − 1)

然後可以選擇 e（一個大於 1 但小於 φ，且與 φ 互質的任意整數）。在 RSA 加密中，通常使用 65,537 作為 e。

4. 產生私鑰（d）

RSA 私鑰由模數（n）和私鑰指數值（d）組成。d 由 p 和 q 計算得出，需要找出這些數字的最大公因數（GCD）。此過程被稱為歐幾里得演算法（輾轉相除法），交給線上計算機會更容易。

金鑰分發

如果有人想使用 RSA 為您的訊息加密，他們需要知道您的公鑰。您可以任何可靠的方式共用公鑰，不一定非要透過秘密途徑。

加密

假設另一端的人取得了您的公鑰（e 和 n），想給您傳送一條訊息（M）。接下來會發生什麼事？

要將明文訊息轉換為密文（C），需要使用以下函數：

C = Me mod n

Mod 代表取模操作（modulo operation），指的是一方除以另一方後剩下的餘數，例如，11 mod 3 = 2（11 除以 3 等於 3 餘 2）。

如果想傳送的訊息是數字，只需將 M 替換為數字即可，此函數會包含所有缺失的部分。如果是封簡訊，就需要先將文本轉換為數字。例如，使用 ASCII 碼，訊息「NORDVPN」的數字即為「78798268868078」。

解密

要解密收到的密文，需要從秘密位置找出私鑰（d 和 n），取出密文（C）並使用以下函數：

M = Cd mod n

其會將秘文轉換回原始訊息。

小明產生自己的一對公鑰和私鑰。小華使用小明的公鑰加密訊息。小明使用 RSA 私鑰解密密文，以便讀取訊息。

RSA 加密用於何處？

RSA 作為一種公開金鑰加密技術，其在您要將訊息安全傳送給之前從未聯繫過的人或伺服器時非常實用，因為他們沒有對稱加密的私鑰。因此，您可在瀏覽器、電子郵件供應商、聊天應用程式、雲端服務、VPN、P2P 系統和其他通訊管道中看到其身影。

然而，就數位加密而言，RSA 現已過時，所以通常會搭配其他加密方案一起使用。一個基本的例子是使用 RSA 加密對對稱加密的私鑰進行加密，進而可以安全共用金鑰，同時又能使用對稱加密保護實際的敏感資料。

RSA 的主要用途包含建立安全連線和創立數位簽名。RSA 不用於加密訊息或檔案，因為其他的加密系統更加安全和快速，所需資源也更少。

建立安全連線

網頁瀏覽器使用 RSA 建立安全的網際網路連線，這有助於防止嗅探或中間人攻擊。大多數網際網路連線都使用 SSL 來確保流量安全，而 RSA 是 SSL/TLS 握手的一部分。您可於 OpenSSL 等加密庫中看到其身影。

OpenVPN 使用 RSA 進行金鑰交換，並在建立 VPN 連線時確保 VPN 用戶端和 VPN 伺服器之間的通訊安全。不過，VPN 通常會使用不同的加密密碼來保護實際資料。例如，NordVPN 的下一代加密就是採用 AES-256-GCM。

RSA 也是 PGP 加密中第一種用於加密連線階段金鑰的演算法。

創立數位簽名

您可以使用私鑰來簽署訊息或文件，而對方則可以使用公鑰來驗證該訊息或文件的真實性。

其功能非常廣泛，因此在數位簽章方面，RSA 可以用於任何地方，從電子郵件、網銀到線上購物都可以。

例如，電子郵件通常使用 PGP 加密進行數位簽章，該技術就是使用 RSA 演算法創立數位簽章。

RSA 加密的優點和缺點

RSA 加密系統有其優缺點，在實施 RSA 加密之前應加以考慮。

RSA 演算法易於實施和理解。此演算法非常基本，與其他演算法相比，功能較不複雜，例如，RSA 的主要替代方案橢圓曲線密碼學，許多服務正在轉向使用橢圓曲線密碼學，因為其在資源管理方面效率更好。
RSA 加密功能廣泛，因此可以（且正在）被廣泛使用。
如果實施得當，RSA 加密是無法使用蠻力攻擊破解的，至少在目前的計算能下是如此。
如果實施不當，RSA 很容易受到多種攻擊的侵害。
RSA 金鑰的長度對於加密安全性至關重要，但產生較長的金鑰需要大量計算能。
解密也需要耗費大量時間且需要大量資源。
可用的 RSA 公鑰數量增加，使得攻擊者更容易設計出破解或克服加密的方法。

RSA 演算法漏洞

RSA 的安全性在很大程度上取決於其實施。過程的每個部分都可能涉及影響到加密結果的漏洞。

較弱的隨機數產生器

RSA 演算法從選擇質數開始，而這第一步可能就是最易受攻擊的部分。如果質數不夠隨機，就很容易因數分解並破解加密。

較弱的隨機數產生器通常會在此處出錯，因此可以使用偽隨機數產生器來避免此漏洞。

錯誤的金鑰產生

質數可能足夠隨機，但是數字太小或彼此太相近，這就是另一個問題。

由於 RSA 演算法使用公鑰進行加密，因此金鑰大小對於防止因數分解至關重要。當數字較小時，找出質數（p 和 q）就更容易。如果數字彼此太相近，那麼私鑰（d）就會相對較小。

這就是為什麼安全專家建議最小金鑰大小為 2048 位元，而較新的 RSA 金鑰通常為 4096 位元。

針對 RSA 加密的攻擊

對上述 RSA 漏洞的忽視會導致 RSA 容易受到攻擊。

因式分解攻擊（Factorization attack）

如果不解決上述漏洞，網路犯罪份子就可以利用漏洞進行因式分解攻擊。

只有在沒有人能從乘積 n 中發現質數 p 和 q 時，RSA 加密才是安全的。然而，如果質數彼此過於相近，或太小和不夠隨機，攻擊者就可以對其進行因式分解，幾乎不費吹灰之力就能暴露私鑰。

旁路攻擊（Side-channel attack）

在旁路攻擊中，攻擊者會分析解密過程中收集到的額外資訊，而非破解加密金鑰。例如，他們會檢驗演算法使用了多少電力，甚至是電腦在解密過程中所發出的聲音。

時間攻擊也是旁路攻擊的一種。在 RSA 時間攻擊中，攻擊者會分析不同已知密文的解密時間，進而推導出私鑰（d）。

明文攻擊（Plaintext attack）

如果攻擊者比對出明文訊息的任何部分與密文，就可以進行明文攻擊：

短訊攻擊。攻擊者可以存取明文訊息的某些部分，並對其加密來取得密文。然後，他們就可以用其來推斷出明文訊息的其他部分。可以透過使用「填充方式」——在加密明文訊息前，在訊息中包含額外資料，來避免此種明文攻擊。
循環攻擊。攻擊者會測試可能用於創立密文的排列操作。如果成功，他們就可以逆轉過程，從密文中取得明文訊息。
公開訊息攻擊。此種情形很少見，但從理論上來說，某些加密密文可能與原始明文訊息完全相同。如果出現此種情形，攻擊者就可以推斷出加密訊息的其他部分，並進行公開訊息攻擊。