fbpx

RSA 加密算法 : 理論上破解不能的非對稱加密法

開放網絡中數據傳輸的安全性一直是一個熱門的話題,無論是在網路上傳送重要文件,還是商業交易,加密都是保障資料安全及用戶私隱的必要手段,加密通訊在未來的重要性只會有增無減。其中一個最常用的加密方法就是RSA,在 1977 年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的, RSA 加密算法 ,並以它的三個發明者的名字首字母命名。



對稱加密:一條鑰匙來加密信息

假如你想傳訊息給別人,又不能確保在傳送的過程中不會被人截取,那加密手段是不可缺少。簡單來說,就是找方法將訊息中的內容打亂,讓第三者即使看到訊息也無法了解內容。

問題來了,要怎樣把訊息打亂,才不能夠被第三方破解呢?

比較常用的加密算法包括對稱加密( symmetric-key encryption), 如AES、DES、3DES 等。對稱加密的原理,就是你把你的文件用鑰匙鎖上,你和收件人分別擁有同一條鑰匙來解開文件。這個的缺點就是如果一方的鑰匙被發現,那加密信息就可以被解開。

RSA 加密:以極大整數做因數分解

RSA 加密演算法是最常用的非對稱加密算法,亦是一種非對稱加密演算法。

在 1977,三位美國麻省理工學院學者 Ron Rivest、Adi Shamir 以及 倫納德·阿德曼 Leonard Adleman 率先公開 RSA 加密演算法,並取得專利權,目前有很多的數位消費性產品,例如視訊轉換器與智慧卡,都是利用了RSA加密來傳遞訊息。

要了解為什麼 RSA 加密比其它算法安全,首先要了解什麼是非對稱加密算法。

非對稱加密算法需要兩個密鑰:公開密鑰(publickey)和私有密鑰(privatekey),私有密鑰是要妥善且由自己秘密保管的,而 公開密鑰則是可以公開的。如果用公開密鑰對數據進行加密,只有用對應的私有密鑰才能解密。

換句話來說,你有一個保險箱,箱上有兩個完全不同的鑰匙孔。如果你把文件放在保險箱中,並用你的鑰匙鎖上。這時候,即使你再用你的鑰匙想打開保險箱,或者你的鑰匙被人複制,但箱已經被鎖住不能再被打開。只有收件人用自己的鑰匙才能夠打開保險箱來取得文件。雖然訊息是由 public key 所加密的,但是卻無法利用 public key 將原本的訊息還原回來。

RSA 演算法要如何確保不容易被破解呢?RSA 的運作方式,都是以兩個很大的質數為基礎來進行的。

維基上給出的例子是這樣的:

123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413

= 3347807169895689878604416984821269081770479498371376856891
  2431388982883793878002287614711652531743087737814467999489 × 
  3674604366679959042824463379962795263227915816434308764267
  6032283815739666511279233373417143396810270092798736308917

極大整數做因數分解的難度決定了 RSA 演算法的可靠性。換言之,對一極大整數做因數分解愈困難,RSA 演算法愈可靠。假如有人找到一種快速因數分解的演算法的話,那麼用RSA加密的訊息的可靠性就肯定會極度下降。但找到這樣的演算法的可能性是非常小的。

但隨著科技發展及電腦的升級,目前已經被證明長度 1024 bits 不夠安全,建議使用 2048 bits 的 RSA 加密。

如果要破解一組 2048 位元的 RSA 加密,理論上大約需要 4000 個量子位元(qubit)。目前 Google 和 IBM 的量子電腦約有 20 個量子位元。就算用目前世界上最強的超級電腦(太湖之光,中國製),花費 46 億年都無法破解。

2002 的圖靈獎頒給了RSA加密演算法的三個發明人,以表揚他們的杰出貢獻。

資料來源:維基

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *

限制時效已用盡。請重新載入驗證碼。