做 CTF 密码学的时候只要看到n、e、c三个字母一起出现基本上就能判断这是 RSA 题。而题目名里带factor的往往直接把任务说清楚了不用绕目标就是把模数n拆开。d3factor就是典型的一类它不考花哨的协议构造而是考你对 RSA 底层安全假设的理解——n p * q一旦被分解私钥d立刻可以算出来明文自然就到手了。这类题目在 CTF 里出现频率极高几乎每场比赛的 Crypto 签到或中等题都会有一个变种。写这篇是想把这类分解 n的题系统地梳理一遍。很多刚接触 CTF 的朋友拿到一道 factor 类题第一反应是这是不是要用什么高深算法然后去翻各种 writeup结果发现别人几行脚本就跑出来了自己却连该用哪种方法都判断不了。问题不在于算法难而在于没有建立从题面信息推断该用哪种分解方法的判断链路。这篇会以d3factor为引子把 RSA 分解类题目常见的几种解法、判定条件、可直接复用的脚本以及我在实际比赛中踩过的坑一次讲清楚。无论你是刚入门 CTF 的新手还是想补全 RSA 攻击面的老手应该都能从里面拿到点东西。1. d3factor 这类题到底在考什么1.1 题目名字里藏着出题人的暗示CTF 题目命名往往不是随便取的。d3factor这个名字d3是那场比赛的系列前缀factor则直白地告诉你核心动作是因式分解。在 RSA 的语境下因式分解的对象只有一个就是模数n。出题人敢把答案写在题目名里说明这题的重点不在于你知不知道要分解而在于你能不能用对的方法在合理时间内分解出来。这其实是 CTF 密码学的一个常见套路真正的难点是已知条件下的分解。纯粹的 2048 位 RSA 模数以目前的公开算力是分解不动的但只要出题人在生成p、q时留下了某种结构性弱点分解就变得可行。d3factor这一类的本质就是让你去找到那个弱点。我见过不少新手拿到题的第一件事是去网上找RSA 分解工具找到一个跑一个跑不出来就卡住。这种盲试效率极低。正确的做法是先读题面把题目给的所有量列出来然后反推它在暗示哪种结构弱点。1.2 只要能分解 n剩下的都是体力活先把 RSA 的基本关系摆清楚这样后面无论用哪种方法分解出p、q你都知道接下来怎么走设n p * q其中p、q是两个大素数。公钥指数e通常取 65537。私钥d满足e * d ≡ 1 (mod φ(n))其中 φ(n) (p - 1) * (q - 1)只要知道p和q就能算出φ(n)进而用扩展欧几里得算法求出d再对密文c做一次模幂运算pow(c, d, n)就得到明文。整个过程是确定性的没有任何技巧可言。所以 factor 类题目的所有难点都集中在如何从n得到p、q这一步。分解出来之后解密的代码几乎是模板from Crypto.Util.number import long_to_bytes, inverse p ... # 分解得到的因子 q n // p phi (p - 1) * (q - 1) d inverse(e, phi) m pow(c, d, n) print(long_to_bytes(m))我建议把这段存成一个本地小工具每次只改p的值。比赛中时间宝贵别在这种体力活上浪费。1.3 题目一定留了缝五种常见弱点RSA 模数在什么情况下能被人为分解总结下来CTF 里高频出现的大致有这几种结构性弱点每一种对应一种攻击方法弱点结构对应攻击典型判定信号p与q非常接近Fermat 分解n开方后附近能凑出平方差p - 1是光滑数Pollards p-1p - 1只有小素因子已知p的高位或低位Coppersmith题面给出了部分比特私钥d很小Wiener / 连分数e很大接近n多个n共享同一个素因子模不互素给了两组以上(n, e, c)d3factor这一题属于其中某一种的具体实现但我不想把这篇文章写成只针对一道题的 writeup。更有价值的做法是把这套判断链路建立起来这样无论遇到哪道 factor 题你都能在几分钟内定位到该用哪种方法。下面几节会逐一展开每种方法的原理、判定和可复用的代码。2. 拿到题面先做信息提取n、e、c 里藏着线索2.1 先量一遍 n 和 e 的体格在动手跑任何脚本之前先做个简单的体检。我通常会看三个数n的位数。是 1024 位、2048 位还是更小位数决定了你能用多大代价去试错。e的大小。e 65537是最常见的情况如果e特别大比如接近n的规模那几乎可以立刻锁定 Wiener 攻击如果e 3那要先试试能不能直接开三次方。c的位数。正常情况下c和n同量级如果c明显比n小很多可能是明文很短、m^e n直接开方就出结果了。这几个数值看一眼题面给的常量就心里有数了。举个判断逻辑如果e是一个 1000 多位的大数和n差不多大那基本不用犹豫去写 Wiener 攻击的连分数脚本如果e 3先做低指数检查。这些一眼判断能帮你省掉大量试错时间。2.2 用几行代码先跑一轮基础筛查体检完之后我习惯先跑一轮很便宜的自动化检查。这一步的目的是排除那些送分但容易漏掉的情况。from math import gcd, isqrt from gmpy2 import is_prime, is_square # 1. n 是否本身就是素数出题人偷懒或故意 print(n is prime:, is_prime(n)) # 2. n 是否是完全平方p q 的退化情况 r isqrt(n) print(n is perfect square:, r * r n) # 3. n 是否能被小素数整除 for p in range(2, 100000): if n % p 0: print(small factor found:, p) break这段代码虽然简单但我确实见过有题目p q生成时手滑或者n被一个三四十位的素数整除的情况。先跑一遍成本极低不跑白不跑。还有一种情况题目给了多组(n, e, c)。这时候第一个念头应该是做两两gcdfrom math import gcd import itertools for (n1, _), (n2, _) in itertools.combinations(pairs, 2): g gcd(n1, n2) if 1 g n1: print(shared factor:, g) break共享素因子是出题人最容易犯的错也最容易利用。如果有两组n的gcd大于 1那么这一组题的n全部可以瞬间分解。2.3 从题目额外给了什么倒推题型这是我认为最关键的一步也是最容易被忽略的。CTF 出题人在 RSA 题里如果额外给了某个量那个量往往就是解题的钥匙。给了p的高几位 → 几乎一定是 Coppersmith 的已知高位攻击给了d的低几位 → Coppersmith 的已知低位或者偏序攻击给了d1、d2这种一组的量 → 考虑 Common Private Exponent 或者相关攻击给了两组e但同一组n→ 考虑共模攻击什么都不额外给就给了n、e、c→ 那大概率是p、q结构问题接近、光滑回到 Fermat 或 Pollard p-1。d3factor的结构属于最后一种——表面上只给了标准的 RSA 三件套但实际上p、q的生成方式里有结构弱点。这种情况下就要靠下面的几种方法逐一排查。我个人的排查顺序是先 Fermat最便宜再 Pollard p-1次便宜再看 Coppersmith需要想清楚最后才考虑其它。顺序很重要因为便宜的方法失败也不会浪费多少时间而复杂方法想错了会很耗神。3. Fermat 分解p 与 q 靠近时最省事的一刀3.1 平方差一个漂亮的恒等式Fermat 分解的核心是一个初中就学过的恒等式n a² - b² (a - b)(a b)如果p、q是两个奇数素数除了 2 都是奇数那么令a (p q) / 2、b (q - p) / 2就恒有n a² - b²。Fermat 分解的思路是从a ceil(sqrt(n))开始逐次递增a每次检查a² - n是不是完全平方。如果恰好是某个整数b的平方那么p a - b、q a b分解完成。这个方法的效率取决于什么取决于a - ceil(sqrt(n))也就是(p q)/2 - sqrt(p*q)。这个差值本质上衡量的是p和q的接近程度。如果p、q差得很远比如一个 200 位、一个 800 位那么p、q的接近程度很差需要迭代的次数是指数级的根本跑不动但如果p、q只差个几百位以内的量级能达到完全平方的迭代次数就很有限了。3.2 判定 p、q 是否靠得足够近理论上如果|p - q| n^(1/4)Fermat 分解一定能很快奏效。这是经典的结论p、q的差小于n的四次方根时从sqrt(n)出发没走几步就能凑出平方差。实际做题时你没法直接知道|p - q|只能通过试跑来判断。我的做法是给 Fermat 设一个迭代上限比如一百万次如果限定次数内跑不出来就换方法。这是一个便宜试探的思路——反正跑一百万次也就几秒钟。另外有个技巧值得提一下如果p、q非常接近但不是特别接近可以先做一轮加速。因为a的起始值是ceil(sqrt(n))而每次a增加 1a² - n大约增加2a 1。这段递增里如果b本身很大a² - n从b²附近开始增长会有一段接近的过程加速的方法是用一个预判函数跳过长时间的非平方区间不过这对于 CTF 来说通常用不上。3.3 可直接复用的 Fermat 脚本from gmpy2 import isqrt, is_square def fermat(n, max_iter1_000_000): a isqrt(n) if a * a n: a 1 for _ in range(max_iter): b2 a * a - n if is_square(b2): b isqrt(b2) return a - b, a b a 1 return None p, q fermat(n) print(p, q)这段代码有个细节要注意isqrt是向下取整所以初始化要判断一下a*a n时a 1确保从ceil(sqrt(n))开始。这一步漏掉的话如果n恰好是完全平方以外的数起始值会少 1虽然最后也能对上但会多迭代一轮。d3factor这一类题目里如果p、q是相邻素数或者相差很小的素数用这段代码基本都是秒出。判断是不是这种情况的一个旁证是题目如果没给任何额外的量、e也是正常的 65537、而n又只有 1024 位那就很值得先跑一遍 Fermat 试试。4. Pollards p-1p-1 光滑是最容易被忽略的送分点4.1 平滑数是能被一堆小素数乘出来的数先解释光滑smooth这个术语如果一个整数的所有素因子都不超过某个上界B这个整数就叫做 B-光滑的。比如360 2³ * 3² * 5它的所有素因子都不超过 5所以它是 5-光滑的。Pollards p-1 算法利用的正是p - 1是光滑数这一性质。它的核心思路是费马小定理的推广如果p是一个素数那么对任意与p互素的a有a^(p-1) ≡ 1 (mod p)。现在假设p - 1是 B-光滑的也就是说p - 1可以写成若干不超过B的素因子的乘积。如果我们构造一个数M让它成为所有不超过B的素因子足够高次幂的乘积那么M一定是p - 1的倍数当B足够大时。于是a^M ≡ 1 (mod p)也就是p | (a^M - 1)。而a^M - 1未必是n的倍数所以gcd(a^M - 1, n)很可能得到非平凡因子p或者q。4.2 算法实现一次 gcd 揭晓成败直接上代码from math import gcd from sympy import primerange def pollard_pm1(n, B1100_000): a 2 for p in primerange(2, B1 1): # 把 p 尽量乘到不超过 B1 的最高次幂 pk p while pk * p B1: pk * p a pow(a, pk, n) d gcd(a - 1, n) if 1 d n: return d return None这里有个小技巧a在每一轮都要对n取模否则a会指数级膨胀变成天文数字。pow(a, pk, n)一次性做了乘方 取模效率最优。另一个细节是pk的计算。对每个小素数p要把p乘到再乘一次就会超过B1为止。这样a在每一轮之后携带的指数就是这批不超过B1的素因子对应的高次幂最终累乘结果近似等于lcm(1, 2, ..., B1)而后者正是p - 1在光滑情况下的倍数。4.3 参数 B1 怎么选跟位数和训练时间挂钩B1是这道题唯一要手调的参数它决定了多大的光滑数算光滑。选大了跑得慢选小了p - 1里的大素因子就凑不齐gcd的结果还是 1。我一般的经验是n 的位数起手 B1512 位以内10^51024 位10^62048 位10^6 ~ 10^7如果B1 10^6跑不出来我会考虑用一个稍大的B1再试一次但不会无脑一直加。因为如果p - 1里有一个六七位的大素因子Pollard p-1 就不是正确的方法了应该考虑 Pollard rho 或者 ECM椭圆曲线方法。d3factor这一题如果走的是这条路径那么出题人会保证p - 1足够光滑B1中等大小就能命中。我踩过的一个坑是gcd最好在每一轮之后都算一次而不是等a累积到最后一起算。原因在于如果a在累积过程中某一轮的指数已经覆盖了p - 1但之后又乘了别的因子导致a对q也变成了1 (mod q)那最终的gcd就会变成n反而失败。每轮都算一次gcd可以尽早抓住那个恰好是 p 的倍数的时机。提示Pollard p-1 和 Pollard rho 不是一回事。前者依赖p - 1光滑后者依赖生日悖论找碰撞代码和适用条件完全不同别搞混。5. Coppersmith 与已知高位部分比特恢复的格方法5.1 已知 p 的高位一个典型的部分信息场景Coppersmith 方法处理的是一类已知部分信息的问题。最典型的场景是题面给出了p的高若干位要求在剩下的低位未知的情况下恢复完整的p。把p写成p p_high * 2^k x其中p_high是已知高位x是未知低位的值k是未知低位的比特数。因为p | n所以n ≡ 0 (mod p)也就是说x是多项式f(x) p_high * 2^k x模n的一个小根。Coppersmith 方法告诉我们如果一个模n的整系数多项式有某个根x0满足|x0| n^(1/d)其中d是多项式的次数这里d 1那么这个根可以在多项式时间内求出来。对于f(x) p_high * 2^k x根的上界就是2^k。只要2^k n^(1/1)实际上更精确的条件是2^k在p的一定比例之内通常要求小于n^0.25这个量级更保险Coppersmith 就有效。5.2 Sage 实现的调用方式Coppersmith 的实现强烈依赖格基约简LLL没有专业格库基本做不出来。实际比赛里我直接用 Sage# 在 Sage 里运行 n ... p_high ... # p 的已知高位部分 kbits ... # 未知的低位比特数 shift 2 ** kbits PR.x PolynomialRing(Zmod(n)) f p_high * shift x roots f.small_roots(Xshift, beta0.4) if roots: p int(p_high * shift roots[0]) q n // p print(p, q)几个参数务必留意。X给的是根的搜索上限一般设成2^kbits就够了。beta是个关键参数它控制着因子相对于n的大小的假设。当p、q量级相同时beta 0.4是个常用且保险的取值如果已知p是n的某个较小比例比如p ≈ n^0.3那beta要相应调小。small_roots返回的可能是空列表也可能返回多个根需要用p n // int(root)一个个验证。注意small_roots的返回值是 Sage 的模环元素必须先转成整数再做除法。另外f.small_roots只在f的常数项和n互素时才有意义如果gcd(f.constant_coefficient(), n) 1那其实你已经直接拿到因子了不用费劲跑格。5.3 已知低位、部分密钥都归到同类Coppersmith 的用法不止于已知 p 的高位。常见的还有几种变体已知p的低位构造f(x) x * 2^k p_low同样求小根已知d的低位利用e * d ≡ 1 (mod φ(n))的关系把d拆成d_low 2^k * x构造多元多项式相关消息攻击Franklin-Reiter如果同一明文的两个线性变换后的密文都给出了可以构造差分来求根。d3factor这类只给n、e、c的题如果最终要靠 Coppersmith那题面通常会给一个额外的量。如果没有额外量这条路走不通。6. Wiener 与小私钥 d连分数逼近的边界在哪里6.1 小 d 为什么危险e/n 约等于 k/dWiener 攻击的出发点是 RSA 的一个近似关系。由e * d ≡ 1 (mod φ(n))可以写成e * d 1 k * φ(n)其中k是个整数量级和e相当。两边除以d * φ(n)得到e / φ(n) k / d 1 / (d * φ(n))因为φ(n)与n非常接近|φ(n) - n| p q - 1只有O(sqrt(n))的量级所以e / n ≈ k / d。也就是说k / d是e / n的一个非常好的有理逼近。Wiener 的结论是当d n^(1/4) / 3时通过连分数展开e / n一定能在展开序列里找到k / d从而恢复出私钥d。6.2 连分数展开和收敛子连分数是数学里的老工具但在 RSA 攻击里它非常好用。核心操作是把e / n做连分数展开然后逐项取收敛子convergent。每个收敛子都是一个有理数k / d它和原分数的误差非常小。def cf_expansion(a, b): cf [] while b: q, a, b a // b, b, a % b cf.append(q) return cf def convergents(cf): numerators, denominators [], [] n_prev, n_curr 0, 1 d_prev, d_curr 1, 0 for a in cf: n_prev, n_curr n_curr, a * n_curr n_prev d_prev, d_curr d_curr, a * d_curr d_prev yield n_curr, d_curr得到每个(k, d)后用φ (e * d - 1) // k反算φ(n)然后看φ(n)是否满足p q n - φ(n) 1且方程x² - (pq)x n 0有整数根。有的话p、q就出来了。def wiener_attack(n, e): for k, d in convergents(cf_expansion(e, n)): if k 0: continue phi (e * d - 1) // k s n - phi 1 # 解 x^2 - s*x n 0 delta s * s - 4 * n if delta 0: t isqrt(delta) if t * t delta and (s t) % 2 0: p (s t) // 2 q (s - t) // 2 if p * q n: return d, p, q return None6.3 Wiener 失效后的下一步Boneh-DurfeeWiener 攻击的边界是d n^(1/4)。如果d比这个稍大一点Wiener 就不灵了。但不要急着换方向因为有一条更强大的攻击在等Boneh-Durfee 攻击能把边界推到d n^0.292左右。Boneh-Durfee 也是基于格的方法Sage 里有现成的实现模板核心也是构造一个小根问题。需要提醒的是Boneh-Durfee 的实现在 Sage 里不是一行调用需要自己构造格和多项式。比赛里如果题目确实需要它一般会给足够的时间。判断是否需要 Boneh-Durfee 的信号是e接近n的大小但 Wiener 的连分数找不到解同时d的量级在n^0.28左右——这些信息可能需要从题面或已知数据结构反推。7. 复盘那些在 d3factor 上让我卡住的细节7.1 精度问题Python 的大整数救场在 RSA 攻击里经常会出现看起来原理对了但跑不出来的情况。排除逻辑错误之后最常见的原因是精度问题。比如用float去算sqrt或者除法在大整数场景下会直接丢精度导致后面的判断全错。我的习惯是任何和n相关的运算只要涉及开方和除法一律用isqrt、gmpy2这种精确的大整数工具绝不混入浮点。Coppersmith 里的参数计算、Wiener 里的连分数展开都要保持整数运算。这一点在 1024 位以上的模数上尤其明显float的 53 位精度远远不够。7.2 多解验证别拿到第一个结果就交Coppersmith 的small_roots、连分数的每个收敛子都可能返回多个看起来像的解。我一开始的习惯是拿到第一个就直接用结果被坑过第一个解可能是p 1或者某个不满足p * q n的伪解。正确的习惯是每一个候选解都验证p * q n并且最好额外验证p、q都是素数。这一步不费事但能帮你排除掉大量假阳性。from gmpy2 import is_prime def verify(n, p): if p 1 or p n: return False if n % p ! 0: return False q n // p return is_prime(p) and is_prime(q)7.3 建立自己的方法判断表最后分享一个让我效率提升明显的习惯给每道做过的 RSA 分解题记一个判断特征表。记录的内容是题面给了什么、最后用了什么方法、为什么是这个方法、有没有走弯路。积累十几道题之后你会发现大部分题目的判断逻辑是高度相似的。比如对于d3factor这种只给标准三件套的题我的第一反应顺序固定是检查n是否本身有小因子、是否完全平方试 Fermat限时一百万次迭代试 Pollard p-1B1从 10^5 起如果都不行回头重读题面看看有没有漏掉的额外量如果确认没有额外量那可能是n的构造更复杂比如q next_prime(p)之后的乘法、p、q共享高位等需要更细的推导。这套顺序不是万能的但它覆盖了绝大多数 CTF 里的 factor 题。遇到新的构造时把新方法补进这个表里下次就能更快响应。提示比赛时如果卡在某个方法超过 20 分钟果断换方法而不是硬啃。CTF 的时间拿来做广撒网的尝试比死磕一个方向更划算。7.4 本地要准备好的环境还有一件容易被忽略的事环境准备。Coppersmith 依赖 SageWiener 和 Pollard p-1 用纯 Python 的sympy、gmpy2就够但 Sage 的安装体积大、首次安装耗时长。我建议在比赛前就把 Sage 装好并把常用的 Coppersmith 模板存成本地脚本比赛时直接改参数。另外gmpy2的isqrt、is_prime比sympy的对应函数快得多大数场景下优先用它。sympy更适合做素数生成和小范围逻辑验证两者配合使用效率最高。说到底d3factor这一类的题目考的是你对 RSA 结构弱点的敏感度而不是某个具体脚本的复制粘贴。这套拆解的逻辑建立起来之后下一次遇到名字里带factor的题你应该能在三分钟内判断出该往哪个方向走然后让代码去干活。剩下的就是把这些方法多练几遍让它们变成肌肉记忆。