背景
前面我们学的攻击手段（共模攻击、dp 泄露）都需要"额外泄露"一些信息才能下手。
但现实里很多新手 RSA 题目根本不需要任何"花活"——只要 n 选得太小，直接把 n 分解掉，私钥就到手了。
RSA 的安全性完全建立在大整数分解的困难性上：
- 公钥 (e, n) 是公开的，n = p × q
- 只要攻击者能把 n 拆回 p 和 q，就能算出 φ(n) = (p-1)(q-1)
- 有了 φ(n)，私钥 d = e⁻¹ mod φ(n) 就能直接算出来
- 于是任意密文都能解密
当 n 足够大（如 2048 位）时，分解 n 在算力上不可行；但当 n 很小（如几十位、甚至 9~10 位十进制数）时，用最朴素的"试除法"就能秒分解。
什么是"逐字符加密"及其弱点
很多题目为了"看起来密文很长"，会把明文的每一个字符单独加密，得到一长串密文：
明文 "flag" → [加密('f'), 加密('l'), 加密('a'), 加密('g')]这其实就是 RSA 的ECB 模式（无填充），它有两个致命弱点：
- 明文空间极小：每个明文块只是一个字符，ASCII 范围 32~126，一共才 95 种可能。如果题目再提示"只有数字和小写字母"，那明文只有 36 种可能。
- 相同明文 → 相同密文：没有随机填充，同一个字符每次加密结果都一样。密文里只要出现重复值，就说明明文里有重复字符，泄露了模式。
这两个弱点带来两种攻击姿势：
- 方法一（分解 n）：把小 n 分解掉，求出 d，对每个密文
m = pow(c, d, n)解密，再chr(m)还原字符。 - 方法二（暴力查表，无需分解 n）：既然明文只有几十种可能，干脆把每个候选字符 m 都加密一次
c = pow(m, e, n)，建立c → m的反查表，然后对着密文逐个反查即可。连 n 都不用分解！
当明文空间远小于密钥空间时，"加密"变成了一个可逆的查表游戏——这正是无填充逐字符加密的悲哀。
简单例子
我们用p=3, q=11来演示，数字小到可以在草稿纸上算完。
生成密钥
- n = p × q = 3 × 11 =33
- φ(n) = (p-1)(q-1) = 2 × 10 =20
- 选 e = 3（gcd(3, 20) = 1 ✓），公钥 (e, n) = (3, 33)
- 求私钥 d：3 × d ≡ 1 (mod 20)
- 3 × 7 = 21 = 20 + 1 ≡ 1 ✓
- 所以d = 7，私钥 (d, n) = (7, 33)
逐字符加密
为方便手算，我们用"字母表位置"给明文编号：a=1, b=2, c=3, …
要加密消息“cab”→ 明文序列 [3, 1, 2]
加密公式 c = mᵉ mod n = m³ mod 33：
| 明文 m | 计算 m³ mod 33 | 密文 c |
|---|---|---|
| 3 ( c ) | 3³ = 27 | 27 |
| 1 ( a ) | 1³ = 1 | 1 |
| 2 ( b ) | 2³ = 8 | 8 |
攻击者最终只看到：n=33, e=3，以及密文序列[27, 1, 8]。
攻击一：分解 n 求私钥
n=33 小到一眼可分：33 = 3 × 11
- φ(n) = (3-1)*(11-1)=20
- e*d≡1 mod φ(n)推出 d = 7
解密 m = cᵈ mod n = c⁷ mod 33：
密文 27：27 ≡ -6 (mod 33)
- (-6)² = 36 ≡ 3
- (-6)⁴ ≡ 3² = 9
- (-6)⁷ = (-6)⁴ × (-6)² × (-6) = 9 × 3 × (-6) = -162 ≡ -162 + 5×33 = 3
- → m = 3 →‘c’
密文 1：1⁷ = 1 → m = 1 →‘a’
密文 8：
- 8² = 64 ≡ 64 - 33 = 31
- 8⁴ ≡ 31² = 961 = 29×33 + 4 ≡ 4
- 8⁷ = 8⁴ × 8² × 8 = 4 × 31 × 8 = 992 = 30×33 + 2 ≡ 2
- → m = 2 →‘b’
恢复明文序列 [3, 1, 2] →“cab”✓ 闭环成功！
攻击二：查表法（不分解 n）
明文空间只有 az（126）共 26 种，干脆全部加密一遍建反查表：
m=1 → c=1 m=2 → c=8 m=3 → c=27 ...拿到密文 [27, 1, 8] 直接反查：27→3©、1→1(a)、8→2(b) →“cab”✓
整个过程没有用到 p、q、d，只用了公开的 e 和 n。可见"逐字符无填充"比"n 太小"还要致命——即使 n 大到分不动，只要明文空间小，查表法照样秒杀。
代码实现
# ============================================================# RSA 小 n 分解 + 逐字符加密（手算例子）# ============================================================## 场景: p=3, q=11, n=33, e=3, d=7# 明文用字母表位置 a=1..z=26 编码，逐字符加密# 攻击:# 方法一: 分解 n=33 → 求 d → 解密每个密文# 方法二: 暴力查表，把 1..26 全加密一遍反查（无需分解 n）# ============================================================deffactor_by_trial(n):"""试除法分解小 n，返回 (p, q)"""i=2whilei*i<=n:ifn%i==0:returni,n//i i+=1raiseValueError("n 是素数，无法分解为两个 >1 的因子")defmain():# ---- 公钥 ----n=33e=3# ---- 原始明文 "cab"，用字母表位置编码 ----plain="cab"ms=[ord(ch)-96forchinplain]# a=1, b=2, c=3print(f"明文:{plain}-> 明文序列{ms}")# ---- 加密（逐字符）----cs=[pow(m,e,n)forminms]print(f"密文序列:{cs}")print()# ============ 方法一：分解 n 求私钥 ============print("=== 方法一：分解 n 求私钥 ===")p,q=factor_by_trial(n)print(f"分解 n={n}={p}×{q}")phi=(p-1)*(q-1)d=pow(e,-1,phi)print(f"φ(n) ={phi}, d ={d}")recovered1=''.join(chr(pow(c,d,n)+96)forcincs)print(f"解密结果:{recovered1}")print()# ============ 方法二：暴力查表（不分解 n）============print("=== 方法二：暴力查表（不分解 n）===")table={pow(m,e,n):mforminrange(1,27)}# c -> mrecovered2=''.join(chr(table[c]+96)forcincs)print(f"解密结果:{recovered2}")if__name__=="__main__":main()运行结果：
明文: cab ->明文序列[3,1,2]密文序列:[27,1,8]===方法一：分解 n 求私钥===分解n=33=3×11φ(n)=20, d=7解密结果: cab===方法二：暴力查表（不分解 n）===解密结果: cab作业：RSA roll
题目
https://ctf2.dasctf.com/dashboard/practice/b9bbb32f-f186-458f-b90b-12440c0f6aea?tab=challenges&challenge=542e42ea-2a5c-44c8-8801-9b30b7e1a973
RSA rollrollroll Only number and a-z don't use editor which MS providedata.txt：
{920139713,19} 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解题过程
第一步：读懂题目格式
{920139713, 19}就是公钥(n, e) = (920139713, 19)- 下面一长串数字，每行一个，是密文序列（逐字符加密的结果）
- 提示解读：
- “Only number and a-z”：flag 内容只含数字和小写字母 → 明文空间极小，非常适合查表
- “roll roll roll”：密文逐行"滚动"排列；仔细看会发现有大量重复值（如
459788476出现了 6 次），这正是无填充逐字符加密的指纹——同一个字符加密结果必然相同 - “don’t use editor which MS provide”：暗示题目足够简单，甚至不需要打开微软家的编辑器写复杂代码，靠计算/查表即可拿下
第二步：观察密文规律
把出现过的密文和它在序列里出现的次数统计一下，会发现只有 17 种不同的密文，对应 17 个不同字符，而密文总数有 38 个——重复率极高，坐实了"逐字符无填充加密"。
第三步：方法一 —— 分解 n 求私钥
n = 920139713 只有 9 位十进制，用最朴素的试除法就能秒分：
- 920139713 = 18443 × 49891
- φ(n) = (18443-1)(49891-1) = 18442 × 49890 =920071380
- d = e⁻¹ mod φ(n) = 19⁻¹ mod 920071380 =96849619
- 验证：19 × 96849619 mod 920071380 = 1 ✓
然后对每个密文m = pow(c, d, n)，再chr(m)还原字符。
第四步：方法二 —— 暴力查表（无需分解 n）
明文只是可打印 ASCII（数字、小写字母，外加flag{}几个符号），范围 32~126，共 95 种。
预计算c = pow(m, e, n)for m in 32…126，建c → m反查表，再对 38 个密文逐个反查即可，全程不需要 p、q、d。
两种方法殊途同归，得到同一段明文。
具体实现代码
# ============================================================# 作业4: RSA roll —— 小 n 分解 + 逐字符加密# ============================================================## 已知: n=920139713, e=19, 以及一串逐字符加密的密文# 目标: 恢复明文 flag## 思路:# 方法一: n 只有 9 位，试除法分解 → 求 d → 逐个解密 chr(pow(c,d,n))# 方法二: 明文空间极小，把 32~126 全加密一遍建反查表，逐个反查# ============================================================deffactor_by_trial(n):"""试除法分解小 n，返回 (p, q)"""i=2whilei*i<=n:ifn%i==0:returni,n//i i+=1raiseValueError("n 是素数，无法分解为两个 >1 的因子")defmain():# ---- 题目参数 ----n=920139713e=19cs=[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,]print("=== 作业4: RSA roll ===")print(f"公钥 (n, e) = ({n},{e})")print(f"密文个数:{len(cs)}个，不同密文:{len(set(cs))}种")print()# ============ 方法一：分解 n 求私钥 ============print("=== 方法一：分解 n 求私钥 ===")p,q=factor_by_trial(n)print(f"分解 n ={p}×{q}")print(f"验证 p*q == n ?{p*q==n}")phi=(p-1)*(q-1)d=pow(e,-1,phi)print(f"φ(n) ={phi}")print(f"d = e^(-1) mod φ ={d}")print(f"验证 (e*d) mod φ ={(e*d)%phi}")msg1=''.join(chr(pow(c,d,n))forcincs)print(f"解密结果:{msg1}")print()# ============ 方法二：暴力查表（不分解 n）============print("=== 方法二：暴力查表（不分解 n）===")table={pow(m,e,n):mforminrange(32,127)}# c -> mmsg2=''.join(chr(table[c])forcincs)print(f"解密结果:{msg2}")print()# ============ 顺带打印 密文 -> 字符 映射 ============print("=== 出现过的 密文 -> 字符 映射 ===")forcindict.fromkeys(cs):print(f"{c}->{repr(chr(table[c]))}")if__name__=="__main__":main()运行结果：
===作业4: RSA roll===公钥(n, e)=(920139713,19)密文个数:38个，不同密文:17种===方法一：分解 n 求私钥===分解 n=18443×49891验证 p*q==n ? True φ(n)=920071380d=e^(-1)mod φ=96849619验证(e*d)mod φ=1解密结果: flag{13212je2ue28fy71w8u87y31r78eu1e2}===方法二：暴力查表（不分解 n）===解密结果: flag{13212je2ue28fy71w8u87y31r78eu1e2}===出现过的 密文 ->字符 映射===704796792->'f'752211152->'l'274704164->'a'18414022->'g'368270835->'{'483295235->'1'263072905->'3'459788476->'2'663551792->'j'475206804->'e'428313374->'u'425392137->'8'458265677->'y'341524652->'7'534149509->'w'828509797->'r'306220148->'}'答案
flag{13212je2ue28fy71w8u87y31r78eu1e2}
