2p2t - watctf 2025

RSA 加密系統的完整流程

1. 金鑰生成（Key Generation）

# Step 1: 選擇兩個大質數
p = 大質數1
q = 大質數2

# Step 2: 計算 N（公開）
N = p × q   # 這個 N 會公開，但 p 和 q 要保密！

# Step 3: 計算歐拉函數 φ(N)
φ(N) = (p-1) × (q-1)   # 這個值要保密

# Step 4: 選擇公鑰指數 e（公開）
e = 65537   # 通常選 65537，因為它是質數且二進位只有兩個 1

# Step 5: 計算私鑰 d（保密）
d = e的模反元素 mod φ(N)
# 即：e × d ≡ 1 (mod φ(N))

2. 加密過程

明文: M (例如: "watctf{...}")
明文轉數字: m = bytes_to_long(M)

密文: c = m^e mod N   # 用公鑰 (N, e) 加密

3. 解密過程

密文: c
明文: m = c^d mod N   # 用私鑰 d 解密
明文轉文字: M = long_to_bytes(m)

每個數值的角色

RSA 的安全性基礎

核心假設：大數分解很困難

給你 N = 15
你能快速知道 N = 3 × 5

但如果 N = 1234567890123456789012345678901234567890...（1024位元）
要分解成 p × q 可能要幾千年！

攻擊流程圖

知道 N, e, ct
    ↓
如果能分解 N = p × q  ← 這步驟應該很困難！
    ↓
計算 φ(N) = (p-1)(q-1)
    ↓
計算 d = e^(-1) mod φ(N)
    ↓
解密: m = ct^d mod N
    ↓
得到 flag！

為什麼 2p2t 題目不安全？

正常 RSA（安全）

p = random(512 bits)  # 完全隨機
q = random(512 bits)  # 完全隨機
N = p × q            # 無法從 N 推出 p 或 q

2p2t 題目（不安全）

p = random(512 bits)
q = nextPrime(2×p)    # q ≈ 2p ← 致命關係！
N = p × q ≈ 2p²      # N 有特殊結構

因為 N ≈ 2p²，所以 p ≈ √(N/2) 我們可以直接算出 p！

其他常見的 RSA 弱點

1. 小公鑰指數攻擊

e = 3  # 太小了！
如果 m^3 < N，則 ct = m^3（沒有 mod）
→ m = ct^(1/3)

2. 共模攻擊

同一個 m，用兩個不同的 e 加密：
c1 = m^e1 mod N
c2 = m^e2 mod N
如果 gcd(e1, e2) = 1 → 可以解出 m

3. Wiener 攻擊

如果 d < N^0.25  # d 太小
可以用連分數攻擊

4. 費馬分解

如果 |p - q| 很小  # p 和 q 太接近
可以從 √N 附近找到 p 和 q

實戰檢查清單

看到 RSA 題目時，檢查：

1. ✅ N 能直接分解嗎？（factordb.com）
2. ✅ e 是否太小？（e = 3, 5, ...）
3. ✅ p 和 q 有特殊關係嗎？（像這題）
4. ✅ 多個加密使用相同 N？
5. ✅ 給了多組相關的加密？