iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

30天不怕演算法:白話文版系列 第 28

Day 28:Diffie–Hellman演算法

一路到了鐵人賽最後階段,最後寫兩個完全不同但都蠻有趣的演算法。

我們之前寫到SHA家族演算法可以用來為資料加密,今天的演算法也跟加密有關,不過並不是直接用來改變資料內容,而是讓通信的雙方可以安全地交換金鑰(key)。

想像如果A, B兩個人要交換機密訊息,他們可以將訊息加密再傳遞,對方收到再以金鑰解開(就像以鑰匙開鎖),來得到真正的內容。例如雙方可以約定金鑰為5,當一人收到訊息"d gjqa tjp.",他可以將字母轉為數字後加上5,就可以知道真正的訊息是"I love you."

姑且先不論這個金鑰是否太簡單,A, B雙方總要以某種方式先同意金鑰為何,但不管是用信件、e-mail、電話、甚至當面用講的,金鑰都還是有被竊取的風險。

上述的方法在加密和解密都是用同一個金鑰,所以雙方必須溝通決定,而Diffie Hellman演算法中,雙方則是各有一組公開金鑰(public key)和私人金鑰(private key),如此一來可以在沒有任何事先資訊的情況下建立密碼。它的作法是:

  1. 首先A, B雙方先約定好一組數字n(可公開)。
  2. A, B各自以祕密的私人金鑰a, b和n做運算,各自得出答案x和y,即為公開金鑰。
  3. 雙方交換公開金鑰x和y。
  4. A, B各自以祕密的私人金鑰a, b、n、公共金鑰x, y進行運算,得出的數字即為雙方共同的秘密。

整個過程中,除了各自的私人金鑰a, b之外,一開始約定的數字和中間交換的數字都是可以公開的,也就是以不安全的管道傳遞也沒關係。因為運算的特性,雙方最後會得到一樣的結果,也就是不需要任何形式的溝通約定,就有共同秘密數字可以作為金鑰使用。

數字選擇合適的話(關於數字挑選細節可以參考百科),攻擊者很難用公開的部分資訊來得出私人金鑰以及最終的密碼,也就保障了密碼系統的安全性。

Diffie Hellman是最早出現的一種公開金鑰方式,它的一個缺點是過程並沒有身分驗證機制,也就是攻擊者可以在中間與雙方進行假的金鑰交換來竊取訊息。不過後續以Diffie Hellman演算法為基礎,也出現了許多身分驗證的解決方案。

下圖是以顏色表達演算法的流程,可以作為參考。過程中兩人各自加入了兩次只有自己知道的secret colours(用私人金鑰作兩次運算),最後得到同樣的顏色(共同密碼)。

圖片來源:維基百科


上一篇
Day 27:碰到困難問題,演算法也救不了?
下一篇
Day 29:K-近鄰演算法(k-nearest neighbors)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言