CTF RSA常见题型与攻击脚本系统整理：从模数分解到共模攻击

1. 从一道解不出的RSA题说起为什么值得系统整理刚接触CTF那会儿我在一道RSA题上卡了整整两天。题目给了一个n、一个e、一个c看起来干净利落但试了各种常规分解工具都跑不出结果。后来翻了不少资料才发现问题根本不在工具而在于我没搞清楚这道题到底属于哪一类攻击场景——是模数分解、低加密指数、共模攻击还是其他变体。RSA题目的“外壳”往往长得很像但内核完全不同选错了攻击路径再强的算力也是白费。这也是我决定系统整理RSA学习和常见CTF题型的原因。RSA作为非对称加密的经典算法在CTF密码学方向里出现频率极高几乎每场比赛都会有一到两道。它的题型变化多端但底层数学原理是固定的。只要把原理吃透再配合几套可复用的解题脚本大部分题目都能在短时间内定位到攻击方向。这篇文章适合两类人一是刚入门CTF密码学、对RSA还停留在“知道公式但不会做题”阶段的新手二是做过一些RSA题、但解题思路比较零散、想建立系统方法论的中级选手。我会从RSA的数学基础讲起然后逐一拆解几种最常见的CTF题型每种题型都配上可运行的Python脚本和详细的参数说明。所有脚本都是我在实际比赛中反复验证过的你可以直接拿去改参数用。需要提前说明的是本文涉及的数学推导和脚本实现都是基于公开的密码学教材和CTF社区常见解法整理而成属于学习研究范畴。实际应用中RSA的安全性依赖于足够大的密钥长度和正确的实现方式CTF题目中的“弱RSA”场景是为了教学目的而人为构造的。2. RSA的数学骨架不搞懂这些脚本抄了也白抄2.1 密钥生成的三步走和背后的数论逻辑RSA的核心思想其实很朴素利用“大整数分解困难”这个数学难题来构造单向陷门函数。密钥生成分三步第一步选两个大素数p和q。这两个数必须足够大且随机通常各取512位或1024位。为什么必须是素数因为后续的模运算需要在模φ(n)下求逆元而φ(n)的计算依赖于p和q的素性。第二步计算n p * q和φ(n) (p-1) * (q-1)。n是公开的模数φ(n)是欧拉函数值必须严格保密。这里有个关键点φ(n)的保密性直接决定了RSA的安全性。如果攻击者能算出φ(n)就能通过解方程pq n - φ(n) 1和p*q n来分解n。第三步选公钥指数e和计算私钥指数d。e通常取65537这个值在二进制下只有两个1加密时计算速度快。d是e在模φ(n)下的乘法逆元即满足e * d ≡ 1 (mod φ(n))。求逆元用扩展欧几里得算法Python里一行gmpy2.invert(e, phi)就能搞定。加密过程是c m^e mod n解密是m c^d mod n。正确性依赖于欧拉定理当m与n互素时m^φ(n) ≡ 1 (mod n)所以m^(e*d) m^(1 k*φ(n)) ≡ m (mod n)。注意实际CTF题目中m可能不与n互素但这种情况概率极低且不影响解密正确性因为RSA的正确性证明可以扩展到m与n不互素的情况。2.2 公钥私钥的表示格式PEM、DER和CTF里的裸参数实际比赛中公钥和私钥可能以多种格式给出。最常见的是PEM格式以-----BEGIN PUBLIC KEY-----开头里面是Base64编码的DER数据。解析这种格式可以用Python的Crypto.PublicKey.RSA模块from Crypto.PublicKey import RSA with open(public.pem, rb) as f: key RSA.import_key(f.read()) n key.n e key.e但更多CTF题目会直接给出裸参数比如n 123456789...、e 65537、c 987654321...。这种反而好处理直接赋值就行。还有一种情况是给出n和e但n特别大这时候就要考虑是不是需要分解n。私钥格式也类似PEM格式的私钥里包含n、e、d、p、q等参数可以用RSA.import_key解析后直接取用。如果题目只给了d那通常意味着需要用d来分解n这是另一种攻击场景。2.3 从加密解密到攻击CTF题目的出题逻辑CTF里的RSA题目本质上都是在“人为削弱”RSA的某个环节让攻击者有机可乘。常见的削弱方式包括n太小可以直接分解e太小且m也小导致m^e n直接开方即可多组密文共用同一个n但e不同可以用共模攻击多组密文共用同一个e但n不同且明文相同可以用低加密指数广播攻击p和q太接近可以用费马分解d太小可以用维纳攻击已知p的高位或低位可以用Coppersmith攻击每种攻击对应一套数学工具和脚本。下面我会逐一拆解每种都给出完整的解题思路和可复用的代码。3. 模数分解类题型当n本身就不够硬3.1 小n直接分解factordb和yafu的实战取舍最基础的RSA题目n只有几十位到一百多位直接用factordb在线查询或者yafu本地分解就能出结果。factordb是一个在线的整数分解数据库很多CTF题目的n都是从这里生成的直接查就能拿到p和q。但factordb有个问题如果题目用的是自定义的n数据库里没有记录就得靠本地工具。yafu是我用得最多的分解工具命令行调用很简单yafu-x64.exe factor(123456789012345678901234567890)它会自动选择试除法、Pollard rho、二次筛法等算法对于200位以下的n通常几秒到几分钟就能出结果。如果n超过300位yafu可能就跑不动了这时候要考虑是不是有其他攻击路径。实操心得拿到n之后先别急着上工具。用Python的sympy.factorint试一下如果n小于50位基本秒出。如果不行再上factordb查。最后才用yafu。这个顺序能省不少时间。3.2 费马分解p和q挨得太近就是送分题当p和q非常接近时n可以表示为((pq)/2)^2 - ((p-q)/2)^2。因为p和q接近所以(p-q)/2很小(pq)/2约等于sqrt(n)。费马分解就是从ceil(sqrt(n))开始逐个尝试a计算a^2 - n是否为完全平方数。import gmpy2 def fermat_factor(n): a gmpy2.isqrt(n) 1 while True: b2 a * a - n b gmpy2.isqrt(b2) if b * b b2: return a - b, a b a 1这个脚本对于p和q相差不超过2^20的情况通常几秒内就能出结果。但如果差距更大循环次数会急剧增加。实际比赛中如果题目暗示p和q接近比如n的位数是p的两倍但p和q位数相同优先试费马分解。3.3 Pollard rho和二次筛法中等规模n的通用解法当n在100到250位之间且p和q差距较大时Pollard rho算法是比较好的选择。它的核心思想是利用生日悖论在模n下寻找两个数x和y使得gcd(|x-y|, n)给出一个非平凡因子。import random from math import gcd def pollard_rho(n): if n % 2 0: return 2 x random.randint(2, n - 1) y x c random.randint(1, n - 1) d 1 while d 1: x (x * x c) % n y (y * y c) % n y (y * y c) % n d gcd(abs(x - y), n) return d这个脚本对于n有较小因子的情况效果很好但如果n是两个大素数的乘积Pollard rho的复杂度是指数级的跑起来会很慢。这时候就需要二次筛法QS或数域筛法NFS但这些算法的实现比较复杂CTF中一般不会要求手写用yafu或msieve就行。注意Pollard rho的随机性很强同样的n可能跑几次才出结果。如果一次没出换个随机种子再试。4. 低加密指数攻击e太小明文直接“漏”出来4.1 小e小m直接开方就完事了当e 3且明文m很小时m^e可能小于n这时候c m^e直接对c开e次方就能得到m。import gmpy2 def small_e_attack(c, e): m, exact gmpy2.iroot(c, e) if exact: return int(m) return None这个脚本的逻辑很简单gmpy2.iroot(c, e)返回c的e次方根如果结果是精确的exact为True那m就是我们要的明文。如果m^e略大于n但m^e 2n那c m^e - n这时候需要对c k*n开方k从0开始尝试。def small_e_attack_with_k(c, e, n, max_k1000): for k in range(max_k): m, exact gmpy2.iroot(c k * n, e) if exact: return int(m) return None4.2 低加密指数广播攻击同一明文多个n同一个e如果同一明文m用相同的e和不同的n加密了多次得到c1, c2, ..., ck可以用中国剩余定理CRT恢复m^e再开方。from sympy.ntheory.modular import crt def broadcast_attack(c_list, n_list, e): # 用CRT求 m^e mod (n1*n2*...*nk) m_e, _ crt(n_list, c_list) m, exact gmpy2.iroot(m_e, e) if exact: return int(m) return None这个攻击的前提是k e且所有n两两互素。如果k eCRT恢复出的m^e可能不完整需要结合其他方法。实操心得广播攻击的题目通常会给出至少e组密文和模数。如果只给了两组但e 3那可能还需要配合其他攻击。另外crt函数返回的是(m_e, modulus)m_e是m^e mod (n1*n2*...*nk)如果m^e小于这个乘积那m_e就是m^e本身。4.3 低加密指数与部分明文泄露的结合有时候题目会给出明文的一部分比如m flag padding其中flag是已知的padding是未知的。这时候可以用Coppersmith方法在已知部分明文的情况下恢复完整明文。这个攻击需要用到SageMath脚本相对复杂但CTF中出现的频率不低。# SageMath脚本 def coppersmith_partial_m(n, e, c, known_bits, known_value): R.x PolynomialRing(Zmod(n)) f (known_value x)^e - c roots f.small_roots(X2^known_bits, beta1) return roots这个脚本的核心思想是构造多项式f(x) (known_value x)^e - c然后找f(x) ≡ 0 (mod n)的小根。known_bits是未知部分的位数known_value是已知部分的数值。5. 共模攻击与相关变体同一个n不同e5.1 经典共模攻击gcd(e1, e2) 1的情况当同一明文m用同一个n但不同的e1和e2加密得到c1和c2且gcd(e1, e2) 1时可以用扩展欧几里得算法找到s1和s2使得s1*e1 s2*e2 1然后m c1^s1 * c2^s2 mod n。import gmpy2 def common_modulus_attack(c1, c2, e1, e2, n): g, s1, s2 gmpy2.gcdext(e1, e2) if g ! 1: return None # 处理s1或s2为负数的情况 if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n return m这个脚本的关键在于处理负指数如果s1或s2是负数需要对c1或c2求模逆元然后把指数取正。5.2 共模攻击的扩展gcd(e1, e2) 1的情况如果gcd(e1, e2) g 1那m^g可以被恢复但m本身需要开g次方。这时候如果g很小可以直接开方如果g较大可能需要结合其他信息。def common_modulus_attack_extended(c1, c2, e1, e2, n): g, 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 m_g (pow(c1, s1, n) * pow(c2, s2, n)) % n m, exact gmpy2.iroot(m_g, g) if exact: return int(m) return None注意如果g较大且m^g n开方可能不精确这时候需要尝试m_g k*n。5.3 共模攻击的实战注意事项共模攻击的题目通常会给出两组(e, c)但有时候会给出更多组。如果有多组可以两两组合尝试或者用更通用的方法把所有e和c配对找到gcd为1的组合。另外共模攻击的前提是n相同。如果题目给了多个n那可能是广播攻击或其他类型。区分这两种攻击的关键就是看n是否相同。实操心得共模攻击的脚本里gmpy2.gcdext返回的s1和s2可能都是正数也可能一正一负。处理负指数时求模逆元是必须的。我见过有人忘了这一步结果算出来的m是错的。6. 私钥泄露与低解密指数攻击d太小也是灾难6.1 已知d分解n从d反推p和q如果题目给出了私钥d那可以直接用d来分解n。原理是e*d ≡ 1 (mod φ(n))所以e*d - 1 k*φ(n)其中k是某个整数。通过尝试不同的k可以找到φ(n)进而分解n。def factor_n_with_d(n, e, d): k e * d - 1 # k 2^t * r其中r是奇数 t 0 while k % 2 0: k // 2 t 1 r k for _ in range(100): g random.randint(2, n - 1) y pow(g, r, n) if y 1 or y n - 1: continue for _ in range(t - 1): x pow(y, 2, n) if x 1: p gcd(y - 1, n) q n // p return p, q if x n - 1: break y x return None这个脚本的核心是Miller-Rabin素性测试的变体通过随机选取g计算g^(r*2^i) mod n找到非平凡平方根从而分解n。6.2 维纳攻击d太小连分数来救场当d n^0.25 / 3时可以用维纳攻击。维纳攻击利用连分数逼近e/n因为e/n ≈ k/d其中k是某个整数。通过计算e/n的连分数展开可以找到k/d的近似值进而恢复d。def wiener_attack(e, n): def continued_fraction(a, b): cf [] while b: cf.append(a // b) a, b b, a % b return cf def convergents(cf): conv [] for i in range(len(cf)): if i 0: conv.append((cf[0], 1)) elif i 1: conv.append((cf[1] * cf[0] 1, cf[1])) else: num cf[i] * conv[i-1][0] conv[i-2][0] den cf[i] * conv[i-1][1] conv[i-2][1] conv.append((num, den)) return conv cf continued_fraction(e, n) conv convergents(cf) for k, d in conv: if k 0: continue if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 解方程 x^2 - (n - phi 1)x n 0 s n - phi 1 discriminant s * s - 4 * n if discriminant 0: continue sqrt_disc gmpy2.isqrt(discriminant) if sqrt_disc * sqrt_disc ! discriminant: continue p (s sqrt_disc) // 2 q (s - sqrt_disc) // 2 if p * q n: return p, q, d return None这个脚本的连分数展开和渐进分数计算是核心。维纳攻击的题目通常会给出一个特别大的e接近n这时候就要考虑d是不是太小了。6.3 低解密指数的边界条件与误判维纳攻击的适用条件是d n^0.25 / 3。如果d稍大一点维纳攻击可能失败但可以用Boneh-Durfee攻击它的边界是d n^0.292。不过Boneh-Durfee的实现更复杂需要用到格基约简CTF中出现的频率较低。实操心得维纳攻击的脚本里连分数展开的精度很重要。如果e/n的连分数展开项数不够可能找不到正确的k/d。我一般会把所有渐进分数都试一遍而不是只试前几项。7. 脚本工具箱我常用的RSA解题模板7.1 通用解密脚本从参数到明文的一站式处理下面这个脚本是我平时用得最多的RSA解题模板涵盖了从参数解析到解密的完整流程import gmpy2 from Crypto.Util.number import long_to_bytes def rsa_decrypt(n, e, c, pNone, qNone, dNone): if p and q: phi (p - 1) * (q - 1) d gmpy2.invert(e, phi) elif d: pass else: raise ValueError(需要提供p和q或者提供d) m pow(c, d, n) return long_to_bytes(m) # 示例用法 n 123456789 e 65537 c 987654321 p 12345 q 67890 print(rsa_decrypt(n, e, c, pp, qq))这个脚本的优点是灵活如果你有p和q它会自动算d如果你直接有d它就直接解密。long_to_bytes把整数转成字节串方便查看flag。7.2 批量处理脚本多组密文的自动化攻击当题目给出多组(n, e, c)时手动一个个试太慢。下面这个脚本可以自动判断攻击类型def auto_attack(data_list): # data_list [(n, e, c), ...] if len(data_list) 1: n, e, c data_list[0] # 尝试小e攻击 m small_e_attack(c, e) if m: return long_to_bytes(m) # 尝试分解n p, q fermat_factor(n) if p and q: return rsa_decrypt(n, e, c, pp, qq) else: # 检查n是否相同 n_set set(d[0] for d in data_list) if len(n_set) 1: # 共模攻击 n data_list[0][0] for i in range(len(data_list)): for j in range(i1, len(data_list)): _, e1, c1 data_list[i] _, e2, c2 data_list[j] m common_modulus_attack(c1, c2, e1, e2, n) if m: return long_to_bytes(m) else: # 广播攻击 c_list [d[2] for d in data_list] n_list [d[0] for d in data_list] e data_list[0][1] m broadcast_attack(c_list, n_list, e) if m: return long_to_bytes(m) return None这个脚本的逻辑是先判断数据组数如果只有一组尝试小e攻击和费马分解如果有多组检查n是否相同相同则共模攻击不同则广播攻击。7.3 脚本调试中的常见坑与修复方法调试RSA脚本时最常见的坑有三个第一gmpy2.iroot返回的是(root, exact)很多人忘了检查exact结果拿到一个错误的根。正确的做法是m, exact gmpy2.iroot(c, e) if exact: # 正确处理第二pow(c, d, n)中的d可能是负数这时候需要先求c的模逆元if d 0: c gmpy2.invert(c, n) d -d m pow(c, d, n)第三long_to_bytes对于大整数可能返回很长的字节串如果明文是flag格式可以用bytes.decode()转成字符串查看。实操心得我习惯在脚本里加一些print语句输出中间结果比如p、q、phi、d等。这样如果最后解密失败可以快速定位是哪一步出了问题。8. 从CTF到实际应用RSA学习的延伸方向CTF里的RSA题目虽然是为了比赛设计的但背后的数学原理和攻击方法在实际密码学研究中都有对应。比如费马分解对应的是“弱密钥”问题共模攻击对应的是“密钥复用”问题维纳攻击对应的是“小私钥指数”问题。这些在实际系统中如果实现不当都会导致严重的安全漏洞。如果你想继续深入我建议从两个方向入手一是学习SageMath它在处理格基约简、多项式求根等问题上比纯Python方便得多二是研究Coppersmith方法它在部分明文泄露、高位攻击等场景下非常有用。另外RSA的变体也值得关注比如Rabin密码、Paillier加密等它们在CTF中也偶尔出现。掌握了RSA的基础这些变体上手会快很多。最后分享一个小技巧平时做题时把每道题的n、e、c和解题脚本都保存下来按攻击类型分类整理。时间长了你就有了一个自己的“RSA题库”遇到新题时先翻翻旧题往往能找到相似的解法。我在实际比赛中用这个方法至少省了一半的思考时间。