# RSA攻击算法指南

## 目录
1. [攻击类型总览](#攻击类型总览)
2. [详细算法说明](#详细算法说明)
3. [参数收集指南](#参数收集指南)
4. [常见CTF题型](#常见ctf题型)

## 攻击类型总览

| 攻击类型 | 适用场景 | 所需参数 | 难度 |
|---------|---------|---------|------|
| factor | n在factordb数据库中 | n, (可选)e, c | 简单 |
| small_e | 明文很短，e很小 | n, e, c | 简单 |
| common_modulus | 相同n，不同e加密同一明文 | n, e1, c1, e2, c2 | 中等 |
| d_leak | 私钥d泄露 | n, d, c | 简单 |
| wiener | d过小（d < n^0.25） | n, e, (可选)c | 中等 |
| necpq | 已分解完成，已知p,q | p, q, e, c | 简单 |
| crt | 广播攻击，多组不同n | c_list, n_list, e | 困难 |
| dp_leak | dp泄露（d mod (p-1)） | n, e, c, dp | 困难 |
| rabin | Rabin密码系统（e=2） | p, q, c | 中等 |
| e_power_two | e为2的幂次方 | n, e, c | 困难 |
| non_coprime_e | e与phi不互素 | n, e, c, p, q | 中等 |

## 详细算法说明

### 1. factordb分解 (factor)

**原理**：利用factordb.com在线数据库查询n的因子分解结果。

**API说明**：
```
API地址: https://factordb.com/api?query=<n>
返回格式: JSON
  - status: 分解状态
    * FF: Fully Factored (完全分解)
    * CF: Composite Factor (部分分解)
    * P: Prime (是素数)
    * U: Unknown (未知)
  - factors: 因子列表 [[factor, exp], ...]
```

**适用条件**：
- n已经在factordb数据库中（大多数CTF题目使用的n都在库中）
- 适用于任意大小的n（只要数据库中有记录）

**示例**：
```bash
python scripts/rsa_solver.py factor --n 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216 --e 3 --c 1271605856918912462699983859985905842276423867777030740152682859600890050685898590999105752584595630467013299575519203653123853137178437196621237640679243779749827039090719670714605250972696434557873580368129958503762635734086800950594749148977042336639587689829975573162748323567814294896446597830609375
```

**注意事项**：
- 需要网络连接访问factordb.com
- 如果n不在数据库中，会返回失败
- 对于超大n，可能需要较长的查询时间

### 2. 低指数攻击 (small_e)

**原理**：当e很小且m^e < n时，可以直接对c开e次方根得到m。

**数学基础**：
```
c = m^e mod n
如果 m^e < n，则 c = m^e
因此 m = c^(1/e)
```

**适用条件**：
- e很小（通常e=3）
- 明文m很短，使得m^e < n

**示例**：
```bash
python scripts/rsa_solver.py small_e --n 123456789 --e 3 --c 987654321
```

### 3. 共模攻击 (common_modulus)

**原理**：当同一明文用相同的n但不同的e加密时，可以利用扩展欧几里得算法求解。

**数学基础**：
```
c1 = m^e1 mod n
c2 = m^e2 mod n
e1和e2互质，可找到s1, s2使得：e1*s1 + e2*s2 = 1
则：m = c1^s1 * c2^s2 mod n
```

**适用条件**：
- 两次加密使用相同的n
- e1和e2互质（gcd(e1, e2) = 1）
- 加密的是同一明文

**示例**：
```bash
python scripts/rsa_solver.py common_modulus --n 123456789 --e1 3 --c1 111 --e2 5 --c2 222
```

### 4. 私钥泄露攻击 (d_leak)

**原理**：直接使用泄露的私钥d解密。

**数学基础**：
```
m = c^d mod n
```

**适用条件**：
- 已知私钥d

**示例**：
```bash
python scripts/rsa_solver.py d_leak --n 123456789 --d 123456789 --c 987654321
```

### 5. Wiener攻击 (wiener)

**原理**：当d很小时（d < n^0.25），可以利用连分数展开找到d。

**数学基础**：
```
e*d ≡ 1 mod φ(n)
k/d 是 e/φ(n) 的连分数逼近
通过测试k/d的值，可以恢复d
```

**适用条件**：
- d < n^0.25
- 通常出现在e很大，但d很小的情况

**示例**：
```bash
python scripts/rsa_solver.py wiener --n 905016087923017239 --e 3 --c 123456789
```

### 6. 已知p,q解密 (necpq)

**原理**：分解完成，直接计算φ(n)和d进行解密。

**数学基础**：
```
φ(n) = (p-1)*(q-1)
d = e^(-1) mod φ(n)
m = c^d mod n
```

**适用条件**：
- 已知p和q
- e和φ(n)互质

**示例**：
```bash
python scripts/rsa_solver.py necpq --p 61 --q 53 --e 17 --c 2790
```

### 7. 中国剩余定理攻击 (crt)

**原理**：当同一明文用不同的n和相同的e加密时，可以使用CRT合并求解。

**数学基础**：
```
c1 = m^e mod n1
c2 = m^e mod n2
...
ck = m^e mod nk

使用CRT计算：C = m^e mod N，其中N = n1*n2*...*nk
然后：m = C^(1/e)

需要：k >= e
```

**适用条件**：
- 同一明文用不同的n加密
- 使用相同的e
- 至少有e组密文

**示例**：
```bash
python scripts/rsa_solver.py crt --c-list "111,222,333" --n-list "1001,2002,3003" --e 3
```

### 8. dp泄露攻击 (dp_leak)

**原理**：已知dp = d mod (p-1)时，可以恢复p。

**数学基础**：
```
dp = d mod (p-1)
存在k使得：e*dp - 1 = k*(p-1)
因此：p = (e*dp - 1)/k + 1
通过枚举k来找到正确的p
```

**适用条件**：
- 已知dp = d mod (p-1)
- 1 <= k < e

**示例**：
```bash
python scripts/rsa_solver.py dp_leak --n 123456789 --e 65537 --c 987654321 --dp 12345
```

### 9. Rabin密码系统 (rabin)

**原理**：Rabin密码系统使用e=2，解密得到4个可能的明文。

**数学基础**：
```
c = m^2 mod n
mp = c^((p+1)/4) mod p
mq = c^((q+1)/4) mod q

使用CRT计算四个解：
m1 = (inv_p*p*mq + inv_q*q*mp) mod n
m2 = n - m1
m3 = (inv_p*p*mq - inv_q*q*mp) mod n
m4 = n - m3
```

**适用条件**：
- e = 2
- p ≡ 3 mod 4
- q ≡ 3 mod 4

**示例**：
```bash
python scripts/rsa_solver.py rabin --p 7 --q 11 --c 23
```

### 10. e为2的幂攻击 (e_power_two)

**原理**：当e = 2^k时，可以连续进行开方运算。

**数学基础**：
```
e = 2^k
c = m^e mod n
连续开方k次，找到可读的明文
```

**适用条件**：
- e是2的幂次方（2, 4, 8, 16...）

**示例**：
```bash
python scripts/rsa_solver.py e_power_two --n 123456789 --e 16 --c 987654321
```

### 11. e与phi不互素 (non_coprime_e)

**原理**：当gcd(e, φ(n)) = g > 1时，可以使用修正算法解密。

**数学基础**：
```
g = gcd(e, φ(n))
计算：d' = (e/g)^(-1) mod φ(n)
m2 = c^d' mod n
m = m2^(1/g)
```

**适用条件**：
- 已知p和q
- gcd(e, φ(n)) > 1

**示例**：
```bash
python scripts/rsa_solver.py non_coprime_e --n 123456789 --e 4 --c 987654321 --p 111 --q 1113
```

## 参数收集指南

### 从题目描述中提取

1. **n（模数）**：通常直接给出，或从公钥文件中提取
2. **e（公钥指数）**：通常是65537，也可能给出其他值
3. **c（密文）**：加密后的数值
4. **p, q（素数因子）**：可能部分泄露或通过其他方式得到
5. **d（私钥）**：可能直接泄露
6. **dp, dq**：CRT参数泄露

### 从公钥文件提取

PEM格式公钥：
```bash
openssl rsa -pubin -in public.pem -text -modulus
```

从证书提取：
```bash
openssl x509 -in cert.pem -modulus
```

### Python脚本提取

```python
from Crypto.PublicKey import RSA

# 读取PEM格式公钥
with open('public.pem', 'r') as f:
    key = RSA.import_key(f.read())
    n = key.n
    e = key.e
    print(f"n = {n}")
    print(f"e = {e}")
```

## 常见CTF题型

### 类型1：低指数广播
**特征**：给出多组(n, e, c)，e很小，n很大
**解法**：使用crt攻击

### 类型2：大e小d
**特征**：e很大，说明d可能很小
**解法**：使用Wiener攻击

### 类型3：共享模数
**特征**：相同的n，不同的e
**解法**：使用共模攻击

### 类型4：部分信息泄露
**特征**：泄露了p的部分位，或dp, dq等
**解法**：使用dp_leak攻击或Coppersmith攻击

### 类型5：已知因子
**特征**：题目直接给出p和q
**解法**：使用necpq直接解密

### 类型6：e=2或e=2^k
**特征**：e为2或2的幂
**解法**：使用rabin或e_power_two攻击

## 注意事项

1. **参数验证**：确保所有参数都是有效的整数
2. **输入清理**：脚本会自动处理空格和换行符
3. **明文识别**：脚本会尝试UTF-8解码，失败则输出十六进制
4. **性能考虑**：某些攻击（如factor）可能需要较长时间
5. **错误处理**：仔细阅读错误信息，可能是参数不满足攻击条件