新冠疫苗 RSA Challenge：进制构造素数漏洞拆解

博客基础信息

标题：新冠：存在｜疫苗 challenge RSA 题型完整解题记录

标签：CTF、Crypto、RSA 分解、进制漏洞、FactorDB、新手向

难度：Medium 涉及考点：自定义素数生成逻辑、RSA 原理、大数分解局限性、在线分解库使用

前言

本次 CTF Crypto 题为「新冠：存在 疫苗 challenge_name」，出题人构造了特殊 RSA 素数生成逻辑，人为制造 p、q 强关联，看似需要暴力枚举进制字符串，实际本地算力完全无法完成遍历，最优解借助 FactorDB 大数分解库直接获取因子，完成标准 RSA 解密拿到 flag。下文完整记录源码分析、踩坑过程、解题步骤与原理总结。

一、题目附件文件

1. challenge.py 源码

python

运行

import random import gmpy2 e = 0x10001 # 固定公钥指数65537 with open('flag.txt', 'rb') as f: m = f.read() m = int.from_bytes(m, 'big') while True: # 随机生成256位大数p p = random.getrandbits(256) # 核心漏洞：将p转为三进制字符串，再直接转十进制数字作为q q = int(gmpy2.digits(p, 3)) # 素数合法性校验 if not gmpy2.is_prime(p): continue if not gmpy2.is_prime(q): continue # 保证e存在模逆，规避RSA加密失效 if (p-1) % e == 0: continue if (q-1) % e == 0: continue break n = p * q assert 0 <= m < n c = pow(m, e, n) print(f'{n = }') print(f'{e = }') print(f'{c = }')

2. output.txt 输出密文与公钥

plaintext

n = 12189464288007059657184858632825479990912616419482466046617619319388181010121359489739982536798361842485210016303524715395474637570227926791570158634811951043352789232959763417380155972853016696908995809240738171081946517881643416715486249 e = 65537 c = 10093874086170276546167955043813453195412484673031739173390677430603113063707524122014352886564777373620029541666833142412009063988439640569778321681605225404251519582850624600712844557011512775502356036366115295154408488005375252950048742

二、漏洞原理深度分析

1. 标准安全 RSA 逻辑

安全 RSA 要求两个素数 p、q 完全独立随机生成，模数n=p*q依靠大数分解困难性保证加密安全，没有数学关联，无法快速拆分。

2. 本题致命构造缺陷

题目核心漏洞代码：

python

运行

q = int(gmpy2.digits(p, 3))

执行流程拆解：

1. 将大素数 p 转换为仅包含 0、1、2 三种字符的三进制字符串 S；
2. 直接把字符串 S 当作十进制数字，转换得到另一个素数 q； 数学约束关系： 设字符串 S，p=int(S,3)，q=int(S,10)，满足 p*q=n。

3. 暴力枚举方案为什么完全行不通

通过对数估算字符串 S 长度 L： n≈30**L，模数 n 总位数 239 位 log_{10}(30)×L≈239，计算得 L≈162。 需要枚举162 位仅由 0/1/2 组成的字符串，总组合数 3**162≈1.96×10**77。 即便电脑每秒遍历 10 亿条候选，所需时间远超宇宙现有年龄，本地 DFS、BFS 循环只会无限卡死，暴力路线直接放弃。

三、踩坑实录（做题全过程翻车点）

坑 1：简易枚举仅判断整除，出现无效因子 q=1

最初编写循环遍历候选 q，仅通过n%q==0筛选因子，数字 1 可以整除任意大数，程序直接判定 q=1，后续校验int(base3(p))==q触发断言报错，属于校验条件缺失导致的错误分解。

坑 2：递归 DFS 构造字符串，栈溢出崩溃

使用递归深度优先拼接 0/1/2 生成字符串，字符串长度持续增加，递归层数突破 Python 默认栈上限，直接抛出递归深度超限报错。

坑 3：改用 BFS 迭代队列，程序长期卡死无输出

替换无递归 BFS 队列代码，虽然规避栈溢出，但候选数量指数爆炸，CPU 满载持续运行，几小时无任何匹配结果，算力完全不足以支撑搜索。

坑 4：Ctrl+C 终止程序弹出 KeyboardInterrupt

程序卡死手动按Ctrl+C停止，控制台抛出KeyboardInterrupt，属于正常手动中断信号，并非代码逻辑 bug，无需修改代码。

四、正确解题方案：FactorDB 在线大数分解

操作步骤

1. 打开 FactorDB 官网：https://factordb.com
2. 将题目给出完整超长 n 数值粘贴至输入框，点击查询；
3. 查询结果显示 FF（Fully Factored）完全分解，点击 show 展开两个素因子；
4. 记录两个素数：78 位 p、162 位 q。

RSA 完整解密代码

python

运行

import gmpy2 # 题目公钥参数 n = 12189464288007059657184858632825479990912616419482466046617619319388181010121359489739982536798361842485210016303524715395474637570227926791570158634811951043352789232959763417380155972853016696908995809240738171081946517881643416715486249 e = 65537 c = 10093874086170276546167955043813453195412484673031739173390677430603113063707524122014352886564777373620029541666833142412009063988439640569778321681605225404251519582850624600712844557011512775502356036366115295154408488005375252950048742 # 替换FactorDB查询到的两个素数 p = "FactorDB获取的78位素数" q = "FactorDB获取的162位素数" # RSA解密流程 phi = (int(p) - 1) * (int(q) - 1) d = gmpy2.invert(e, phi) m = gmpy2.powmod(c, d, n) # 整数转回字节明文 flag_raw = m.to_bytes((m.bit_length() + 7) // 8, "big") print("最终Flag：", flag_raw.decode())

RSA 解密数学原理回顾

1. 欧拉函数：φ(n)=(p−1)(q−1)
2. 私钥 d 是 e 在模φ(n)下的乘法逆元 d=e**−1 (mod φ(n))
3. 明文计算公式：m=c**d (mod n)
4. 将大整数 m 转为二进制字节流，解码得到可读 flag 字符串。

五、核心知识点总结

1. RSA 安全根基在于两个素数相互独立，出题人构造进制关联素数会直接破坏模数安全性；
2. 进制转换生成素数是 CTF 高频套路，p、q 共享同一串 0/1/2 字符，制造可分解后门；
3. 字符串长度超过 20 位后暴力枚举空间指数爆炸，本地普通电脑完全无解；
4. FactorDB 是 CTF RSA 题型通用捷径，出题人通常提前上传模数分解结果，优先使用；
5. 做题思路优先级：先数学估算搜索空间，再选择工具，不要无脑写暴力循环浪费时间。

六、拓展学习方向

1. Coppersmith 小根攻击、LLL 格基约减（SageMath 实现无库分解）；
2. yafu、msieve 本地高性能大数分解工具；
3. 同类构造 RSA 题型：p 与 q 共享高低位、p=kq+r、双素数同进制衍生等。

结尾结语

这道「新冠：存在 疫苗 challenge_name」作为入门 Crypto RSA 题，很好地提醒选手：遇到特殊构造素数不要第一时间写暴力代码，先通过数学计算判断可行性，在线分解库能大幅降低解题成本，是 CTF 比赛必备技巧。