1. 项目概述从一道CTF题看RSA的实战攻防最近在复盘一些经典的CTFCapture The Flag题目特别是密码学方向的发现“[RoarCTF 2019]RSA”这道题在圈内讨论度一直不低。它不像那些单纯考察RSA基础加密解密的题目而是把多个常见的RSA攻击场景和知识点巧妙地融合在了一起非常考验解题者对RSA算法原理及其脆弱性的深入理解。很多人一看到RSA就觉得是“大数分解”但实战中密钥生成、参数选择、加密模式乃至多组密钥之间的关系都可能成为突破口。这道题就是一个绝佳的综合性案例它涉及了共模攻击、低加密指数攻击以及对于RSA算法中几个核心参数n,e,c之间关系的灵活运用。通过拆解这道题我们不仅能重温RSA更能学到在“黑盒”或“有限信息”场景下如何像攻击者一样思考逆向寻找加密体系的裂缝。无论你是CTF爱好者、安全从业者还是对应用密码学感兴趣的学习者这个分析过程都会很有收获。2. 核心思路与攻击路径预判面对一道RSA题目尤其是CTF中只给出若干组(n, e, c)模数、公钥指数、密文的情况我们首先得有一个清晰的排查思路。盲目尝试分解大数n在当今计算能力下通常是不现实的除非n本身很小或者存在结构性缺陷。因此我们的核心思路是先识别特征再匹配攻击模型。2.1 经典RSA攻击模型速览在深入本题之前快速回顾几种在CTF中高频出现的RSA攻击方式有助于我们建立解题的“武器库”模数n分解最直接的方法。如果n较小如小于512位或由不安全的随机数生成器产生可能被工具如yafu、factordb直接分解。如果n是两个很接近的素数乘积可以使用费马分解法。共模攻击当同一份明文m用相同的模数n但不同的公钥指数e1和e2进行加密得到密文c1和c2且gcd(e1, e2)1即e1和e2互质时可以利用扩展欧几里得算法恢复明文而无需分解n。低加密指数攻击小e明文爆破当公钥指数e很小如3并且明文m也很小使得m^e n时加密过程实际上没有取模操作即c m^e。此时直接对密文c开e次方即可得到明文m。广播攻击同一份明文m用相同的e但不同的模数n1, n2, ..., nk加密得到密文c1, c2, ..., ck。当k e时可以利用中国剩余定理CRT求解m^e再开方得到m。低解密指数攻击当私钥指数d过小时可以使用Wiener攻击或Boneh-Durfee攻击从公钥(n, e)中恢复出私钥d。本题未涉及。因数碰撞如果题目给出了多组(n, e, c)其中两个不同的n存在非1的最大公因数gcd(n1, n2) ! 1那么这个公因数就是n1和n2的一个质因子可以瞬间分解这两个n。解题时我们就像一名法医需要检查给出的“证据”n, e, c组合看看它们符合以上哪种“伤痕特征”。2.2 本题数据特征与初步观察根据对“[RoarCTF 2019]RSA”题目信息的回顾题目通常会提供两个或更多的密文文件每个文件包含类似如下的内容n 1234567890... (一个非常大的整数) e 65537 (或其它值) c 9876543210... (密文整数)有时还会给出n和e的另一种组合。第一步永远是观察n和e。检查n是否可分解将给出的n值提交到在线分解网站如 factordb.com或尝试用yafu本地分解。对于CTF比赛中的n如果位数不是特别大比如1024位以下且有故意设置漏洞有可能直接分解。但更常见的是n本身是安全的需要其他攻击路径。比较多个n如果题目给了多组数据立即计算任意两组n之间的最大公约数gcd。如果gcd(n_i, n_j) ! 1那么恭喜你找到了共享的质因子p可以立刻分解这两个n计算出对应的私钥d。这是最快的一种突破口。观察e的值注意公钥指数e。e65537是最常见的安全选择。如果出现e3或e5等很小的值就要立刻警惕低加密指数攻击的可能性。观察密文c的数量和对应关系明确每一组(n, e, c)的对应关系。是同一明文用不同密钥加密还是不同明文题目描述或文件名有时会给出提示。在“[RoarCTF 2019]RSA”中一个典型的情况是提供了两组密文它们使用了相同的模数n但不同的公钥指数e1和e2并且e1和e2是互质的。这几乎就是教科书式的共模攻击场景。同时可能还存在另一组数据其e值非常小比如3指向低加密指数攻击。解题的关键就在于识别出这些特征并组合运用相应的攻击方法。注意在实际操作中务必先确认数据完整性。将题目给出的n, e, c以整数形式正确读取到Python或其他计算环境中是第一步也是最容易出错的一步比如误读字符l为数字1。3. 密码学原理深度解析为什么这些攻击会生效知其然更要知其所以然。直接套用脚本解题固然快但理解背后的数学原理才能举一反三。我们来深入剖析一下本题可能用到的两种核心攻击的原理。3.1 共模攻击的数学原理与推导共模攻击成立需要三个条件相同的模数n。两个互质的公钥指数e1和e2即gcd(e1, e2) 1。同一明文m分别用(n, e1)和(n, e2)加密得到密文c1 ≡ m^e1 (mod n)和c2 ≡ m^e2 (mod n)。攻击原理 因为e1和e2互质根据数论中的贝祖定理Bézout‘s identity存在两个整数s和t使得s * e1 t * e2 gcd(e1, e2) 1我们可以通过扩展欧几里得算法高效地计算出这对整数(s, t)。现在观察密文c1和c2c1^s ≡ (m^e1)^s ≡ m^(e1*s) (mod n) c2^t ≡ (m^e2)^t ≡ m^(e2*t) (mod n)将上面两式相乘c1^s * c2^t ≡ m^(e1*s e2*t) (mod n)而根据贝祖等式e1*s e2*t 1。因此c1^s * c2^t ≡ m^1 ≡ m (mod n)这样我们就直接得到了明文m全程没有涉及私钥d或分解n。计算细节与陷阱 扩展欧几里得算法得到的s和t可能为一正一负。假设s为正t为负。那么计算c2^t时指数为负数在模运算中需要计算模逆元。即c2^t ≡ (c2^{-1})^{-t} (mod n)这里-t为正数。所以实际操作是先计算c2在模n下的逆元c2_inv然后计算(c2_inv)^{-t}。最终公式调整为m ≡ c1^s * (c2_inv)^{-t} (mod n)在Python中可以使用gmpy2.invert(c2, n)求逆元。3.2 低加密指数攻击与小明文爆破这种攻击针对的是加密过程“未溢出”的情况。标准RSA加密c m^e mod n。取模操作意味着如果m^e本身小于n那么c就等于m^e取模没有产生效果。攻击原理 当公钥指数e很小如3并且明文m也不大时极有可能满足m^e n。此时c m^e (没有mod n)那么恢复明文就变得异常简单直接对密文整数c开e次方根即可。m integer_nth_root(c, e)在Python中对于大整数可以用gmpy2.iroot(c, e)函数它返回一个元组(root, is_exact)其中is_exact为True表示正好开尽这通常就是我们要的明文。为什么e65537就安全因为65537足够大使得即使对于较小的mm^65537这个数字也会变得极其巨大远超通常的n比如2048位从而确保加密过程一定经过了取模运算破坏了上述简单的代数关系。广播攻击的延伸 如果同一明文m用e3加密了三次但使用了三个不同的模数n1, n2, n3且m^3 n1*n2*n3那么我们可以利用中国剩余定理CRT构造一个在模Nn1*n2*n3下的方程解出M m^3再对M开三次方得到m。这就是低加密指数广播攻击。在本题中如果存在多组e3的密文就需要考虑这种可能。4. 实战解题过程与Python代码实现假设我们拿到了“[RoarCTF 2019]RSA”题目的数据经过观察发现有两组数据符合共模攻击条件还有一组数据e3。下面我们一步步还原解题过程。4.1 数据准备与特征确认首先将题目给出的n, e, c整理好。假设数据如下# 共模攻击组 (共享同一个n) n_common 123...456 # 很大的整数 e1 65537 c1 789...012 # 密文1 e2 10001 c2 345...678 # 密文2 # 低加密指数攻击组 n_small 987...321 # 另一个模数 e_small 3 c_small 555...666 # 密文3第一步验证gcd(e1, e2)是否互质并计算gcd(n_common, n_small)看是否有公因子。import gmpy2 from Crypto.Util.number import long_to_bytes # 检查e1, e2是否互质 if gmpy2.gcd(e1, e2) 1: print(“e1和e2互质满足共模攻击条件”) else: print(“e1和e2不互质需考虑其他方法”) # 检查n之间是否有公因子 gcd_val gmpy2.gcd(n_common, n_small) if gcd_val ! 1: print(f“发现公因子 gcd {gcd_val} 可以快速分解n”) p gcd_val q n_common // p # ... 后续可以计算私钥解密 else: print(“n之间无公因子继续既定攻击路径”)4.2 实施共模攻击恢复明文确认e1和e2互质后我们使用扩展欧几里得算法求s和t。# 计算贝祖系数 s 和 t # g, s, t gmpy2.gcdext(e1, e2) 返回 ggcd(e1,e2), s, t 满足 s*e1 t*e2 g g, s, t gmpy2.gcdext(e1, e2) print(f“gcd(e1,e2){g}, s{s}, t{t}”) # 确保我们得到了 s*e1 t*e2 1 assert s*e1 t*e2 1 # 根据s和t的正负情况计算明文 if s 0: # 如果s为负需要计算c1的模逆元然后指数取正 c1_inv gmpy2.invert(c1, n_common) m1_part pow(c1_inv, -s, n_common) else: m1_part pow(c1, s, n_common) if t 0: # 如果t为负需要计算c2的模逆元然后指数取正 c2_inv gmpy2.invert(c2, n_common) m2_part pow(c2_inv, -t, n_common) else: m2_part pow(c2, t, n_common) # 计算最终明文 m (c1^s * c2^t) mod n m_recovered (m1_part * m2_part) % n_common # 尝试将整数明文转换为字节字符串flag通常为文本 try: flag_part1 long_to_bytes(m_recovered).decode(‘utf-8’) print(f“通过共模攻击恢复的明文: {flag_part1}”) except: print(f“恢复的明文整数: {m_recovered}”) print(“可能不是直接可读文本或是flag的一部分。”)这段代码是共模攻击的核心。gmpy2.gcdext函数一次性完成了扩展欧几里得算法的计算。之后根据s和t的符号谨慎处理模逆元最后进行模幂运算相乘。4.3 实施低加密指数攻击对于e_small 3的那组数据我们首先尝试直接开方。# 尝试对c_small直接开3次方 root, is_exact gmpy2.iroot(c_small, e_small) # e_small3 if is_exact: print(f“低加密指数攻击成功明文为: {long_to_bytes(root).decode()}”) flag_part2 long_to_bytes(root).decode(‘utf-8’) else: print(“直接开方失败可能 m^3 n需要尝试广播攻击或其他方法。”) # 如果还有其他e3的密文可以在此处实现CRT广播攻击如果is_exact为True说明c_small恰好是一个整数的三次方攻击成功。否则可能需要结合其他e3的密文进行广播攻击或者考虑其他可能性比如明文进行了填充。4.4 信息组合与Flag获取在CTF中通过共模攻击和低加密指数攻击恢复出的可能是完整的flag也可能是flag的两部分需要拼接。也可能恢复出的是一段提示指向下一步操作比如另一个密钥或隐藏的文件。因此得到明文后要仔细查看内容。它可能是一个网址、一个密码、一段Base64编码、或者其他格式的数据。常见情况处理直接出Flag恢复的明文直接是flag{...}格式皆大欢喜。Hex或Base64编码恢复的明文是一串十六进制字符或Base64字符串需要进一步解码。提示信息明文可能是“The second part is in the file named ‘secret’.”之类的提示需要根据提示继续操作。拼接组合两部分攻击得到两个字符串需要按顺序拼接才能得到完整flag。实操心得在CTF中RSA题目恢复出的明文一定要先用long_to_bytes()转换成字节然后尝试decode(‘utf-8’)。如果报错不要轻易放弃尝试decode(‘latin-1’)或者直接打印字节看看是不是特殊格式如PKZIP头、图片头等。有时flag会被故意放在非文本数据中。5. 工具链与调试技巧工欲善其事必先利其器。除了Python一些专业工具能极大提升解题效率。5.1 核心Python库gmpy2 / mpmath处理大整数运算的利器。gmpy2速度极快尤其是pow,gcd,invert,iroot,gcdext等函数是密码学解题的标配。如果安装困难Python原生的pow(a, b, mod)函数也支持模幂运算但其他功能需要自己实现或用sympy库替代。Crypto.Util.number来自pycryptodome库。long_to_bytes()和bytes_to_long()是整数和字节流转换的神器。inverse()函数也可以求模逆元。sympy一个强大的数学符号计算库。它的gcdex,invert_mod,isprime,factorint尝试分解等功能也很实用可以作为gmpy2的备选。5.2 辅助工具与网站Factordb (factordb.com)这是一个在线的大数分解数据库。把n贴进去如果它之前被分解过或者n本身很小很容易分解它会直接返回p和q。这是解题的第一道“快筛”。RSACTFtool / RsaCtfTool一个功能强大的RSA攻击集成工具GitHub开源。它自动化了几乎所有常见的RSA攻击方式。你可以把n, e, c以特定格式保存到文件然后运行工具它会自动尝试各种攻击分解、共模、维纳、广播等。对于不熟悉脚本编写的新手或者想快速验证思路这个工具非常有用。Wolfram Alpha对于中小规模的整数运算、因式分解、方程求解直接在网页上输入非常方便。比如输入factor(123456789)或gcd(123, 456)。5.3 调试与排错实录即使思路正确代码也常常因为细节问题跑不出结果。以下是我踩过的一些坑问题1gmpy2安装失败。解决方案在Windows上推荐使用预编译的whl文件。在Linux/macOS上确保已安装libgmp和libmpc开发库。如果实在装不上可以暂时用Python原生整数和sympy库替代只是速度会慢一些。对于CTF题目通常数据量不大sympy也够用。问题2共模攻击计算出的明文是一串乱码或很大的数字。排查步骤检查数据输入确认n, e, c的值没有复制错误特别是数字1和字母l数字0和字母O。最好将题目源文件用文本编辑器打开确认编码。验证互质条件再次打印gmpy2.gcd(e1, e2)确保结果为1。检查模逆元计算当s或t为负数时模逆元计算是否正确用pow(c, -1, n)或gmpy2.invert(c, n)计算后验证(c * c_inv) % n 1。检查最终模运算确保m (c1^s * c2^t) % n中的乘法是在取模n之后进行的或者整个表达式在pow函数内完成。大整数直接相乘可能会溢出或效率极低。尝试交换s和t扩展欧几里得算法解不唯一。如果一组(s,t)不行可以尝试另一组比如(s k*e2, t - k*e1)其中k为任意整数。通常用gcdext返回的即可。问题3低加密指数攻击开方失败。可能原因m^e确实大于等于n这是最可能的原因。此时直接开方得到的是m^e // n的商不是m。需要尝试广播攻击如果有多组数据或其他攻击。密文c本身不是整数确保从文件读取时c被正确解析为整数而不是字符串。明文进行了填充标准的RSA加密前会对明文进行填充如PKCS#1 v1.5或OAEP。填充后的消息m’比原始明文大得多使得m’^e很可能大于n。CTF中为了简化经常使用“裸RSA”或自定义填充但这点需要注意。如果攻击失败查看恢复出的明文开头是否有标准的填充结构如0x00 0x02 ...。问题4恢复出的明文看起来像flag但格式不对或无法提交。处理技巧检查是否有不可见字符如换行符\n被包含在内。尝试将字节流用Hex编码输出看看。如果明文是数字考虑它是不是其他数据的索引或长度。将明文作为密钥尝试解密题目附带的另一个加密文件如果有的话。6. 从解题到防御RSA安全实践启示通过解这道题我们站在了攻击者的视角。反过来这也深刻地告诉我们在实际应用RSA时如何避免这些坑。6.1 密钥生成与参数选择禁忌绝对不要复用模数n这是共模攻击的根源。每一个用户、每一次密钥生成都必须使用独立、随机生成的大素数p和q来计算n。一个n对应一对密钥。公钥指数e的选择虽然e可以很小以提升加密速度但e3已被证明在多场景下不安全如广播攻击、小明文攻击。e65537 (0x10001)是目前公认的最佳选择。它是一个素数二进制表示中只有两个1使得模幂运算速度较快且足够大能有效抵御低加密指数攻击。私钥指数d不能太小虽然本题未涉及但d过小会导致Wiener攻击。确保在密钥生成时d的长度至少是n的位长度的1/4左右。素数p和q的生成必须使用密码学安全的随机数生成器CSPRNG来生成大素数。p和q应强度相当差值不能过小防费马分解p-1和q-1也应有大素因子防Pollard‘s p-1分解。6.2 加密填充的必要性“裸RSA”即直接对明文整数m进行m^e mod n运算在现实中是绝对不安全的。它存在多种问题确定性加密同样的明文永远产生同样的密文无法隐藏模式。** malleable可延展性**攻击者可以在不知道明文的情况下按照特定规则修改密文导致解密出的明文也按规则变化。对结构性明文脆弱正如低加密指数攻击所示如果明文是小的整数或具有某种结构很容易被破解。因此在实际使用中RSA必须与填充方案结合如OAEP最优非对称加密填充。填充方案会在加密前向明文引入随机性和冗余使得即使加密很小的消息填充后的结果也会是一个很大、很随机的数从而破坏代数结构抵御各类攻击。在CTF中题目常为了考察核心算法而省略填充但实际工程中绝不能省略。6.3 系统层面的考量密钥管理安全地存储和分发公钥/私钥防止私钥泄露。定期更换密钥。协议安全RSA通常用于密钥交换或数字签名而非直接加密大量数据。确保使用它的上层协议如TLS、PGP本身是安全的。算法升级关注密码学进展。RSA目前仍安全但其安全性依赖于大数分解的难度。随着量子计算的发展未来可能需要迁移到抗量子密码算法。回过头看“[RoarCTF 2019]RSA”这道题它就像是一个安全反面案例的集合复用n、使用小e。通过亲手破解它这些安全原则从枯燥的文字变成了刻骨铭心的教训。在真正构建系统时牢记这些禁忌使用经过严格审计的密码学库如Python的cryptography而不是自己手动实现RSA才是避免安全漏洞的正道。