一、RSA 簡介
RSA 是一種公鑰密碼體制，由羅納德?李維斯特（Ron Rivest）、阿迪?薩莫爾（Adi Shamir）和倫納德?阿德曼（Leonard Adleman）于 1977 年提出，算法名稱由他們三人姓氏的首字母組成。與對稱加密算法不同，RSA 使用不同的加密密鑰與解密密鑰，屬于非對稱加密方式。
RSA 涉及三個重要參數：n、e、d。其中，(n, e) 作為公鑰可對外公開，(n, d) 則作為私鑰由用戶妥善保存。這里的 n 是兩個大素數 p 和 q 的乘積，即 n = p * q；e 是一個滿足 1 < e < φ(n) 且與 φ(n) 互素的整數，其中 φ(n) 是 n 的歐拉函數值，在 RSA 算法中，φ(n) = (p - 1) * (q - 1) ；d 是 e 關于模 φ(n) 的乘法逆元，即滿足 e * d ≡ 1 (mod φ(n)) 。
二、算法原理
（一）費馬小定理
若 p 為素數，對于任意整數 a，滿足 a^(p - 1) ≡ 1 (mod p) 。該定理在 RSA 算法原理推導中起到了一定的鋪墊作用。例如，當 p = 5，a = 3 時，3^(5 - 1) = 81，81 mod 5 = 1，符合費馬小定理。
（二）歐拉定理
- 歐拉函數：對于任意給定的正整數 n，歐拉函數 φ(n) 表示小于等于 n 的正整數中與 n 構成互質關系的數的個數。在 RSA 算法中，若 n = p * q（p、q 為互質的素數），則有 φ(n) = φ(pq) = φ(p) * φ(q) ，且當 p 為質數時，φ(p) = p - 1，所以 φ(n) = (p - 1) * (q - 1) 。
- 歐拉定理與模反元素：若兩個正整數 a 和 n 互質，則存在 a^φ(n) ≡ 1 (mod n) 。從這個等式可以推導出模反元素的概念，因為 a^φ(n) = a * a^(φ(n) - 1) ≡ 1 (mod n) ，所以如果兩個正整數 a 和 n 互質，那么一定存在整數 b（這里 b = a^(φ(n) - 1) ），使得 a * b - 1 能被 n 整除，即 a * b 被 n 除的余數是 1，b 就是 a 關于模 n 的模反元素。在 RSA 算法中，求私鑰 d 的公式為 d * e ≡ 1 (mod (p - 1) * (q - 1)) ，即 d 是 e 關于模 (p - 1) * (q - 1) 的模反元素。
（三）模運算
模運算與基本四則運算類似，但除法運算有所不同。其具有結合律、交換律、分配律等性質。同余的定義為：給定一個正整數 m，如果兩個整數 a 和 b 滿足 (a - b) 能被 m 整除，即 (a - b) mod m = 0，則稱 a 和 b 對模 m 同余。在模 n 意義下，除法規則有所變化，除以一個數等價于乘以它的逆元。
（四）拓展歐幾里得原理
對于互素的兩個整數 e1、e2，可以通過拓展歐幾里得算法求解滿足 e1 * x + e2 * y = gcd (e1, e2) 的整數 x 和 y。在 RSA 算法中，計算 e 關于模 φ(n) 的乘法逆元 d 時，可以利用拓展歐幾里得算法，此時 e1 = e，e2 = φ(n)，求解出的 x 即為 d（需確保 x 為正數，若為負數則通過模運算轉換為正數）。
三、算法流程
圖解版：
文解版：
（一）密鑰生成
- 選取大素數 p、q：隨機選取兩個大素數 p 和 q，并嚴格保密這兩個數。例如，假設選取 p = 17，q = 19（實際應用中 p 和 q 通常是非常大的素數）。
- 計算乘積 n、歐拉函數值 φ(n)：
- 計算 n = p * q ，在上述例子中，n = 17 * 19 = 323。
- 計算 φ(n) = (p - 1) * (q - 1) ，即 φ(323) = (17 - 1) * (19 - 1) = 16 * 18 = 288。
- 選取整數 e：選取一個整數 e，滿足 1 <e < φ(n) 且 gcd (φ(n), e) = 1（即 e 與 φ(n) 互素）。例如，選取 e = 5（5 與 288 互素）。
- 計算乘法逆元 d：計算 d，使得 d * e ≡ 1 (mod φ(n)) 。這里利用拓展歐幾里得算法，對于 e = 5，φ(n) = 288，求解 5 * d ≡ 1 (mod 288) ，通過計算可得 d = 173（因為 5 * 173 = 865，865 mod 288 = 1）。
- 生成密鑰：
- 公開鑰為 {e, n}，即 {5, 323}。
- 秘密鑰為 {d, n}，即 {173, 323}。
（二）加密
加密時需將明文比特串進行分組，分組長度要小于 log?n 。假設明文 m = 88（滿足小于 log?323 ≈ 8.34，即分組長度合理），對明文分組 m 進行加密運算，公式為 c ≡ m^e (mod n) 。代入 e = 5，n = 323，m = 88，計算可得 c = 88^5 mod 323 = 233，得到的 c = 233 即為密文。
（三）解密
對密文分組 c 進行解密運算，公式為 m ≡ c^d (mod n) 。將 c = 233，d = 173，n = 323 代入，計算可得 m = 233^173 mod 323 = 88，成功還原出明文。
四、安全性分析
RSA 的安全性主要依賴于大數分解的難度，即給定 n = p * q，要從 n 分解出 p 和 q 在計算上是非常困難的。目前尚未從理論上證明破解 RSA 就一定等同于進行大數分解，也沒有證明破譯 RSA 的難度與大數分解難度完全等價。但無論如何，分解 n 是攻擊 RSA 的最直接方法。隨著計算機計算能力的不斷提升，為了保證 RSA 的安全性，需要選擇足夠大的 p 和 q，使 n 的長度足夠長。例如，早期較短長度的 RSA 密鑰已能被破解，如今通常推薦使用 2048 位甚至更長的密鑰長度。同時，密鑰生成過程中的隨機數生成質量、p 和 q 的選取方式等也對 RSA 的安全性有重要影響。若隨機數可預測、p 和 q 選擇不當（如太靠近或 p - 1、q - 1 的因子太小等），都可能導致 RSA 被破解。
五、應用場景
RSA 廣泛應用于現代通信加密、數字簽名等領域。在通信加密中，發送方使用接收方的公鑰對消息進行加密，接收方使用自己的私鑰進行解密，保證了通信內容的保密性。在數字簽名場景中，發送方使用自己的私鑰對消息進行簽名（對消息的哈希值進行加密），接收方使用發送方的公鑰驗證簽名，確保消息的完整性和發送方身份的真實性。例如在網絡支付、安全郵件傳輸等場景中，RSA 算法都發揮著關鍵作用，保障了信息的安全傳輸與交互。
六、總結
RSA 作為一種重要的非對稱加密算法，其原理基于數論中的多個定理，通過巧妙的密鑰生成、加密和解密流程，實現了安全的信息加密與數字簽名功能。理解 RSA 算法對于掌握現代密碼學知識、保障信息安全具有重要意義。同時，隨著技術的發展，需持續關注 RSA 的安全性，不斷優化參數選擇與應用方式，以應對潛在的安全威脅。
