RSA 加密逐步模擬器

什麼是 RSA 加密？

RSA (Rivest-Shamir-Adleman) 是最早發布的公鑰加密系統之一，由 Ron Rivest、Adi Shamir 和 Leonard Adleman 於 1977 年發表。與對稱加密（使用相同密鑰進行加密與解密）不同，RSA 使用一對密鑰對：任何人都可以使用的公鑰用於加密數據，而只有所有者擁有的私鑰用於解密數據。

RSA 的數學安全性建立在大整數分解問題之上：將兩個大質數相乘非常簡單，但將其乘積分解回質數在計算上對於足夠大的數字是不可行的。

RSA 密鑰生成的工作原理

RSA 密鑰生成過程包含五個基本步驟：

• 步驟 1 – 選擇質數： 選擇兩個不同的、足夠大的質數 p 和 q。質數越大，密鑰越安全。
• 步驟 2 – 計算模數： 計算 n = p × q。n 的位元長度決定了密鑰的大小（例如 2048 位元）。
• 步驟 3 – 尤拉函數： 計算 φ(n) = (p−1)(q−1)。此數值對於選擇 e 和計算 d 至關重要。
• 步驟 4 – 公鑰指數： 選擇 e，使得 1 < e < φ(n) 且 gcd(e, φ(n)) = 1。標準選擇通常為 65537。
• 步驟 5 – 私鑰指數： 使用擴展歐幾里得演算法計算 d，使得 d × e ≡ 1 (mod φ(n))。

擴展歐幾里得演算法

計算私鑰指數 d 需要找到 e 模 φ(n) 的模反元素 (modular multiplicative inverse)。擴展歐幾里得演算法能有效解決此問題，它擴展了標準的 GCD 演算法，同時找出係數 x 和 y，使得 a·x + b·y = gcd(a, b)。

當 gcd(e, φ(n)) = 1 時，演算法會產出 x，使得 e·x ≡ 1 (mod φ(n))，進而得出 d = x mod φ(n)。

RSA 安全性考量

• 密鑰大小： 現代 RSA 使用 2048 或 4096 位元密鑰。本模擬器中的小質數僅用於教學目的，可被瞬間分解。
• 填充方案 (Padding)： 現實世界中的 RSA 實現會使用填充（如 OAEP, PKCS#1）來防止針對原始 RSA 的數學攻擊。
• 效能： RSA 的運算速度遠慢於對稱加密。實務上，RSA 通常用於加密一個隨機的對稱金鑰，再由該金鑰加密實際數據（混合加密）。
• 量子威脅： 在足夠強大的量子電腦上運行 Shor 演算法可以高效分解大數，威脅 RSA 安全性。後量子密碼學 (PQC) 正被開發作為應對措施。

RSA 的實際應用

• TLS/SSL (HTTPS)： RSA 用於握手期間安全地交換對稱會話金鑰。
• 數位簽章： RSA 透過使用私鑰加密雜湊值來簽署文件，並可透過公鑰進行驗證。
• 電子郵件加密： PGP 和 S/MIME 使用 RSA 來加密郵件通訊。
• SSH 驗證： RSA 密鑰對為遠端伺服器訪問提供免密碼驗證。
• 程式碼簽章： 軟體發行商使用 RSA 對執行檔進行簽名，以證明真實性與完整性。

常見問題