寫給開發人員的實用密碼學（五）—— 密鑰交換 DHKE 與完美前向保密 PFS

2022 年 3 月 14 日
筆記
密碼學, 算法

本文主要翻譯自 Practical-Cryptography-for-Developers-Book，筆者額外補充了 DHKE/ECDH 的代碼示例，以及「PFS 完美前向保密協議 DHE/ECDHE」一節。

《寫給開發人員的實用密碼學》系列文章目錄：

一、前言

在密碼學中密鑰交換是一種協議，功能是在兩方之間安全地交換加密密鑰，其他任何人都無法獲得密鑰的副本。通常各種加密通訊協議的第一步都是密鑰交換。
密鑰交換技術具體來說有兩種方案：

密鑰協商：協議中的雙方都參與了共享密鑰的生成，兩個代表算法是 Diffie-Hellman (DHKE) 和 Elliptic-Curve Diffie-Hellman (ECDH)
密鑰傳輸：雙方中其中一方生成出共享密鑰，並通過此方案將共享密鑰傳輸給另一方。密鑰傳輸方案通常都通過公鑰密碼系統實現。比如在 RSA 密鑰交換中，客戶端使用它的私鑰加密一個隨機生成的會話密鑰，然後將密文發送給服務端，服務端再使用它的公鑰解密出會話密鑰。

密鑰交換協議無時無刻不在數字世界中運行，在你連接 WiFi 時，或者使用 HTTPS 協議訪問一個網站，都會執行密鑰交換協議。
密鑰交換可以基於匿名的密鑰協商協議如 DHKE，一個密碼或預共享密鑰，一個數字證書等等。有些通訊協議只在開始時交換一次密鑰，而有些協議則會隨着時間的推移不斷地交換密鑰。

認證密鑰交換（AKE）是一種會同時認證相關方身份的密鑰交換協議，比如個人 WiFi 通常就會使用 password-authenticated key agreement (PAKE)，而如果你連接的是公開 WiFi，則會使用匿名密鑰交換協議。

目前有許多用於密鑰交換的密碼算法。其中一些使用公鑰密碼系統，而另一些則使用更簡單的密鑰交換方案（如 Diffie-Hellman 密鑰交換）；其中有些算法涉及服務器身份驗證，也有些涉及客戶端身份驗證；其中部分算法使用密碼，另一部分使用數字證書或其他身份驗證機制。下面列舉一些知名的密鑰交換算法：

Diffie-Hellman Key Exchange (DHКЕ) ：傳統的、應用最為廣泛的密鑰交換協議
橢圓曲線 Diffie-Hellman (ECDH)
RSA-OAEP 和 RSA-KEM（RSA 密鑰傳輸）
PSK（預共享密鑰）
SRP（安全遠程密碼協議）
FHMQV（Fully Hashed Menezes-Qu-Vanstone）
ECMQV（Ellictic-Curve Menezes-Qu-Vanstone）
CECPQ1（量子安全密鑰協議）

二、Diffie–Hellman 密鑰交換

迪菲-赫爾曼密鑰交換（Diffie–Hellman Key Exchange）是一種安全協議，它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道安全地協商出一個安全密鑰，而且任何竊聽者都無法得知密鑰信息。
這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

DHKE 可以防範嗅探攻擊（竊聽），但是無法抵擋中間人攻擊（中繼）。

DHKE 有兩種實現方案：

傳統的 DHKE 算法：使用離散對數實現
基於橢圓曲線密碼學的 ECDH

為了理解 DHKE 如何實現在「大庭廣眾之下」安全地協商出密鑰，我們首先使用色彩混合來形象地解釋下它大致的思路。

跟編程語言的 Hello World 一樣，密鑰交換的解釋通常會使用 Alice 跟 Bob 來作為通信雙方。
現在他倆想要在公開的信道上，協商出一個秘密色彩出來，但是不希望其他任何人知道這個秘密色彩。他們可以這樣做：

分步解釋如下：

首先 Alice 跟 Bob 溝通，確定一個初始的色彩，比如黃色。這個溝通不需要保密。
然後，Alice 跟 Bob 分別偷偷地選擇出一個自己的秘密色彩，這個就得保密啦。
現在 Alice 跟 Bob，分別將初始色彩跟自己選擇的秘密色彩混合，分別得到兩個混合色彩。
之後，Alice 跟 Bob 再回到公開信道上，交換雙方的混合色彩。
- 我們假設在僅知道初始色彩跟混合色彩的情況下，很難推導出被混合的秘密色彩。這樣第三方就猜不出 Bob 跟 Alice 分別選擇了什麼秘密色彩了。
最後 Alice 跟 Bob 再分別將自己的秘密色彩，跟對方的混合色彩混合，就得到了最終的秘密色彩。這個最終色彩只有 Alice 跟 Bob 知道，信道上的任何人都無法猜出來。

DHKE 協議也是基於類似的原理，但是使用的是離散對數（discrete logarithms）跟模冪（modular exponentiations ）而不是色彩混合。

三、經典 DHKE 協議

首先介紹下「模冪」，它是指求 \(g\) 的 \(a\) 次冪模 \(p\) 的值 \(c\) 的過程，其中 \(g\) \(a\) \(c\) 均為整數，公式如下：

\[g^a \mod p = c
\]

已知使用計算機計算上述「模冪」是非常快速的，但是求它的逆運算——即離散對數，在已知 \(g\) \(p\) \(c\) 的情況下，求冪指數 \(a\)——卻是非常難的。

下面該輪到 Alice 跟 Bob 出場來介紹 DHKE 的過程了，先看圖（下面綠色表示非秘密信息，紅色表示秘密信息）：

Alice 跟 Bob 協定使用兩個比較獨特的正整數 \(p\) 跟 \(g\)
- 假設 \(p=23\), \(g=5\)
Alice 選擇一個秘密整數 \(a\)，計算 \(A\)\(\ = g^a \mod p\) 並發送給 Bob
- 假設 \(a=4\)，則 \(A\)\(\ = 5^4 \mod 23 = 4\)
Bob 也選擇一個秘密整數 \(b\)，計算 \(B\)\(\ = g^b \mod p\) 並發送給 Alice
- 假設 \(b=3\)，則 \(B\)\(\ = 5^3 \mod 23 = 10\)
Alice 計算 \(S_1 = B^a \mod p\)
- \(S_1 = 10^4 \mod 23 = 18\)
Bob 計算 \(S_2 = A^b \mod p\)
- \(S_2 = 4^3 \mod 23 = 18\)
已知 \(B^a \mod p = g^{ab} \mod p = A^b \mod p\)，因此 \(S_1 = S_2 = S\)
這樣 Alice 跟 Bob 就協商出了密鑰 \(S\)
因為離散對數的計算非常難，任何竊聽者都幾乎不可能通過公開的 \(p\) \(g\) \(A\) \(B\) 逆推出 \(S\) 的值

在最常見的 DHKE 實現中（RFC3526），基數是 \(g = 2\)，模數 \(p\) 是一個 1536 到 8192 比特的大素數。
而整數 \(A\) \(B\) 通常會使用非常大的數字（1024、2048 或 4096 比特甚至更大）以防範暴力破解。

DHKE 協議基於 Diffie-Hellman 問題的實際難度，這是計算機科學中眾所周知的離散對數問題（DLP）的變體，目前還不存在有效的算法。

使用 Python 演示下大概是這樣：

# pip install cryptography==36.0.1
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh

# 1. 雙方協商使用兩個獨特的正整數 g 與 p
## generator => 即基數 g，通常使用 2, 有時也使用 5
## key_size => 模數 p 的長度，通常使用 2048-3096 位（2048 位的安全性正在減弱）
params = dh.generate_parameters(generator=2, key_size=2048)
param_numbers = params.parameter_numbers()
g = param_numbers.g  # => 肯定是 2
p = param_numbers.p  # => 一個 2048 位的整數
print(f"{g=}, {p=}")

# 2. Alice 生成自己的秘密整數 a 與公開整數 A
alice_priv_key = params.generate_private_key()
a = alice_priv_key.private_numbers().x
A = alice_priv_key.private_numbers().public_numbers.y
print(f"{a=}")
print(f"{A=}")

# 3. Bob 生成自己的秘密整數 b 與公開整數 B
bob_priv_key = params.generate_private_key()
b = bob_priv_key.private_numbers().x
B = bob_priv_key.private_numbers().public_numbers.y
print(f"{b=}")
print(f"{B=}")

# 4. Alice 與 Bob 公開交換整數 A 跟 B（即各自的公鑰）

# 5. Alice 使用 a B 與 p 計算出共享密鑰
## 首先使用 B p g 構造出 bob 的公鑰對象（實際上 g 不參與計算）
bob_pub_numbers = dh.DHPublicNumbers(B, param_numbers)
bob_pub_key = bob_pub_numbers.public_key()
## 計算共享密鑰
alice_shared_key = alice_priv_key.exchange(bob_pub_key)

# 6. Bob 使用 b A 與 p 計算出共享密鑰
## 首先使用 A p g 構造出 alice 的公鑰對象（實際上 g 不參與計算）
alice_pub_numbers = dh.DHPublicNumbers(A, param_numbers)
alice_pub_key = alice_pub_numbers.public_key()
## 計算共享密鑰
bob_shared_key = bob_priv_key.exchange(alice_pub_key)

# 兩者應該完全相等， Alice 與 Bob 完成第一次密鑰交換
alice_shared_key == bob_shared_key

# 7. Alice 與 Bob 使用 shared_key 進行對稱加密通訊

四、新一代 ECDH 協議

Elliptic-Curve Diffie-Hellman (ECDH) 是一種匿名密鑰協商協議，它允許兩方，每方都有一個橢圓曲線公鑰-私鑰對，它的功能也是讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道安全地協商出一個安全密鑰。

ECDH 是經典 DHKE 協議的變體，其中模冪計算被橢圓曲線的乘法計算取代，以提高安全性。

ECDH 跟前面介紹的 DHKE 非常相似，只要你理解了橢圓曲線的數學原理，結合前面已經介紹了的 DHKE，基本上可以秒懂。
我會在後面「非對稱算法」一文中簡單介紹橢圓曲線的數學原理，不過這裡也可以先提一下 ECDH 依賴的公式（其中 \(a, b\) 為常數，\(G\) 為橢圓曲線上的某一點的坐標 \((x, y)\)）：

\[(a * G) * b = (b * G) * a
\]

這個公式還是挺直觀的吧，感覺小學生也能理解個大概。
下面簡單介紹下 ECDH 的流程：

Alice 跟 Bob 協商好橢圓曲線的各項參數，以及基點 G，這些參數都是公開的。
Alice 生成一個隨機的 ECC 密鑰對（公鑰：\(alicePrivate * G\), 私鑰: \(alicePrivate\)）
Bob 生成一個隨機的 ECC 密鑰對（公鑰：\(bobPrivate * G\), 私鑰: \(bobPrivate\)）
兩人通過不安全的信道交換公鑰
Alice 將 Bob 的公鑰乘上自己的私鑰，得到共享密鑰 \(sharedKey = (bobPrivate * G) * alicePrivate\)
Bob 將 Alice 的公鑰乘上自己的私鑰，得到共享密鑰 \(sharedKey = (alicePrivate * G) * bobPrivate\)
因為前面提到的公式，Alice 與 Bob 計算出的共享密鑰應該是相等的

這樣兩方就通過 ECDH 完成了密鑰交換。

而 ECDH 的安全性，則由 ECDLP 問題提供保證。
這個問題是說，「通過公開的 \(kG\) 以及 \(G\) 這兩個參數，目前沒有有效的手段能快速求解出 \(k\) 的值。」

從上面的流程中能看到，公鑰就是 ECDLP 中的 \(kG\)，另外 \(G\) 也是公開的，而私鑰就是 ECDLP 中的 \(k\)。
因為 ECDLP 問題的存在，攻擊者破解不出 Alice 跟 Bob 的私鑰。

代碼示例：

# pip install tinyec  # ECC 曲線庫
from tinyec import registry
import secrets

def compress(pubKey):
    return hex(pubKey.x) + hex(pubKey.y % 2)[2:]

curve = registry.get_curve('brainpoolP256r1')

alicePrivKey = secrets.randbelow(curve.field.n)
alicePubKey = alicePrivKey * curve.g
print("Alice public key:", compress(alicePubKey))

bobPrivKey = secrets.randbelow(curve.field.n)
bobPubKey = bobPrivKey * curve.g
print("Bob public key:", compress(bobPubKey))

print("Now exchange the public keys (e.g. through Internet)")

aliceSharedKey = alicePrivKey * bobPubKey
print("Alice shared key:", compress(aliceSharedKey))

bobSharedKey = bobPrivKey * alicePubKey
print("Bob shared key:", compress(bobSharedKey))

print("Equal shared keys:", aliceSharedKey == bobSharedKey)

五、PFS 完美前向保密協議 DHE/ECDHE

前面介紹的經典 DHKE 與 ECDH 協議流程，都是在最開始時交換一次密鑰，之後就一直使用該密鑰通訊。
因此如果密鑰被破解，整個會話的所有信息對攻擊者而言就完全透明了。

為了進一步提高安全性，密碼學家提出了「完全前向保密（Perfect Forward Secrecy，PFS）」的概念，並在 DHKE 與 ECDH 的基礎上提出了支持 PFS 的 DHE/ECDHE 協議（末尾的 E 是 ephemeral 的縮寫，即指所有的共享密鑰都是臨時的）。

完全前向保密是指長期使用的主密鑰泄漏不會導致過去的會話密鑰泄漏，從而保護過去進行的通訊不受密碼或密鑰在未來暴露的威脅。

下面使用 Python 演示下 DHE 協議的流程（ECDHE 的流程也完全類似）：

# pip install cryptography==36.0.1
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh

# 1. 雙方協商使用兩個獨特的正整數 g 與 p
## generator => 即基數 g，通常使用 2, 有時也使用 5
## key_size => 模數 p 的長度，通常使用 2048-3096 位（2048 位的安全性正在減弱）
params = dh.generate_parameters(generator=2, key_size=2048)
param_numbers = params.parameter_numbers()
g = param_numbers.g  # => 肯定是 2
p = param_numbers.p  # => 一個 2048 位的整數
print(f"{g=}, {p=}")

# 2. Alice 生成自己的秘密整數 a 與公開整數 A
alice_priv_key = params.generate_private_key()
a = alice_priv_key.private_numbers().x
A = alice_priv_key.private_numbers().public_numbers.y
print(f"{a=}")
print(f"{A=}")

# 3. Bob 生成自己的秘密整數 b 與公開整數 B
bob_priv_key = params.generate_private_key()
b = bob_priv_key.private_numbers().x
B = bob_priv_key.private_numbers().public_numbers.y
print(f"{b=}")
print(f"{B=}")

# 4. Alice 與 Bob 公開交換整數 A 跟 B（即各自的公鑰）

# 5. Alice 使用 a B 與 p 計算出共享密鑰
## 首先使用 B p g 構造出 bob 的公鑰對象（實際上 g 不參與計算）
bob_pub_numbers = dh.DHPublicNumbers(B, param_numbers)
bob_pub_key = bob_pub_numbers.public_key()
## 計算共享密鑰
alice_shared_key = alice_priv_key.exchange(bob_pub_key)

# 6. Bob 使用 b A 與 p 計算出共享密鑰
## 首先使用 A p g 構造出 alice 的公鑰對象（實際上 g 不參與計算）
alice_pub_numbers = dh.DHPublicNumbers(A, param_numbers)
alice_pub_key = alice_pub_numbers.public_key()
## 計算共享密鑰
bob_shared_key = bob_priv_key.exchange(alice_pub_key)

# 上面的流程跟經典 DHKE 完全一致，代碼也是從前面 Copy 下來的
# 但是從這裡開始，進入 DHE 協議補充的部分

shared_key_1 = bob_shared_key # 第一個共享密鑰

# 7. 假設 Bob 現在要發送消息 M_b_1 給 Alice
## 首先 Bob 使用對稱加密算法加密消息 M_b
M_b_1 = "Hello Alice, I'm bob~"
C_b_1 = Encrypt(M_b_1, shared_key_1)  # Encrypt 是某種對稱加密方案的加密算法，如 AES-256-CTR-HMAC-SHA-256
## 然後 Bob 需要生成一個新的公私鑰 b_2 與 B_2（注意 g 與 p 兩個參數是不變的）
bob_priv_key_2 = parameters.generate_private_key()
b_2 = bob_priv_key.private_numbers().x
B_2 = bob_priv_key.private_numbers().public_numbers.y
print(f"{b_2=}")
print(f"{B_2=}")

# 8. Bob 將 C_b_1 與 B_2 一起發送給 Alice

# 9. Alice 首先解密數據 C_b_1 得到原始消息 M_b_1
assert M_b_1 == Decrypt(C_b_1, shared_key_1)  # Dncrypt 是某種對稱加密方案的解密算法，如 AES-256-CTR-HMAC-SHA-256
## 然後 Alice 也生成新的公私鑰 a_2 與 A_2
alice_priv_key_2 = parameters.generate_private_key()
## Alice 使用 a_2 B_2 與 p 計算出新的共享密鑰 shared_key_2
bob_pub_numbers_2 = dh.DHPublicNumbers(B_2, param_numbers)
bob_pub_key_2 = bob_pub_numbers_2.public_key()
shared_key_2 = alice_priv_key_2.exchange(bob_pub_key_2)

# 10. Alice 回復 Bob 消息時，使用新共享密鑰 shared_key_2 加密消息得到 C_a_1
# 然後將密文 C_a_1 與 A_2 一起發送給 Bob

# 11. Bob 使用 b_2 A_2 與 p 計算出共享密鑰 shared_key_2
# 然後再使用 shared_key_2 解密數據
# Bob 在下次發送消息時，會生成新的 b_3 與 B_3，將 B_3 隨密文一起發送

## 依次類推

通過上面的代碼描述我們應該能理解到，Alice 與 Bob 每次交換數據，實際上都會生成新的臨時共享密鑰，公鑰密鑰在每次數據交換時都會更新。
即使攻擊者破解了花費了很大的代價破解了其中某一個臨時共享密鑰 shared_key_k（或者該密鑰因為某種原因泄漏了），它也只能解密出其中某一次數據交換的信息 M_b_k，其他所有的消息仍然是保密的，不受此次攻擊（或泄漏）的影響。

參考

Tags: 密碼學算法