RSA 的核心思想：為什麼「分解大數」這麼難

Published: Sat Feb 01 2025 | Modified: Sat Feb 07 2026 , 6 minutes reading.

1. 為什麼要關心這個問題？

1977 年，三位 MIT 的研究者——Rivest、Shamir 和 Adleman——發表了一個看似不可能的東西：一種加密方法，讓你可以公開發布加密用的金鑰，而只有你能解密。

這徹底改變了安全通訊的遊戲規則。

在 RSA 之前，Alice 想和 Bob 安全通訊，他們必須先見面交換金鑰。現在，Bob 可以在網站上公開他的公鑰，任何人都可以給他發加密訊息，而只有 Bob 能讀取。

這怎麼可能？答案藏在一個數學問題的不對稱性裡。

2. 定義

RSA 是一種非對稱加密演算法，使用一對數學上相關但不同的金鑰：

公鑰（Public Key）： 可以公開，用於加密資料或驗證簽章
私鑰（Private Key）： 必須保密，用於解密資料或建立簽章

RSA 的安全性基於整數分解問題：給定兩個大質數 p 和 q，計算 n = p × q 很容易，但給定 n，找出 p 和 q 極其困難。

3. 核心直覺：單向函式

乘法 vs 分解

正向（容易）：
p = 61
q = 53
n = p × q = 3233

反向（困難）：
n = 3233
p = ?
q = ?

對於小數字，你可以手算。但當數字變大：

n = 25195908475657893494027183240048398571429282126204
    03202777713783604366202070759555626401852588078440
    69182906412495150821892985591491761845028084891200
    72844992687392807287776735971418347270261896375014
    97182469116507761337985909570009733045974880842840
    17974291006424586918171951187461215151726546322822
    16869987549182422433637259085141865462043576798423
    38718477444792073993423658482382428119816381501067
    48104516603773060562016196762561338441436038339044
    14952634432190114657544454178424020924616515723350
    77870774981712577246796292638635637328991215483143
    81678998850404453640235273819513786365643912120103
    97122822120720357

這是 RSA-2048 的一個模數
目前沒有人能分解它

為什麼分解這麼難

嘗試分解 n = 15：
15 ÷ 2 = 7.5 ✗
15 ÷ 3 = 5 ✓ → 15 = 3 × 5

嘗試分解 n = 2048 位元的數：
需要嘗試大約 √n 個候選質數
√(2^2048) ≈ 2^1024
即使每秒嘗試 10^18 次
也需要 10^290 年
宇宙的年齡才 1.4 × 10^10 年

4. RSA 金鑰是怎麼來的

步驟 1：選擇兩個大質數

p = 一個大質數（例如 1024 位元）
q = 另一個大質數（同樣大小）

步驟 2：計算模數 n

n = p × q

這個 n 是公開的
它的位元數就是「RSA-2048」中的 2048

步驟 3：計算歐拉函數 φ(n)

φ(n) = (p - 1) × (q - 1)

這個值必須保密！
知道 φ(n) 就等於知道 p 和 q

步驟 4：選擇公開指數 e

e 必須滿足：
1 < e < φ(n)
gcd(e, φ(n)) = 1（e 和 φ(n) 互質）

常用值：e = 65537 = 2^16 + 1
為什麼？因為二進位只有兩個 1，計算快

步驟 5：計算私有指數 d

d × e ≡ 1 (mod φ(n))

即：d 是 e 對於 φ(n) 的模逆元
使用擴展歐幾里得算法可以高效計算

金鑰對

公鑰 = (n, e)
私鑰 = (n, d)

實際上私鑰還會儲存 p、q 和一些預計算值來加速運算

5. RSA 加密和解密

加密（使用公鑰）

密文 C = M^e mod n

M = 明文（必須小於 n）
e = 公開指數
n = 模數

解密（使用私鑰）

明文 M = C^d mod n

C = 密文
d = 私有指數
n = 模數

為什麼這能工作？

C^d mod n
= (M^e)^d mod n
= M^(e×d) mod n
= M^(1 + k×φ(n)) mod n  （因為 e×d ≡ 1 mod φ(n)）
= M × M^(k×φ(n)) mod n
= M × (M^φ(n))^k mod n
= M × 1^k mod n         （歐拉定理：M^φ(n) ≡ 1 mod n）
= M

6. 數字範例

# 小數字範例（僅用於理解，實際 RSA 使用大得多的數字）

# 步驟 1：選擇質數
p = 61
q = 53

# 步驟 2：計算 n
n = p * q  # n = 3233

# 步驟 3：計算 φ(n)
phi_n = (p - 1) * (q - 1)  # φ(n) = 60 × 52 = 3120

# 步驟 4：選擇 e
e = 17  # gcd(17, 3120) = 1 ✓

# 步驟 5：計算 d
# d × 17 ≡ 1 (mod 3120)
# d = 2753（可以驗證：17 × 2753 = 46801 = 15 × 3120 + 1）

d = 2753

# 公鑰：(n=3233, e=17)
# 私鑰：(n=3233, d=2753)

# 加密訊息 M = 123
M = 123
C = pow(M, e, n)  # C = 123^17 mod 3233 = 855

# 解密
M_decrypted = pow(C, d, n)  # 855^2753 mod 3233 = 123
print(M_decrypted)  # 123 ✓

7. 為什麼金鑰越來越長

RSA 金鑰長度的演進

年份	推薦長度	原因
1990	512 位元	當時足夠
2000	1024 位元	512 位元被分解
2010	2048 位元	計算能力提升
2020	2048-4096 位元	安全邊際
2030+	至少 3072 位元	NIST 建議

為什麼需要這麼長

對稱金鑰 vs RSA 金鑰的安全等級：

AES-128（128 位元）≈ RSA-3072（3072 位元）
AES-256（256 位元）≈ RSA-15360（15360 位元）

RSA 金鑰需要比對稱金鑰長得多
因為分解問題的複雜度不是指數級的
而是次指數級（數域篩法）

量子威脅

Shor 演算法可以在多項式時間內分解大數
如果大規模量子電腦實現：
- RSA 將完全失效
- 需要遷移到後量子密碼學

目前：
- 實用的量子電腦還不存在
- 但「現在收集，未來解密」是真實威脅
- 敏感資料應該考慮後量子方案

8. RSA 的實際限制

訊息大小限制

RSA 只能加密小於 n 的數
對於 RSA-2048：
最大明文 = 2048 位元 = 256 位元組

實際更小，因為需要填充
OAEP 填充後：256 - 42 = 214 位元組

效能問題

RSA 加密：O(e × log³n)
RSA 解密：O(d × log³n)

因為 d 很大（接近 n），解密很慢
比 AES 慢約 1000 倍

這就是為什麼 RSA 不直接加密資料
而是加密對稱金鑰（混合加密）

填充的重要性

教科書 RSA（不帶填充）是不安全的：

1. 確定性加密
   相同明文 → 相同密文
   攻擊者可以建立對照表

2. 可延展性
   C' = C × 2^e mod n
   解密得到 2M
   攻擊者可以操縱密文

正確做法：使用 OAEP 填充
RSA-OAEP 是語義安全的

9. 程式碼範例

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

# 產生 RSA 金鑰對
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
)
public_key = private_key.public_key()

# 加密（使用公鑰）
message = b"Hello, RSA!"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# 解密（使用私鑰）
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print(f"原文: {message}")
print(f"密文長度: {len(ciphertext)} 位元組")
print(f"解密: {plaintext}")

10. 常見誤區

誤區	現實
「公鑰加密，私鑰解密，所以私鑰更強」	兩個金鑰數學上對等，只是用途不同
「RSA 2048 有 2048 位元安全性」	RSA-2048 約等於 112 位元對稱安全性
「可以用 RSA 加密任意大小的資料」	RSA 只能加密很小的資料，大資料用混合加密
「RSA 比 AES 更安全因為金鑰更長」	它們解決不同問題，無法直接比較
「知道公鑰就能推導私鑰」	需要分解 n，這正是困難所在

11. 本章小結

三點要記住：

RSA 的安全性來自分解的困難。 乘法容易，分解難。這個不對稱性讓公鑰可以公開而不洩漏私鑰。
RSA 金鑰需要比對稱金鑰長得多。 RSA-2048 只提供約 112 位元的安全性，相當於 AES-128 級別。
RSA 不適合直接加密資料。 它有大小限制且速度慢。實際系統使用 RSA 加密對稱金鑰，然後用對稱金鑰加密資料。

12. 下一步

我們理解了 RSA 的數學基礎。但在現代系統中，RSA 的角色正在改變。TLS 1.3 甚至完全移除了 RSA 金鑰交換。

在下一篇文章中，我們將探討：RSA 在現代系統中的真實角色——為什麼不用 RSA 直接加密資料，RSA 在 TLS 中的歷史與退場，以及實際的安全問題。

Luke Sun