1. 项目概述从零到一理解CTF中的RSA挑战如果你刚接触CTFCapture The Flag安全竞赛面对那些满是数学符号和长串数字的RSA题目是不是感觉一头雾水无从下手别担心这种感觉每个新手都经历过。RSA作为现代密码学的基石在CTF的Crypto密码学类别中出场率极高它不像Web题那样有直观的页面交互也不像Pwn题那样涉及底层内存操作它更像是一场纯粹的逻辑与数学博弈。很多新手望而却步不是因为它真的有多难而是因为不知道从哪里切入以及缺乏一套系统的解题“工具箱”。这篇内容就是为你准备的“工具箱”和“路线图”。我不会一上来就堆砌复杂的数论公式而是会从CTF出题人最常见的五种套路出发手把手带你拆解每一种题型背后的核心思路。更重要的是每一部分都会附上可以直接运行、修改的Python代码。我们的目标很明确让你不仅能看懂答案更能理解“为什么这么做”并且具备自己动手解决新题目的能力。无论你是计算机专业的学生还是对安全感兴趣的爱好者只要具备基础的Python语法知识就能跟着这篇文章一步步揭开RSA在CTF中的神秘面纱。2. 核心思路拆解CTF RSA题目的本质与解题哲学在深入具体题型之前我们必须建立一个正确的认知CTF中的RSA题目绝大多数都不是让你去破解一个标准、完整、参数巨大的RSA加密。在现实世界中使用足够长的密钥如2048位以上的RSA在可预见的时间内是无法被暴力破解的这是其安全性的基础。那么CTF考什么呢考的是**“非标准”和“不安全”**。出题人会刻意地在RSA实现的某个环节引入漏洞或者给出一些额外的泄漏信息。你的任务就是利用这些“不完美”结合数学知识还原出加密前的明文也就是Flag。因此解题的核心思路可以归纳为已知一部分求另一部分。这个“已知”可能是加密后的密文c、公钥(n, e)也可能是泄漏的私钥d的某几位、素数p和q的关系、或者是多组加密之间的关系。所以面对一道RSA题你的第一反应不应该是“我怎么破解RSA算法”而应该是“题目给了我哪些信息这些信息之间可能存在什么数学关系哪种已知的攻击模型能套用上去”。这五种常见题型正是五种经典的“信息泄漏”模型和对应的攻击方法。掌握它们你就掌握了打开大部分RSA题目的钥匙。2.1 题型一模数n分解攻击Factoring Attack这是最直接、最经典的一种题型。RSA的安全性建立在“大整数分解是困难的”这一假设上。公钥中的模数n等于两个大素数p和q的乘积n p * q。如果出题人使用的p和q不够大或者n本身存在缺陷比如是两个非常接近的素数那么我们就可以在有限时间内分解n。为什么能攻击一旦成功分解n得到p和q我们就可以计算出欧拉函数 φ(n) (p-1)(q-1)。随后根据公钥指数e利用扩展欧几里得算法求出私钥指数d满足 ed ≡ 1 mod φ(n)。最后用私钥解密公式 m c^d mod n 即可得到明文m。实战场景题目通常只给你一个pub.key文件包含n和e和密文c或者直接在描述里给出n、e、c的值。n的位数可能在256位到1024位之间对于现代计算机和高效的分解算法如Pollard‘s rho、p-1分解法或者直接使用factordb这样的在线数据库来说是可分解的。Python实战代码与解析import gmpy2 from Crypto.Util.number import long_to_bytes # 假设题目给出 n 742449129124467073921545687640895127535705902454369756401331 e 65537 c 39207274348578481322317340648475596807303160111338236677373 # 第一步分解n。这里n较小我们可以用gmpy2的next_prime或直接查询factordb。 # 在实际CTF中对于不大的n可以尝试用factordb.com的API或yafu工具。 # 此处我们假设通过某种方式分解得到 p 752708788837165590355094155871 q 986369682585281993933185289261 # 第二步计算欧拉函数 φ(n) 和 私钥d phi (p - 1) * (q - 1) # 使用gmpy2.invert求模逆元即私钥d d gmpy2.invert(e, phi) # 第三步解密 m pow(c, d, n) # 使用pow函数进行模幂运算效率远高于 c**d % n # 第四步将解密得到的整数长整数转换为字节字符串即flag flag long_to_bytes(m) print(f解密后的flag为{flag})注意事项与心得分解工具对于较小的n如小于512位可以尝试在 factordb.com 网站查询它积累了海量的分解结果。对于本地分解yafu是一个非常强大的整数分解工具尤其擅长自动选择算法。Python库gmpy2是处理大整数运算的利器pow(a, b, c)是内置的模幂运算函数效率极高。Crypto.Util.number中的long_to_bytes和bytes_to_long是RSA题中数字与字节流转换的标配。判断n是否可分解拿到n后第一步是评估其位数。在常规CTF中256位以下的n几乎肯定可分解512位需要一些运气和好的工具1024位在现代标准下是安全的但在CTF中如果出现往往意味着有其他漏洞如共模攻击而不是让你直接分解。2.2 题型二共模攻击Common Modulus Attack这种题型的特点是相同的明文m使用相同的模数n但不同的公钥指数e1和e2进行加密得到了两个密文c1和c2。即 c1 m^e1 mod n c2 m^e2 mod n为什么能攻击如果e1和e2互素即gcd(e1, e2) 1那么根据贝祖定理存在整数s和t使得 se1 te2 1。这个s和t可以通过扩展欧几里得算法求出。注意s和t可能一正一负。假设s为正t为负令 t -k k0则有 se1 - ke2 1。 那么我们可以进行如下推导 (c1)^s * (c2)^{-k} mod n (m^e1)^s * (m^e2)^{-k} mod n m^{se1 - ke2} mod n m^1 mod n m。这样我们就在不知道私钥d、没有分解n的情况下直接恢复了明文m。实战场景题目会给出n e1, c1, e2, c2。你需要验证gcd(e1, e2)是否等于1。如果等于1共模攻击就成立。Python实战代码与解析import gmpy2 from Crypto.Util.number import long_to_bytes, inverse # 假设题目给出 n 102211578173447275999691508355507769924837578389124790777279423508782416706799 e1 65537 c1 83004716839703584535893242018157676038713255217367989705404952110250010602533 e2 100001 c2 70742180835212541482147432273987954145304387264154304168381150762710664188301 # 第一步验证e1和e2是否互素 gcd, s, t gmpy2.gcdext(e1, e2) # 扩展欧几里得算法返回(gcd, s, t) 使得 s*e1 t*e2 gcd print(fgcd(e1, e2) {gcd}) if gcd ! 1: print(e1和e2不互素共模攻击不适用) exit() # 第二步使用得到的s和t。注意s或t可能为负数。 # 如果s为负数我们需要计算c1的模逆元如果t为负数则需要计算c2的模逆元。 if s 0: c1_inv inverse(c1, n) # 计算c1关于模n的逆元 m (pow(c1_inv, -s, n) * pow(c2, t, n)) % n elif t 0: c2_inv inverse(c2, n) m (pow(c1, s, n) * pow(c2_inv, -t, n)) % n else: # 两者都为正理论上可能但实践中因为e1,e21s和t通常一正一负 m (pow(c1, s, n) * pow(c2, t, n)) % n # 第三步输出明文 flag long_to_bytes(m) print(f通过共模攻击解密得到的flag为{flag})注意事项与心得负指数的处理这是共模攻击代码中最容易出错的地方。当s或t为负数时不能直接计算pow(c, 负数, n)因为幂运算的底数需要是模n下的整数。正确的做法是先计算对应密文的模逆元然后对逆元进行正数次幂运算。gmpy2.gcdext是核心这个函数一次性求出了最大公约数和贝祖系数s, t非常方便。攻击前提务必牢记攻击成立的前提是相同的明文m、相同的模数n。如果明文不同或者模数不同此攻击无效。2.3 题型三低加密指数攻击Low Public Exponent Attack当公钥指数e非常小例如e3或e5并且明文m也很小使得 m^e n 时加密过程c m^e mod n实际上退化成了c m^e因为m^e小于n取模后不变。此时我们直接对密文c开e次方根即可得到明文m。即使 m^e 略大于 n如果满足 m^e k*n c k是一个较小的整数我们也可以通过枚举k计算(k*n c)的e次方根看结果是否为整数来恢复m。这被称为**低加密指数广播攻击Håstads Broadcast Attack**的一种简单形式。为什么能攻击因为加密过程失去了“取模”的混淆作用。RSA的安全性依赖于模运算的单向性当m^e没有“溢出”模数n时这种单向性就不复存在了。实战场景题目会给出一个很小的e如3以及密文c。明文m通常是一个字符串转换的整数比如flag的十六进制或Base64编码形式。Python实战代码与解析以e3为例import gmpy2 from Crypto.Util.number import long_to_bytes # 假设题目给出 n 17258212916191948536348548470938004244269544560039009244721959293554822498047075403658429865201816363311805874117705688359853941515579440852166618074161313773416434156467811969628473425365608002907061241714688204565170146117869742910273064909154666642642308154422770994836108669814632309362483307560217924183202838588431342616751519279810171252930840889894494293249592794576299658182558918326088274763701335986374662345160356271494964568301985288759534703425515047275913857189580919848128894689345440732397688122049240463493914785597920174711513290479450999725245376359761881114712284531219363900246432595696363135312 e 3 c 155189610416250618761353776116407614004644398324266829090181090970046468422755353665483760162095444640789333810188462797757699 # 方法一直接开e次方根适用于 m^e n 的简单情况 # 对于e3我们可以尝试对c直接开三次方 m_int, is_exact gmpy2.iroot(c, e) # iroot返回 (整数根, 是否精确) if is_exact: flag long_to_bytes(int(m_int)) print(f情况一直接开方得到flag - {flag}) else: print(直接开方失败m^e可能大于n尝试枚举k...) # 方法二枚举k (低加密指数广播攻击的简化版) for k in range(1000000): # 枚举一个合理范围的k # 计算 (k*n c) 的e次方根 m_test, is_exact gmpy2.iroot(k * n c, e) if is_exact: flag long_to_bytes(int(m_test)) print(f情况二枚举k{k}后开方得到flag - {flag}) break else: print(枚举k也未找到解可能需要更复杂的低加密指数广播攻击涉及中国剩余定理。)注意事项与心得gmpy2.iroot函数这个函数用于计算大整数的整数次方根并返回一个布尔值指示结果是否精确是处理此类问题的神器。枚举k的范围理论上k可以从0开始枚举。实践中因为m通常不会太大m^e相对于n不会大太多所以k通常是一个很小的数字0, 1, 2, 3...。设置一个上限比如100万在大多数CTF题目中足够了。更一般的情况如果明文m被填充例如使用PKCS#1 v1.5或者e稍大如e17直接开方和简单枚举k可能失效。此时需要用到完整的低加密指数广播攻击Håstads Broadcast Attack其场景是相同的明文m用相同的低加密指数e但不同的模数n1, n2, ..., nk进行加密得到密文c1, c2, ..., ck。当k e时可以利用中国剩余定理CRT构造一个在模Nn1n2...*nk下的方程最终恢复m^e再开e次方。这需要用到sympy或自定义的CRT函数。2.4 题型四维纳攻击Wiener‘s Attack与低解密指数攻击这是一种针对私钥指数d过小的攻击。在RSA中为了加快解密速度有人可能会选择较小的私钥d。维纳攻击表明如果d (1/3) * n^(1/4)那么可以通过公钥(n, e)连分数展开的方式快速计算出私钥d。为什么能攻击攻击的核心基于一个数学事实当d较小时分数 e/n 是 k/d 的一个很好逼近其中k是某个整数。而连分数展开可以有效地找到这种逼近。实战场景题目给出一组公钥(n, e)你需要判断d是否可能很小。一个经验性的提示是e非常大通常接近n因为e和d在模φ(n)下互为逆元如果d很小那么e就会很大。当你看到e的位数和n差不多时就要警惕维纳攻击了。Python实战代码与解析维纳攻击的实现涉及连分数和渐进分数的计算。我们可以使用现成的库RSAwienerHacker或者自己实现。# 方法一使用现成的脚本/库推荐 # 通常网上有名为RSAwienerHacker.py的脚本我们这里演示其核心逻辑的简化版。 import gmpy2 def wiener_attack(e, n): 维纳攻击实现 返回私钥d如果攻击失败则返回None # 将 e/n 展开为连分数 def continued_fraction(e, n): cf [] while n: q e // n cf.append(q) e, n n, e - q * n return cf # 根据连分数计算渐进分数 def convergents(cf): convergents [] for i in range(1, len(cf)1): num cf[i-1] den 1 for j in range(i-2, -1, -1): num, den cf[j] * num den, num convergents.append((num, den)) return convergents cf continued_fraction(e, n) convergents_list convergents(cf) for k, d in convergents_list: # 遍历所有渐进分数 k/d if k 0: continue # 检查 d 是否为有效的私钥 # 根据 ed ≡ 1 mod φ(n)可以推导出 φ(n) (ed - 1)/k 是整数 if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 根据 φ(n) 和 n可以解一元二次方程 x^2 - (n - phi 1)x n 0根应为p和q b n - phi 1 delta b * b - 4 * n if delta 0: continue sqrt_delta, is_square gmpy2.iroot(delta, 2) if not is_square: continue p (b sqrt_delta) // 2 q (b - sqrt_delta) // 2 if p * q n: return d return None # 假设题目给出一个e很大d可能很小的场景 n 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597 e 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619 c 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192 d wiener_attack(e, n) if d: print(f[] 维纳攻击成功私钥d {d}) # 使用私钥d解密 m pow(c, d, n) from Crypto.Util.number import long_to_bytes flag long_to_bytes(m) print(f[] 解密得到的flag为{flag}) else: print([-] 维纳攻击失败d可能不符合攻击条件。)注意事项与心得攻击条件维纳攻击成功的核心条件是d (1/3) * n^(1/4)。这是一个充分条件并非必要条件。有时d稍大也可能被攻击但概率较低。e的特征因为 e*d ≡ 1 mod φ(n)且 φ(n) ≈ n如果d很小那么e必然很大接近n。所以看到e的位数和n差不多是尝试维纳攻击的一个强烈信号。现成工具在实战中强烈推荐使用成熟的脚本如RSAwienerHacker.py或者RsaCtfTool等综合工具它们经过充分测试比自己手写更可靠。2.5 题型五p或q泄漏或具有特殊关系这是CTF中最灵活多变的一类题型。出题人不会直接给你完整的n分解而是泄漏关于p和q的部分信息让你利用这些信息恢复出完整的p和q。常见变种包括已知p和q的一部分高位或低位例如题目给出p的前256位或者q的后若干位。p和q具有特殊的数学关系例如p和q是相邻的素数|p-q|很小或者p next_prime(q)或者p k*q rk, r已知。已知φ(n)或d的一部分例如泄漏了d的低位或者给定了φ(n)的值。为什么能攻击因为这些泄漏的信息极大地缩小了p和q的搜索空间结合数学推导如Coppersmith定理、费马分解法可以在可接受的时间内恢复出完整的素数。实战场景以已知p的高位为例题目描述“在RSA加密中素数p的高位被泄漏了。” 并给出nec以及p的高位部分p_high。Python实战代码与解析使用SageMath或sympy的Coppersmith方法Coppersmith定理是解决此类问题的强大数学工具它可以在模数n的因子如p已知部分比特时快速恢复剩余部分。SageMath内置了相关函数。以下示例演示在已知p高位的场景下如何使用SageMath求解。# 注意此代码通常在SageMath环境中运行或使用安装了sage库的Python。 # 以下为SageMath脚本示例 # 假设题目给出 n 0x1234567890abcdef... # 一个很大的整数这里用十六进制表示 p_high 0xdeadbeefcafe... # p的高位位数约为p总位数的一半或更多 e 65537 c 0x8ac0f... # 密文 # p的总位数比特数 p_bits n.nbits() // 2 # 假设p和q位数相近 # 已知高位的位数 known_bits p_high.nbits() # 未知的低位位数 unknown_bits p_bits - known_bits print(fp的总位数约为{p_bits}) print(f已知高位位数{known_bits}) print(f未知低位位数{unknown_bits}) # 构造多项式环。变量x代表p的未知低位部分。 PR.x PolynomialRing(Zmod(n)) # 构造多项式 f(x) (p_high * 2^unknown_bits x) # 我们的目标是找到一个小根x0使得 f(x0) ≡ 0 mod p即 p_high * 2^unknown_bits x0 是n的一个因子p。 f p_high * (2 ** unknown_bits) x # 使用small_roots方法寻找小根。参数beta通常设为0.5epsilon可以调整。 # 我们需要设定根的上界这里设为 2^unknown_bits即未知部分的最大可能值。 x0 f.small_roots(X2^unknown_bits, beta0.5, epsilon0.05) if x0: x0 int(x0[0]) p int(p_high * (2 ** unknown_bits) x0) if n % p 0: q n // p print(f[] 成功分解n) print(fp {p}) print(fq {q}) # 后续计算φ(n), d, 解密m的步骤同题型一 phi (p-1)*(q-1) d inverse_mod(e, phi) m pow(c, d, n) flag bytes.fromhex(hex(m)[2:]) if m.bit_length() % 8 0 else bytes.fromhex(0hex(m)[2:]) print(f解密得到的flag为{flag}) else: print([-] 找到的x未产生正确的因子p。) else: print([-] Coppersmith方法未找到解。可能已知位数不足或参数需要调整。)注意事项与心得SageMath环境Coppersmith攻击通常依赖SageMath的强大数论库。你可以安装SageMath或者寻找在纯Python下实现Coppersmith的库如defund的coppersmith脚本但后者可能更复杂。已知信息量要成功恢复已知的比特数需要达到一定的比例。对于RSA-1024p和q各512位通常需要知道p的高位或低位大约256位以上成功率才比较高。small_roots方法中的X参数根的上界和epsilon参数可能需要根据实际情况调整。其他变种对于p和q相近的情况|p-q|很小可以使用费马分解法。其原理是设a (pq)/2,b (p-q)/2则n a^2 - b^2。由于p和q接近b很小我们可以从a ceil(sqrt(n))开始尝试检查a^2 - n是否为完全平方数。3. 解题流程与工具箱整合掌握了以上五种题型你已经能解决CTF中80%以上的RSA题目。在实际比赛中面对一道陌生的RSA题我建议你遵循以下流程信息收集仔细阅读题目描述和附件。提取所有给出的数字n, e, c, p, q, d, dp, dq, iq等等。特别注意是否有“泄漏”、“部分”、“高位”、“低位”、“相近”等提示词。初步判断检查n的位数尝试用factordb或yafu分解。观察e的大小。如果e3或5或17考虑低加密指数攻击。如果e非常大接近n考虑维纳攻击。检查是否有多个(n, e, c)对。如果n相同e不同考虑共模攻击如果e相同n不同考虑低加密指数广播攻击。查看是否有关于p或q的特殊描述泄漏部分、数学关系。工具尝试使用集成的RSA工具进行快速测试如RsaCtfTool。它可以自动尝试多种攻击方式分解、维纳、共模、费马等往往能快速解决标准题型。# 示例命令 python RsaCtfTool.py -n N -e E --uncipher C python RsaCtfTool.py --publickey pub.key --uncipherfile cipher.txt手动推导与编码如果工具无法直接解决或者你想彻底理解过程就根据题目提示选择对应的攻击模型手动编写Python/SageMath脚本进行求解。这就是我们上面详细讲解的内容。Flag格式化解密得到的m是一个长整数需要用long_to_bytes转换。转换后可能直接是字符串也可能是hex或base64编码需要进一步解码。最终的flag格式通常是flag{...}、CTF{...}等。4. 常见问题与排查技巧实录在实际操作中你肯定会遇到各种报错和意外情况。下面是我踩过的一些坑和解决技巧Q1: 运行解密代码后输出的是一串乱码或b‘\x89PNG\r\n...’之类的字节。A1: 这说明解密得到的m其字节表示可能不是一个UTF-8编码的字符串。有几种可能 *Flag是其他编码尝试hex(m)看看是否是十六进制字符串或者base64.b64encode(long_to_bytes(m))看看是否是Base64。 *解密错误最可能的原因是n分解错误或者攻击模型不适用导致恢复的p, q, d不正确。请回头检查每一步计算特别是模逆元、欧拉函数计算。 *需要去除填充真实的RSA加密会先对明文进行填充如PKCS#1 v1.5。CTF题中为了简化经常使用无填充的“教科书式RSA”。但如果题目提示了填充你可能需要手动解析解密后的字节流去除填充部分才能得到flag。Q2: 使用gmpy2库时报错ModuleNotFoundError。A2:gmpy2是一个性能库需要单独安装且对Python版本和系统环境有要求。在Kali Linux或Ubuntu上可以尝试sudo apt install libgmp-dev libmpfr-dev libmpc-dev后再用pip install gmpy2。如果安装困难对于不太大的整数可以用Python内置的pow(a, b, c)进行模幂运算用math.gcd求最大公约数。但对于维纳攻击、大数开方等gmpy2几乎是必须的。也可以考虑使用pycryptodome库中的一些大数运算函数作为替代。Q3: 共模攻击代码运行后得到的m是负数或非常大转换字节失败。A3: 这几乎肯定是负指数处理错误。请仔细检查代码中if s 0和if t 0的分支逻辑。确保当指数为负时你是先计算了密文关于模n的模逆元然后对逆元进行正数次幂运算。公式是m ≡ (c1^s * c2^t) mod n当s为负时c1^s mod n等价于(c1^{-1})^{-s} mod n。Q4: 已知p高位的Coppersmith攻击在SageMath里运行small_roots()很久没结果。A4: Coppersmith方法对参数敏感。 *检查已知位数未知位数unknown_bits不能太大。通常要求未知部分小于n的约1/2次方对于因子p是小于p的比特数的大约一半。如果已知位数太少攻击会失败。 *调整参数尝试调整small_roots(X..., beta0.5, epsilon...)中的epsilon值例如从0.05调到0.1或更小。epsilon越小搜索能力越强但计算量越大。 *尝试其他方法如果已知的是p的低位也可以构造类似的多项式f(x) p_low x * 2^{known_low_bits}。如果已知的是中间部分情况更复杂可能需要更高级的Coppersmith技巧。Q5: 题目给了n, e, c还有dp和dq这是什么题型A5: 这是中国剩余定理CRT优化参数泄漏。dp d mod (p-1),dq d mod (q-1)。当给出这些参数时即使没有完整的d也可以利用CRT快速解密。解密公式为m1 c^dp mod pm2 c^dq mod qq_inv inverse(q, p)h (q_inv * (m1 - m2)) mod pm m2 h * q这种题目直接考察你对RSA-CRT解密过程的理解代码实现起来比通用解密更简单高效。最后再分享一个我个人的习惯每解完一道题尤其是费了很大劲才解出来的题我会把题目描述、给出的参数、解题思路、最终的攻击脚本和flag整理到一个Markdown笔记里。久而久之这就成了我专属的RSA题型手册和代码库。下次再遇到似曾相识的题目直接翻笔记效率能提高好几倍。密码学解题就像拼图见的套路越多手里的“拼图块”就越多解题也就越快。希望这五种基础题型能成为你CTF密码学之旅中最坚实的第一批拼图块。
