一文搞懂 RSA 演算法

來自專欄 Python 學習之道4 人贊了文章

地球上最重要的演算法

如果沒有 RSA 演算法，現在的網路世界毫無安全可言，也不可能有現在的網上交易。上一篇文章 ssh 協議為什麼安全 中的 ssh 協議也是基於 RSA 加密演算法才能確保通訊是加密的，可靠的。

1976年以前，所有的加密方法都使用對稱加密演算法：加密和解密使用同一套規則。例如：甲使用密鑰 A 加密，將密文傳遞給乙，乙仍使用密鑰 A 解密。如果密鑰 A 在甲傳遞給乙的過程中泄露，或者根據已知的幾次密文和明文推導出密鑰 A，則甲乙之間的通訊將毫無祕密。

1976年，兩位美國計算機學家 Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構思，可以在不傳遞密鑰的情況下，完成解密。這被稱為 Diffie-Hellman密鑰交換演算法 假如甲要和乙通訊，甲使用公鑰 A 加密，將密文傳遞給乙，乙使用私鑰 B 解密得到明文。其中公鑰在網路上傳遞，私鑰只有乙自己擁有，不在網路上傳遞，這樣即使知道了公鑰 A 也無法解密。反過來通訊也一樣。只要私鑰不泄漏，通信就是安全的，這就是非對稱加密演算法。

1977年，三位數學家 Rivest、Shamir 和 Adleman 設計了一種演算法，可以實現非對稱加密。演算法用他們三個人的名字命名，叫做 RSA 演算法。直到現在，RSA 演算法仍是最廣泛使用的"非對稱加密演算法"。毫不誇張地說，只要有計算機網路的地方，就有 RSA 演算法。

下面我以一個簡單的例子來描述 RSA 演算法。

第一步：生成密鑰對，即公鑰和私鑰。

1：隨機找兩個質數 P 和 Q ,P 與 Q 越大，越安全。

比如 P = 67 ，Q = 71。計算他們的乘積 n = P * Q = 4757 ，轉化為二進為 1001010010101，該加密演算法即為 13 位，實際演算法是 1024 位 或 2048 位，位數越長，演算法越難被破解。

2：計算 n 的歐拉函數 φ(n)。

φ(n) 表示在小於等於 n 的正整數之中，與 n 構成互質關係的數的個數。例如：在 1 到 8 之中，與 8 形成互質關係的是1、3、5、7，所以 φ(n) = 4。 如果 n = P * Q，P 與 Q 均為質數，則 φ(n) = φ(P * Q)= φ(P - 1)φ(Q - 1) = (P - 1)(Q - 1) 。 本例中 φ(n) = 66 * 70 = 4620，這裡記為 m， m = φ(n) = 4620

3：隨機選擇一個整數 e，條件是1< e < m，且 e 與 m 互質。

公約數只有 1 的兩個整數，叫做互質整數，這裡我們隨機選擇 e = 101 請注意不要選擇 4619，如果選這個，則公鑰和私鑰將變得相同。

4：有一個整數 d，可以使得 e*d 除以 m 的餘數為 1。

即找一個整數 d，使得 (e * d ) % m = 1。 等價於 e * d + 1 = y * m ( y 為整數） 找到 d ，實質就是對下面二元一次方程求解。 e * x - m * y =1 ，其中 e = 101，m = 4620 101x - 4620y =1 這個方程可以用"擴展歐幾裏得演算法"求解，此處省略具體過程。 總之算出一組整數解（x，y ）= （ 1601，35），即 d = 1601。 到此密鑰對生成完畢。不同的 e 生成不同的 d，因此可以生成多個密鑰對。

本例中公鑰為 （n，e) = (4757 , 101)，私鑰為 （n，d) = (4757 ，1601) ，僅（n，e) = (4757 , 101) 是公開的，其餘數字均不公開。可以想像如果只有 n 和 e，如何推導出 d，目前只能靠暴力破解，位數越長，暴力破解的時間越長。

第二步：加密生成密文 。

比如甲向乙發送漢字「中」，就要使用乙的公鑰加密漢字 "中"， 以 utf-8 方式編碼為 [e4 b8 ad]，轉為 10 進位為 [228,184,173]。要想使用公鑰（n，e) = (4757 , 101)加密，要求被加密的數字必須小於 n，被加密的數字必須是整數，字元串可以取 ascii 值或unicode值，因此將「中」字折為三個位元組 [228,184,173]，分別對三個位元組加密。 假設 a 為明文，b 為密文，則按下列公式計算出 b

a^e % n = b

計算 [228,184,173]的密文：

228^101 % 4757 = 4296

184^101 % 4757 = 2458

173^101 % 4757 = 3263

即 [228,184,173]加密後得到密文 [4296，2458，3263] ，如果沒有私鑰 d ,神仙也無法從 [4296，2458，3263]中恢復 [228,184,173]。

解密生成明文。

乙收到密文 [4296，2458，3263]，並用自己的私鑰（n，d) = (4757 ，1601) 解密。解密公式如下： 假設 a 為明文，b 為密文，則按下列公式計算出 a

a^d % n = b

密文 [4296，2458，3263]的明文如下：

4296^1601% 4757 = 228

2458^1601% 4757 = 184

3263^1601% 4757 = 173

即密文 [4296，2458，3263] 解密後得到 [228,184,173] 將[228,184,173] 再按 utf-8 解碼為漢字 "中"，至此解密完畢。

加密和解密的過程使用了費爾馬小定理的兩種等價的描述。

最後，問題來了，有沒有可能在已知 （n，e) 的情況下，推導出 d。

根據以上密鑰對的生成過程：

如果想知道 d 需要知道歐拉函數 φ(n)

如果想知道歐拉函數 φ(n) 需要知道 P 和 Q

要知道 P 和 Q 需要對 n 進行因數分解。

對於本例中的 4757 你可以輕鬆進行因數分解，但對於大整數的因數分解，是一件很困難的事情，目前除了暴力破解，還沒有更好的辦法，如果以目前的計算速度，破解需要50年以上，則這個演算法就是安全的。 維基百科這樣描述：

"對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA演算法愈可靠。 　 假如有人找到一種快速因數分解的演算法，那麼RSA的可靠性就會極度下降。但找到這樣的演算法的可能性是非常小的。今天只有短的RSA密鑰纔可能被暴力破解。到2008年為止，世界上還沒有任何可靠的攻擊RSA演算法的方式。 　 只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。"

目前已經破解的最大整數：

1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413=33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489x36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

即（232個十進位位，768個二進位位），目前被破解的最長RSA密鑰就是768位。實際應用中 RSA 的密鑰長度為 1024 位，重要場合 2048 位，未來半個世紀不可能破解。 (完）

參考文檔： RSA演算法原理（二）（阮一峯）（http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html） 數學之美：談談密碼學的數學原理（吳軍）

如果您對文章感興趣，請關注微信公眾號搜索 somenzz 關注。

推薦閱讀：

相關文章