國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

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

答：

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

首先 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，計算 g^x mod p，並將計算結果傳送給 Bob。

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

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

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

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

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

α= g^x 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：

g^x mod p = 17⁷⁵ mod 203 ≡ 41 mod 203

計算過程如下：

17¹ = 17 ≡ 17 mod 203

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

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

17⁸ ≡ (88×88) mod 203 ≡ 7,744 mod 203 ≡ 30 mod 203

17¹⁶ ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

17³² ≡ (88×88) mod 203 ≡ 7,744 mod 203 ≡ 30 mod 203

17⁶⁴ ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

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

註：17⁷⁵ = 17¹×17²×17⁸×17⁶⁴。

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

g^y mod p = 17⁸⁸ mod 203 ≡ 88 mod 203

計算過程如下：

17⁸⁸ ≡ (88×88×88×88) mod 203 ≡ 59,969,536 mod 203 ≡ 88 mod 203

註：17⁸⁸ = 17⁴×17⁴×17¹⁶×17⁶⁴。

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

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

(g^y mod p)^x = g^xy mod p = 88⁷⁵ mod 203 = 1 mod 203 (g^y mod p = 88)

計算過程如下：

88¹ = 88 ≡ 88 mod 203

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

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

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

88¹⁶ ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

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

88⁶⁴ ≡ (30×30) mod 203 ≡ 900 mod 203 ≡ 88 mod 203

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

註：88⁷⁵ = 88¹×88²×88⁸×88⁶⁴。

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

(g^x mod p)^y = g^xy mod 203 = 41⁸⁸ mod 203 = 1 mod 203 (g^x mod p = 41)

計算過程如下：

41¹ = 41 ≡ 41 mod 203

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

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

41⁸ ≡ (1×1) mod 203 = 1 mod 203

41¹⁶ ≡ (1×1) mod 203 = 1 mod 203

41³² ≡ (1×1) mod 203 = 1 mod 203

41⁶⁴ ≡ (1×1) mod 203 = 1 mod 203

41⁸⁸ ≡ (1×1×1×1) mod 203 = 1 mod 203

註：41⁸⁸ = 41⁴×41⁴×41¹⁶×41⁶⁴。

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?