跳轉到

7.2 RSA 的數學與實作#

概念說明#

RSA（Rivest、Shamir、Adleman，1977）是第一個實用的公開金鑰系統，根基是大整數分解難題（8.3 節）：

  • 正向（加密）：C = M^e mod n，人人可算。
  • 逆向（解密）：M = C^d mod n，只有知道 d（私鑰）的人可算。
  • 陷門：要從 (n, e) 求 d，必須先分解 n = p·q——而 2048 位元的 n 以現有技術不可分解。

演算法步驟#

金鑰產生：

  1. 選兩個大質數 p、q（各約 1024 位元）。
  2. n = p·q；φ(n) = (p−1)(q−1)。
  3. 選 e 與 φ(n) 互質（慣用 e = 65537）。
  4. 求 d = e⁻¹ mod φ(n)（擴展歐幾里得演算法）。
  5. 公鑰 (n, e)，私鑰 (n, d)。銷毀 p, q, φ(n)。

加密/解密：C = M^e mod n、M = C^d mod n。簽章/驗證：σ = H(M)^d mod n、驗證 σ^e == H(M)（實務用 RSA-PSS 填充）。

為什麼可逆：歐拉定理 M^(φ(n)) ≡ 1 (mod n)（gcd(M,n)=1 時），故 M^(e·d) = M^(1 + kφ(n)) ≡ M (mod n)。

Python 實作（教學版，含素性測試）#

import random, hashlib

def is_prime(n, k=40):
    """Miller-Rabin 素性測試"""
    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):
        x = pow(random.randrange(2, n - 1), 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

def gen_prime(bits):
    while True:
        c = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_prime(c): return c

def gen_rsa(bits=1024):   # 教學用 1024；實務至少 2048
    e = 65537
    while True:
        p, q = gen_prime(bits // 2), gen_prime(bits // 2)
        if p == q: continue
        n, phi = p * q, (p - 1) * (q - 1)
        if phi % e == 0: continue
        d = pow(e, -1, phi)
        return (n, e), (n, d)

pub, priv = gen_rsa(1024)
n, e = pub; _, d = priv

# 加解密（教學版無填充！）
m = int.from_bytes(b"RSA!", "big")
c = pow(m, e, n)
assert pow(c, d, n) == m
print("加密→解密 OK:", pow(c, d, n).to_bytes(4, "big"))

# 實務：PyCryptodome + OAEP 填充 + PSS 簽章
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Signature import pss
from Crypto.Hash import SHA256

key = RSA.generate(2048)
ct = PKCS1_OAEP.new(key.publickey()).encrypt(b"secret with OAEP")
print("OAEP 解密:", PKCS1_OAEP.new(key).decrypt(ct))
h = SHA256.new(b"document")
sig = pss.new(key).sign(h)
pss.new(key.publickey()).verify(h, sig)   # 不通過會 raise
print("PSS 簽章驗證 OK")

安全性分析#

  • 絕不可「教科書式 RSA」上線：確定性（同明文同密文）、小 e 低熵訊息可直接開 e 次方、乘法同態可偽造簽章。實務必用 OAEP（加密）/PSS（簽章）填充。
  • 分解能力持續進步：RSA-768 已於 2009 年被分解（數月、數千核），學界估計 RSA-1024 在國家級算力下岌岌可危——最低 2048 位元，長期建議 3072 或轉 ECC/後量子。
  • 私鑰保護：CRT 加速存儲 (p, q, dp, dq, qinv)，洩漏其中任一即等於洩漏 d；側頻道（時間、電力、快取）攻擊對 RSA 解密尤其致命，需常數時間實作（或用蒙哥馬利乘法的防護版）。
  • 與 ECC 的比較：RSA 3072 位元 ≈ EC P-256 的 128 位元安全度，後者金鑰與運算小一個數量級，是現代新系統的首選（7.3 節）；兩者都敵不過 Shor 演算法（10.2 節）。

練習#

  1. 手算迷你 RSA：p=3, q=11, e=7。求 n、φ(n)、d；加密 m=4，再解密驗證。
  2. 用教學版實作觀察「小指數攻擊」：e=3 且訊息很小時，C = m^3 可能根本沒繞過模數——用 round(c ** (1/3)) 直接還原明文。
  3. 解釋為什麼 d = e⁻¹ mod φ(n) 可以用 pow(e, -1, phi) 求出（Python 3.8+），並實作擴展歐幾里得演算法做同樣的事。