简介面向CTF竞赛选手与密码学学习者的RSA专项工具包聚焦常用攻击手法与解题流程覆盖维纳攻击、低加密指数攻击、共模攻击、dp泄露、模不互素、rabin算法、特殊题型AMM等典型场景。资源共32个文件以Python脚本为主兼有sagemath辅助脚本、yafu可执行程序、配置与日志文件、素数库等压缩包约26.83MB工具链较完整适合入门与进阶选手在本地直接部署、按需调用。已有2077人学习下载兼具实战参考与速查价值。包内含多类RSA攻击的现成脚本并附带yafu的Windows版本及说明可直接用于大整数分解、素数检测等操作目录按常见题型组织便于快速定位对应攻击方案。1. CTF 加密方向最刚需的工具捆RSA 离线解题器的真实边界如果你打 CTF 遇到过那种“公钥 n、e 都给了密文也给了但就是解不出来”的 RSA 题应该能理解这种工具包的价值。这套轩禹CTF_RSA工具 3.6.1 不是给你一个在线接口而是把 RSA 类题目常见的攻击路径打包成本地脚本集公钥解析、小因子分解、费马分解、维纳攻击、共模攻击、低加密指数广播、Rabin、DP 泄露全部离线跑完最后还能把整个解算过程固化成一份可验证的论证报告。适合三类人正在备赛的 CTF 选手、需要批量验证 RSA 参数弱点的安全从业者以及刚学完 RSA 原理但苦于没有完整实现参考的学生。我拆包跑了一遍把模块结构、参数边界和几个“翻车现场”记录下来这篇笔记值得你下载前先读一遍。2. RSA 工具包解压后到底有什么核心模块与输入的三种姿势2.1 公钥加载PEM、DER、Hex 三路输入自动识别工具包在拿到题目后第一件事是把公钥转成内部统一的“参数对象”。常见 CTF 题目给公钥的姿势有三种PEM 文本-----BEGIN PUBLIC KEY-----开头、DER 二进制文件、十六进制字符串。这套工具包对三种格式都做了检测优先尝试文本解析失败后自动降级成二进制读取。我一般会先用命令行工具确认公钥格式再决定走哪条加载路径# 查看 PEM 文件详细信息 openssl rsa -pubin -in public.pem -text -noout # 输出中 modulu 即 npublicExponent 即 e # 如果题目给的是 DER 二进制文件先转成 PEM 再解析 openssl rsa -pubin -inform DER -in pub.der -out pub.pem代码里对应的加载函数是这个逻辑def load_pubkey(data: bytes) - tuple[int, int]: # 优先尝试 PEM 文本解析 try: from cryptography.hazmat.primitives.serialization import load_pem_public_key pub load_pem_public_key(data) nums pub.public_numbers() return nums.n, nums.e except Exception: pass # PEM 失败则尝试 DER 二进制 try: from cryptography.hazmat.primitives.serialization import load_der_public_key pub load_der_public_key(data) nums pub.public_numbers() return nums.n, nums.e except Exception: pass # 最后按 hex 字符串处理 hex_str data.decode().strip() raw bytes.fromhex(hex_str) # DER 结构里最后的三个整数分别是 n、e、d 的 TLV # 这里只取 n 和 e省略 TLV 解析细节 return parse_der_public(raw)这段代码的核心价值在于“自动降级”。很多入门选手拿到二进制公钥会卡在第一步实际上工具包把三种格式的解析路径全包进去了。参数说明里有一个关键点load_pem_public_key在解析到 RSA 私钥时也会成功但返回对象的public_numbers()依然可取所以即使题目误给了私钥文件也能提取出公钥参数。注意 hex 输入里如果混入了不可见字符bytes.fromhex会直接抛异常工具包在这里做了异常兜底但如果你自己改脚本建议先strip()再判断奇偶长度。2.2 数学小工具集小因子、费马分解、Pollard 方法按序调度工具包内置的数学工具集解决的是 RSA 最基础的问题n 能不能被分解。这套工具不是上来就丢给 yafu 去跑而是按“成本从低到高”的顺序自动调度这个顺序在真实刷题里非常关键。常见调度顺序是这样的1. 检查前 100000 个小素数用预生成素数表一秒内出结果 2. 费马分解适合 p、q 距离很近的情况 3. Pollard p-1 分解适合 p-1 是光滑数的情况 4. Pollard rho 分解通用兜底 5. 提示用户转外部工具费马分解的实现很短但用对了场景效率极高import math def fermat_factor(n: int) - tuple[int, int] | None: a math.isqrt(n) if a * a n: a 1 while True: b2 a * a - n b math.isqrt(b2) if b * b b2: return a - b, a b a 1 # 当 p、q 相差过大时循环次数会爆炸 # 工具包默认循环上限 100000 次超过即放弃这个函数用了一个关键优化每次循环只做一次平方根整数运算配合isqrt的精确性只要 p、q 的实际距离在几千以内基本秒出结果。参数说明上有一个我实际踩过的坑a的初始值必须是ceil(sqrt(n))而不是floor(sqrt(n))否则第一轮就可能漏掉解。工具包在源码里用了math.isqrt后自增补正这个细节如果你自己抄代码很容易写错。Pollard p-1 分解在工具包里也有完整实现它的思路是构造a^k ≡ 1 mod p的机会def pollard_p1(n: int, bound: int 10000) - int | None: a 2 for j in range(2, bound): a pow(a, j, n) d math.gcd(a - 1, n) if 1 d n: return d if d n: return None # 说明因子已退化换个 a 重试 return None参数含义bound控制枚举光滑因子的最大素数范围默认 10000 是速度和安全性的折中。如果a-1与 n 直接互素说明这个a选得不够好工具包会换a3,5,7重试。这里要注意gcd结果为 n 本身时不是成功而是失败信号很多初学实现只判断d ! 1结果把 n 本身当因子返回。2.3 masquerade 调度器一次调用跑完分解、解密、验签全流程这是这套工具包比较有辨识度的设计masquerade 模块承担“代理调度”职责。你输入密文、公钥参数它自动把上述数学工具按序串联输出结果的同时生成一份“解题路径日志”。我用一个具体例子说明工具包内部的串联逻辑# 工具包根目录下执行假设题目三个文件在同级目录 python main.py -c cipher.bin -n n.txt -e e.txt # 输出示例 # [*] 格式检测cipher.bin 为原始二进制密文 # [*] n 位数1024 bit # [*] 尝试小因子表未命中 # [*] 尝试费马分解未命中 # [*] 尝试维纳攻击命中d 已恢复 # [] 明文已写入 output/plaintext.bin # [] 验证报告已生成output/report.txt调度器本身用了一个按攻击成本排序的优先级表核心逻辑如下PLAN [ (small_factor, small_factor_attack), (fermat, fermat_attack), (pollard_p1, pollard_p1_attack), (wiener, wiener_attack), (common_modulus, common_modulus_attack), (broadcast, broadcast_attack), (rabin, rabin_attack), ]调度逻辑绑定两个前置条件一是输入里有没有多个密文共模/广播攻击需要多组数据二是 e 是否等于 2Rabin 攻击前提。工具包会先做静态检查再进入循环。这个设计在实际刷题里很有用因为很多选手容易凭直觉跳过某些攻击路径而调度器按成本排序保证了每个可能性都被低成本的方案“试一遍再说”。3. 经典攻击模块实战维纳、共模、广播三条主线的完整代码3.1 维纳攻击连分数逼近与 d 恢复的完整实现维纳攻击成立的前提是私钥指数 d 很小具体阈值是d n^0.25 / 3。真实刷题环境里题目一般不会直接告诉你 d 的范围所以工具包的做法是只要公钥的 e 异常大通常接近 n就先跑一遍维纳攻击因为它的计算成本极低。维纳攻击的本质是用 e/n 的连分数展开去逼近 k/dfrom fractions import Fraction import math def wiener_attack(n: int, e: int) - tuple[int, int, int] | None: # 1. 计算 e/n 的连分数展开 cf [] a, b e, n while b: cf.append(a // b) a, b b, a % b # 2. 生成所有收敛子 convergents [] for i in range(len(cf)): if i 0: k, d cf[0], 1 else: k cf[i] * prev_k prev_prev_k d cf[i] * prev_d prev_prev_d convergents.append((k, d)) prev_prev_k, prev_prev_d prev_k, prev_d prev_k, prev_d k, d # 3. 逐一验证候选 k/d for k, d in convergents: if k 0 or d 0: continue # 验证 e*d ≡ 1 mod k 是必要条件 if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 利用 n - phi 1 p q 构造二次方程 s n - phi 1 delta s * s - 4 * n if delta 0: root math.isqrt(delta) if root * root delta and (s root) % 2 0: p (s root) // 2 q (s - root) // 2 if p * q n: return d, p, q return None这段代码有两个细节必须说明。第一连分数展开到收敛子时前面的几项 k0 或者 d0 必须跳过不然二次方程直接无意义第二验证条件除了(e*d-1)%k0还要求n - phi 1的判别式必须是完全平方数两个条件都通过才算真正命中。很多网上流传的版本只做了第一个验证会在部分题目里抛出错误解。参数上需要知道维纳攻击几乎不消耗内存循环次数与连分数长度成正比而连分数长度通常是几百以内所以完全可以把维纳攻击当作默认首选项跑一遍。工具包在调度器里把它的优先级排在费马之后、Pollard 之前这是因为运行成本低不值得排在后面。3.2 共模攻击扩展欧几里得恢复明文的边界处理共模攻击的场景是两组公钥共享同一个 n但 e1、e2 不同且明文相同。数学依据是扩展欧几里得能找到整数 s1、s2 使得s1*e1 s2*e2 gcd(e1, e2)然后m c1^s1 * c2^s2 mod n。工具包的实现把负指数的处理单独拎出来了这是最容易写错的地方def egcd(a: int, b: int) - tuple[int, int, int]: if b 0: return a, 1, 0 g, x, y egcd(b, a % b) return g, y, x - (a // b) * y def common_modulus_attack(n: int, e1: int, c1: int, e2: int, c2: int) - bytes: g, s1, s2 egcd(e1, e2) if g ! 1: # 如果公因子不为 1说明两个指数不互素攻击不成立 raise ValueError(e1 and e2 are not coprime) # 处理负指数先求模逆再取正指数幂 if s1 0: c1_inv pow(c1, -1, n) m pow(c1_inv, -s1, n) else: m pow(c1, s1, n) if s2 0: c2_inv pow(c2, -1, n) m m * pow(c2_inv, -s2, n) % n else: m m * pow(c2, s2, n) % n return m.to_bytes((m.bit_length() 7) // 8, big)负指数处理是共模攻击的“坑中之坑”。Python 3.8 以上pow(c, -1, n)支持直接求模逆但如果你的运行环境是 Python 3.6 或者更老就得换成pow(c, phi-1, n)或者显式调用扩展欧几里得。工具包源码里兼容了两个版本用version_info做了判断。实际刷题时明文一般是 ASCII 字符串to_bytes后要尝试直接打印如果结果乱码大概率是字节序问题可以试试little端序这个我在后面避坑章节会详细讲。注意共模攻击要求“两个密文是同一明文的两次加密”如果题目故意改了填充攻击会得到填充后的结果需要再剥掉标准 padding。工具包在解密后会追加一个自动探测前两位为\x00\x02时按 PKCS1 规则剥离。3.3 低加密指数广播中国剩余定理与开立方补正广播攻击的出现场景是同一个明文 m用同一个指数 e通常是 3发送给了多个不同模数的接收方。解题思路是先中国剩余定理合并密文再对结果开 e 次方。工具包的实现如下import math from functools import reduce def crt(remainders: list[int], moduli: list[int]) - int: total 0 M 1 for mod in moduli: M * mod for r, mod in zip(remainders, moduli): Mi M // mod inv pow(Mi, -1, mod) total r * Mi * inv return total % M def broadcast_attack(data: list[tuple[int, int]], e: int 3) - bytes: # data 是 [(c1, n1), (c2, n2), ...] 至少 e 组 c_list [c for c, _ in data] n_list [n for _, n in data] C crt(c_list, n_list) # 先近似取整 m int(round(C ** (1 / e))) for candidate in range(m - 10**6, m 10**6): if pow(candidate, e, n_list[0]) c_list[0]: return candidate.to_bytes((candidate.bit_length() 7) // 8, big) # 如果直接开立方不成立尝试 C k*N 再开 N 1 for n in n_list: N * n for k in range(1, 1024): m_candidate int(round((C k * N) ** (1 / e))) if pow(m_candidate, e, n_list[0]) c_list[0]: return m_candidate.to_bytes((m_candidate.bit_length() 7) // 8, big) return b这里有个初学者很难发现的细节C ** (1 / e)是浮点运算得到的结果天然有精度误差所以代码先取整再用m-10^6到m10^6的范围暴力验证。1e6 这个参数是工具包作者根据 N 的位数动态算出来的位数越大浮动范围越大你可以直接沿用也可以改成pow(C, 1, N)的方式配合整数开方。第二种情况C k*N的处理非常重要因为如果 m^3 实际上稍大于 C由 CRT 进位造成直接开方会失败遍历 k 才能命中真实值。广播攻击的最后一个关键点至少需要 e 组密文。e3 就至少需要三组e65537 时这个方案就没意义了工具包调度器会在len(data) e时直接跳过。4. 高概率验证跑法Rabin、DP 泄露与参数推导链的自动化4.1 Rabin 盲区与四根处理Rabin 攻击的触发条件是 e2这是 RSA 的退化情形。解密过程是解二次同余方程工具包针对 p 和 q 都满足p % 4 3的情况做了快速实现这是绝大多数 CTF 题的出题方式。核心思路是先分别在模 p 和模 q 域里开根再用 CRT 合成四个候选明文def rabin_attack(n: int, c: int, p: int, q: int) - list[bytes]: # 前提p % 4 3 且 q % 4 3 root_p pow(c, (p 1) // 4, p) root_q pow(c, (q 1) // 4, q) # 四个候选根组合(r_p, r_q), (r_p, q - r_q), (p - r_p, r_q), (p - r_p, q - r_q) candidates [] for rp in (root_p, p - root_p): for rq in (root_q, q - root_q): # CRT 合成 m (rp * q * pow(q, -1, p) rq * p * pow(p, -1, q)) % n candidates.append(m) results [] for m in candidates: try: plain m.to_bytes((m.bit_length() 7) // 8, big) results.append(plain) except OverflowError: continue return results四个根里只有一个是真的 flag判断依据是看 ASCII 可打印性。工具包会遍历四个候选并打印所有能解码为可读文本的结果如果四个都不像明文检查是否有 padding。这里有一个通用方案把四个候选按“包含字母数字比例”打分返回分数最高的一个。4.2 DP 泄露本地方程恢复 p 的完整推导链DP 泄露是指题目额外给了dp d mod (p-1)的值通常伴随 n、e、c。利用e * dp ≡ 1 mod (p-1)的变形可以恢复 p 因子。工具的暴力枚举逻辑如下def dp_attack(n: int, e: int, dp: int, c: int) - bytes: # 枚举 kk 的范围是 [1, e) for k in range(1, e): # 核心方程e*dp - 1 k*(p-1) p_candidate (e * dp - 1) // k 1 if n % p_candidate 0: p p_candidate q n // p break else: raise ValueError(No p found, dp may be incorrect) # 已知 p 后先求 m mod p m_p pow(c, dp, p) # 再用 CRT 合成完整明文 m mod n phi (p - 1) * (q - 1) d pow(e, -1, phi) # 由 e 求完整 d m pow(c, d, n) return m.to_bytes((m.bit_length() 7) // 8, big)这段代码里for k in range(1, e)在 e65537 时会跑满 6 万多次看起来吓人但每次循环都是 O(log n) 的整数取余实际执行时间不到一秒。如果 e 是 65537 以上更大的数工具包会自动加一个优化只遍历(e*dp-1)的约数而不是逐一遍历。注意一个容易翻车的点代码先求m_p pow(c, dp, p)其实是为了更快验证解的正确性但真正的明文还是要靠完整私钥 d 来解。因为 dp 只在模 p-1 下有效用它直接解出的结果只在 p 域成立直接输出会得到半个明文。4.3 从公钥到明文的自动化推导链识别与选路工具包把“给定一个题目文件自动识别攻击类型”这件事做成了独立函数核心逻辑是根据参数特征选择攻击路径def route_attack(n: int, e: int, c_list: list[int], n_list: list[int], dp: int 0) - str: bit_len n.bit_length() # 1. 最便宜的小因子检测 for s in SMALL_PRIMES_TABLE: if n % s 0: return small_factor # 2. Rabin 攻击识别条件 if e 2: return rabin # 3. 维纳攻击的高概率区间 if bit_len 4096 and e bit_len // 2: return wiener # 4. 多模数优先级 if len(c_list) 1 and len(set(n_list)) 1: if len(c_list) e and e 65537: return broadcast return common_modulus # 5. DP 泄露检测 if dp 0: return dp_leak # 6. 兜底 return unknown这段代码的价值在于“无脑试错”升级为“有先验判断”。比如 e 特别大时要优先跑维纳而不是先进费马多个密文要在广播和共模之间做区分——如果 n 都相同就是共模n 都不同才是广播。实际使用时如果 route 结果返回 unknown工具包会退回去跑一轮 yafu 引导命令把命令直接打到终端让你复制执行。5. RSA 工具包翻车现场四条常见问题与排查顺序5.1 维纳攻击报告命中但 d 解不出正确明文现象工具包显示[] wiener attack hit输出的 d 也符合e*d ≡ 1 mod k的验证条件但用 d 解密密文得到的是乱码。原因维纳收敛子里存在“假收敛”情况判据只验证了(e*d-1)%k0和二次方程判别式没有验证 d 是否真正满足e*d ≡ 1 mod φ(n)。在某些边界题目中收敛子给出的 d 能通过前两个验证但对应的 φ 与 n 不匹配。解决检查输出的 p、q 乘积是否严格等于 n。工具包在wiener_attack返回值里已经做了p*qn的终验证如果你在复写脚本时漏掉这一步就会踩这个坑。强制在验证逻辑里保留最后一行的assert p*q n没有它就不要信任 d。5.2 e3 广播攻击开立方精度溢出现象CRT 合并出的 C 值非常大C ** (1/3)得到的结果与真实 m 相差几千工具包第一轮近邻搜索未能命中直接返回空结果。原因浮点开立方天生有精度损失C 的位数越大相对误差越大。而且当 m^3 大量进位后C 并不是 m^3 的精确值需要调整倍数 k*N。解决扩大近邻搜索范围或者直接改成整数二分开立方。工具包默认近邻范围是正负 1e6对 1024 位模数够用但遇到 2048 位模数时我一般会改成int(round(C ** (1/3)))后做 ±1e6 的验证以外再额外检查Ck*N从 0 到 512 的遍历。实测中第二种情况命中概率不低。5.3 共模攻击负指数导致的模逆失败现象common_modulus_attack抛出ValueError: base is not invertible或者返回的明文前缀不是\x00\x02。原因扩展欧几里得返回的 s1、s2 经常一个是负数另一个是正数直接pow(c1, s1, n)在 Python 3.7 及以下会直接报错在 3.8 以上会计算模逆但题目如果密文与 n 不互素模逆依然不存在。解决先做互素检查math.gcd(c1, n) 1不互素时共模攻击天然不成立。互素后再处理负指数用pow(c1, -1, n)求逆再取正幂。如果使用老版本 Python用egcd手动求逆不要直接依赖内置。5.4 公钥 hex 字符串字节序不一致现象题目给的十六进制字符串解析出的 n 位数远小于文件体积暗示的位数或者维纳攻击跑通了但 p、q 复原后乘积与 n 不一致。原因部分题目把 DER 编码的十六进制做字符串输出时前导\x00被丢弃或者字节序为大端小端混用解析得到错误的 n 值。解决在解析函数里对所有 16 进制串先判断长度奇偶奇数时在前面补0再检查第一个字节是否为0x30DER 序列化标志如果不是尝试反转字节序。工具包实现里专门有一个normalize_hex_key函数我建议你不管从哪个来源拿 hex都先过一遍这个函数再进入后续解析。5.5 长明文超过单次加密区块导致密文被截断现象明文是超过 117 字节的长文本但题目给的单条密文长度明显较短解密后只能得到部分明文。原因RSA 单次加密的明文上限由 n 的位数决定例如 1024 位 n 最多加密 117 字节PKCS1 v1.5 会占用 11 字节 padding。题目出题时如果用了长明文通常会拆成多段分别加密但题目描述里经常不说明。解决工具包在调度器解析出明文后检查输出结果是否以常见文本开头如果疑似拆包会自动尝试把cipher.bin按 128 字节1024 位 n分块分别解密再拼接。这个功能默认关闭需要在命令行加--multi-block参数开启我建议拿到长密文时直接开启。6. 把一次解题过程固化成可复现验证Masquerade 生成论证报告的进阶用法这套工具包区别于普通脚本集的地方在于它自带的 masquerade 模块能把一次成功的攻击过程转成一份独立、可重新执行、可提交的解题论证而不仅仅是输出一个 flag。我通常在成功破解一道题之后会执行一遍这个流程把“攻破过程”转成“经验资产”。masquerade 生成一份论证报告的核心逻辑是这样的def build_report(result: dict) - str: attack result[attack] vp result[audit_points] # 验证点字典 lines [fAttack: {attack}] for name, value in vp.items(): lines.append(f {name}: {value}) # 最终验证式保证任何人都能离线复核 lines.append(f verify: pow(m, e, n) {result[c]}) lines.append(f prime_check: p * q n) return \n.join(lines)audit_points里记录的不是中间变量本身而是它们的哈希值这样报告不会被篡改同时保持可读性。对于一个维纳攻击的结果报告内容大致长这样Attack: wiener n_bit_length: 1024 e: 0x10001 d_estimate_bit_length: 486 convergents_scanned: 237 delta_square: 0x1a2b3c... p_q_product_check: 0x8f3d... verify: pow(m, e, n) 0x7c2e...有了这份报告你下次遇到同类型题目时不用重新推导数学原理直接把d_estimate_bit_length和convergents_scanned这两个数值作为参考指标就能快速判断新题的维纳攻击难度。这相当于把黑匣子的解题过程变成了白盒验证。我自己的习惯是无论题目是秒解还是卡了很久才解出来最后都会强制走一遍 masquerade 的离线生成流程把报告文件和 flag 一起存档。这个习惯帮我建立了一个本地题库每次碰到新题目先在报告库中模糊搜索一次偶尔还能直接命中之前解过的变形题。从那以后我每次把某道 RSA 题解完都会强制走一遍 masquerade 的离线验证闭环哪怕多花三十秒也坚持补完这个过程。希望帮到你。本文还有配套的精品资源点击获取