8.1 模運算與群環體#

模運算：密碼學的呼吸#

模運算（modular arithmetic）就是「只看餘數」的算術：a ≡ b (mod n) 表示 a 與 b 除以 n 的餘數相同。時鐘是最直覺的例子：13 點即 1 點（mod 12）。密碼學熱愛模運算的理由很實際——運算結果被壓縮在固定範圍內（不會無限膨脹），且「去路徑、留餘數」的過程本身就是單向性的來源。

基本性質（加法與乘法都「取模後仍成立」）：

(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a · b) mod n = ((a mod n) · (b mod n)) mod n

最大公因數與擴展歐幾里得#

• gcd(a, b)：輾轉相除 gcd(a, b) = gcd(b, a mod b)，複雜度 O(log b)。
• 互質：gcd(a, n) = 1。
• 擴展歐幾里得：找整數 x, y 使 a·x + b·y = gcd(a, b)。當 gcd(e, φ)=1 時可得 e·x ≡ 1 (mod φ)，即模反元素——這正是 RSA 求 d 的方法，也是 Python pow(e, -1, φ) 的內涵。

費馬小定理與歐拉定理（RSA 的正確性證明）#

• 費馬小定理：p 質數、gcd(a,p)=1 ⇒ a^(p−1) ≡ 1 (mod p)。
• 歐拉定理：n 任意、gcd(a,n)=1 ⇒ a^φ(n) ≡ 1 (mod n)，其中 φ(n)（歐拉函數）是 1..n 中與 n 互質的個數；對 n = p·q（質數積）有 φ(n) = (p−1)(q−1)。

RSA 回顧（7.2 節）：e·d ≡ 1 (mod φ(n))，故 M^(ed) = M^(1+kφ(n)) ≡ M^(1) ≡ M (mod n)——兩行就證明了加解密可逆。

群、環、體：三分鐘版#

密碼學常用的三個舞台：Z_p（p 質數的非零元素乘法群，階為 p−1，DH 的老家）、*GF(2^8)（AES MixColumns 的體）、橢圓曲線點群**（ECC 的家）。

群的階（order）：群中元素個數。元素的階：使 g^m = 1 的最小 m，必整除群階（拉格朗日定理）——RSA 金鑰產生時要求 e 與 φ(n) 互質、橢圓曲線要求基點階為大質數，都是這條定理的應用。

Python 實作#

def egcd(a, b):                       # 擴展歐幾里得
    if b == 0: return (a, 1, 0)
    g, x, y = egcd(b, a % b)
    return (g, y, x - (a // b) * y)

def modinv(a, n):                     # 模反元素
    g, x, _ = egcd(a % n, n)
    assert g == 1, "不互質，無反元素"
    return x % n

print(pow(7, 128, 13), (7 % 13) ** 2 % 13)  # 7^128 = 7^(6*21+2) → 驗證費馬
print(modinv(65537, (101 * 103 - 101 - 103 + 1)))   # RSA 的 d
print(pow(3, 322 - 1, 323), "歐拉定理：3^φ(323) mod 323 = 1")

# Z_p* 的元素階必整除 p−1（拉格朗日）
p = 23
for g in range(2, p):
    o, v = 1, g
    while v != 1:
        v = v * g % p; o += 1
    print(f"g={g:2} 階={o:2}", "← 生成元" if o == p - 1 else "")

安全性分析#

• 模運算的單向性不是萬能：加法、乘法、開方皆「可逆容易」；真正難的是離散對數（8.2）與分解（8.3）——單向難題是挑出來的，不是模運算自動給的。
• 弱參數的教訓：p−1 若為「光滑數」（只有小質因數），Pohlig–Hellman 演算法把離散對數拆成小問題逐個擊破——DH 參數的 p 必須使 p−1 含大質因數（或直接用安全素數 p = 2q+1）。
• 非質數模數的陷阱：Z_n（n 合數）不是體，除法/開方可能「沒有答案」或多解；RSA 之所以敢在 Z_n 上工作，全靠私鑰持有 φ(n) 這個陷門。

練習#

1. 用 egcd 求 17 在 mod 3120 下的反元素（即迷你 RSA 的 d：φ(3120)=φ(65×48) 自行拆解 p=65 需先分解）。
2. 對 p=11 的每個 g∈[2,10] 列出階，找出所有生成元；觀察生成元個數是 φ(p−1)。
3. 證明：若 p 質數且 a^(p−1) ≢ 1 (mod p)，則 p 不是質數——這正是 Fermat 素性測試；再用一個合數（如 341 = 11×31）找出「欺騙 Fermat 測試」的 a，體會為何需要 Miller–Rabin（8.3 節）。