背景前面我们学的攻击手段共模攻击、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 都不用分解当明文空间远小于密钥空间时加密变成了一个可逆的查表游戏——这正是无填充逐字符加密的悲哀。简单例子我们用p3, q11来演示数字小到可以在草稿纸上算完。生成密钥n p × q 3 × 11 33φ(n) (p-1)(q-1) 2 × 10 20选 e 3gcd(3, 20) 1 ✓公钥 (e, n) (3, 33)求私钥 d3 × d ≡ 1 (mod 20)3 × 7 21 20 1 ≡ 1 ✓所以d 7私钥 (d, n) (7, 33)逐字符加密为方便手算我们用字母表位置给明文编号a1, b2, c3, …要加密消息“cab”→ 明文序列 [3, 1, 2]加密公式 c mᵉ mod n m³ mod 33明文 m计算 m³ mod 33密文 c3 ( c )3³ 27271 ( a )1³ 112 ( b )2³ 88攻击者最终只看到n33, e3以及密文序列[27, 1, 8]。攻击一分解 n 求私钥n33 小到一眼可分33 3 × 11φ(n) (3-1)*(11-1)20e*d≡1 mod φ(n)推出 d 7解密 m cᵈ mod n c⁷ mod 33密文 2727 ≡ -6 (mod 33)(-6)² 36 ≡ 3(-6)⁴ ≡ 3² 9(-6)⁷ (-6)⁴ × (-6)² × (-6) 9 × 3 × (-6) -162 ≡ -162 5×33 3→ m 3 →‘c’密文 11⁷ 1 → m 1 →‘a’密文 88² 64 ≡ 64 - 33 318⁴ ≡ 31² 961 29×33 4 ≡ 48⁷ 8⁴ × 8² × 8 4 × 31 × 8 992 30×33 2 ≡ 2→ m 2 →‘b’恢复明文序列 [3, 1, 2] →“cab”✓ 闭环成功攻击二查表法不分解 n明文空间只有 az126共 26 种干脆全部加密一遍建反查表m1 → c1 m2 → c8 m3 → c27 ...拿到密文 [27, 1, 8] 直接反查27→3©、1→1(a)、8→2(b) →“cab”✓整个过程没有用到 p、q、d只用了公开的 e 和 n。可见逐字符无填充比n 太小还要致命——即使 n 大到分不动只要明文空间小查表法照样秒杀。代码实现# # RSA 小 n 分解 逐字符加密手算例子# ## 场景: p3, q11, n33, e3, d7# 明文用字母表位置 a1..z26 编码逐字符加密# 攻击:# 方法一: 分解 n33 → 求 d → 解密每个密文# 方法二: 暴力查表把 1..26 全加密一遍反查无需分解 n# deffactor_by_trial(n):试除法分解小 n返回 (p, q)i2whilei*in:ifn%i0:returni,n//i i1raiseValueError(n 是素数无法分解为两个 1 的因子)defmain():# ---- 公钥 ----n33e3# ---- 原始明文 cab用字母表位置编码 ----plaincabms[ord(ch)-96forchinplain]# a1, b2, c3print(f明文:{plain}- 明文序列{ms})# ---- 加密逐字符----cs[pow(m,e,n)forminms]print(f密文序列:{cs})print()# 方法一分解 n 求私钥 print( 方法一分解 n 求私钥 )p,qfactor_by_trial(n)print(f分解 n{n}{p}×{q})phi(p-1)*(q-1)dpow(e,-1,phi)print(fφ(n) {phi}, d {d})recovered1.join(chr(pow(c,d,n)96)forcincs)print(f解密结果:{recovered1})print()# 方法二暴力查表不分解 nprint( 方法二暴力查表不分解 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 求私钥分解n333×11φ(n)20, d7解密结果: cab方法二暴力查表不分解 n解密结果: cab作业RSA roll题目https://ctf2.dasctf.com/dashboard/practice/b9bbb32f-f186-458f-b90b-12440c0f6aea?tabchallengeschallenge542e42ea-2a5c-44c8-8801-9b30b7e1a973RSA rollrollroll Only number and a-z dont 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 920071380d 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 分解 逐字符加密# ## 已知: n920139713, e19, 以及一串逐字符加密的密文# 目标: 恢复明文 flag## 思路:# 方法一: n 只有 9 位试除法分解 → 求 d → 逐个解密 chr(pow(c,d,n))# 方法二: 明文空间极小把 32~126 全加密一遍建反查表逐个反查# deffactor_by_trial(n):试除法分解小 n返回 (p, q)i2whilei*in:ifn%i0:returni,n//i i1raiseValueError(n 是素数无法分解为两个 1 的因子)defmain():# ---- 题目参数 ----n920139713e19cs[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,qfactor_by_trial(n)print(f分解 n {p}×{q})print(f验证 p*q n ?{p*qn})phi(p-1)*(q-1)dpow(e,-1,phi)print(fφ(n) {phi})print(fd e^(-1) mod φ {d})print(f验证 (e*d) mod φ {(e*d)%phi})msg1.join(chr(pow(c,d,n))forcincs)print(f解密结果:{msg1})print()# 方法二暴力查表不分解 nprint( 方法二暴力查表不分解 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 求私钥分解 n18443×49891验证 p*qn ? True φ(n)920071380de^(-1)mod φ96849619验证(e*d)mod φ1解密结果: flag{13212je2ue28fy71w8u87y31r78eu1e2}方法二暴力查表不分解 n解密结果: flag{13212je2ue28fy71w8u87y31r78eu1e2}出现过的 密文 -字符 映射704796792-f752211152-l274704164-a18414022-g368270835-{483295235-1263072905-3459788476-2663551792-j475206804-e428313374-u425392137-8458265677-y341524652-7534149509-w828509797-r306220148-}答案flag{13212je2ue28fy71w8u87y31r78eu1e2} 
长河君 · 2026/8/7 10:17:56 · 阅读 1.2k 【CTF-CRYPTO-教学-RSA】第五节：9位数小 n 分解攻击
背景前面我们学的攻击手段共模攻击、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 都不用分解当明文空间远小于密钥空间时加密变成了一个可逆的查表游戏——这正是无填充逐字符加密的悲哀。简单例子我们用p3, q11来演示数字小到可以在草稿纸上算完。生成密钥n p × q 3 × 11 33φ(n) (p-1)(q-1) 2 × 10 20选 e 3gcd(3, 20) 1 ✓公钥 (e, n) (3, 33)求私钥 d3 × d ≡ 1 (mod 20)3 × 7 21 20 1 ≡ 1 ✓所以d 7私钥 (d, n) (7, 33)逐字符加密为方便手算我们用字母表位置给明文编号a1, b2, c3, …要加密消息“cab”→ 明文序列 [3, 1, 2]加密公式 c mᵉ mod n m³ mod 33明文 m计算 m³ mod 33密文 c3 ( c )3³ 27271 ( a )1³ 112 ( b )2³ 88攻击者最终只看到n33, e3以及密文序列[27, 1, 8]。攻击一分解 n 求私钥n33 小到一眼可分33 3 × 11φ(n) (3-1)*(11-1)20e*d≡1 mod φ(n)推出 d 7解密 m cᵈ mod n c⁷ mod 33密文 2727 ≡ -6 (mod 33)(-6)² 36 ≡ 3(-6)⁴ ≡ 3² 9(-6)⁷ (-6)⁴ × (-6)² × (-6) 9 × 3 × (-6) -162 ≡ -162 5×33 3→ m 3 →‘c’密文 11⁷ 1 → m 1 →‘a’密文 88² 64 ≡ 64 - 33 318⁴ ≡ 31² 961 29×33 4 ≡ 48⁷ 8⁴ × 8² × 8 4 × 31 × 8 992 30×33 2 ≡ 2→ m 2 →‘b’恢复明文序列 [3, 1, 2] →“cab”✓ 闭环成功攻击二查表法不分解 n明文空间只有 az126共 26 种干脆全部加密一遍建反查表m1 → c1 m2 → c8 m3 → c27 ...拿到密文 [27, 1, 8] 直接反查27→3©、1→1(a)、8→2(b) →“cab”✓整个过程没有用到 p、q、d只用了公开的 e 和 n。可见逐字符无填充比n 太小还要致命——即使 n 大到分不动只要明文空间小查表法照样秒杀。代码实现# # RSA 小 n 分解 逐字符加密手算例子# ## 场景: p3, q11, n33, e3, d7# 明文用字母表位置 a1..z26 编码逐字符加密# 攻击:# 方法一: 分解 n33 → 求 d → 解密每个密文# 方法二: 暴力查表把 1..26 全加密一遍反查无需分解 n# deffactor_by_trial(n):试除法分解小 n返回 (p, q)i2whilei*in:ifn%i0:returni,n//i i1raiseValueError(n 是素数无法分解为两个 1 的因子)defmain():# ---- 公钥 ----n33e3# ---- 原始明文 cab用字母表位置编码 ----plaincabms[ord(ch)-96forchinplain]# a1, b2, c3print(f明文:{plain}- 明文序列{ms})# ---- 加密逐字符----cs[pow(m,e,n)forminms]print(f密文序列:{cs})print()# 方法一分解 n 求私钥 print( 方法一分解 n 求私钥 )p,qfactor_by_trial(n)print(f分解 n{n}{p}×{q})phi(p-1)*(q-1)dpow(e,-1,phi)print(fφ(n) {phi}, d {d})recovered1.join(chr(pow(c,d,n)96)forcincs)print(f解密结果:{recovered1})print()# 方法二暴力查表不分解 nprint( 方法二暴力查表不分解 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 求私钥分解n333×11φ(n)20, d7解密结果: cab方法二暴力查表不分解 n解密结果: cab作业RSA roll题目https://ctf2.dasctf.com/dashboard/practice/b9bbb32f-f186-458f-b90b-12440c0f6aea?tabchallengeschallenge542e42ea-2a5c-44c8-8801-9b30b7e1a973RSA rollrollroll Only number and a-z dont 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 920071380d 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 分解 逐字符加密# ## 已知: n920139713, e19, 以及一串逐字符加密的密文# 目标: 恢复明文 flag## 思路:# 方法一: n 只有 9 位试除法分解 → 求 d → 逐个解密 chr(pow(c,d,n))# 方法二: 明文空间极小把 32~126 全加密一遍建反查表逐个反查# deffactor_by_trial(n):试除法分解小 n返回 (p, q)i2whilei*in:ifn%i0:returni,n//i i1raiseValueError(n 是素数无法分解为两个 1 的因子)defmain():# ---- 题目参数 ----n920139713e19cs[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,qfactor_by_trial(n)print(f分解 n {p}×{q})print(f验证 p*q n ?{p*qn})phi(p-1)*(q-1)dpow(e,-1,phi)print(fφ(n) {phi})print(fd e^(-1) mod φ {d})print(f验证 (e*d) mod φ {(e*d)%phi})msg1.join(chr(pow(c,d,n))forcincs)print(f解密结果:{msg1})print()# 方法二暴力查表不分解 nprint( 方法二暴力查表不分解 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 求私钥分解 n18443×49891验证 p*qn ? True φ(n)920071380de^(-1)mod φ96849619验证(e*d)mod φ1解密结果: flag{13212je2ue28fy71w8u87y31r78eu1e2}方法二暴力查表不分解 n解密结果: flag{13212je2ue28fy71w8u87y31r78eu1e2}出现过的 密文 -字符 映射704796792-f752211152-l274704164-a18414022-g368270835-{483295235-1263072905-3459788476-2663551792-j475206804-e428313374-u425392137-8458265677-y341524652-7534149509-w828509797-r306220148-}答案flag{13212je2ue28fy71w8u87y31r78eu1e2}