2008年1月18日 星期五

Asymmetric Encryption (非對稱式加密)

簡介

Asymmetric Encryption (非對稱式加密) 即是為了改良 Symmetric Encryption(對稱式加密)的缺點而產生的。

在對稱式加密中,通訊雙方往來的訊息是由同一把金鑰進行加密;假設 A 與 B 通訊,兩個人必須有一把相同的金鑰;而若是 A 也要與 C 通訊,則 A 與 C 則必須擁有另外一把不同的金鑰;否則若是都使用相同金鑰,C 就可以解密出 A 要給 B 的訊息,相對的,B 也可以解密出 A 要給 C 的訊息,如此一來資訊在傳送就不再安全!

除此之外,還要防範金鑰被竊取的問題,只要通訊雙方任何一個人把金鑰洩露出去,也就破壞了原本建立的安全機制了。

因此,Asymmetric Encryption(非對稱式加密) 使用了一對金鑰(key pair)的方式解決了這個問題


Key Pair

在 Asymmetric Encryption 的架構中,要通訊的雙方都各持有一對金鑰,分別是私鑰(private key)以及公鑰(public key)。

顧名思義,private key 是要妥善且由自己秘密保管的,而 public key 則是可以公開出去。

假設使用者 A 有一對金鑰,若是 B 要與 A 進行通訊,則 B 必須使用 A 所提供的 public key 進行加密,再將加密的內容傳送給 A,接著 A 可以用自己的 private key 進行解密。

同樣的,A 要是要傳訊息給 B,則是要使用 B 所提供的 public key 進行加密,而 B 則可以用自己的 private key 進行解密。

有趣的是,雖然訊息是由 public key 所加密的,但是卻無法利用 public key 將原本的訊息還原回來,這就是非對稱式加密的精華所在,也是目前非常受到歡迎的原因。

而這一來一往之間,所使用的演算法,即為 RSA 演算法。


RSA Algorithm

RSA 演算法要如何確保不容易被破解呢? 答案在於「要算出一個很大的數,是由那兩個質數相乘的結果(進行因數分解),是很困難的」,因此可以很明顯看出,RSA 的運作方式,都是以兩個很大的質數為基礎來進行的。

RSA 演算法的基礎,取決於兩個很大的質數(可能達數百位數),運作流程大概如下:
  1. 選擇兩個大質數 P & Q
  2. 計算 N = P * Q
  3. 選擇公鑰(public key) E,使它不為 (P-1) 或 (Q - 1) 的因數
  4. 選擇私鑰(private key) D,讓右邊算式成立:(D * E) % [(P - 1) * (Q - 1)] = 1
  5. 加密過程為:密文(CT) = 明文(PT^E) % N
  6. 解密過程為:明文(PT) = 密文(CT^D) % N

如此看來,其實 RSA 的加解密過程是很簡單的,因此重點就是在於金鑰的產生,目前已經被證明長度 1024 bits 不夠安全,因此建議使用長度為 2048 bits 的金鑰作為加解密之用,來提升重要資訊傳輸的安全性。

最後,雖然非對稱式加密解決了金鑰交換的問題,但是卻衍生出加解密效率不彰的問題,因為相較於 DES,RSA 的速度只有其百分之一不到。


Asymmetric + Symmetric

真的沒有更好的 solution 嗎? 當然是有的......只要巧妙的結合兩者的優點即可啦!!

其中的原理很簡單,假設 A 要傳訊息給 B,就會發生大概類似以下流程:
  1. A 透過對稱式演算法,產生出一把對稱式加密用的金鑰(注意:這把金鑰只用在這一次的傳輸)
  2. 接著 A 使用 B 所提供的 public key,將這把金鑰加密,並將加密後的內容傳給 B
  3. B 接收到後,使用自己的 private key 解密,取得這把一次性金鑰
  4. 接著之後雙方訊息的往來,都使用對稱式加密

如此一來,就不僅解決了金鑰交換的問題,也解決了非對稱式加解密效率不彰的問題。

當然,這樣的 solution 其實還不算最安全,因此才會有 Digital Signature(數位簽章) 的誕生......


參考資料
  1. RSA 加密演算法
  2. RSA 加密演算法(PDF)
  3. developerWorks - 讓軟體運轉:歷經考驗的真正加密

1 則留言: