資訊與網路安全技術 第三章 現代公開鑰匙系統  上一頁      下一頁

 

3-6 Diffie-Hellman 鑰匙交換法

內容:

3-6-1 DH 演算法推論

目前許多廠商皆採用 Diffie-Hellman『鑰匙交換』(Key Exchange)技術,製作公開鑰匙系統,但此演算法並不直接使用於加密或數位簽章,而僅應用於鑰匙交換方面(製作秘密鑰匙,再用它來加密),這與 RSA 演算法的使用有很大的區隔。

Diffie-Hellman 鑰匙交換法是利用 RSA 編碼演算法的特性(同餘乘法與指數運算),雙方互相傳送一段訊息,他們再由這些訊息建立共享鑰匙(又稱會議鑰匙)。其演算法敘述如下:首先 Alice Bob 共用 n g 兩個參數(n, g 是公開的,又稱公鑰),其中 n 是很大的質數且 g n 的原根(primitive),並且 (n - 1) 必須有很大的質因數;接下來,Alice Bob 各選擇一個小於 n 的數值 x y (又稱私鑰),必須是秘密的,不可讓他人知道(經過運算後很難知道)。其運作程序如圖 3-5 所示,說明如下:

  • 訊號 (1)Alice 選擇一個小於 n 的數值 x,計算 gx mod n,並將計算結果傳送給 Bob(該值又稱為『鑰匙材料』)。

  • 訊號 (2)Bob 也選擇一個小於 n 的數值 y,同樣計算 gy mod n,並將計算結果(鑰匙材料)傳送給 Alice

  • 訊號 (3)AliceBob分別將收到的訊息(gy mod n)與(gx mod n),使用自己的私鑰分別計算(gy mod nx 與(gx mod ny,其結果都等於(gyx mod n),該數值便成為他們雙方共享的會議鑰匙。

3-5 Diffie-Hellman 鑰匙交換的運作程序

簡單的說,DH 演算法是利用:

(gx mod n)y mod n = (gy mod n) x mod = gxy mod n

同餘運算的特性來達成。我們先以一個例子說明,再討論其安全性。假設公開參數(公鑰)分別是 n = 47g = 3(通訊雙方皆知曉),雙方建立會議鑰匙如下:

  • 步驟一:若 Alice選擇的私鑰 x = 8,依下列計算結果:

gx mod n = 38 mod 47 28 mod 47

計算過程如下:

31 = 3 3 mod 47

32 (3 × 3) mod 47 9 mod 47

34 (9 × 9) mod 47 81 mod 47 34 mod 47

38 (34 × 34) mod 47 1156 mod 47 28 mod 47

Alice 傳送 {28}(鑰匙材料)給 Bob

  • 步驟二:若Bob 選擇的私鑰y = 10,依計算下列結果:

gy mod n = 310 mod 47 = 17 mod 47

計算過程如下:

31 = 3 3 mod 47

32 (3 × 3) mod 47 9 mod 47

34 (9 × 9) mod 47 81 mod 47 34 mod 47

38 (34 × 34) mod 47 1156 mod 47 28 mod 47

310 = 38× 32 (28 × 9) mod 47 17 mod 47

Bob 傳送 {17} Alice。同時 Bob 利用 Alice 傳送鑰匙材料 {28} 計算會議鑰匙,如下:(會議鑰匙 = 4

(gx mod n)y = gxy mod n = 2810 mod 47 = 4 mod 47

計算過程如下:

281 = 28 28 mod 47

282 (28 × 28) mod 47 32 mod 47

283 (32 × 28) mod 47 3 mod 47

2810 (3 × 3 × 3 × 28) mod 47 4 mod 47

  • 步驟三:Alice利用Bob的鑰匙材料計算會議鑰匙,如下:(結果 = 4

(gy mod n)x = gxy mod n = 178 mod 47 = 4 mod 47

計算過程如下:

171 = 17 17 mod 47

172 (17 × 17) mod 47 289 mod 47 7 mod 47

174 (7 × 7) mod 47 2 mod 47

178 (2 × 2 ) mod 47 4 mod 47

最後我們可以發現,AliceBob所計算出來的值都是 4,該值就是他們的共享鑰匙。

3-6-2 中間人攻擊

雖然Diffie-Hellman 演算法要從公開參數(公鑰)計算出私鑰不容易,但可能遭受『中間人攻擊』(Man-in-the-middle Attack。圖 3-6 中,假設 Alice 欲與 Bob 通訊:

  • 訊號 (1)Alice送出交換鑰匙訊息(gx mod n)給 Bob,但此訊息被 Trudy 攔截到。

  • 訊號 (2)Trudy 知道訊息欲由 Alice 發送至 Bob ;便偽裝成 Alice,並發送交換鑰匙訊息(gz mod n)給 Bob

  • 訊號 (3)同時Trudy 亦偽裝Bob,回應鑰匙交換訊息(gz mod n)給 Alice,此時 Alice Trudy 便建立了共享鑰匙(gxz mod n)。

  • 訊號 (4)另一方面,Bob 收到 Trudy 的訊息之後,誤認為係由 Alice 傳送過來的,便回應鑰匙交換訊息(gy mod n)給 Trudy,並建立共享鑰匙(gzy mod n)。

3-6 中間人攻擊

接下來會發生什麼事情已不必多言,Alice Bob 都誤認為 Trudy 是他們通訊的對象,他們之間通訊的訊息必然被Bob一覽無遺,一般我們又稱為『桶列攻擊法』(Bucket Bridge Attack

3-6-3 防禦中間人攻擊

Diffie-Hellman 鑰匙交換法對資訊安全的貢獻非常大,其實中間人攻擊法並不難防禦,諸多文獻已提出解決方案,並且已嵌入許多安全系統中。接下來,介紹幾種防禦方法,這些方法或許會被混合使用(因為沒有一種方法是百分之一百安全的)。

【(A)公開 Diffie-Hellman 參數】

Diffie-Hellman 演算法中有兩個公開的參數 n g,若將其值固定,並且對外公佈(由鑰匙交換協定規範)。當中間人攔截到訊息之後,因無法傳送另一個參數欺騙另一方(如圖 4-8 訊號 (2)),就可以避免中間人的主動攻擊,但儘管如此,也不盡然能完全防禦中間人攻擊,仍需仰賴其它配套措施。

【(B)認證的 Diffie-Hellman

遭受中間人攻擊的主要原因,是因為不能確認通訊對方的身分,若能在交換訊息之前,先確認彼此身分,便不會受到攻擊,『認證的 Diffie-Hellman』(Authenticated Diffie-Hellman 正是如此,其實現的方法有下列幾種:

  • 利用『前置共享密鑰』(Pre-shared Secret)向 Diffie-Hellman 交換訊息加密。雙方先建立一個安全通道之後,再利用此安全通道交換訊息,一般又稱為兩階段的訊息交換(第十六與十七章再詳細介紹)。

  • 利用對方的公開鑰匙 Diffie-Hellman 交換訊息加密。

  • 利用自己的私有鑰匙 Diffie-Hellman 交換訊息加密。

  • Diffie-Hellman 交換之後,緊接著傳送 Diffie-Hellman 共享數值、名稱、與前置共享密鑰的雜湊值

  • Diffie-Hellman 交換之後,緊接著傳送前置共享密鑰與所傳送 Diffie-Hellman 參數的雜湊值

後面兩種方法,都能提供再確認的功能,至於如何建立安全通道之『前置共享密鑰』的方法,爾後再詳細介紹。

 

主講人:粘添壽博士

 

資訊與網路安全技術