密碼學 - Diffie-Hellman 金鑰交換演算法

import random

def is_prime(n, k=5):  
    """  
    使用 Miller-Rabin 素性檢定來判斷一個數是否為質數。  
    """  
    if n <= 1:  
        return False  
    if n <= 3:  
        return True  
    if n % 2 == 0:  
        return False

    # 將 n-1 寫成 2^r * d 的形式  
    d = n - 1  
    r = 0  
    while d % 2 == 0:  
        d //= 2  
        r += 1

    # 進行 k 次檢定  
    for _ in range(k):  
        a = random.randint(2, n - 2)  
        x = pow(a, d, n)  
        if x == 1 or x == n - 1:  
            continue  
        for _ in range(r - 1):  
            x = pow(x, 2, n)  
            if x == n - 1:  
                break  
        else:  
            return False  
    return True

def generate_large_prime(bits=64):  
    """  
    生成一個指定位元數的大質數。  
    """  
    while True:  
        p = random.getrandbits(bits)  
        # 確保是奇數且位元數正確  
        p |= (1 << bits - 1) | 1  
        if is_prime(p):  
            return p

# --- 1. 公開參數的約定 ---  
# 在真實世界中，這些數字會非常大 (例如 2048 位元)  
# 為了方便展示，我們使用較小的數字  
# p 必須是一個質數  
p = generate_large_prime(32)  
# g 是一個生成元 (這裡我們簡單選擇一個小的數字)  
g = 5

print(f"--- 公開參數 ---")  
print(f"大質數 (p): {p}")  
print(f"生成元 (g): {g}n")

# --- 2. 各自生成私鑰 ---  
# 愛麗絲 (Alice) 選擇一個秘密數字 a  
a = random.randint(2, p - 2)  
print(f"愛麗絲的私鑰 (a): {a}")

# 鮑伯 (Bob) 選擇一個秘密數字 b  
b = random.randint(2, p - 2)  
print(f"鮑伯的私鑰 (b): {b}n")

# --- 3. 計算並交換公鑰 ---  
# 愛麗絲計算她的公鑰 A 並公開  
# A = (g 的 a 次方) 再除以 p 取餘數  
A = pow(g, a, p)  
print(f"愛麗絲的公鑰 (A)，她會將此公開: {A}")

# 鮑伯計算他的公鑰 B 並公開  
# B = (g 的 b 次方) 再除以 p 取餘數  
B = pow(g, b, p)  
print(f"鮑伯的公鑰 (B)，他會將此公開: {B}n")

# --- 4. 計算共享秘密 ---  
# 愛麗絲使用鮑伯的公鑰 B 和自己的私鑰 a 來計算共享秘密  
# s_alice = (B 的 a 次方) 再除以 p 取餘數  
s_alice = pow(B, a, p)  
print(f"愛麗絲計算出的共享秘密 (s): {s_alice}")

# 鮑伯使用愛麗絲的公鑰 A 和自己的私鑰 b 來計算共享秘密  
# s_bob = (A 的 b 次方) 再除以 p 取餘數  
s_bob = pow(A, b, p)  
print(f"鮑伯計算出的共享秘密 (s): {s_bob}n")

# --- 驗證 ---  
if s_alice == s_bob:  
    print("✅ 成功！愛麗絲和鮑伯得到了相同的共享秘密。")  
    print(f"他們現在可以使用 {s_alice} 作為對稱加密的金鑰。")  
else:  
    print("❌ 失敗！共享秘密不相同。")