010tools.comRSA在線加密解密工具(010tools 最好用的在線工具集合)

   
加密或解密的結果:
日誌記錄:



什麼是RSA算法

RSA加密算法是一種非對稱加密算法,在公開密鑰加密和電子商業中被廣泛使用。RSA是1977年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

1973年,在英國政府通訊總部工作的數學家克利福德·柯克斯(Clifford Cocks)在一個內部文件中提出了一個與之等效的算法,但該算法被列入機密,直到1997年才得到公開。

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

1983年9月12日麻省理工學院在美國為RSA算法申請了專利。這個專利於2000年9月21日失效。由於該算法在申請專利前就已經被髮表了,在世界上大多數其它地區這個專利權不被承認。


算法描述

第一步:生成密鑰對,即公鑰和私鑰。

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 解碼為漢字 "中",至此解密完畢。


簽名消息

RSA也可以用來為一個消息署名。假如Alice想給Bob傳遞一個署名的消息的話,那麼她可以為她的消息計算一個散列值(Message digest),然後用她的私鑰“加密”(如同前面“加密消息”的步驟)這個散列值並將這個“署名”加在消息的後面。這個消息只有用她的公鑰才能被解密。Bob獲得這個消息後可以用Alice的公鑰“解密”(如同前面“解密消息”的步驟)這個散列值,然後將這個數據與他自己為這個消息計算的散列值相比較。假如兩者相符的話,那麼Bob就可以知道發信人持有Alice的私鑰,以及這個消息在傳播路徑上沒有被篡改過。