以公開的方式交換資訊生成對稱式金鑰

最近讀的密碼學的書裡面介紹了Diffie–Hellman Key Exchange,覺得很有趣,紀錄一下

 

使用情節

小明想與小華想利用對稱式加密建立加密連線

可是不管是任何一方先產生金鑰再傳送給另外一方都有被第三方監聽的風險

這時,Diffie–Hellman Key Exchange就派上用場了

Diffie–Hellman Key Exchange用於當溝通的雙方處於不安全連線(被第三方監聽)下

仍能交換資訊生成對稱式金鑰建立加密連線

 

密鑰生成步驟

藍色表示可以公開被第三方聽到的資訊
灰色表示可以公開被第三方聽到的資訊
橘色表示兩人運算完後產生的金鑰

  1. 小明隨機把兩個質數PG傳送給小華
    質數PG可以用明碼傳送,被第三方知道了也沒關係

  2. 小明額外再生成一個隨機數A
    這個隨機數A就不能讓任何人知道,連小華也不必知道

  3. 小華生成一個隨機數B
    這個隨機數B也不能讓任何人知道,連小明也是

  4. 小明(GA mod P) 的值計算出來傳送給小華

  5. 小華(GB mod P) 的值計算出來傳送給小明

小明現在有PGA(GB mod P) 這四個值,而小華現在有PGB(GA mod P) 這四個值

  1. 小明(GB mod P)A mod P 的值計算出來
    (GB mod P)A mod P 可以簡化成 (GBA mod P)

  2. 同樣地,小華(GA mod P)B mod P 的值計算出來
    (GA mod P)B mod P 可以簡化成 (GAB mod P)

到這裡可以發現,小明小華計算出來的值都一樣是 (GAB mod P)

(GAB mod P) 也就是他們兩個之間產出拿來加密對話的對稱式金鑰

 

代數字示範

因為是示範,所以拿比較短的數字,實際上PB必須夠大才安全

  1. 小明把兩個質數PG傳送給小華
    質數P = 23
    質數G = 5

  2. 小明額外再生成一個隨機數AA = 6

  3. 小華生成一個隨機數BB = 15

  4. 小明(GA mod P) 的值計算出來傳送給小華
    (56 mod 23) = 8

  5. 小華(GB mod P) 的值計算出來傳送給小明
    (515 mod 23) = 19

  6. 小明(GB mod P)A mod P 的值計算出來
    (515 mod 23)6 mod 23 = 196 mod 23 = 2

  7. 同樣地,小華(GA mod P)B mod P 的值計算出來
    (56 mod 23)15 mod 23 = 815 mod 23 = 2

最終小明小華都得到了共同數值 2 成為雙方拿來加密對話的對稱式金鑰

 

第三方能透過監聽算出金鑰嗎

假如第三方小美從頭到尾完整擷取了他們使用Diffie–Hellman Key Exchange的過程

小美共可以獲得PG(GA mod P)(GB mod P) 這四個值

但是只要PB夠大,根據離散對數問題,是沒辦法輕易找出 (GAB mod P)

 

弱點

使用Diffie–Hellman Key Exchange產生金鑰雖然可以防止第三方監聽

但如果遇到中間人攻擊那就沒輒了

小美若介入了小明小華的對話

小明(GA mod P) 傳送給小華時把訊息給攔截

並假冒成小明傳送 (GC mod P)小華
(C小美自己產生的隨機數,加上公開的PG即可產生 (GC mod P) )

依樣畫葫蘆,當小華(GB mod P) 傳送給小明時把訊息攔截

並假冒成小華傳送 (GD mod P)小明
(D小美自己產生的隨機數,加上公開的PG即可產生 (GD mod P) )

如此一來,小美即成為擁有金鑰的中間人

往後可以神不知鬼不覺的把加密訊息用現有的PGCD給解密了


發佈留言