1. 项目概述从一道CTF题看RSA算法的实战应用最近在BUUCTF平台上刷题又遇到了经典的RSA类型题目题目编号是“rsarsa”。这类题目在CTF竞赛中几乎是常客无论是Web、Crypto还是Misc方向RSA的身影都无处不在。对于刚接触CTF的新手来说RSA相关的题目往往是一道坎看着题目描述里给出的n、e、c或者一个.pem格式的公钥文件常常会感到无从下手。而对于有一定经验的选手RSA题则是快速拿分的保障因为其解题模式相对固定关键在于对算法原理的理解和工具链的熟练使用。这道“rsarsa”题目从名字就能看出它考察的核心就是RSA加密算法的攻击与解密。RSA作为一种非对称加密算法其安全性基于大数分解的困难性。在CTF中我们很少需要去正面破解一个正确实现的、参数安全的RSA出题人往往会故意设置一些“不安全”的参数或者泄露一些关键信息从而为我们打开突破口。解决这类题目的过程本质上就是一次对RSA算法脆弱点的系统性排查和实践。通过这道题我们不仅能巩固RSA的基础知识如公钥(n, e)、私钥(n, d)、加密c m^e mod n、解密m c^d mod n更能学习到在CTF场景下面对一个黑盒的RSA加密结果如何通过逆向思维利用已知条件可能是n的分解、e和d的关系、或是加密模式的缺陷来还原出明文m。这不仅仅是一次解题更是一次对密码学理论应用于安全攻防的深度体验。接下来我将详细拆解面对此类题目的通用思路、具体工具的使用方法以及我在实战中积累的避坑技巧。2. 解题环境准备与核心思路解析在开始动手解题之前搭建一个顺手的解题环境至关重要。CTF中的密码学题目尤其是RSA很少需要我们从零开始编写复杂的数论计算代码更多的是依靠成熟的工具和库来快速进行数学运算。2.1 工具链选择与配置我的核心工具是Python3配合gmpy2或sympy库来处理大整数运算。gmpy2是GMP库的Python接口速度极快是处理CTF中动辄1024位、2048位大数的首选。如果安装gmpy2遇到困难特别是在Windows上sympy库的n、factorint、gcdex等函数也是不错的替代品虽然速度稍慢但对于CTF题目规模的数据完全足够。除了Python环境还有一些专门针对RSA的工具非常好用RsaCtfTool这是一个功能强大的RSA攻击工具集合用Python编写。它集成了数十种针对弱RSA参数的攻击方法比如小n分解、费马分解、维纳攻击、共模攻击等。你只需要把题目给的n、e、c喂给它它就能自动尝试各种攻击方式对于不熟悉各种攻击场景的新手来说简直是神器。通常我会先用它跑一下看看有没有“一键秒杀”的可能。openssl命令行工具用于处理PEM格式的密钥文件。题目有时会给一个public.pem公钥文件我们需要用openssl rsa -pubin -in public.pem -text -modulus命令来提取出模数n和指数e。factordb.com网站这是一个收录了大量整数分解结果的在线数据库。很多时候CTF题目中的n并不是一个随机生成的、难以分解的大数而是出题人特意选用的、已经有记录的合数。将n提交到这个网站很可能直接得到p和q题目瞬间解决。注意在比赛环境中要确保对工具有充分的了解。过度依赖RsaCtfTool这类自动化工具可能导致在工具失效时束手无策。理解其背后的原理并能用Python手动实现核心攻击脚本才是根本。2.2 通用解题流程框架无论题目如何变化面对一个RSA题我的分析流程大致遵循以下步骤这就像一个诊断清单收集信息仔细阅读题目描述和附件。提取所有给出的数字它们可能是十进制的也可能是十六进制的通常以0x开头或结尾有L。关键信息包括模数n、公钥指数e、密文c。有时也会给出私钥指数d、p和q、或phi(n)欧拉函数值。将所有这些信息整理好复制到你的脚本或笔记中。初步观察检查n的大小。如果n很小比如小于512位直接尝试用sympy.factorint分解或者去factordb查询。检查e的值。常见的e有655370x10001也有非常小的e如3。小e可能带来低加密指数攻击。检查是否给出了多组(n, e, c)。如果有两组或以上且n相同e不同可能是共模攻击如果e相同n不同则可能是低加密指数广播攻击。尝试分解n这是RSA最直接的攻击路径。如果n能被分解为p和q那么一切迎刃而解。除了factordb还可以尝试费马分解当p和q接近时即|p-q|很小有效。Pollard‘s p-1算法当p-1或q-1的质因数都很小时有效。使用yafu这类强大的本地分解工具对于稍大的n。分析n、e、d的关系如果题目给出了d或者给出了与d相关的信息如dp、dq则可能不需要分解n。例如已知e和d可以通过计算e*d - 1来得到一个phi(n)的倍数进而可能分解n或直接解密。应用特定攻击模型如果常规分解走不通就要根据观察到的特征判断属于哪种已知的RSA攻击模型如维纳攻击d很小、低加密指数攻击、共模攻击等然后使用对应的脚本进行攻击。解密与格式化得到私钥参数后计算私钥指数d e^(-1) mod phi(n)然后解密m pow(c, d, n)。得到的m是一个大整数需要将其转换为字节串long_to_bytes或字符串这可能就是flag。3. 核心攻击手法详解与实战脚本理解了流程我们深入看看几种在CTF中最常见的RSA攻击手法及其Python实现。我会结合“rsarsa”这类题目的常见套路来讲解。3.1 模数分解一切的基础绝大多数简单的RSA题突破口都在于n可以被分解。假设我们从题目中得到了n 12345678901234567890123456789012345678901234567890123456789012345678901234567 e 65537 c 密文一个大整数第一步尝试在线分解将n粘贴到 factordb.com。如果运气好网站直接返回了p和q。第二步本地脚本计算一旦有了p和q后续计算就标准化了。下面是一个完整的解密脚本import gmpy2 from Crypto.Util.number import long_to_bytes # 题目给出的数据 n 0x... # 你的n十六进制或十进制 e 65537 c 0x... # 你的密文c # 从factordb获得的p和q p 1234567890123456789012345678901234567890123456789012345678901234 q n // p # 或者直接给出q # 1. 计算欧拉函数 φ(n) phi (p-1) * (q-1) # 2. 计算私钥指数 d即 e 模 φ(n) 的模逆元 d gmpy2.invert(e, phi) # 使用gmpy2快速计算大数模逆 # 3. 解密得到明文 m m pow(c, d, n) # 使用模幂运算效率远高于 (c**d) % n # 4. 将整数m转换为字节即flag flag long_to_bytes(m) print(flag.decode()) # 尝试解码为字符串实操心得gmpy2.invert和pow(a, b, c)是RSA解题脚本的“黄金搭档”。一定要用pow(c, d, n)这种三参数形式它采用了模幂优化算法可以瞬间计算c^d mod n。如果写成(c**d) % n对于CTF级别的大数你的程序会卡死甚至内存溢出。3.2 低加密指数攻击当e很小时为了加密快速有时会使用非常小的公钥指数e比如e3或e5。如果同时明文m也比较小使得m^e n那么加密过程c m^e mod n实际上就等于m^e因为没超过模数n。此时直接对密文c开e次方根即可得到明文m。攻击条件e很小且m^e n。攻击方法直接计算m gmpy2.iroot(c, e)[0]如果结果是整数则攻击成功。import gmpy2 from Crypto.Util.number import long_to_bytes n 非常大的数 e 3 c 一个比n小很多的数 # 尝试开e次方 m, is_exact gmpy2.iroot(c, e) if is_exact: print(“低加密指数攻击成功”) print(long_to_bytes(int(m))) else: print(“开方结果不是整数可能m^e n需尝试其他攻击。”)更常见的情况m^e只是略大于n即c m^e - k*n其中k是一个不大的整数。这时我们可以遍历k计算(c k*n)再开e次方看结果是否为整数。import gmpy2 for k in range(1000000): # 遍历一个合理范围的k m, is_exact gmpy2.iroot(c k*n, e) if is_exact: print(f“Found k{k}”) print(long_to_bytes(int(m))) break3.3 共模攻击同一明文不同密钥加密如果同一个明文m用相同的n但不同的e比如e1和e2进行加密得到了两个密文c1和c2并且e1和e2互素gcd(e1, e2)1那么我们就可以在不分解n、不知道私钥的情况下恢复明文。原理根据扩展欧几里得算法存在整数s1和s2使得e1*s1 e2*s2 1。那么我们可以计算m (c1^s1 * c2^s2) mod n如果s1或s2是负数我们需要先计算对应密文的模逆元。攻击脚本import gmpy2 from Crypto.Util.number import long_to_bytes n 相同的模数 e1, c1 第一组公钥和密文 e2, c2 第二组公钥和密文 # 1. 使用扩展欧几里得算法求系数s1, s2 gcd, s1, s2 gmpy2.gcdext(e1, e2) # gcdext返回 (g, s, t) 使得 a*s b*t g gcd(a,b) # 因为e1和e2互素所以gcd1 # 注意s1或s2可能为负数 if s1 0: # 如果s1为负需要计算c1的模逆元并将s1取正 c1_inv gmpy2.invert(c1, n) m1 pow(c1_inv, -s1, n) else: m1 pow(c1, s1, n) if s2 0: c2_inv gmpy2.invert(c2, n) m2 pow(c2_inv, -s2, n) else: m2 pow(c2, s2, n) # 2. 计算明文 m m1 * m2 mod n m (m1 * m2) % n print(long_to_bytes(m))3.4 维纳攻击当私钥d过小时如果私钥指数d相对于模数n来说太小具体来说满足d (1/3) * n^(1/4)那么可以通过连分数展开的方法利用公钥(n, e)快速计算出d。这在CTF中也是常见考点。攻击条件d很小通常e很大接近n。攻击方法通常直接使用RsaCtfTool的--attack wiener选项或者使用现成的维纳攻击脚本。由于实现涉及连分数理论手动编写较复杂在此不展开代码但理解其适用场景非常重要。当你看到n很大e也很大比如和n一个数量级并且其他简单攻击都无效时就该考虑维纳攻击了。4. BUUCTF “rsarsa” 典型解题过程模拟与深度剖析由于无法获取原题的具体数值我将基于BUUCTF平台RSA题目的常见模式和上述攻击手法构建一个高度仿真的解题场景并展示完整的思考过程和脚本调试细节。假设题目附件rsarsa.zip包含以下文件public.pem: 一个PEM格式的公钥文件。flag.enc: 一个二进制文件即加密后的密文。4.1 第一步信息提取与初步观察首先使用openssl提取公钥信息openssl rsa -pubin -in public.pem -text -modulus -noout输出可能类似于Public-Key: (256 bit) Modulus: 00:c2:63:3f:... [很长一串十六进制] Exponent: 65537 (0x10001) ModulusC2633F...这里我们得到了模数n从Modulus后面的一串十六进制字符串转换而来和公钥指数e65537。注意openssl输出的模数十六进制可能没有0x前缀且需要去掉冒号拼接起来。接着读取密文文件。密文可能是直接表示c的十六进制或Base64字符串也可能就是原始的二进制字节。我们需要将其转换为Python整数。with open(‘flag.enc’, ‘rb’) as f: c_bytes f.read() c int.from_bytes(c_bytes, ‘big’) # 假设是大端序存储的整数 # 或者如果文件里是16进制文本 # c int(open(‘flag.enc’).read().strip(), 16)现在我们手头有了n,e65537,c。4.2 第二步尝试分解模数n观察到n是256位从openssl输出可知这在现代密码学中是非常不安全的但在CTF中很常见。我们首先尝试分解。方法A使用factordb网站将n的十进制或十六进制值提交到 factordb.com。假设我们幸运地得到结果p 12345678901234567890123456789012345678901234567890123456789012345678901234567 q 98765432109876543210987654321098765432109876543210987654321098765432109876543注意实际题目中的p和q会是质数这里仅为示例格式方法B使用yafu工具如果factordb没有结果可以尝试用yafu在本地分解。对于256位的nyafu的factor()命令通常能在几秒到几分钟内完成。方法C检查是否为简单分解有时n可能是由两个非常接近的质数相乘或者p和q其中一个很小。可以写一个简单的脚本检查小质因数import sympy small_primes [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97] for prime in small_primes: if n % prime 0: print(f“Found small factor: {prime}”) p prime q n // p break4.3 第三步执行标准解密流程一旦成功分解得到p和q就进入“垃圾时间”——标准计算。但这里依然有细节需要注意。import gmpy2 from Crypto.Util.number import long_to_bytes # 假设我们已经获得了p和q p 从分解得到的p q 从分解得到的q n p * q # 可以验算一下是否和题目给的n一致 e 65537 c 从文件读取的c # 计算私钥 phi (p-1) * (q-1) d gmpy2.invert(e, phi) # 解密 m pow(c, d, n) # 输出结果 print(“Decrypted integer m:”, m) flag long_to_bytes(m) try: print(“Flag:”, flag.decode(‘utf-8’)) # 尝试UTF-8解码 except UnicodeDecodeError: print(“Flag (hex):”, flag.hex()) # 如果不是UTF-8输出16进制看看 # 有时flag可能包含不可打印字符或者本身就是其他格式如bytes4.4 第四步处理非预期情况与深度排查如果按照上述“分解-解密”流程没有得到可读的flag那就要启动深度排查模式。这是区分新手和老手的关键。情况1解密出的m是一个很大的整数但转成字节后是乱码。可能原因1p和q顺序错了。RSA要求p和q都是质数但计算phi(n)和d时p和q的顺序无关紧要。但有一种罕见情况如果题目用的不是标准RSA而是基于np*q*r多素数RSA那分解和计算就完全不同了。首先检查p和q是否确实是质数用sympy.isprime。可能原因2密文c提取错误。回头检查flag.enc文件。用hexdump -C flag.enc看看文件原始内容。密文可能不是直接的整数字节流而是经过Base64或十六进制文本编码的。你需要先解码再转换成整数。import base64 with open(‘flag.enc’, ‘r’) as f: b64_data f.read() c_bytes base64.b64decode(b64_data) c int.from_bytes(c_bytes, ‘big’)可能原因3解密后的m并不是最终的flag。有时m是另一段需要进一步处理的数据。比如m可能是一个压缩包的密码或者它本身还需要用其他方式解码如Base64、ROT13等。尝试对m的字节形式进行各种常见解码。情况2根本无法分解n。这说明题目可能不是简单的分解题。需要回到第2.2节的“初步观察”步骤重新审视数据。检查是否有多组(n, e, c)题目可能给了两个flag.enc和两个public.pem暗示共模攻击或广播攻击。检查e是否非常小如果e3或e5尝试低加密指数攻击。检查e是否非常大如果e和n差不多大考虑维纳攻击。检查是否给出了dp或dqdp d mod (p-1)dq d mod (q-1)。如果给出了dp、dq、p、q、c即使没有n和完整的d也可以利用中国剩余定理(CRT)快速解密。这是RSA-CRT的故障注入攻击的常见考点。重新审题题目描述中可能隐藏了关键信息比如“素数生成有问题”、“两个公钥有联系”等。5. 进阶技巧与实战避坑指南在经历了数十道RSA题目的“洗礼”后我总结出一些教科书和工具文档里不会写的经验和技巧。5.1 数据格式处理的那些“坑”编码陷阱题目给的n、c可能是十进制、十六进制带或不带0x、Base64甚至可能是写在代码注释里。openssl输出的Modulus是十六进制带冒号的格式需要先去掉冒号。养成一个好习惯任何从文件或网页复制来的数字先用Python的print(repr(data))看看它的原始字符串形式。字节序问题当密文是二进制文件时int.from_bytes(c_bytes, ‘big’)中的’big’和’little’要试一下。大部分网络传输和标准RSA库默认使用大端序(’big’)但也不排除出题人用的小端序。PEM文件读取除了用openssl命令行在Python中可以用Crypto.PublicKey.RSA.importKey()来直接导入PEM文件并提取n和e更不容易出错。from Crypto.PublicKey import RSA with open(‘public.pem’, ‘r’) as f: key RSA.importKey(f.read()) n key.n e key.e5.2 脚本调试与验证技巧构造验证用例在写攻击脚本时可以先自己用小的p、q比如100位左右生成一组RSA密钥加密一个已知消息然后用你的脚本去攻击解密。这能极大增强你对脚本正确性的信心。中间结果打印在关键步骤后打印中间变量比如分解后的p、q计算出的phi、d解密前的m。确保它们的值符合预期例如p*qne*d % phi 1。使用long_to_bytes和bytes_to_longCrypto.Util.number里的这两个函数是处理整数和字节转换的利器比手动用hex、encode、decode拼接要可靠得多。5.3 面对陌生题型的思维策略当你遇到一道全新的、用常规套路解不开的RSA题时可以按以下顺序思考信息是否给全是否漏掉了附件里的某个文本文件、图片隐写、或网页源代码中的注释是否是非标准RSA变种如Rabin算法e2、Paillier算法等。但CTF中通常会在题目描述中提示。是否是侧信道或故障攻击这类题通常会给一些额外的信息比如多次加密的计时数据、错误的签名结果等。是否考察对RSA底层数学的深刻理解比如已知n,e,d如何分解n已知n和(pq)或(p-q)如何分解这些都有固定的数学推导方法。最后的手段搜索。将题目中独特的数字如n的后几位、特殊的e值或描述关键词加上“CTF RSA”一起搜索很可能找到类似的题目和Writeup。5.4 资源与工具清单最后把我常用的资源整理一下方便随时取用本地环境Python3 gmpy2/sympypycryptodome提供Crypto.Util.number。分解工具第一选择 factordb.com本地重型武器yafu适用于~200位以下的nPython库sympy.factorint适用于小n综合攻击工具RsaCtfToolGitHub搜索即可找到建议在Docker中运行以避免依赖问题。在线计算工具对于一些简单的模逆、幂运算可以用 wolframalpha.com 验证。学习资源CTF Wiki的RSA板块、各种CTF平台的Writeup合集。理解原理比记住工具命令更重要。解决“rsarsa”这类题目的过程就像一次系统的密码学体检。从信息收集、工具使用到攻击路径选择、脚本调试最后成功解密出flag每一步都考验着你的细心、耐心和对知识的灵活运用。希望这篇结合了实战经验和深度剖析的长文能帮你建立起一套应对CTF中RSA题目的坚固方法论。下次再看到n、e、c你就能从容地打开Python开始你的“拆解”之旅了。