跳轉到

8.3 大數分解問題#

概念說明#

質因數分解：把整數 n 寫成質數的乘積 n = p·q·r...。RSA 的安全假設可表述為：

給定 n = p·q（p、q 為大質數），求 p、q 在計算上不可行。

有趣的歷史：分解「在數論上」的研究超過兩千年（Eratosthenes 篩法約在西元前 3 世紀），但始終沒有人證明它難——我們相信 RSA 的依據是「人類動用數百年智慧仍未找到多項式演算法」這個經驗事實。這是密碼學「計算安全」假設的典型：基於最佳已知攻擊，而非數學證明。

已知演算法與時間界#

演算法 年代 複雜度 適用
試除 上古 O(√n) n < 10^16
Pollard p−1 1974 光滑數時多項式 p−1 為光滑數的 n
Pollard rho 1975 O(n^(1/4)) 小因數
二次篩法（QS） 1981 亞指數 exp(√(ln n·ln ln n)) n < ~10^80
數域篩法（GNFS） 1993 exp(c·(ln n)^(1/3)(ln ln n)^(2/3)) 現行最強，RSA-250（829 位元）於 2020 年被分解

GNFS 是「亞指數」——比窮舉快得多，但仍遠超多項式。安全位元換算：RSA-2048 ≈ 112 位元安全、RSA-3072 ≈ 128 位元。

演算法步驟（Pollard rho，教學版）#

核心思想：隨機函數的序列會進入環（生日悖論），若序列是 x → x²+c (mod n)，則兩個項的差 |x_i − x_j| 有高機率與 n 的某個質因數 gcd 不為 1。

  1. 迭代 x_{i+1} = (x_i² + c) mod n。
  2. 用 Floyd 判圈：同時追蹤龜（t）與兔（r = f(f(r))）。
  3. 每步算 d = gcd(|t − r|, n)；若 1 < d < n，找到非平凡因數 d。

Python 實作#

import math, random

def pollard_rho(n):
    if n % 2 == 0: return 2
    while True:
        x = random.randrange(2, n)
        c = random.randrange(1, n)
        y, d = x, 1
        while d == 1:
            x = (x * x + c) % n
            y = (y * y + c) % n; y = (y * y + c) % n
            d = math.gcd(abs(x - y), n)
        if d != n: return d

def factorize(n):
    if n == 1: return []
    if is_prime(n): return [n]
    d = pollard_rho(n)
    return sorted(factorize(d) + factorize(n // d))

def is_prime(n, k=20):               # Miller–Rabin（RSA 產生 p、q 必備）
    if n < 2: return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37):
        if n % p == 0: return n == p
    d, r = n - 1, 0
    while d % 2 == 0: d //= 2; r += 1
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x in (1, n - 1): continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1: break
        else: return False
    return True

n = 8051
print(factorize(n))                  # [83, 97]

# 觀察「分解 2048 位元」的遙不可及：試對 RSA-2048 估計 GNFS 工作量
import datetime
print("RSA-2048 以 GNFS 估計：數千 CPU-年的叢集、數月牆鐘時間")

安全性分析#

  • 素性測試是快、分解是慢：Miller–Rabin 判斷 2048 位元數是否為質數是多項式時間（毫秒級），而分解同樣位元的合數是亞指數——這個不對稱正是 RSA 能「生成容易、破解困難」的原因。
  • 生成紀律：p、q 必須隨機、等長、相差夠大（p≈q 時費馬分解法奏效）、且 p−1、p+1 不可全光滑；決不可重用或「人工挑選」質數（2012 年 RoCA 研究發現部分智慧卡的質數生成有偏誤，導致私鑰可被 Coppersmith 攻擊還原）。
  • 共因數災難：兩把不同 RSA 金鑰若共享一個質數 p，兩者皆可被 gcd(n1, n2) 秒殺——2012 年 Lenstra 等人掃描網路上數百萬把公鑰，找到數萬把共因數金鑰。教訓：熵不足的隨機數源 + 高並發生成 = 大規模災難。
  • 量子崩塌：Shor 演算法（10.2 節）把分解變成多項式時間——RSA 的「難」將不復存在，這是 NIST 推動後量子標準（10.3 節）的核心理由。

練習#

  1. 用 pollard_rho 分解 10403 = 101×103，並手動追蹤前 5 步的 (x, y, d)。
  2. 寫程式產生 512 位元的 RSA n，再用 factorize 嘗試分解，記錄耗時；推算 2048 位元需要多久，與「宇宙年齡」比較。
  3. 解釋 Miller–Rabin 為何要用多個獨立隨機底數 a（k 次）：誤判機率如何隨 k 下降？k=40 對 2048 位元金鑰生成是否足夠？