Diffie-Hellman Key Exchange整理

在雙方要做加密通信時,需要共同協商出密鑰,無論是加解密同一把,或是加密/解密分開, 都需要某種方式讓雙方得到密鑰。最簡單的做法就是透過事先設定好密鑰,或是另外透過安全的傳輸傳輸密鑰。

但是密鑰要在安全傳輸的通道裡傳輸,安全傳輸的通道怎麼來的,例如可能是實體的額外的線路,也可能是兩方私下先共同約定好特定密鑰的加密通道,不過這兩種做法似乎都要先約定好,是否有辦法直接在不安全的通道裡在雙方都沒有事先溝通的參數的情況下協商出一把只有雙方才知道的密鑰呢?

這個問題等同於如果有一個人在偷聽兩個陌生人的加密對話,從頭聽到尾(包括兩個人加密協商階段也能偷聽到的情況下),是否可以讓偷聽的人無法知道兩個陌生人原始的對話,也就是避免偷聽的人解開兩人通信使用的密鑰,答案是可以,這邊必須注意的是 – 偷聽是只在旁邊偷偷觀察,不是MTIM中間人攻擊

關於這個問題可參考 https://en.wikipedia.org/wiki/Key_exchange 比較多詳細的描述

Diffie-Hellman密鑰交換算法可以解決這個問題:

即使是在不安全的通道裡雙方還是可以協商出一同一把密鑰,而竊聽的人無法輕易得知那把密鑰。

他的做法是給定兩個數 p, g
p是質數、g是 primitive root modulo p
https://en.wikipedia.org/wiki/Primitive_root_modulo_n

Alice、Bob透過不安全的通道交換p, g的資訊(所以這個資訊可能被第三者知道)

Alice挑了一個數字a 計算出 A=g^a mod p,然後將A數字給Bob
Bob挑了一個數字b 計算出 B=g^b mod p,然後將B數字給Alice
Alice將拿到的B 計算出 K1=B^a mod p
Bob將拿到的A 計算出 K2=A^b mod p
事實上 K1 = K2 亦即他們已經協商出同一把密鑰了

第三者可能得到的資訊是 p, g, A, B,但是沒辦法算出K
而a則是只有Alice知道,b則是只有Bob知道

以下說明 K1=K2

g^a = M * p + A
A = g^a – M * p
A^b = (g^a – M * p)^b
K1 = A^b mod p = (g^a – M * p)^b mod p = g^a^b mod p (二項式展開後只有第一項不整除)

g^b = M’ * p + B
B = g^b – M’ * p
B^a = (g^b – M’ * p)^a
K2 = B^a mod p = (g^b – M’ * p)^a mod p = g^b^a mod p

K1 = K2 = g^b^a mod p

在實務上,a, b, p取較大的數字,因為K是由mod p決定,如果p太小,代表K 可能是 {0…p-1}的數,很容易被猜出來。

這裡只單純處理通道加密而沒有authenticate的概念,所以他沒辦法阻擋MITM(man-in-the-middle),但是可以避免eavesdrop。 應用常見於一開始的session連線加密,例如ssh在一開始做key exchange時就用到此算法的變形。

另外一個應用是手機通訊軟體的end-to-end加密,有些情況兩個client訊息是透過server加密傳輸(client-server而不是p2p),雖然client server之間的連線是加密的,旁人無法竊聽,但是server可以看到plain text,透過D-H Key exchange,可以做到連server也不知道密鑰,從而只有兩個client之間能加解密訊息內容。所以整個系統就會有連線transport加密,application層訊息的加密。

而因為session key不是事先決定的,所以也可以用來達成forward secrecy,
forward secrecy主要是防止事後因為某種原因密鑰洩漏造成session內容可被解開。 (舉例來說,如果加密的key可由密碼得出或是用固定的私鑰加密,一旦在未來的某個時間點密鑰洩漏, 如果當時的雙方通信內容被側錄,就有機會被解開,而達到forward secrecy的做法則是 session key用另一把獨立的key)

參考 https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange

https://www.digitalocean.com/community/tutorials/understanding-the-ssh-encryption-and-connection-process

https://security.stackexchange.com/questions/76894/how-does-ssh-use-both-rsa-and-diffie-hellman

This entry was posted in General. Bookmark the permalink.

Leave a Reply