从CTF靶场到实战：手把手教你用Python脚本破解5种RSA经典变种题
从CTF靶场到实战：手把手教你用Python脚本破解5种RSA经典变种题
1. 密码学竞赛中的RSA攻防艺术
在网络安全竞赛和实际渗透测试中，RSA算法变种题目是最常见的挑战之一。不同于教科书式的标准RSA，这些变种往往通过精心设计的数学陷阱考验选手的密码分析能力。本文将深入剖析5类典型RSA变种题的破解技巧，并提供可直接复用的Python解决方案。
RSA变种题的三大特征：
- 模数N的特殊构造（如相近素数、多素数相乘）
- 加密指数e的非常规选择（极小/极大值、多组密钥）
- 参数间的隐藏数学关系（威尔逊定理、中国剩余定理等）
# RSA基础解密函数模板 from Crypto.Util.number import long_to_bytes import gmpy2 def rsa_decrypt(c, e, p, q): n = p * q phi = (p-1)*(q-1) d = gmpy2.invert(e, phi) return long_to_bytes(pow(c, d, n))2. 共模攻击：当N被重复使用时
典型场景：相同模数N配合多组加密指数(e₁,e₂)加密同一明文，且gcd(e₁,e₂)=1
def common_modulus_attack(c1, c2, e1, e2, n): # 扩展欧几里得算法求系数 gcd, s1, s2 = gmpy2.gcdext(e1, e2) # 确保得到正指数 if s1 < 0: c1 = gmpy2.invert(c1, n) s1 = -s1 if s2 < 0: c2 = gmpy2.invert(c2, n) s2 = -s2 return (pow(c1, s1, n) * pow(c2, s2, n)) % n实战案例：某CTF题目提供两组密文：
N = 7850954...（2048位） e1 = 1697, e2 = 599 c1 = [41262..., 49464..., ...] c2 = [59216..., 37394..., ...]通过共模攻击还原出base64编码的flag后，还需处理隐写数据。
3. 小指数攻击与中国剩余定理
低加密指数广播攻击：当e=3且相同明文用不同N加密时
def chinese_remainder_theorem(items): N = 1 for a, n in items: N *= n result = 0 for a, n in items: m = N // n d = gmpy2.invert(m, n) result += a * m * d return result % N def small_e_attack(ctexts, moduli, e=3): items = list(zip(ctexts, moduli)) m_e = chinese_remainder_theorem(items) return gmpy2.iroot(m_e, e)[0]参数恢复技巧：当给出nextprime(a*b mod c)类参数时，使用威尔逊定理逆向计算：
def wilson_reverse(A, B): """ 根据B! mod A恢复B的下一个素数 """ fact_mod = (-1) * pow(gmpy2.invert(reduce(lambda x,y:x*y%A, range(B+1,A-1)), A), 1, A) return sympy.nextprime(fact_mod)4. 特殊参数构造的破解方法
相近素数分解：当p和q接近时，费马分解法效率极高
def fermat_factorization(n): a = gmpy2.isqrt(n) + 1 b2 = a*a - n while not gmpy2.is_square(b2): a += 1 b2 = a*a - n return (a - gmpy2.isqrt(b2), a + gmpy2.isqrt(b2))多素数RSA分析：对于N=pqr系统，欧拉函数变为：
phi = (p-1)*(q-1)*(r-1)5. 混合加密系统的联合攻击
当RSA与其他加密方式结合时（如本题的base64隐写），需要分阶段处理：
- 参数恢复阶段：
# 从阶乘模数恢复素数 def recover_prime_from_factorial_mod(A, B): product = 1 for num in range(B+1, A): product = (product * num) % A return sympy.nextprime(gmpy2.invert(product, A))- 方程组求解阶段：
def solve_equation_system(c1, c2): """ 解方程组： f1 + f2 = c1 f1^3 + f2^3 = c2 """ F1 = sympy.Symbol('F1') F2 = sympy.Symbol('F2') eq1 = sympy.Eq(F1 + F2, c1) eq2 = sympy.Eq(F1**3 + F2**3, c2) return sympy.solve((eq1, eq2), (F1, F2))- 最终解密流程：
def full_decryption_workflow(): # 步骤1：分解N获取p,q p, q = fermat_factorization(N) # 步骤2：解密得到中间参数 d = gmpy2.invert(e, (p-1)*(q-1)) c1 = pow(m1, d, N) c2 = pow(m2, d, N) # 步骤3：解方程组 solutions = solve_equation_system(c1, c2) flag_part1, flag_part2 = solutions[0] return long_to_bytes(flag_part1) + long_to_bytes(flag_part2)实战工具箱推荐
必备Python库：
pycryptodome==3.18.0 gmpy2==2.1.5 sympy==1.12 libnum==1.7优化技巧：
- 使用
gmpy2.mpz处理大整数运算 - 预计算常用数值加速模幂运算
- 对多组密文采用并行解密策略
在真实CTF比赛中，RSA变种往往结合编码混淆（如base64、hex）、数学陷阱（如伪随机数生成）和网络协议分析。建议建立自己的密码破解代码库，将常见攻击方法模块化。