1977 - RSA#

案件摘要#

1977 年，MIT 的三位年輕人 Rivest、Shamir、Adleman 發表《A Method for Obtaining Digital Signatures and Public-Key Cryptosystems》：用大數分解的單向性實現完整的公鑰加密與數位簽章。加密 = 冪運算模 \(n = pq\) ，解密 = 用 Euler 定理反推——數學優雅到一頁論文就能寫完。RSA 成為 40 年來公鑰密碼的標準，是 HTTPS、電子簽章、軟體發行的基礎。

前因 -- 為什麼會有這個案子#

Diffie–Hellman（1976，見 1976-DiffieHellman金鑰交換.md）解決了金鑰交換，但留下了懸案：公鑰「加密」——任何人用公鑰加密、只有私鑰能解——沒有實例。Rivest、Shamir、Adleman 在 MIT 嘗試了數十種單向陷門函數（背包、組合數學……），一整年的失敗後，1977 年 4 月 Rivest 在猶太逾越節前夕想到：大數分解。

線索與推理 -- 數學式、程式、理論#

RSA 的數學#

金鑰生成：

選兩大質數 \(p, q\) （各 1024 位元以上）
\(n = pq\) （模數，公開）
\(\varphi(n) = (p-1)(q-1)\) （Euler 函數，保密）
選 \(e\) （公開）， \(\gcd(e, \varphi(n)) = 1\) （典型 \(e = 65537\) ）
\(d = e^{-1} \bmod \varphi(n)\) （私鑰，用擴展歐幾里得算法）

加密（任何人，用公鑰 \(n, e\) ）：

\[ c = m^e \bmod n \]

解密（只有私鑰 \(d\) ）：

\[ m = c^d \bmod n \]

為什麼解密能還原：Euler 定理#

Euler 定理： \(\gcd(m, n) = 1\) 時：

\[ m^{\varphi(n)} \equiv 1 \pmod n \]

於是：

\[ c^d = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \pmod n \quad \blacksquare \]

（ \(ed \equiv 1 \pmod{\varphi(n)}\) 保證 \(ed = 1 + k\varphi(n)\) 。）

單向性：分解是唯一後門#

為什麼安全：要從 \((n, e, c)\) 求 \(m\) ，需要 \(d = e^{-1} \bmod \varphi(n)\) ，而 \(\varphi(n) = (p-1)(q-1)\) 需要知道 \(p, q\) ——**需要分解 \(n\) **。

\(n\) 是 2048 位元時，數域篩法的成本 \(\approx 2^{112}\) 次運算——不可行
陷門：知道 \(p, q\) （私鑰持有者）， \(\varphi(n)\) 與 \(d\) 秒算

單向陷門函數（Diffie 1976 的構想，見 1974-Diffie公鑰構想.md）的完美實現：

\[ f(m) = m^e \bmod n \quad \text{：容易算，難逆，陷門 } = p, q \]

數位簽章#

公鑰密碼的反向使用（Diffie–Hellman 的構想）：

\[ \text{簽章：} \sigma = m^d \bmod n \quad \text{（只有私鑰能算）} \]

\[ \text{驗證：} \sigma^e \bmod n = m \quad \text{（任何人可驗）} \]

不可偽造（無 \(d\) 難算）、可驗證（公鑰公開）、不可否認（只有你能簽）——實務上先雜湊再簽（ \(\sigma = H(m)^d\) ，防結構攻擊）。

程式碼：完整 RSA#

import random

def mod_pow(b, e, n):
    result = 1; b %= n
    while e > 0:
        if e & 1: result = result * b % n
        b = b * b % n; e >>= 1
    return result

def extended_gcd(a, b):
    if b == 0: return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def mod_inverse(e, phi):
    g, x, _ = extended_gcd(e % phi, phi)
    return x % phi

def rsa_keygen(bits=512):
    """簡化：假設 p, q 已是質數（實務用 Miller-Rabin，見 ../隨機算法/1980-Rabin質數檢驗.md）"""
    from sympy import randprime  # 若無 sympy 用下面的篩法
    p, q = randprime(2**(bits//2-1), 2**(bits//2)), randprime(2**(bits//2-1), 2**(bits//2))
    n, phi = p * q, (p-1)*(q-1)
    e = 65537
    d = mod_inverse(e, phi)
    return (n, e), (n, d), (p, q)

(n, e), (n, d), (p, q) = rsa_keygen(512)
msg = 123456789
c = mod_pow(msg, e, n)           # 加密（任何人）
m = mod_pow(c, d, n)             # 解密（私鑰）
print(f"解密還原：{m == msg}")     # True

# 簽章
sig = mod_pow(msg, d, n)
print(f"簽章驗證：{mod_pow(sig, e, n) == msg}")   # True

# 陷門：知道 p, q 才能算 phi 與 d
phi = (p-1) * (q-1)
print(f"分解 n = {p} × {q}：陷門在分解")

（無 sympy 的純 Python 版本：用 ../隨機算法/1980-Rabin質數檢驗.md 的 is_probable_prime 產生質數。）

填補與攻擊的歷史#

朴素的 RSA 有攻擊，教科書式 RSA 不是安全協議： - 確定性：同一明文永遠同密文——字典攻擊 - 選擇密文攻擊：解密機器可被利用 - 對策：OAEP 填補（Bellare–Rogaway 1994）——隨機化填補使加密語義安全（IND-CCA2） - 簽章：先雜湊（見 1985-密碼學雜湊函數.md）再簽——PSS 填補

偵探筆記：RSA 的推理是「用最老的數學問題當陷門」——分解問題（Gauss 時代就知難）成為密碼的陷門。單向性與陷門的分離：公開方向（乘、冪）容易，保密方向（分解、取對數）難——Euler 定理是橋樑（ \(ed \equiv 1 \bmod \varphi(n)\) 的性質只在知道 \(\varphi(n)\) 時可逆）。

結案 -- 後果與影響#

40 年的標準：HTTPS 憑證、軟體簽章、PGP、區塊鏈——RSA 是公鑰密碼的代名詞。
公鑰密碼學的完整實現：加密 + 簽章，Diffie–Hellman 的構想全部落地。
金鑰長度軍備競賽：512 → 1024 → 2048 → 4096 位元——計算機變快， \(n\) 跟著變大。
OAEP/PSS 填補：教科書式 RSA → 語義安全的 RSA——證明式安全（provable security）的誕生。
圖靈獎：Rivest、Shamir、Adleman 獲 2002 年圖靈獎。
量子威脅：Shor 演算法（1994，見 1994-Shor演算法.md）多項式時間分解——RSA 的死刑判決，後量子密碼學的動機（見 2017-後量子密碼學.md）。

關鍵人物與文獻#

Ron Rivest（1947–）、Adi Shamir（1952–）、Len Adleman（1945–）：MIT；圖靈獎 2002（Rivest 與 Shamir）
Rivest, Shamir, Adleman: A Method for Obtaining Digital Signatures... (1978, Comm. ACM)
Bellare & Rogaway：OAEP (1994)
Clifford Cocks（GCHQ）：1973 秘密發明等價系統（保密至 1997）
交叉參照：1976-DiffieHellman金鑰交換.md、1985-ElGamal.md、1994-Shor演算法.md、2017-後量子密碼學.md