跳轉到

8.2 離散對數問題#

概念說明#

在群 G 中取生成元 g，任一元素可寫成 h = g^x。離散對數問題（Discrete Logarithm Problem, DLP）：

給定 g 與 h，求整數 x（記作 x = log_g h）。

「對數」在實數世界用計算機一按即得，為何在 mod p 的世界變成難題？因為連續的對數（如 ln）可以靠「夾逼、微積分」逐步逼近，而模世界裡 g^x 在 0..p−2 之間跳來跳去，毫無順序——你無法靠「接近」縮小範圍，只能挨家挨戶地找。這種「離散化抹掉所有結構」正是單向性的來源。

DLP 是 DH 金鑰交換（7.1）與 ElGamal 加密/簽章的根基；其橢圓曲線版本 ECDLP 是 ECC 的根基（7.3）。

已知演算法與時間界#

演算法 適用群 複雜度
窮舉 任意 O(n)，n 為群階
Baby-step Giant-step 任意 O(√n) 時間與記憶體
Pollard rho 任意 O(√n) 時間、O(1) 記憶體
Pohlig–Hellman 群階為光滑數 拆成小質因數的子問題
指數積分（Index Calculus） 僅 Z_p* 模群 亞指數 exp(√(ln p · ln ln p))

關鍵差異：*Z_p 上存在亞指數攻擊（指數積分法），橢圓曲線群上至今沒有*——這就是 ECC 用 256 位元即可達 128 位元安全、而 Z_p 的 DH 需要 2048+ 位元的根本原因（√n 與亞指數的差別）。

演算法步驟（Baby-step Giant-step，教學必學）#

  1. 取 m = ⌈√n⌉。把 x 寫成 x = i·m − j（0 ≤ i, j < m），則 h·g^j = (g^m)^i。
  2. Baby steps：預建表 {g^j : j → j}。
  3. Giant steps：對 i = 0..m−1 計算 (g^m)^i，查表命中即得 x。

Python 實作#

import math

def bsgs(g, h, p):
    """在 Z_p* 上解 h = g^x (mod p)"""
    m = math.isqrt(p - 1) + 1
    table = {}
    e = 1
    for j in range(m):               # baby steps
        table[e] = j
        e = e * g % p
    gm = pow(g, m * (p - 2), p)      # g^(-m) mod p（用費馬求反元素）
    gamma = h % p
    for i in range(m):               # giant steps
        if gamma in table:
            return i * m + table[gamma]
        gamma = gamma * gm % p
    return None

p = 1000003        # 素數
g = 2
x = 123456
h = pow(g, x, p)
print(bsgs(g, h, p))                 # 123456（約 √p ≈ 1000 步）

# Pollard rho：O(1) 記憶體的 √n 演算法（概要）
def pollard_rho_log(g, h, p, n):     # n 為群階
    def f(t):                        # 隨機遊走的三分法
        x, a, b = t
        if x % 3 == 0: return (x * x % p, 2 * a % n, 2 * b % n)
        if x % 3 == 1: return (x * g % p, (a + 1) % n, b)
        return (x * h % p, a, (b + 1) % n)
    t = f((1, 0, 0)); r = f(f((1, 0, 0)))
    while t[0] != r[0]:              # 找到 x_t = x_r ⇒ g^a h^b = g^c h^d
        t, r = f(t), f(f(r))
    a, b, c, d = t[1], t[2], r[1], r[2]
    return (c - a) * pow(b - d, -1, n) % n   # 若 gcd(b-d, n)=1

安全性分析#

  • √n 的意義：256 位元群階 ⇒ Pollard rho 約 2^128 步——這就是「ECC-256 ≈ 128 位元安全」的出處；同時提醒：群階必須是大質數（或含大質因數），否則 Pohlig–Hellman 拆解。
  • 參數紀律：p 不可為 512 位元以下（Logjam：預運算後分鐘級破解出口級 DH）；DLP 與「DH 假設」（由 g^a、g^b 求 g^(ab)）一般認為等價或近等價，但嚴格歸約仍是理論研究課題。
  • 量子崩塌：Shor 演算法（10.2 節）用量子傅立葉變換在多項式時間解 DLP——ECDLP 與 DLP 的「難」在量子模型下同時消失，這是後量子遷移（10.3）的直接動機。

練習#

  1. 手算 p=23, g=5, h=8 的離散對數（窮舉即可），再用 bsgs 驗證。
  2. 把 bsgs 的群階換成 p−1 = 2q（q 大質數）的例子，並解釋為什麼 Pohlig–Hellman 在「p−1 光滑」時遠快於 √p。
  3. 比較實測：對同一 p（如 2^31−1），分別用窮舉與 bsgs 解一個隨機 DLP，記錄運算次數，驗證 √n 的加速。