> ## Content Index
> Fetch the complete content index at: https://taiwanding.com/llms.txt
> Use this file to discover other available public pages before exploring further.

# 2p2t - watctf 2025
- URL: https://taiwanding.com/2p2t-watctf-2025/
- Published: 2025-09-12T06:20:23.000Z
- Updated: 2025-09-12T06:20:23.000Z
- Author: Kevin Chen
- Tags: #ctf-watctf, #2025

## RSA 加密系統的完整流程

### 1\. 金鑰生成（Key Generation）

```python
# 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\. 加密過程

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

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

```

### 3\. 解密過程

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

```

## 每個數值的角色

| 數值       | 公開/私密 | 用途            |
| -------- | ----- | ------------- |
| **N**    | 🌐 公開 | 模數，加解密都要用     |
| **e**    | 🌐 公開 | 公鑰指數，用來加密     |
| **p, q** | 🔒 私密 | N 的質因數，知道就能破解 |
| **φ(N)** | 🔒 私密 | 用來計算私鑰 d      |
| **d**    | 🔒 私密 | 私鑰，用來解密       |

## 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（安全）

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

```

### 2p2t 題目（不安全）

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

```

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

## 其他常見的 RSA 弱點

### 1\. **小公鑰指數攻擊**

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

```

### 2\. **共模攻擊**

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

```

### 3\. **Wiener 攻擊**

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

```

### 4\. **費馬分解**

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

```

## 實戰檢查清單

看到 RSA 題目時，檢查：

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