1. 项目概述为什么RSA攻击是CTF密码学的核心战场如果你玩过几场CTF尤其是其中的Crypto密码学方向那你一定对RSA不陌生。它几乎成了现代CTF密码学题目的“半壁江山”从最简单的模数分解到各种花式攻击RSA以其清晰的数学原理和灵活多变的出题方式成为了检验选手密码学功底和脚本能力的绝佳靶场。我见过太多新手拿到一个RSA题目只知道公钥(n, e)和密文c然后就卡在那里无从下手最后只能去网上漫无目的地搜索“RSA攻击脚本”结果往往因为不理解原理而用错方法或者面对稍微变形的题目就束手无策。这篇内容就是为你打破这个瓶颈准备的。我们不谈高深的理论推导只聚焦于实战。我将为你拆解在CTF比赛中最高频出现的5种RSA攻击手法每一种都配有可直接运行、修改的Python脚本。这些攻击手法的选择完全基于我多年来打比赛、出题目、复盘Writeup的经验它们覆盖了CTF中RSA题目80%以上的场景。从最基础的因式分解攻击到需要一点数论知识的共模攻击、低加密指数攻击再到稍微进阶的维纳攻击和费马分解我们会逐一击破。我的目标很明确让你在下次遇到RSA题目时能像条件反射一样快速判断出题人可能埋下的漏洞并拿出对应的“武器库”进行破解。2. 攻击手法一模数分解攻击——当n不够大的时候这是最直接、最经典的RSA攻击方式其原理根植于RSA安全性的核心假设大整数分解是困难的。RSA的公钥包含模数nn p * qp和q为大素数和加密指数e。私钥d的计算依赖于φ(n) (p-1)*(q-1)。因此如果我们能成功分解n得到p和q那么整个RSA体系就被完全攻破。2.1 核心原理与攻击场景为什么分解n就能破解回顾一下私钥d的计算公式d ≡ e^(-1) mod φ(n)。而φ(n)的计算需要p和q。一旦你有了p和q计算φ(n)、进而计算私钥d、最后解密cm ≡ c^d mod n就是顺理成章的事情。在CTF中这类题目通常有两种表现形式故意使用小素数出题人为了降低难度或是故意设置漏洞使用了长度很短的p和q导致n可能只有256位、512位甚至更短。在现代计算机上分解这样的n是瞬间完成的。n具有特殊结构或已知因子有时n可能不是两个素数的乘积或者其中一个因子很小、是已知的素数比如3, 5, 65537又或者n本身可以被某些在线数据库如factordb直接查询到因子。2.2 实战工具与Python脚本对于小n例如小于512位我们完全可以在本地进行分解。最常用的工具是sympy库的factorint函数或者专门的分解工具yafu。对于在线查询可以尝试访问factordb.com。下面是一个通用的Python分解攻击脚本。这个脚本会尝试多种方法先尝试用sympy本地分解如果不行可能因为n太大或sympy默认算法效率问题则尝试调用系统安装的yafu如果存在最后还会尝试请求factordb的API。import requests import sympy from Crypto.Util.number import long_to_bytes, inverse import subprocess import os def factorize_n(n): 尝试分解模数n返回(p, q)元组。 尝试顺序1. sympy本地分解 2. yafu分解 3. factordb查询 print(f[*] 尝试分解 n: {n}) # 方法1: 使用sympy的factorint适用于较小整数 print([*] 尝试方法1: sympy.factorint...) try: # factorint返回一个字典质因数-指数 factors sympy.factorint(n) if len(factors) 2 and all(exp 1 for exp in factors.values()): p, q list(factors.keys()) print(f[] sympy分解成功! p {p}, q {q}) return int(p), int(q) else: print([-] sympy分解结果不是两个素数或含有重因子。) except Exception as e: print(f[-] sympy分解失败: {e}) # 方法2: 调用yafu需要本地安装yafu print([*] 尝试方法2: 调用yafu如果存在...) yafu_path “yafu-x64.exe” # Windows示例Linux/Mac可能是“yafu” if os.path.exists(yafu_path): try: # 将n写入临时文件 with open(“temp.txt”, “w”) as f: f.write(f“factor({n})\n”) # 运行yafu cmd [yafu_path, “onefiletemp.txt”] result subprocess.run(cmd, capture_outputTrue, textTrue, timeout30) # 解析yafu输出寻找P和PRP因子 for line in result.stdout.split(‘\n’): if ‘P’ in line or ‘PRP’ in line: parts line.split() if len(parts) 3 and parts[2].isdigit(): factor int(parts[2]) if n % factor 0: p factor q n // p if sympy.isprime(p) and sympy.isprime(q): print(f“[] yafu分解成功! p {p}, q {q}”) os.remove(“temp.txt”) return p, q except Exception as e: print(f“[-] yafu调用失败: {e}”) finally: if os.path.exists(“temp.txt”): os.remove(“temp.txt”) else: print(“[-] 未找到yafu跳过此方法。”) # 方法3: 查询factordb print(“[*] 尝试方法3: 查询factordb.com...”) try: url f“http://factordb.com/api?query{n}” resp requests.get(url, timeout10) data resp.json() status data.get(“status”) if status “FF”: # Fully Factored factors data.get(“factors”, []) if len(factors) 2: p int(factors[0][0]) q int(factors[1][0]) print(f“[] factordb查询成功! p {p}, q {q}”) return p, q else: print(f“[-] factordb返回了 {len(factors)} 个因子不符合RSA。”) else: print(f“[-] factordb状态: {status} 未完全分解。”) except Exception as e: print(f“[-] factordb查询失败: {e}”) print(“[-] 所有分解方法均失败。”) return None, None def rsa_decrypt_from_factors(n, e, c, p, q): 已知p, q, 解密RSA phi (p-1) * (q-1) d inverse(e, phi) # 计算私钥d m pow(c, d, n) # 解密 return long_to_bytes(m) # 示例用法 if __name__ “__main__”: # 这里替换成题目给的参数 n 0x726639ac33e … (你的n这里用大整数或16进制) e 65537 c 0x3a2e … (你的密文c) p, q factorize_n(n) if p and q: flag rsa_decrypt_from_factors(n, e, c, p, q) print(f“[] 解密成功! 明文(flag)为: {flag}”) else: print(“[-] 分解失败无法解密。”)注意使用yafu和factordbAPI需要网络或本地环境支持。在CTF比赛中如果题目允许联网factordb往往是第一选择如果离线则依赖本地sympy或提前准备好的yafu。另外sympy.factorint对于大数如1024位以上会非常慢甚至内存溢出此时不应作为首选。2.3 实操心得与避坑指南优先检查n的长度拿到题目第一件事就是用n.bit_length()看看n有多少位。如果小于512直接本地分解如果在512-768之间可以尝试yafu如果更大就要考虑其他攻击路径了。factordb的妙用很多CTF题目的n是故意从某些已知素数生成的或者直接使用了往年题目出现过的n。因此将n提交到factordb.com是一个成本极低且可能瞬间解题的操作务必养成习惯。注意n的格式题目给的n可能是10进制整数、16进制字符串以0x开头、或者Base64编码。c和e也可能如此。在代入脚本前务必统一转换成Python的int类型。一个常见的错误是忘记转换类型导致分解或解密失败。分解后的验证得到p和q后一定要验证p * q n且p和q均为素数可以用sympy.isprime。有时分解工具会返回多个因子或合数需要仔细甄别。3. 攻击手法二共模攻击——一把锁配了多把相同的钥匙这是一种非常巧妙的攻击场景是相同的明文m使用相同的模数n但不同的加密指数e1和e2进行加密得到了两个密文c1和c2。并且这两个加密指数e1和e2是互质的即gcd(e1, e2) 1。如果攻击者同时获得了这两组公钥和密文他就可以在不分解n、不知道私钥d的情况下恢复出明文m。3.1 数学原理深度解析为什么可以这样这背后是扩展欧几里得算法Extended Euclidean Algorithm和贝祖定理Bézout‘s identity的经典应用。我们知道c1 ≡ m^e1 (mod n)c2 ≡ m^e2 (mod n)如果e1和e2互质那么根据贝祖定理存在整数s和t使得e1 * s e2 * t gcd(e1, e2) 1注意这里的s和t通常一正一负。我们可以通过扩展欧几里得算法高效地计算出这对s和t。现在关键的一步来了。我们对同余式进行变换c1^s * c2^t ≡ (m^e1)^s * (m^e2)^t (mod n) ≡ m^(e1*s e2*t) (mod n) ≡ m^1 (mod n) ≡ m (mod n)因此我们得到了明文m。在实际计算中因为s或t可能是负数我们需要求其模逆元。例如若s为负则计算c1模n的逆元然后求其-s次幂。3.2 实战脚本与步骤拆解下面这个脚本实现了完整的共模攻击流程并处理了s和t为负数的常见情况。from Crypto.Util.number import long_to_bytes, inverse import gmpy2 # 使用gmpy2进行大数运算更高效但非必须 from math import gcd def common_modulus_attack(n, e1, c1, e2, c2): 共模攻击 参数: n: 公共模数 e1, c1: 第一组公钥指数和密文 e2, c2: 第二组公钥指数和密文 返回: 解密后的明文m (bytes) # 1. 验证e1和e2互质 if gcd(e1, e2) ! 1: print(“[-] e1 和 e2 不互质共模攻击可能失败。”) return None # 2. 使用扩展欧几里得算法求 s, t 使得 e1*s e2*t 1 # 这里使用gmpy2的gcdext它直接返回(g, s, t) g, s, t gmpy2.gcdext(e1, e2) # g是最大公约数理论上应为1 assert g 1, “e1和e2应互质” # 3. 根据s和t的正负情况计算m if s 0: # 如果s为负需要计算 c1 模 n 的逆元然后计算 (c1_inv)^(-s) * (c2)^t c1_inv inverse(c1, n) part1 pow(c1_inv, -s, n) else: part1 pow(c1, s, n) if t 0: # 如果t为负需要计算 c2 模 n 的逆元然后计算 (c1)^s * (c2_inv)^(-t) c2_inv inverse(c2, n) part2 pow(c2_inv, -t, n) else: part2 pow(c2, t, n) # 4. 计算 m (part1 * part2) % n m (part1 * part2) % n return long_to_bytes(m) # 示例用法 if __name__ “__main__”: # 示例参数通常题目会给出两组 (n, e, c) n 0xabcdef... # 相同的n e1 65537 c1 0x123456... e2 10001 c2 0x789abc... try: flag common_modulus_attack(n, e1, c1, e2, c2) if flag: # 解密结果可能包含不可见字符尝试解码 try: print(f“[] 共模攻击成功解密结果: {flag.decode()}”) except UnicodeDecodeError: print(f“[] 共模攻击成功解密结果(hex): {flag.hex()}”) print(f“[] 解密结果(bytes): {flag}”) except Exception as e: print(f“[-] 攻击过程中发生错误: {e}”)3.3 典型出题模式与识别技巧在CTF中共模攻击的题目通常有以下特征题目描述或附件中明确给出了两组或多组公钥和密文。这是最明显的信号。这些公钥的模数n完全相同。你需要仔细检查有时n会以文件pubkey1.pem,pubkey2.pem形式给出需要用openssl或Python的Crypto.PublicKey.RSA库提取。加密指数e不同但通常都比较常规如65537, 10001, 3等。密文c可能直接给出也可能隐藏在流量包、编码字符串中。重要心得共模攻击的成功不依赖于n的大小。即使n是2048位或4096位的安全大数只要满足上述条件攻击依然成立。因此当你看到“相同的n不同的e”时共模攻击应该成为你的第一反应。4. 攻击手法三低加密指数攻击与小明文攻击——当e太小m也不够随机RSA加密过程是c ≡ m^e mod n。当加密指数e非常小比如3 17并且明文m相对于模数n也很小时就会产生严重的漏洞。4.1 低加密指数广播攻击Håstad‘s Broadcast Attack攻击场景相同的明文m用相同的小加密指数e如e3但**不同的模数n1, n2, n3, …**进行加密得到密文c1, c2, c3, …。如果收集到的密文数量k满足k e那么就可以利用中国剩余定理CRT恢复出m^e然后直接开e次方根得到m。原理因为m^e n1 * n2 * n3 * …当m较小且e较小时可能成立所以m^e实际上没有经过模运算的“缠绕”c_i m^e mod n_i等价于m^e c_i k_i * n_i。利用中国剩余定理我们可以找到一个唯一的整数X满足X ≡ c_i (mod n_i)对所有i成立并且X在模N n1*n2*…的范围内。这个X就是m^e。由于e很小直接对X开e次方整数运算即可得到m。from Crypto.Util.number import long_to_bytes import gmpy2 from functools import reduce def crt(remainders, moduli): 中国剩余定理实现 N reduce(lambda a, b: a*b, moduli) result 0 for r_i, n_i in zip(remainders, moduli): p N // n_i # 求 p 模 n_i 的逆元 inv gmpy2.invert(p, n_i) result (result r_i * p * inv) % N return result def low_exponent_broadcast_attack(c_list, n_list, e): 低加密指数广播攻击 参数: c_list: 密文列表 [c1, c2, ...] n_list: 模数列表 [n1, n2, ...]与c_list一一对应 e: 公共的小加密指数 返回: 明文m (bytes) # 使用CRT计算 X m^e X crt(c_list, n_list) # 尝试对X开e次方根 # gmpy2.iroot 返回 (根, 是否完全开方) m, is_perfect gmpy2.iroot(X, e) if is_perfect: return long_to_bytes(int(m)) else: print(“[-] 开方失败可能收集的密文数量不足或m^e N。”) return None # 示例用法 if __name__ “__main__”: # 假设e3有三组不同的(n, c) e 3 n_list [n1, n2, n3] # 替换为实际的模数 c_list [c1, c2, c3] # 替换为实际的密文 flag low_exponent_broadcast_attack(c_list, n_list, e) if flag: print(f“[] 低加密指数广播攻击成功明文: {flag.decode()}”)4.2 小明文攻击或称为低加密指数攻击这是广播攻击的一个特例或简化版。当e很小如3并且明文m满足m^e n时加密过程c m^e mod n实际上就等于m^e本身因为m^e还没超过n取模后不变。即c m^e。那么攻击者只需要计算c的e次方根即可得到m。识别与攻击判断条件就是c的e次方根是否为整数。例如e3时直接计算m round(c ** (1/3))并验证m^3 c是否成立。def small_message_attack(c, e, nNone): 小明文攻击 当 m^e n 时c m^e直接开方即可。 参数n可选用于验证 m^e 是否真的小于 n。 # 尝试整数开方 m, is_perfect gmpy2.iroot(c, e) if is_perfect: m_int int(m) if n is not None: if pow(m_int, e) n: print(“[] 满足 m^e n 条件小明文攻击成功。”) else: print(“[!] 警告 m^e n但开方恰好为整数需谨慎验证。”) return long_to_bytes(m_int) else: print(“[-] 开方结果不是整数小明文攻击不适用。”) return None4.3 实操注意事项广播攻击的密文数量理论上需要至少e组密文。对于e3至少需要3组不同的(n_i, c_i)。但有时两组也可能成功如果m足够小的话。开方失败的处理如果gmpy2.iroot失败可能是因为m^e仍然大于所有n的乘积N或者m本身不是完美的e次方数比如m被填充了。这时需要考虑其他攻击或者检查是否遗漏了密文。e3是最常见的情况因为e3加密速度最快历史上被广泛使用也因此在CTF中成为高频考点。看到e3一定要优先检查是否可以应用此类攻击。5. 攻击手法四维纳攻击——当私钥d太小时这是一种针对私钥d过小情况的攻击由Michael J. Wiener在1990年提出。在RSA中为了加快解密速度有时会选择较小的私钥d。然而如果d小于n的约1/4次方具体是d (1/3) * n^(1/4)那么攻击者就可以仅从公钥(n, e)中高效地恢复出私钥d。5.1 攻击原理简述连分数逼近维纳攻击的核心数学工具是连分数Continued Fraction和连分数逼近。它基于一个数论事实如果d很小那么分数e/n的某个渐进分数convergentk/d会非常接近e/n。更具体地说攻击目标是找到满足以下等式的k和de*d ≡ 1 (mod φ(n))e*d k*φ(n) 1由于φ(n) ≈ n所以e/n ≈ k/d。通过计算e/n的连分数展开并检查每一个渐进分数k/d验证其是否满足RSA方程从而找到正确的d。5.2 完整Python实现与逐行解析下面是一个实现了经典维纳攻击的Python脚本包含了详细的注释。from Crypto.Util.number import long_to_bytes, inverse, isPrime import gmpy2 def wiener_attack(e, n): 维纳攻击实现 参数: e: 公钥指数 n: 模数 返回: 私钥d如果找到的话 # 1. 将 e/n 展开为连分数 def continued_fraction(e, n): 计算 e/n 的连分数展开序列 [a0, a1, a2, ...] cf [] while n: q e // n cf.append(q) e, n n, e - q * n return cf # 2. 根据连分数序列计算渐进分数convergents k/d def convergents(cf): 根据连分数序列生成渐进分数 (k, d) convs [] for i in range(len(cf)): # 初始化连分数 if i 0: ki cf[0] di 1 elif i 1: ki cf[0] * cf[1] 1 di cf[1] else: # 递归计算: 新的分数 a_i * 上一个分数 上上个分数 ki cf[i] * convs[i-1][0] convs[i-2][0] di cf[i] * convs[i-1][1] convs[i-2][1] convs.append((ki, di)) return convs cf continued_fraction(e, n) convs convergents(cf) # 3. 遍历每一个渐进分数 (k, d)检查是否满足条件 for k, d in convs: # 跳过 k0 的情况 if k 0: continue # 条件1: 如果 d 是偶数跳过RSA私钥d通常是奇数 if d % 2 0: continue # 条件2: 根据公式 ed kφ(n) 1推导出 φ(n) (ed - 1)/k # 计算 (e*d - 1) 是否能被 k 整除 if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 条件3: 根据 φ(n) (p-1)(q-1) n - (pq) 1可以建立一元二次方程 # sum pq n - φ(n) 1 # product p*q n # 方程: x^2 - sum*x n 0 sum_pq n - phi 1 # 判别式 delta sum^2 - 4n delta sum_pq * sum_pq - 4 * n if delta 0: continue # 检查判别式是否为完全平方数 sqrt_delta, is_square gmpy2.iroot(delta, 2) if not is_square: continue # 计算可能的 p 和 q p (sum_pq sqrt_delta) // 2 q (sum_pq - sqrt_delta) // 2 # 验证 p*q n 且 p, q 为素数 if p * q n and isPrime(p) and isPrime(q): print(f“[] 维纳攻击成功找到 d: {d}”) print(f“[] 分解得到 p: {p}, q: {q}”) return d print(“[-] 维纳攻击失败未找到合适的d。”) return None # 示例用法 if __name__ “__main__”: n 0x… # 替换为题目中的n e 0x… # 替换为题目中的e通常e会很大与n同量级 c 0x… # 密文 d wiener_attack(e, n) if d: # 使用找到的d解密 m pow(c, d, n) flag long_to_bytes(m) print(f“[] 解密成功明文: {flag}”)5.3 适用条件与识别特征维纳攻击并非万能它有明确的适用条件d必须足够小这是前提。通常题目会给出一个非常大的e与n位数相近这暗示着d可能很小因为e和d在模φ(n)下互为逆元一个很大往往意味着另一个很小。q p 2q素数p和q不能相差太悬殊这是维纳攻击原始论文中的假设大多数常规RSA生成都满足。攻击的典型场景题目只给了(n, e, c)n很大无法分解e也很大。你尝试了低指数攻击、共模攻击都不行这时就应该考虑维纳攻击。避坑指南维纳攻击脚本计算量很小几乎瞬间完成。如果脚本运行后没有输出结果大概率意味着d不满足攻击条件。此时不要纠结应转向其他攻击方法如接下来的费马分解或Pollard‘s rho等。6. 攻击手法五费马分解与Pollard‘s rho——针对特殊结构的n当模数n的两个素数因子p和q非常接近时一种高效的分解方法叫做费马分解法Fermat‘s Factorization Method。而当n的某个因子具有特殊性质如p-1或p1是光滑数时Pollard‘s p-1算法和Williams‘ p1算法就可能派上用场。6.1 费马分解法当p和q是“邻居”原理如果两个大素数p和q很接近那么它们的平均数(pq)/2与n的平方根sqrt(n)也很接近。设a (pq)/2,b (p-q)/2则有n p*q a^2 - b^2。因此a^2 - n b^2是一个完全平方数。费马分解就是从a ceil(sqrt(n))开始依次检查a^2 - n是否为完全平方数直到找到为止。import gmpy2 from math import isqrt, ceil def fermat_factorization(n): 费马分解法 适用于p和q接近的情况。 print(f“[*] 尝试费马分解 n (位数: {n.bit_length()})...”) a gmpy2.isqrt(n) 1 # 或者 ceil(sqrt(n)) b2 a*a - n while True: b, is_square gmpy2.iroot(b2, 2) if is_square: p a b q a - b if p * q n: print(f“[] 费马分解成功p {p}, q {q}”) return int(p), int(q) # 递增a更新b2 a 1 b2 a*a - n # 可选设置一个上限避免无限循环 if a - gmpy2.isqrt(n) 1000000: # 例如尝试100万次后放弃 print(“[-] 费马分解尝试次数过多放弃。”) return None, None # 示例当p和q非常接近时这个方法极快。 # n 0x… (p和q接近的n) # p, q fermat_factorization(n)6.2 Pollard‘s p-1 分解法原理如果n的一个质因子p满足p-1是“光滑”的即p-1的所有质因子都很小那么我们可以通过计算一个所有小素数乘积的大整数M使得p-1能整除M。根据费马小定理对于任意与p互质的整数a有a^M ≡ 1 (mod p)。这意味着p能整除a^M - 1。因此计算gcd(a^M - 1, n)结果就很有可能是p或者n本身。import gmpy2 from sympy import primerange def pollard_pm1(n, B1000000, a2): Pollard‘s p-1 分解算法 参数: n: 要分解的合数 B: 光滑边界即考虑所有小于等于B的素数 a: 随机选择的底数通常从2开始 返回: 一个非平凡因子或None print(f“[*] 尝试Pollard‘s p-1分解光滑边界B{B}...”) # 1. 计算 M product(prime^e) prime B, e使得 prime^e n M 1 for prime in primerange(2, B1): # 计算 prime^e n 的最大e e int(gmpy2.log(n, prime)) M * pow(prime, e) # 2. 计算 g gcd(a^M - 1, n) g gmpy2.gcd(pow(a, M, n) - 1, n) if 1 g n: print(f“[] Pollard‘s p-1找到因子: {g}”) return g elif g n: print(“[-] 找到的因子是n本身尝试减小B或更换a。”) # 可以尝试减小B或者更换a的值如a3, 5... return None else: print(“[-] 未找到因子可尝试增大B。”) return None # 示例用法通常需要尝试不同的B和a # factor pollard_pm1(n, B100000) # if factor: # p factor # q n // factor6.3 如何选择与组合使用优先尝试费马分解如果发现n的位数是偶数并且sqrt(n)看起来“很整”或者题目提示“两个素数很接近”首先尝试费马分解。它速度很快。p-1/p1攻击作为备选当n无法用常规方法分解且怀疑其因子具有光滑性时使用。在CTF中这类题目有时会故意使用弱素数生成器使得p-1或p1是光滑的。你需要尝试不同的B值从小到大如1e4, 1e5, 1e6。工具整合在实际解题中我通常会写一个“分解综合工具箱”按顺序尝试sympy.factorint- 费马分解 - Pollard‘s p-1 - 在线factordb查询。大部分中等难度的RSA分解题都能被这个组合拳解决。7. 实战问题排查与脚本调试技巧即使掌握了所有攻击方法在实战中依然会遇到各种问题。这里分享一些我踩过的坑和调试技巧。7.1 数据格式处理最常见的“拦路虎”90%的脚本运行错误源于数据格式不对。题目给的参数可能是各种形式十进制整数直接复制到Python中注意Python支持大整数。十六进制字符串以0x开头或\x形式。使用int(hex_str, 16)转换。Base64编码需要先base64.b64decode然后将得到的字节串转为整数。int.from_bytes(bytes_data, ‘big’)。PEM格式公钥文件使用Crypto.PublicKey.RSA.import_key(open(‘pubkey.pem’).read())提取n和e。多行文本或特定格式用正则表达式或字符串处理提取数字。通用处理函数示例import base64 import re from Crypto.PublicKey import RSA def parse_rsa_params_from_string(data_str): 尝试从混乱的字符串中提取n, e, c params {‘n’: None, ‘e’: None, ‘c’: None} # 方法1: 查找十六进制模式 hex_pattern r‘0x[0-9a-fA-F]’ hex_numbers re.findall(hex_pattern, data_str) if len(hex_numbers) 3: # 假设顺序是 n, e, c params[‘n’] int(hex_numbers[0], 16) params[‘e’] int(hex_numbers[1], 16) params[‘c’] int(hex_numbers[2], 16) return params # 方法2: 查找十进制大整数长数字串 dec_pattern r‘\b\d{100,}\b’ # 匹配100位以上的数字 dec_numbers re.findall(dec_pattern, data_str) if len(dec_numbers) 3: params[‘n’] int(dec_numbers[0]) params[‘e’] int(dec_numbers[1]) params[‘c’] int(dec_numbers[2]) return params # 方法3: 尝试解析为PEM if ‘—–BEGIN PUBLIC KEY—–’ in data_str: key RSA.import_key(data_str) params[‘n’] key.n params[‘e’] key.e # c可能需要另外寻找 return params7.2 解密结果不是Flag编码与填充问题成功解密得到整数m后long_to_bytes(m)得到的可能是一串乱码而不是可读的flag。这是因为Flag可能被编码了常见的编码有Base64、Hex、ASCII等。你需要尝试解码。m_bytes long_to_bytes(m) # 尝试UTF-8解码最常用 try: print(m_bytes.decode(‘utf-8’)) except: pass # 尝试Base64解码 import base64 try: print(base64.b64decode(m_bytes).decode()) except: pass # 尝试Hex解码 try: print(bytes.fromhex(m_bytes.decode()).decode()) except: pass可能存在RSA填充如PKCS#1 v1.5或OAEP。纯文本RSA即直接加密m在CTF中很常见但有时也会考察填充。如果解密结果开头有固定的字节如\x00\x02…可能需要手动剥离填充。对于CTF题目描述通常会提示格式如flag{…}或CTF{…}你可以直接在解密后的字节中搜索这些模式。7.3 脚本运行环境与依赖确保你的Python环境安装了必要的库pip install pycryptodome gmpy2 sympy requestspycryptodome提供了Crypto.Util.number模块包含long_to_bytes,inverse,GCD等常用函数。gmpy2处理大整数运算和开方非常高效几乎是CTF密码学脚本的标配。sympy用于分解小整数和素数检测。requests用于在线查询factordb。如果安装gmpy2失败尤其在Windows上可以尝试使用libnum库作为替代它提供了类似的大数运算功能但性能稍差。7.4 思维导图与攻击路径选择面对一个陌生的RSA题目如何快速选择攻击路径我总结了一个简单的决策流程第一步收集信息。提取n, e, c。如果有多个(n,e,c)对记录所有。第二步检查n是否可分解。n很小512位 - 直接用sympy或yafu分解。n能在factordb查到 - 在线分解。p和q很接近 - 尝试费马分解。怀疑p-1光滑 - 尝试Pollard‘s p-1。第三步检查e和c。多组(n, e, c)n相同e不同 -共模攻击。多组(n, e, c)e相同且很小如3n不同 -低加密指数广播攻击。单组e很小如3且c开e次方是整数 -小明文攻击。单组e非常大与n同量级 -维纳攻击。第四步其他特殊攻击。如果以上都不行考虑更复杂的攻击如Coppersmith相关攻击需要用到SageMath这通常出现在更难的题目中。这套流程能解决绝大部分CTF中的RSA题目。最重要的是多练习培养对数字的敏感度。比如看到e65537是常态看到e3就要警惕低指数攻击看到e巨大就要想到维纳攻击。把每种攻击的脚本都保存好整理成自己的工具箱下次解题时就是组合拳出击。