博客基础信息标题新冠存在疫苗 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 输出密文与公钥plaintextn 12189464288007059657184858632825479990912616419482466046617619319388181010121359489739982536798361842485210016303524715395474637570227926791570158634811951043352789232959763417380155972853016696908995809240738171081946517881643416715486249 e 65537 c 10093874086170276546167955043813453195412484673031739173390677430603113063707524122014352886564777373620029541666833142412009063988439640569778321681605225404251519582850624600712844557011512775502356036366115295154408488005375252950048742二、漏洞原理深度分析1. 标准安全 RSA 逻辑安全 RSA 要求两个素数 p、q 完全独立随机生成模数np*q依靠大数分解困难性保证加密安全没有数学关联无法快速拆分。2. 本题致命构造缺陷题目核心漏洞代码python运行q int(gmpy2.digits(p, 3))执行流程拆解将大素数 p 转换为仅包含 0、1、2 三种字符的三进制字符串 S直接把字符串 S 当作十进制数字转换得到另一个素数 q 数学约束关系 设字符串 Spint(S,3)qint(S,10)满足 p*qn。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简易枚举仅判断整除出现无效因子 q1最初编写循环遍历候选 q仅通过n%q0筛选因子数字 1 可以整除任意大数程序直接判定 q1后续校验int(base3(p))q触发断言报错属于校验条件缺失导致的错误分解。坑 2递归 DFS 构造字符串栈溢出崩溃使用递归深度优先拼接 0/1/2 生成字符串字符串长度持续增加递归层数突破 Python 默认栈上限直接抛出递归深度超限报错。坑 3改用 BFS 迭代队列程序长期卡死无输出替换无递归 BFS 队列代码虽然规避栈溢出但候选数量指数爆炸CPU 满载持续运行几小时无任何匹配结果算力完全不足以支撑搜索。坑 4CtrlC 终止程序弹出 KeyboardInterrupt程序卡死手动按CtrlC停止控制台抛出KeyboardInterrupt属于正常手动中断信号并非代码逻辑 bug无需修改代码。四、正确解题方案FactorDB 在线大数分解操作步骤打开 FactorDB 官网https://factordb.com将题目给出完整超长 n 数值粘贴至输入框点击查询查询结果显示 FFFully Factored完全分解点击 show 展开两个素因子记录两个素数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 解密数学原理回顾欧拉函数φ(n)(p−1)(q−1)私钥 d 是 e 在模φ(n)下的乘法逆元 de**−1 (mod φ(n))明文计算公式mc**d (mod n)将大整数 m 转为二进制字节流解码得到可读 flag 字符串。五、核心知识点总结RSA 安全根基在于两个素数相互独立出题人构造进制关联素数会直接破坏模数安全性进制转换生成素数是 CTF 高频套路p、q 共享同一串 0/1/2 字符制造可分解后门字符串长度超过 20 位后暴力枚举空间指数爆炸本地普通电脑完全无解FactorDB 是 CTF RSA 题型通用捷径出题人通常提前上传模数分解结果优先使用做题思路优先级先数学估算搜索空间再选择工具不要无脑写暴力循环浪费时间。六、拓展学习方向Coppersmith 小根攻击、LLL 格基约减SageMath 实现无库分解yafu、msieve 本地高性能大数分解工具同类构造 RSA 题型p 与 q 共享高低位、pkqr、双素数同进制衍生等。结尾结语这道「新冠存在 疫苗 challenge_name」作为入门 Crypto RSA 题很好地提醒选手遇到特殊构造素数不要第一时间写暴力代码先通过数学计算判断可行性在线分解库能大幅降低解题成本是 CTF 比赛必备技巧。
