歡迎光臨
每天分享高質量文章

五分鐘知識科普:什麼是 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 演算法為保證安全性,會大大提升密鑰長度,導致運算速度變慢。這導致它在大量資料加密時並不適用。

END

已同步到看一看
赞(0)

分享創造快樂