跳轉到

7.1 迪菲-赫爾曼金鑰交換#

概念說明#

迪菲—赫爾曼金鑰交換（Diffie–Hellman, DH）解決的問題聽起來像魔術：Alice 與 Bob 在所有人都能竊聽的頻道上，商量出一把只有他們兩人知道的對稱金鑰。

魔術的數學核心是單向函數的不對稱性：

  • 正向：給定 g 與 a，算 g^a mod p 很快（平方—乘法，多項式時間）。
  • 逆向：給定 g、g^a、g^b，要算出 g^(ab)——即離散對數問題（8.2 節）——在參數夠大時至今無有效演算法。

演算法步驟#

公開參數：大質數 p 與生成元 g（p 的乘法群的生成元，8.1 節）。

  1. Alice 選祕密 a，計算並廣播 A = g^a mod p。
  2. Bob 選祕密 b，計算並廣播 B = g^b mod p。
  3. Alice 計算 s = B^a mod p = g^(ab) mod p。
  4. Bob 計算 s = A^b mod p = g^(ab) mod p——兩者相同！
  5. 用 s（或 KDF(s)）當對稱加密金鑰。

竊聽者 Eve 知道 p, g, A, B，卻算不出 g^(ab)（Diffie–Hellman 問題：由 g^a, g^b 求 g^(ab)，一般認為不比離散對數容易）。

Python 實作#

import random, hashlib

# 教學參數（實務用 2048+ 位元 p，或 X25519 曲線）
p = 0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E08  # 224-bit 素數示例
g = 2

a = random.randrange(2, p - 1)      # Alice 私鑰
b = random.randrange(2, p - 1)      # Bob 私鑰
A = pow(g, a, p)                    # 公開
B = pow(g, b, p)                    # 公開

s_alice = pow(B, a, p)              # Alice 得共享祕密
s_bob = pow(A, b, p)                # Bob 得共享祕密
assert s_alice == s_bob
key = hashlib.sha256(s_alice.to_bytes((s_alice.bit_length()+7)//8, "big")).digest()
print("共享金鑰:", key.hex()[:32])

# 實務：X25519（橢圓曲線版 DH，TLS 1.3 預設）
from cryptography.hazmat.primitives.asymmetric.x25519 import X25519PrivateKey
ak = X25519PrivateKey.generate(); bk = X25519PrivateKey.generate()
shared1 = ak.exchange(bk.public_key())
shared2 = bk.exchange(ak.public_key())
assert shared1 == shared2
print("X25519 共享金鑰:", shared1.hex()[:32])

安全性分析#

  • 純 DH 不防中間人：Eve 可攔下 A、B，各用自己的 E = g^e 換掉，與 Alice、Bob 分別建立金鑰——雙方渾然不覺。DH 只解決「竊聽」，不解決「冒充」。防禦：對 DH 訊息做簽章（→ authenticated DH，TLS 的做法，9.1 節）或以憑證綁定長期公鑰。
  • 靜態 DH vs 暫態 DH：每則連線用新的臨時金鑰（ephemeral, DHE/ECDHE）可提供前向保密（forward secrecy）——長期私鑰日後洩漏，也不影響過去對話的機密性。TLS 1.3 已強制只用暫態金鑰。
  • 參數紀律：p 必須至少 2048 位元（Logjam 攻擊已能破解 512 位元的出口級參數），且 p、g 不可由對方指定為弱參數；群上小元素攻擊（small subgroup）需驗證對方的公鑰落在合法群中。
  • 量子威脅：Shor 演算法（10.2 節）可在多項式時間解離散對數——DH 與 ECDH 的根基在量子時代全數崩塌，需遷移至後量子 KEM（10.3 節）。

練習#

  1. 手算 p=23, g=5, a=6, b=15 的完整 DH 交換，驗證雙方得出相同共享祕密。
  2. 寫程式實作中間人攻擊：Eve 攔截並替換 A、B，顯示 Alice 與 Bob 各自算出「與 Eve 而非彼此」共享的金鑰。
  3. 查閱 RFC 7748（X25519），說明橢圓曲線版 DH 把「模指數」換成了什麼運算，以及為什麼曲線版能用 256 位元金鑰達到模數 3072 位元 DH 的同等安全度。