RSA-批量单字符解密

## 背景

在 CTF 密码学题目中，偶尔会遇到一种 RSA 变体：明文消息的**每一个字符**都被单独取出，分别用同一个公钥加密后得到密文列表。题目一般直接给出密文列表、公钥 $(n, e)$ 以及 $n$ 的两个素因子 $p, q$（或 $n$ 很小，可以直接分解）。本文从一个具体脚本出发，分析这种加密方式为何**本质脆弱**，并给出统一的批量解密方案。

## 原始脚本

[hide]

```python
import libnum
from Crypto.Util.number import long_to_bytes

list1 = [704796792, 752211152, 274704164, 18414022, 368270835,
         483295235, 263072905, 459788476, 483295235, 459788476,
         663551792, 475206804, 459788476, 428313374, 475206804,
         459788476, 425392137, 704796792, 458265677, 341524652,
         483295235, 534149509, 425392137, 428313374, 425392137,
         341524652, 458265677, 263072905, 483295235, 828509797,
         341524652, 425392137, 475206804, 428313374, 483295235,
         475206804, 459788476, 306220148]

flag = ""
n = 920139713
q = 18443
p = 49891
e = 19

for i in list1:
    c = i
    d = libnum.invmod(e, (p - 1) * (q - 1))
    m = pow(c, d, n)
    string = long_to_bytes(m)
    flag += string.decode()

print(flag)
```

[/hide]

## 逐行解析

### 公钥与私钥参数

```python
n = 920139713      # 模数，约 10^9 量级
p = 49891          # 素因子 1
q = 18443          # 素因子 2
e = 19             # 公钥指数
```

验证：$p \times q = 49891 \times 18443 = 920139713 = n$，数量级仅约 $10^9$。对现代计算机而言，这个 $n$ 可以在毫秒级时间内被分解（即使用 Pollard-Rho 或试除法）。这是该类题目的核心突破口。

### 密文列表

`list1` 包含 38 个整数，每一个都对应明文消息的一个字符独立加密后的密文值。可以观察到列表中部分值重复出现，例如 `483295235` 出现 6 次，`459788476` 出现 7 次——这恰好对应明文中相同字符出现多次的情况。

### 解密循环

[hide]

```python
for i in list1:
    d = libnum.invmod(e, (p - 1) * (q - 1))   # 计算私钥指数
    m = pow(c, d, n)                            # RSA 解密
    string = long_to_bytes(m)                   # 大整数 → 字节串
    flag += string.decode()                     # 拼接为最终明文
```

[/hide]
循环体中的 `d` 计算本可以提前到循环之外——因为 $p, q, e$ 均不变，$d$ 是固定的。将其放在循环内部属于冗余计算，但不影响正确性。

## 为什么单字符 RSA 是本质脆弱的

### 1. 模数太小，可直接分解

RSA 的安全性建立在「大整数分解困难」这一假设之上。生产环境中 $n$ 通常为 2048 位（约 $10^{617}$），而本题的 $n$ 只有 $10^9$ 量级，任何编程语言的标准库都能瞬间分解。

一般地，若题目仅给出 $n, e$ 而未给出 $p, q$，对于小模数可以直接使用以下工具分解：

| 工具                                 | 说明                 |
| ------------------------------------ | -------------------- |
| [factordb.com](http://factordb.com/) | 在线大整数分解数据库 |
| `sympy.factorint(n)`                 | Python 符号计算库    |
| `yafu`                               | 经典大整数分解工具   |
| `sagemath` 的 `factor(n)`            | Sage 数学平台        |

### 2. 退化为单表替换密码

这是更深层的漏洞。对于给定的公钥 $(n, e)$，同一个明文 $m$ 永远产生相同的密文 $c = m^e \bmod n$。因此：

$$
m_1 = m_2 \quad\Longrightarrow\quad c_1 = c_2
$$

这就意味着单字符 RSA **退化为一个确定性的单表替换密码（monoalphabetic substitution cipher）**。攻击者甚至不需要分解 $n$——只需在已知的明文-密文字典下做查表替换即可。例如若通过某条已知明文推测出字符 `a` 对应密文 $c_a$，那么列表中所有值为 $c_a$ 的项都可替换为 `a`。

这与经典的凯撒密码、简单替换密码共享相同的弱点：**频率分析**。在英文中，`e` 出现频率最高；本题中 `459788476` 出现 7 次（频率约 18.4%），很可能是英文最常见的字母。

### 3. 对称性攻击与信息泄露

除了频率分析，攻击者还可以利用以下信息：

- **分组长度泄露**：密文列表长度 = 明文字符数，直接暴露明文长度。
- **位置对应保留**：第 $i$ 个密文必然对应第 $i$ 个明文字符，语义结构（如空格位置、常见前后缀）完全保留。
- **无填充（No Padding）**：标准 RSA 会在加密前对明文做填充（如 OAEP），用于随机化和抵御选择密文攻击。但单字符场景下 $m$ 极小（通常 $\leq 255$），填充根本无从谈起。

### 4. 为什么题目仍然出现

尽管存在上述诸多弱点，单字符 RSA 仍常见于：

1. **入门级 CTF 赛题**：训练学生对 RSA 数学原理的理解（如私钥计算、模逆运算），无需攻克难度较高的 Coppersmith 或 Boneh-Durfee 等攻击。
2. **密码学课后练习**：以最直观的方式展示「为何单纯 RSA 不安全」。
3. **逆向/混淆题目**：将某种加密算法包装为「自研算法」，实际底层仍是单字符 RSA，考察识别能力。

## 统一解密脚本

将原脚本优化为一次性计算私钥、一次遍历完成解密的版本，并增加无 $p, q$ 时的自动分解分支。
[hide]

```python
import libnum
from Crypto.Util.number import long_to_bytes

def decrypt_single_char_rsa(cipher_list, n, e, p=None, q=None):
    """
    批量解密单字符 RSA 密文。

参数:
        cipher_list : list[int]  密文列表
        n           : int        模数
        e           : int        公钥指数
        p, q        : int|None   素数因子，若为 None 则尝试自动分解 (小 n)

返回:
        str  解密后的明文字符串
    """
    # 1. 如果未提供 p, q，尝试分解 n
    if p is None or q is None:
        try:
            from sympy import factorint
            factors = factorint(n)
            if len(factors) == 2:
                p, q = list(factors.keys())
            else:
                raise ValueError(f"n={n} 不是两个素数的乘积: {factors}")
        except ImportError:
            raise ImportError(
                "未提供 p, q，需要安装 sympy 以自动分解 n: pip install sympy"
            )

assert p * q == n, f"p*q={p * q} != n={n}"

# 2. 一次性计算私钥指数 d
    phi = (p - 1) * (q - 1)
    d = libnum.invmod(e, phi)
    print(f"[+] p = {p}, q = {q}")
    print(f"[+] phi(n) = {phi}")
    print(f"[+] d = {d}")

# 3. 批量解密并拼接
    flag_chars = []
    for i, c in enumerate(cipher_list):
        m = pow(c, d, n)
        ch = long_to_bytes(m).decode(errors="replace")
        flag_chars.append(ch)
        print(f"    [{i:02d}] c = {c:>10d}  →  m = {m:>3d}  →  '{ch}'")

flag = "".join(flag_chars)
    print(f"\n[+] Flag: {flag}")
    return flag

if __name__ == "__main__":
    cipher_list = [704796792, 752211152, 274704164, 18414022, 368270835,
                   483295235, 263072905, 459788476, 483295235, 459788476,
                   663551792, 475206804, 459788476, 428313374, 475206804,
                   459788476, 425392137, 704796792, 458265677, 341524652,
                   483295235, 534149509, 425392137, 428313374, 425392137,
                   341524652, 458265677, 263072905, 483295235, 828509797,
                   341524652, 425392137, 475206804, 428313374, 483295235,
                   475206804, 459788476, 306220148]

n = 920139713
    p = 49891
    q = 18443
    e = 19

decrypt_single_char_rsa(cipher_list, n, e, p, q)
```

[/hide]
脚本提供了两种使用方式：

1. **已知 $p, q$**：直接传入即可批量解密。
2. **未知 $p, q$ 但 $n$ 很小**：脚本自动调用 `sympy.factorint` 分解 $n$ 后继续解密。

运行输出示例：

```
[+] p = 49891, q = 18443
[+] phi(n) = 920071380
[+] d = 96849619
    [00] c =  704796792  →  m = 102  →  'f'
    [01] c =  752211152  →  m = 108  →  'l'
    [02] c =  274704164  →  m =  97  →  'a'
    [03] c =   18414022  →  m = 103  →  'g'
    [04] c =  368270835  →  m = 123  →  '{'
    ... (后续省略) ...

[+] Flag: flag{***}
```

## 总结

| 攻击方法               | 难度       | 适用条件                          |
| ---------------------- | ---------- | --------------------------------- |
| 直接分解$n$            | ★☆☆☆☆ | $n$ 很小（$\leq 2^{64}$）         |
| 频率分析 / 单表替换    | ★☆☆☆☆ | 明文为自然语言，无需任何 RSA 知识 |
| 计算私钥$d$ 后批量解密 | ★★☆☆☆ | 本题解法，已知或已分解出$p, q$    |

单字符 RSA 本质上不是一个安全的加密方案，它只是将 RSA 作为一种混淆手段套用在单个字节上。理解了这一本质后，任何依赖 $n$ 过小、填充缺失或重复加密同类数据的 RSA 变体都可以用统一思路快速求解。

## 参考文献

1. Rivest, R., Shamir, A., and Adleman, L. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." *Communications of the ACM*, 1978.
2. Menezes, A., van Oorschot, P., and Vanstone, S. *Handbook of Applied Cryptography*. CRC Press, 1996.

AI摘要

本文分析了CTF中单字符RSA的脆弱性。因模数小易分解且无填充，其退化为单表替换。文章给出了优化脚本，通过计算私钥d批量解密，并支持自动分解n。

背景

在 CTF 密码学题目中，偶尔会遇到一种 RSA 变体：明文消息的每一个字符都被单独取出，分别用同一个公钥加密后得到密文列表。题目一般直接给出密文列表、公钥 $(n, e)$ 以及 $n$ 的两个素因子 $p, q$（或 $n$ 很小，可以直接分解）。本文从一个具体脚本出发，分析这种加密方式为何本质脆弱，并给出统一的批量解密方案。

原始脚本

此处内容需要评论回复后（审核通过）方可阅读。

逐行解析

公钥与私钥参数

n = 920139713      # 模数，约 10^9 量级
p = 49891          # 素因子 1
q = 18443          # 素因子 2
e = 19             # 公钥指数

密文列表

list1 包含 38 个整数，每一个都对应明文消息的一个字符独立加密后的密文值。可以观察到列表中部分值重复出现，例如 483295235 出现 6 次，459788476 出现 7 次——这恰好对应明文中相同字符出现多次的情况。

解密循环

此处内容需要评论回复后（审核通过）方可阅读。

循环体中的 d 计算本可以提前到循环之外——因为 $p, q, e$ 均不变，$d$ 是固定的。将其放在循环内部属于冗余计算，但不影响正确性。

为什么单字符 RSA 是本质脆弱的

1. 模数太小，可直接分解

一般地，若题目仅给出 $n, e$ 而未给出 $p, q$，对于小模数可以直接使用以下工具分解：

工具	说明
factordb.com	在线大整数分解数据库
`sympy.factorint(n)`	Python 符号计算库
`yafu`	经典大整数分解工具
`sagemath` 的 `factor(n)`	Sage 数学平台

2. 退化为单表替换密码

这是更深层的漏洞。对于给定的公钥 $(n, e)$，同一个明文 $m$ 永远产生相同的密文 $c = m^e \bmod n$。因此：

$$ m_1 = m_2 \quad\Longrightarrow\quad c_1 = c_2 $$

这就意味着单字符 RSA 退化为一个确定性的单表替换密码（monoalphabetic substitution cipher）。攻击者甚至不需要分解 $n$——只需在已知的明文-密文字典下做查表替换即可。例如若通过某条已知明文推测出字符 a 对应密文 $c_a$，那么列表中所有值为 $c_a$ 的项都可替换为 a。

这与经典的凯撒密码、简单替换密码共享相同的弱点：频率分析。在英文中，e 出现频率最高；本题中 459788476 出现 7 次（频率约 18.4%），很可能是英文最常见的字母。

3. 对称性攻击与信息泄露

除了频率分析，攻击者还可以利用以下信息：

分组长度泄露：密文列表长度 = 明文字符数，直接暴露明文长度。
位置对应保留：第 $i$ 个密文必然对应第 $i$ 个明文字符，语义结构（如空格位置、常见前后缀）完全保留。
无填充（No Padding）：标准 RSA 会在加密前对明文做填充（如 OAEP），用于随机化和抵御选择密文攻击。但单字符场景下 $m$ 极小（通常 $\leq 255$），填充根本无从谈起。

4. 为什么题目仍然出现

尽管存在上述诸多弱点，单字符 RSA 仍常见于：

入门级 CTF 赛题：训练学生对 RSA 数学原理的理解（如私钥计算、模逆运算），无需攻克难度较高的 Coppersmith 或 Boneh-Durfee 等攻击。
密码学课后练习：以最直观的方式展示「为何单纯 RSA 不安全」。
逆向/混淆题目：将某种加密算法包装为「自研算法」，实际底层仍是单字符 RSA，考察识别能力。

统一解密脚本

将原脚本优化为一次性计算私钥、一次遍历完成解密的版本，并增加无 $p, q$ 时的自动分解分支。

此处内容需要评论回复后（审核通过）方可阅读。

脚本提供了两种使用方式：

已知 $p, q$：直接传入即可批量解密。
未知 $p, q$ 但 $n$ 很小：脚本自动调用 sympy.factorint 分解 $n$ 后继续解密。

运行输出示例：

[+] p = 49891, q = 18443
[+] phi(n) = 920071380
[+] d = 96849619
    [00] c =  704796792  →  m = 102  →  'f'
    [01] c =  752211152  →  m = 108  →  'l'
    [02] c =  274704164  →  m =  97  →  'a'
    [03] c =   18414022  →  m = 103  →  'g'
    [04] c =  368270835  →  m = 123  →  '{'
    ... (后续省略) ...

[+] Flag: flag{***}

总结

攻击方法	难度	适用条件
直接分解$n$	★☆☆☆☆	$n$ 很小（$\leq 2^{64}$）
频率分析 / 单表替换	★☆☆☆☆	明文为自然语言，无需任何 RSA 知识
计算私钥$d$ 后批量解密	★★☆☆☆	本题解法，已知或已分解出$p, q$

参考文献

Rivest, R., Shamir, A., and Adleman, L. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." Communications of the ACM, 1978.
Menezes, A., van Oorschot, P., and Vanstone, S. Handbook of Applied Cryptography. CRC Press, 1996.

投币支持一下吧

END

👤 作者 Monarchdos

📄 标题 RSA-批量单字符解密

🔗 地址 https://ayfre.com/39.html

RSA-批量单字符解密

背景

原始脚本