从CTF题到实战：手把手教你用Python的sympy和gmpy2破解RSA变种（附完整脚本）

从CTF题到实战手把手教你用Python的sympy和gmpy2破解RSA变种附完整脚本在网络安全竞赛和实际渗透测试中RSA加密算法的各种变种经常出现。这些变种往往通过引入特殊的数学性质或构造方式使得标准的RSA攻击方法失效。本文将从一个真实的CTF竞赛题目出发详细讲解如何利用Python中的sympy和gmpy2库来破解一种特殊的RSA变种加密。1. 理解题目与加密机制首先我们需要完全理解题目给出的加密机制。这个RSA变种与标准RSA有几个关键区别素数生成方式特殊p 2^79 * r 1 (r是70位随机数)q 4 * r 3 (r是147-148位随机数)加密过程引入二次剩余选择一个y使得y对p和q都不是二次剩余加密公式c (y^m * x^(2^k)) mod n消息处理明文flag被分成5段每段10字节(79位)每段单独加密这种构造方式使得直接应用标准的RSA解密方法变得不可行我们需要分析其数学特性来找到突破口。2. 破解思路分析2.1 分解模数n由于p的特殊构造形式(p2^79*r1)我们可以使用Coppersmith方法来恢复小根from sage.all import * def coppersmith_attack(n, k79): P.x PolynomialRing(Zmod(n)) f 2^k * x 1 roots f.monic().small_roots(X2^70, beta0.499, epsilon0.02) if roots: r int(roots[0]) p int(f(r)) return p return None这个攻击能够成功是因为r相对较小(70位)而n有约217位(70147)满足Coppersmith定理的条件。2.2 利用二次剩余性质加密公式c y^m * x^(2^k) mod n中y被特意选择为非二次剩余。这给了我们判断m的奇偶性的能力如果m是偶数c是二次剩余如果m是奇数c是非二次剩余我们可以利用Legendre符号或Jacobi符号来判断这一点from gmpy2 import jacobi def is_quadratic_residue(c, p): return jacobi(c, p) 12.3 递归开平方根由于x^(2^k)部分在模p下总是二次剩余(因为指数是2的高次幂)我们可以通过递归开平方来消除这部分如果c是二次剩余(m为偶数)直接开平方如果c不是二次剩余(m为奇数)先除以y再开平方每次开平方都会将m的位数减半最终我们可以恢复完整的m。3. 完整破解脚本实现下面是将上述思路整合后的完整Python脚本from sage.all import * from gmpy2 import jacobi, invert from Crypto.Util.number import long_to_bytes def coppersmith_attack(n, k79): P.x PolynomialRing(Zmod(n)) f 2**k * x 1 roots f.monic().small_roots(X2**70, beta0.499, epsilon0.02) if roots: r int(roots[0]) p int(f(r)) return p return None def rabin_decrypt(c, p): if c 0: return [0] if jacobi(c, p) ! 1: return [] P.x PolynomialRing(GF(p)) f x**2 - c roots f.roots() return [int(r[0]) for r in roots] def decrypt_block(c, p, y, k79): global flag_pieces ok False flag_piece b def getm(c, m_bits): nonlocal ok, flag_piece if ok: return if len(m_bits) k: m int(m_bits, 2) flag_piece long_to_bytes(m) ok True return if jacobi(c, p) -1: new_m 1 m_bits c_new (c * invert(y, p)) % p else: new_m 0 m_bits c_new c roots rabin_decrypt(c_new, p) for root in roots: getm(root, new_m) getm(c, ) return flag_piece # 题目给出的参数 n 542799179636839492268900255776759322356188435185061417388485378278779491236741777034539347 y 304439269593920283890993394966761083993573819485737741439790516965458877720153847056020690 cs [ 302425991290493703631236053387822220993687940015503176763298104925896002167283079926671604, 439984254328026142169547867847928383533091717170996198781543139431283836994276036750935235, 373508223748617252014658136131733110314734961216630099592116517373981480752966721942060039, 246328010831179104162852852153964748882971698116964204135222670606477985487691371234998588, 351248523787623958259846173184063420603640595997008994436503031978051069643436052471484545 ] # 第一步分解n p coppersmith_attack(n) q n // p print(f分解结果: p{p}, q{q}) # 第二步解密每个密文块 flag b for c in cs: piece decrypt_block(c, p, y) flag piece print(f解密得到片段: {piece}) print(f完整flag: {flag})4. 关键技术与调试技巧4.1 Coppersmith方法参数调整在实际应用中Coppersmith方法的参数可能需要调整# 调整epsilon和beta参数 roots f.monic().small_roots(X2^70, beta0.4, epsilon0.05)常见调试技巧如果找不到根尝试减小beta或增大epsilon确保多项式的构造正确检查X的边界是否足够大4.2 二次剩余处理中的陷阱在实现递归开平方时有几个容易出错的地方Jacobi符号计算必须使用素数模数不能直接用n根的选择每次开平方可能得到两个根需要递归处理所有可能性终止条件需要准确判断何时停止递归4.3 性能优化对于较长的消息或较大的k值递归开平方可能很耗时。可以考虑以下优化并行处理对不同的根分支使用多线程剪枝提前终止不可能的分支缓存缓存中间计算结果5. 扩展应用与防御建议5.1 类似加密系统的识别这种加密变种的特征包括模数n的特殊构造加密公式中引入随机数的高次幂使用二次剩余等数论性质在实际中遇到类似系统时可以尝试分析素数生成方式检查是否有小根可以利用研究加密公式的数学性质5.2 安全建议如果要设计类似的加密系统应当避免使用可预测的素数生成方式确保所有参数足够大抵抗Coppersmith等攻击对加密公式进行全面的安全性分析6. 实战中的变通应用在实际渗透测试中可能会遇到各种加密系统的变种。掌握这种分析方法后可以识别加密模式通过分析加密代码或网络流量识别加密方式数学建模将加密过程抽象为数学问题工具选择根据问题特点选择合适的数学工具和库定制开发针对特定问题编写专用解密脚本例如在分析一个未知的加密协议时可以收集足够的加密样本尝试分解模数或找出数学关系使用符号计算工具验证猜想开发自动化解密工具这种从具体问题出发通过数学分析和编程实现解决问题的思路正是CTF竞赛和实际安全工作的核心技能。