105年資訊技師高等系統分析與資訊安全

六、迪菲赫爾曼 (Diffie-Hellman) 金鑰交換演算法可使通訊雙方通過不安全通道，建立一把雙方共用之秘密金鑰 (secret key)。

(一)請描述迪菲赫爾曼金鑰交換演算法之內容。（5分）

(二)迪菲赫爾曼演算法之安全性係基於何種計算複雜性？（3分）

(三)迪菲赫爾曼演算法易受何種攻擊？如何防止？（4分）

(四)假設 Alice 與 Bob 欲使用迪菲赫爾曼演算法建立共用秘密金鑰。雙方事先約定模數 (modulo) p = 203，生成元素 (generator) g = 17。於秘密金鑰建立期間，Alice 送出之訊息為75，而 Bob 送出之訊息為88。請問Alice 與 Bob 之共用秘密金鑰為何？（8分）

答：

(一)迪菲赫爾曼金鑰交換演算法的內容

首先 Alice 與 Bob 共用 p 與 g 兩個參數 (p, g 是公開的，又稱公鑰)，其中 p 是很大的質數且 g 是 p 的原根 (primitive root) [如 p = 47, g = 3]，並且 (p-1) 必須有很大的質因數；接下來，Alice 與 Bob 各選擇一個小於 p 的數值 x 與 y (又稱私鑰)，必須是秘密的，不可讓他人知道。運作程序如下：

1.Alice 選擇一個小於 p 的數值 x，計算 gx mod p，並將計算結果傳送給 Bob。

2.Bob 也選擇一個小於 p 的數值 y，同樣計算 gy mod p，並將計算結果傳送給 Alice。

3.Alice 與 Bob 分別將收到的訊息 (gy mod p) 與 (gx mod p)，使用自己的私鑰分別計算 (gy mod p)x 與 (gx mod p)y，其結果都等於 (gyx mod p)，該數值便成為他們雙方共享的秘密金鑰 (secret key)。

※參考資料：黏添壽-資訊與網路安全技術 4-24~4-26

(二)迪菲赫爾曼演算法之安全性係基於何種計算複雜性？

指數運算取餘數後不易逆向推導。首先觀察一下之前提到的方程式，如下：

α= gx mod p

很明顯，給定 g、x 與 p，不難計算出α，縱使數值很大，目前已存在眾多高效率的演算法，可以快速計算出α。然而，給定α、g 與 p，欲計算出 x，就困難多了。

※參考資料：黏添壽-資訊與網路安全技術 4-24~4-26

(三)迪菲赫爾曼演算法易受何種攻擊？如何防止？

1.易受何種攻擊？

在最初的描述中，迪菲赫爾曼金鑰交換本身並沒有提供通訊雙方的身分驗證服務，因此它很容易受到中間人攻擊。

2.如何防止？

使用公開金鑰基礎建設 (Public Key Infrastructure, PKI) 來確保公開金鑰和個人身分鏈結，可以防止抵賴。

※參考資料：

1.黏添壽-資訊與網路安全技術 4-24~4-26

2.https://zh.wikipedia.org/wiki/%E8%BF%AA%E8%8F%B2-%E8%B5%AB%E7%88%BE%E6%9B%BC%E5%AF%86%E9%91%B0%E4%BA%A4%E6%8F%9B#.E5.AE.89.E5.85.A8.E6.80.A7：

3.https://zh.wikipedia.org/wiki/%E5%85%AC%E9%96%8B%E9%87%91%E9%91%B0%E5%9F%BA%E7%A4%8E%E5%BB%BA%E8%A8%AD

(四)Alice與Bob的共用秘密金鑰為何？ add

公開參數 (公鑰) 分別是 p = 203 與 g = 17，

1.Alice 自己選擇的私鑰 x = 75，並傳送給 Bob：

gx mod p = 1775 mod 203 ≡ 41 mod 203

計算過程如下：

171 = 17 ≡ 17 mod 203

172 ≡ (17×17) mod 203 = 289 mod 203 = 86 mod 203

174 ≡ (86×86) mod 203 = 7,396 mod 203 ≡ 88 mod 203

178 ≡ (88×88) mod 203 ≡ 7,744 mod 203 ≡ 30 mod 203

1716 ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

1732 ≡ (88×88) mod 203 ≡ 7,744 mod 203 ≡ 30 mod 203

1764 ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

1775 ≡ (17×86×30×88) mod 203 ≡ 3,859,680 mod 203 ≡ 41 mod 203

註：1775 = 171×172×178×1764。

2.Bob 選擇的私鑰 y = 88，並傳送給 Alice：

gy mod p = 1788 mod 203 ≡ 88 mod 203

計算過程如下：

1788 ≡ (88×88×88×88) mod 203 ≡ 59,969,536 mod 203 ≡ 88 mod 203

註：1788 = 174×174×1716×1764。

3.Alice 與 Bob 分別接收到對方傳送過來的數值 (88與41) 後，再各自分別使用自己的私鑰計算如下：

[Alice收到Bob傳送過來的數值]

(gy mod p)x = gxy mod p = 8875 mod 203 = 1 mod 203 (gy mod p = 88)

計算過程如下：

881 = 88 ≡ 88 mod 203

882 ≡ (88×88) mod 203 = 7,744 mod 203 = 30 mod 203

884 ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

888 ≡ (88×88) mod 203 = 7,744 mod 203 = 30 mod 203

8816 ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

8832 ≡ (88×88) mod 203 = 7,744 mod 203 = 30 mod 203

8864 ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

8875 ≡ (88×30×30×88) mod 203 ≡ 6,969,600 mod 203 ≡ 1 mod 203

註：8875 = 881×882×888×8864。

[Bob收到Alice傳送過來的數值]

(gx mod p)y = gxy mod 203 = 4188 mod 203 = 1 mod 203 (gx mod p = 41)

計算過程如下：

411 = 41 ≡ 41 mod 203

412 ≡ (41×41) mod 203 = 1,681 mod 203 = 57 mod 203

414 ≡ (57×57) mod 203 = 3,249 mod 203 = 1 mod 203

418 ≡ (1×1) mod 203 = 1 mod 203

4116 ≡ (1×1) mod 203 = 1 mod 203

4132 ≡ (1×1) mod 203 = 1 mod 203

4164 ≡ (1×1) mod 203 = 1 mod 203

4188 ≡ (1×1×1×1) mod 203 = 1 mod 203

註：4188 = 414×414×4116×4164。

4.最後 Alice 與 Bob 計算出來的值都是4，該值就是他們的共享鑰匙。

※參考資料：

1.黏添壽-資訊與網路安全技術 4-24~4-26

2.https://zh.wikipedia.org/wiki/%E8%BF%AA%E8%8F%B2-%E8%B5%AB%E7%88%BE%E6%9B%BC%E5%AF%86%E9%91%B0%E4%BA%A4%E6%8F%9B#.E5.AE.89.E5.85.A8.E6.80.A7

3.http://www.irongeek.com/diffie-hellman.php?

arrow
arrow
    文章標籤
    系統分析與資訊安全
    全站熱搜

    jacksaleok 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄