密碼學 RSA 演算法

---

---

RSA（Rivest-Shamir-Adleman）是一種著名的加密方案，它使用公鑰和私鑰的組合。這意味著您擁有一個非公開金鑰和一個可以公開共享的金鑰。每個金鑰都可以用於加密資料，但只有相反的金鑰才能解密。RSA 由麻省理工學院的研究人員羅恩·萊維斯特、阿迪·薩莫爾和倫納德·阿德曼於 1977 年開發，規則集的名稱也以他們的名字命名。

儘管 RSA 作為一種強大的加密方法很受歡迎，但其高計算需求使其效率低下且資源密集。因此，它可能不是加密大型訊息或檔案的最佳選擇，因為它可能會耗盡系統的資源。

RSA 如何工作？

RSA 基於將大數分解為其素因子的問題。要建立 RSA 金鑰對，您需要選擇非常大的素數 p 和 q。隨機選擇這些素數並確保它們彼此唯一非常重要。p 和 q 的乘積，表示為 n，成為公鑰和私鑰的模數。雖然 n 是公開的，但 p 和 q 的值保持機密。

計算兩個素數 p 和 q 的乘積的卡邁克爾函式。選擇一個整數 e 作為公鑰指數。最後一步涉及計算 d，它充當私鑰指數。

示例

假設我們選擇 p = 61 和 q = 53。

n = p * q = 61 * 53 = 3233

φ(n) = (p-1)(q-1) = 60 * 52 = 3120

讓我們選擇 e = 17（一個常見的選擇）。

d = 2753（計算方式為 (17 * d) mod 3120 = 1)

因此，公鑰為 (3233, 17)，私鑰為 (3233, 2753)。

加密

要加密訊息，傳送方使用接收方提供的公鑰 (n, e)。使用以下公式將明文訊息 (m) 轉換為密文 (c)：

c = m^e mod n。

假設我們要加密訊息“HELLO”。我們將其轉換為 ASCII：H(72) E(69) L(76) L(76) O(79)。

我們將分別加密每個 ASCII 值：

• H：C = 72^17 mod 3233 = 2103
• E：C = 69^17 mod 3233 = 2464
• L：C = 76^17 mod 3233 = 2190
• L：C = 76^17 mod 3233 = 2190
• O：C = 79^17 mod 3233 = 875

解密

收到密文 (c) 後，接收方使用其私鑰 (n, d) 解密訊息。使用以下公式計算明文訊息 (m)：

m = c^d mod n。

接收方收到密文 (2103, 2464, 2190, 2190, 875)。

他們使用他們的私鑰解密每個值：

• M = 2103^2753 mod 3233 = 72 (H)
• M = 2464^2753 mod 3233 = 69 (E)
• M = 2190^2753 mod 3233 = 76 (L)
• M = 2190^2753 mod 3233 = 76 (L)
• M = 875^2753 mod 3233 = 79 (O)

因此，解密後的訊息為“HELLO”。

應用和用例

RSA 用於各種資訊安全和密碼學應用。一些最流行的應用程式包括：

數字簽名

數字簽名是一種技術，允許訊息的接收者確認其真實性、完整性和不可否認性。它驗證訊息在傳輸過程中未被更改。

在建立數字簽名時，傳送方首先使用密碼雜湊函式為訊息生成雜湊值。然後使用私鑰執行 RSA 演算法對其進行簽名，從而生成數字簽名作為輸出。接收方可以使用傳送方的公鑰對數字簽名應用 RSA 演算法。

您還可以透過將其與為訊息建立的雜湊值進行比較來驗證簽名。

數字證書

RSA 通常用於數字證書，包括 SSL 證書。這些證書可用於驗證執行網站的人員或組織的身份。

數字證書使用 RSA 加密證書頒發機構的數字簽名，然後使用其公鑰進行驗證。數字證書包含域名和擁有該網站的組織等資訊，這有助於向客戶端建立網站的真實性。

安全金鑰交換

RSA 的另一個應用是在兩個以前從未共享過秘密金鑰的個人之間進行安全金鑰交換。雙方使用 RSA 方法生成公鑰-私鑰對。

傳送方建立一個對稱金鑰，使用接收方的公鑰對其進行加密，並將加密後的金鑰傳輸給接收方。

接收方使用私鑰對其進行解密。傳送方和接收方共享相同的對稱金鑰，他們可以使用該金鑰進行安全通訊。

安全通訊協議

RSA 在不安全的網路（如網際網路）中在雙方之間加密訊息。例如，RSA 與傳輸層安全 (TLS) 一起用於在網路伺服器和瀏覽器之間建立安全連線。此外，RSA 透過啟用訊息加密和解密來實現安全的電子郵件通訊。

它也用於虛擬專用網路 (VPN)。VPN 使用 TLS 在共享資訊的雙方之間建立握手。TLS 握手使用 RSA 方法來驗證參與交易的雙方的真實身份。

RSA 如何保證安全？

RSA 的安全性依賴於計算機難以找到加密金鑰中的素數。更長的金鑰增加了破解程式碼的難度。雖然 1024 位金鑰曾經被認為是安全的，但計算能力的提高導致轉向 2048 位金鑰。

橢圓曲線密碼術 (ECC) 是一種金鑰生成方法，它提供了更快的速度和更低的電池消耗，使其成為移動裝置的首選。一項研究成果涉及使用聲波建立 RSA 金鑰，但這種方法對於大多數駭客來說仍然不切實際。請記住，無論如何，每種加密方法都可以被破解，這只是時間和精力的問題。

RSA 的優勢

Rivest-Shamir-Adleman 有一些優勢 -

• 增強的安全性 - RSA 加密消除了共享金鑰的需要，最大程度地降低了未經授權訪問的風險。
• 驗證的通訊真實性 - 金鑰對的互連確保只有授權的接收者可以訪問訊息，防止攔截。
• 高效加密 - 與 DSA 演算法相比，RSA 加密提供更快的加密速度，從而加快資料傳輸速度。
• 資料完整性 - 在傳輸過程中更改資料將破壞金鑰的使用，防止未經授權的解密。這確保檢測到篡改並通知接收者。

總結

RSA 是一種自 1977 年以來流行的加密演算法，它使用公鑰和私鑰對。雖然適用於各種任務，但 RSA 的複雜性限制了其用於加密大型資料的使用。相反，RSA 擅長建立數字簽名和證書，確保安全的身份驗證、通訊和金鑰交換。RSA 面臨潛在的漏洞，包括未經授權的訪問、弱金鑰編號、不安全的素數、故障利用和金鑰盜竊。為了降低這些風險，在將 RSA 用於加密應用時，實施本文中提供的建議至關重要。