企业官网建设流程全解析

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的公钥包含模数n（n = p * q，p和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、最后解密c（m ≡ c^d mod n）就是顺理成章的事情。在CTF中，这类题目通常有两种表现形式：

1. 故意使用小素数：出题人为了降低难度（或是故意设置漏洞），使用了长度很短的p和q，导致n可能只有256位、512位甚至更短。在现代计算机上，分解这样的n是瞬间完成的。
2. 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, “onefile=temp.txt”] result = subprocess.run(cmd, capture_output=True, text=True, timeout=30) # 解析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, timeout=10) 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 实操心得与避坑指南

1. 优先检查n的长度：拿到题目，第一件事就是用n.bit_length()看看n有多少位。如果小于512，直接本地分解；如果在512-768之间，可以尝试yafu；如果更大，就要考虑其他攻击路径了。
2. factordb的妙用：很多CTF题目的n是故意从某些已知素数生成的，或者直接使用了往年题目出现过的n。因此，将n提交到factordb.com是一个成本极低且可能瞬间解题的操作，务必养成习惯。
3. 注意n的格式：题目给的n可能是10进制整数、16进制字符串（以0x开头）、或者Base64编码。c和e也可能如此。在代入脚本前，务必统一转换成Python的int类型。一个常见的错误是忘记转换类型，导致分解或解密失败。
4. 分解后的验证：得到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中，共模攻击的题目通常有以下特征：

1. 题目描述或附件中明确给出了两组或多组公钥和密文。这是最明显的信号。
2. 这些公钥的模数n完全相同。你需要仔细检查，有时n会以文件（pubkey1.pem,pubkey2.pem）形式给出，需要用openssl或Python的Crypto.PublicKey.RSA库提取。
3. 加密指数e不同，但通常都比较常规（如65537, 10001, 3等）。
4. 密文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（如e=3），但**不同的模数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__”: # 假设e=3，有三组不同的(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次方根是否为整数。例如e=3时，直接计算m = round(c ** (1/3))并验证m^3 == c是否成立。

def small_message_attack(c, e, n=None): """ 小明文攻击 当 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 None

4.3 实操注意事项

1. 广播攻击的密文数量：理论上需要至少e组密文。对于e=3，至少需要3组不同的(n_i, c_i)。但有时两组也可能成功，如果m足够小的话。
2. 开方失败的处理：如果gmpy2.iroot失败，可能是因为m^e仍然大于所有n的乘积N，或者m本身不是完美的e次方数（比如m被填充了）。这时需要考虑其他攻击，或者检查是否遗漏了密文。
3. e=3是最常见的情况：因为e=3加密速度最快，历史上被广泛使用，也因此在CTF中成为高频考点。看到e=3，一定要优先检查是否可以应用此类攻击。

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的某个渐进分数（convergent）k/d会非常接近e/n。更具体地说，攻击目标是找到满足以下等式的k和d：e*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: # 跳过 k=0 的情况 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 - (p+q) + 1，可以建立一元二次方程 # sum = p+q = 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 适用条件与识别特征

维纳攻击并非万能，它有明确的适用条件：

1. d必须足够小：这是前提。通常题目会给出一个非常大的e（与n位数相近），这暗示着d可能很小，因为e和d在模φ(n)下互为逆元，一个很大往往意味着另一个很小。
2. q < p < 2q：素数p和q不能相差太悬殊，这是维纳攻击原始论文中的假设，大多数常规RSA生成都满足。
3. 攻击的典型场景：题目只给了(n, e, c)，n很大无法分解，e也很大。你尝试了低指数攻击、共模攻击都不行，这时就应该考虑维纳攻击。

避坑指南：维纳攻击脚本计算量很小，几乎瞬间完成。如果脚本运行后没有输出结果，大概率意味着d不满足攻击条件。此时不要纠结，应转向其他攻击方法，如接下来的费马分解或Pollard‘s rho等。

6. 攻击手法五：费马分解与Pollard‘s rho——针对特殊结构的n

当模数n的两个素数因子p和q非常接近时，一种高效的分解方法叫做费马分解法（Fermat‘s Factorization Method）。而当n的某个因子具有特殊性质（如p-1或p+1是光滑数）时，Pollard‘s p-1算法和Williams‘ p+1算法就可能派上用场。

6.1 费马分解法：当p和q是“邻居”

原理：如果两个大素数p和q很接近，那么它们的平均数(p+q)/2与n的平方根sqrt(n)也很接近。设a = (p+q)/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, B=1000000, a=2): """ 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, B+1): # 计算 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的值（如a=3, 5...） return None else: print(“[-] 未找到因子，可尝试增大B。”) return None # 示例用法：通常需要尝试不同的B和a # factor = pollard_pm1(n, B=100000) # if factor: # p = factor # q = n // factor

6.3 如何选择与组合使用

1. 优先尝试费马分解：如果发现n的位数是偶数，并且sqrt(n)看起来“很整”，或者题目提示“两个素数很接近”，首先尝试费马分解。它速度很快。
2. p-1/p+1攻击作为备选：当n无法用常规方法分解，且怀疑其因子具有光滑性时使用。在CTF中，这类题目有时会故意使用弱素数生成器，使得p-1或p+1是光滑的。你需要尝试不同的B值（从小到大，如1e4, 1e5, 1e6）。
3. 工具整合：在实际解题中，我通常会写一个“分解综合工具箱”，按顺序尝试：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 params

7.2 解密结果不是Flag：编码与填充问题

成功解密得到整数m后，long_to_bytes(m)得到的可能是一串乱码，而不是可读的flag。这是因为：

1. 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

2. 可能存在RSA填充：如PKCS#1 v1.5或OAEP。纯文本RSA（即直接加密m）在CTF中很常见，但有时也会考察填充。如果解密结果开头有固定的字节（如\x00\x02…），可能需要手动剥离填充。对于CTF，题目描述通常会提示格式，如flag{…}或CTF{…}，你可以直接在解密后的字节中搜索这些模式。

7.3 脚本运行环境与依赖

确保你的Python环境安装了必要的库：

pip install pycryptodome gmpy2 sympy requests

• pycryptodome：提供了Crypto.Util.number模块，包含long_to_bytes,inverse,GCD等常用函数。
• gmpy2：处理大整数运算和开方非常高效，几乎是CTF密码学脚本的标配。
• sympy：用于分解小整数和素数检测。
• requests：用于在线查询factordb。

如果安装gmpy2失败（尤其在Windows上），可以尝试使用libnum库作为替代，它提供了类似的大数运算功能，但性能稍差。

7.4 思维导图与攻击路径选择

面对一个陌生的RSA题目，如何快速选择攻击路径？我总结了一个简单的决策流程：

1. 第一步：收集信息。提取n, e, c。如果有多个(n,e,c)对，记录所有。
2. 第二步：检查n是否可分解。
   • n很小（<512位）？ -> 直接用sympy或yafu分解。
   • n能在factordb查到？ -> 在线分解。
   • p和q很接近？ -> 尝试费马分解。
   • 怀疑p-1光滑？ -> 尝试Pollard‘s p-1。
3. 第三步：检查e和c。
   • 多组(n, e, c)，n相同，e不同？ ->共模攻击。
   • 多组(n, e, c)，e相同且很小（如3），n不同？ ->低加密指数广播攻击。
   • 单组，e很小（如3），且c开e次方是整数？ ->小明文攻击。
   • 单组，e非常大（与n同量级）？ ->维纳攻击。
4. 第四步：其他特殊攻击。如果以上都不行，考虑更复杂的攻击，如Coppersmith相关攻击（需要用到SageMath），这通常出现在更难的题目中。

这套流程能解决绝大部分CTF中的RSA题目。最重要的是多练习，培养对数字的敏感度。比如，看到e=65537是常态，看到e=3就要警惕低指数攻击，看到e巨大就要想到维纳攻击。把每种攻击的脚本都保存好，整理成自己的工具箱，下次解题时就是组合拳出击。