五分鐘知識科普：什麼是 RSA 演演算法

RSA 演演算法歷史

RSA 是 1977 年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。

當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。

但實際上，在 1973 年，在英國政府通訊總部工作的數學家克利福德·柯克斯（Clifford Cocks）在一個內部檔案中提出了一個相同的演演算法，但他的發現被列入機密，一直到 1997 年才被髮表。

RSA 演演算法基礎知識

密碼學知識

明文：是指沒有加密的文字（或者字串）。

加密：是以某種特殊的演演算法改變原有的資訊資料，使得未授權的使用者即使獲得了已加密的資訊，但因不知解密的方法，仍然無法瞭解資訊的內容。

密文：密文是對明文進行加密後的報文。

對稱加密：對稱是指，在對明文進行加密，對密文執行解密加密過程採用相同的規則（通常將雙方採用的規則稱為”金鑰”）。

例如：
（1）甲方選擇某一種加密規則，對資訊進行加密；
（2）乙方使用同一種規則，對資訊進行解密。

非對稱加密：非對稱加密是指通訊雙方採用不同的金鑰進行加密解密。

例如：
（1）乙方生成兩把金鑰（公鑰和私鑰）。公鑰是公開的，任何人都可以獲得，私鑰則是保密的。
（2）甲方獲取乙方的公鑰，然後用它對資訊加密。
（3）乙方得到加密後的資訊，用私鑰解密。

數學知識

互質關係：如果兩個正整數，除了數字 1 之外沒有其他公因子，我們稱這兩個數是互質關係。

同餘定理：給定一個正整數 m，如果兩個整數a和b滿足a-b能夠被m整除，即(a-b)/m得到一個整數，那麼就稱整數 a 與 b 對模 m 同餘，記作 a ≡ b(mod m)。

RSA 演演算法流程

（1）選擇兩個不相等的質數p和q

例如：選擇兩個不等質數分別為 61 和 53 （實際應用中選擇的質數都相當大）。

（2）計算p和q的乘積n

n = p*q = 61 * 53 = 3233。

（3）計算 n 的尤拉函式 φ(n)

φ(3233) = φ(61 * 53) = φ(61) * φ(53)。

由於 61 為質數，因此 φ(61) = 61 – 1 = 60。同理 φ(53) = 53  – 1 = 52。則 φ(3233) = 60 * 52 = 3120。

（4）隨機選擇一個整數 e ，條件是1< e < φ(n)，且 e 與 φ(n) 互質

隨機選擇一個質數e，保證1< e < 3120，這裡選擇e = 17。

（5）計算e對於φ(n)的模反元素d
e * d ≡ 1 (mod φ(n))。其中e = 17，φ(n) = 3120。

設e*d是φ(n)的k的整數倍，餘數為1。則上式可以轉化為：
17 * d = 3120k + 1。繼續轉化得到：
17 * d + 3120y = 1。其中y = -k。

其中，對於d的求解轉化為二元一次方程求解。此方程可以使用擴充套件歐幾裡得方法進行求解。透過輾轉相除法計算出一組解為(2753,-15)。

解得d = 2753。

（6）將n和e封裝成公鑰，n和d封裝成私鑰

加密公鑰為(3233,17)，私鑰為(3233,2753)。

RSA 演演算法分析

那麼 RSA 演演算法是如何保證安全性的呢？

在 RSA 演演算法中 n 與 e 是公開的，那麼破解 RSA 加密的步驟即為透過 n 與 e 計算出私鑰 d 的值。

（1）ed ≡ 1 (mod φ(n))。只有知道 e 和 φ(n)，才能算出 d 。
（2）φ(n) = (p-1)(q-1)。只有知道 p 和 q ，才能算出 φ(n)。

由此得出密碼破解的實質問題是：從p * q的值n，去求出 (p-1) 和 (q-1)。換句話說，只要求出 p 和 q 的值，我們就能求出 d 的值而得到私鑰。但是，當 p 和 q 是是很大的質數時，從它們的積 p * q 去分解因子 p 和 q ，這是一個公認的數學難題。

比如當p * q大到1024位時，迄今為止還沒有人能夠利用任何計算工具去完成分解因子的任務。

雖然理論上 RSA 是可以破解的，但是隨著金鑰長度增加，破解的代價是不可接受的。

因此，只要金鑰長度足夠長，用 RSA 加密的資訊實際上是不能被解破的。目前被破解的最長 RSA 金鑰就是 768 位。

RSA 演演算法總結

RSA 的安全性依賴於大數分解，因此 RSA 演演算法加密安全性較高。但是，RSA 演演算法為保證安全性，會大大提升金鑰長度，導致運算速度變慢。這導致它在大量資料加密時並不適用。