CTF实战：从RSA核心原理到BabyRSA题目解析与Python脚本实现 1. 项目概述从一道典型RSA题切入CTF实战如果你刚接触CTFCapture The Flag竞赛尤其是密码学方向看到RSA相关的题目可能会有点发怵。那些大整数、模运算、公钥私钥的概念光看理论就够头疼了更别说上手解题了。别担心今天我们就以一道在BUU北京联合大学CTF平台上非常经典的入门题——GUET-CTF2019的BabyRSA为例用最接地气的方式手把手带你走一遍完整的解题流程。我的目标不是让你死记硬背几个公式而是让你真正理解“为什么这么做”以及“遇到类似问题该怎么想”。这道BabyRSA题之所以经典是因为它剥离了复杂的网络协议、混淆编码直指RSA最核心的几个考点大数分解、中国剩余定理CRT、以及简单的数学推导。通过这道题你将学会如何用Python的gmpy2库处理大整数如何从给定的参数中寻找漏洞并最终计算出私钥解密得到flag。我会附上每一步的完整代码和详细注释你完全可以跟着操作复现整个解题过程。无论你是零基础的爱好者还是有一定编程基础想入门CTF的同学这篇内容都将是一份极佳的实战手册。2. 题目分析与核心思路拆解拿到一道CTF的RSA题第一步永远不是急着写代码而是仔细阅读题目描述和附件理解它给了我们什么以及它可能隐藏了什么。对于BabyRSA题目通常会提供一个task.py或类似的脚本里面包含了RSA加密的关键参数。2.1 题目参数解析与潜在漏洞识别典型的BabyRSA题目会给出以下参数n: 模数由两个大素数p和q相乘得到n p * q。e: 公钥指数通常是一个较小的数如65537。c: 密文即flag经过pow(m, e, n)计算后的结果。安全RSA的前提是n足够大无法在有限时间内分解出p和q。但“Baby”级别的题目其n往往存在某种弱点让分解成为可能。常见的弱点包括模数n过小直接使用在线分解网站如factordb.com或本地工具如yafu就能分解。素数p和q过于接近导致n可以被费马分解法或简单的遍历攻击破解。使用了不安全的素数生成方法例如素数有某种数学关系使得n可以被其他数学方法分解。共模攻击如果两次加密使用了相同的n但不同的e且e1和e2互素则可以恢复明文。低加密指数攻击如果e非常小比如3而明文m也很小使得m^e n那么直接对密文c开e次方就能得到m。对于GUET-CTF2019 BabyRSA其核心漏洞在于素数生成不当。题目给出的n并不是一个随机的、难以分解的大数而是通过一个特定的数学过程生成的这使得我们可以通过推导而不是暴力分解来得到p和q。注意在真实比赛或练习中第一步永远是尝试用factordb查询n是否已被分解。如果数据库中有记录能直接得到p和q那题目就秒解了。这是一个非常重要的实战习惯。2.2 解题路线图规划基于对题目的初步分析我们可以规划出清晰的解题步骤获取并分析题目文件拿到task.py理解其中的参数定义和逻辑。推导素数关系这是本题最关键的思维部分。需要仔细分析p和q的生成代码找出它们之间的数学联系。构建方程求解利用找到的数学关系建立一个关于p或q的方程。编写求解脚本使用Python的sympy或通过数学变换解方程得到p和q的值。计算私钥参数得到p和q后计算欧拉函数φ(n) (p-1)*(q-1)然后求私钥指数d满足e * d ≡ 1 (mod φ(n))。解密得到Flag使用私钥(n, d)对密文c进行解密即计算m pow(c, d, n)再将得到的整数m转换为字节字符串flag。下面我们就进入最核心的环节一步步拆解并实现。3. 核心细节解析与数学推导我们假设拿到的task.py核心内容如下这是此类题目的常见形式import libnum from Crypto.Util.number import * flag flag{xxxxxxxxxxxxxx} m libnum.s2n(flag) # 将flag字符串转为大整数 p getPrime(512) q getPrime(512) n p * q e 65537 c pow(m, e, n) print(n , n) print(c , c) print(e , e) # 额外给出了一些提示信息 hint1 pow(2020 * p 2021, q, n) hint2 pow(2021 * p 2020, q, n) print(hint1 , hint1) print(hint2 , hint2)当然实际题目可能会把p和q的生成过程藏得更深比如# 另一种常见形式p和q与某个数有关联 x getPrime(256) y getPrime(256) p next_prime(x * y) # p是x*y的下一个素数 q next_prime(pow(x, 2) pow(y, 2)) # q是x^2y^2的下一个素数 n p * q对于GUET-CTF2019 BabyRSA其关键就在于分析hint1和hint2这两个提示。它们不是无用的数据而是解题的钥匙。3.1 利用Hint进行数学推导我们有两个提示hint1 pow(2020 * p 2021, q, n)hint2 pow(2021 * p 2020, q, n)首先理解pow(a, b, n)在Python中表示计算a^b mod n。所以hint1 ≡ (2020p 2021)^q (mod n)hint2 ≡ (2021p 2020)^q (mod n)这里的模数是n p * q。根据模运算的性质一个数模n的结果也等同于它分别模p和模q的结果在中国剩余定理的意义下。一个非常关键的突破口是考虑这两个表达式模p时的情形。因为n p * q所以任何计算模n的表达式我们都可以先看看它模p会怎样。对于hint1hint1 ≡ (2020p 2021)^q (mod p)由于2020p这一项模p等于0因为p能整除2020p所以上式简化为hint1 ≡ 2021^q (mod p)同理对于hint2hint2 ≡ (2021p 2020)^q (mod p) ≡ 2020^q (mod p)但是题目给我们的hint1和hint2是模n的结果我们并不知道它们模p的具体值。不过我们还有另一个强大的工具费马小定理。费马小定理指出如果p是一个素数且a不是p的倍数那么a^(p-1) ≡ 1 (mod p)。我们不知道2021和2020是不是p的倍数但通常在这种构造题中它们不是。即使万一它们是题目可能也无法解出所以我们可以先假设gcd(2020, p) 1且gcd(2021, p) 1。在这个假设下费马小定理成立。现在我们不知道q但我们可以利用hint1和hint2的表达式本身。注意hint1和hint2是已知的数。我们考虑计算(hint1 * 2021 - hint2 * 2020) mod n。为什么要这么算让我们展开看看根据之前的推导我们知道在模p的意义下hint1 ≡ 2021^q (mod p)hint2 ≡ 2020^q (mod p)那么hint1 * 2021 - hint2 * 2020 ≡ 2021^q * 2021 - 2020^q * 2020 (mod p)≡ 2021^(q1) - 2020^(q1) (mod p)这看起来没什么帮助。但如果我们考虑原表达式在模q下的情况呢这会引向另一个更巧妙的思路。实际上GUET-CTF2019 BabyRSA最经典的解法利用了二项式定理。我们重新审视hint1hint1 (2020p 2021)^q mod (pq)根据二项式定理展开(2020p 2021)^q除了最后一项2021^q其他每一项都包含p作为因子。因此当我们计算这个展开式模p时所有含p的项都变为0只剩下最后一项hint1 ≡ 2021^q (mod p)。这和之前一样。但关键点在于因为n p*q所以hint1模q会怎样由于底数(2020p 2021)模q等于多少我们不知道p mod q。但是我们可以利用费马小定理在模q下的形式。不过更常见的解法是直接利用两个提示构造一个方程。观察hint1和hint2我们可以尝试将它们相乘或者进行线性组合目标是消去未知的p得到一个只关于q和已知数的同余式。网上公开的Writeup揭示了一个巧妙的变换令A 2020p 2021B 2021p 2020那么hint1 A^q mod n,hint2 B^q mod n。考虑计算(hint1 - 2021^q)和(hint2 - 2020^q)。因为A^q (2020p2021)^q根据二项式定理A^q 2021^q k * p其中k是某个整数。因此A^q - 2021^q能被p整除。同理B^q - 2020^q也能被p整除。所以p能整除(A^q - 2021^q)和(B^q - 2020^q)。进而p也能整除它们的某个线性组合。通过精心构造我们可以让这个线性组合等于p乘以另一个已知或可求的数从而通过计算最大公约数gcd来得到p。具体地一个广泛使用的推导是hint1 * 2021 - hint2 * 2020 ≡ 2021^(q1) - 2020^(q1) (mod n)这个同余式对模p和模q都成立。在模p下右边等于2021^(q1) - 2020^(q1)。在模q下利用费马小定理假设2020,2021与q互质有2021^(q1) ≡ 2021^2 (mod q)2020^(q1) ≡ 2020^2 (mod q)。因此hint1*2021 - hint2*2020 ≡ 2021^2 - 2020^2 (mod q)即(hint1*2021 - hint2*2020) - (2021^2 - 2020^2) ≡ 0 (mod q)。这意味着q整除(hint1*2021 - hint2*2020) - (2021^2 - 2020^2)。而n也整除这个数吗不一定。但我们可以计算t (hint1*2021 - hint2*2020) - (2021^2 - 2020^2)那么q是t的一个因子。同时n也是已知的。因此我们可以计算gcd(n, t)。因为n p * q且q整除t那么gcd(n, t)很可能就是q本身除非t恰好也有p这个因子但概率极低。一旦得到qp n // q就迎刃而解。这就是本题最精妙的数学部分。它不需要高深的数论知识但需要敏锐的观察力和将已知条件转化为方程的能力。3.2 实操中的关键检查点在动手写代码前有几点必须确认数据完整性确保你从题目中获取的n, c, e, hint1, hint2数值正确无误一个字符的错误都会导致后续全盘皆输。大整数处理Python原生支持大整数但进行模逆运算求d和GCD计算时使用gmpy2库效率更高且能处理更大的数。互质条件在求私钥d时需要保证e和φ(n)互质即gcd(e, φ(n)) 1。通常e65537是素数只要它不整除(p-1)或(q-1)一般都没问题。算出d后可以验证一下pow(pow(123, e, n), d, n)是否等于123。Flag编码解密得到的m是一个大整数需要转换成字符串。通常使用libnum.n2s(m)或long_to_bytes(m)。注意字节序有时解密出的字节可能包含不可见字符需要尝试utf-8解码或直接打印十六进制查看。4. 完整Python解题脚本实现与逐行解读理论分析完毕现在进入最激动人心的实操环节。我们将编写一个Python脚本自动完成从推导到解密的全部过程。我推荐使用gmpy2这个库来处理大数运算它比Python原生的pow和math.gcd在超大数时更高效。4.1 环境准备与库安装首先确保你的Python环境建议3.8以上已经安装了必要的库。打开终端或命令提示符执行pip install gmpy2 pycryptodomegmpy2提供高性能的多精度算术运算。pycryptodome一个强大的密码学库这里我们主要用到它的Crypto.Util.number模块中的long_to_bytes函数。如果安装gmpy2遇到困难特别是在Windows上可以尝试安装预编译的轮子文件或者使用libnum库作为替代pip install libnum。4.2 解题脚本编写与注释假设我们从题目中获取到的数据如下实际解题时需替换为真实数据n 123456789... # 一个非常大的整数通常为1024或2048位 c 987654321... # 密文大整数 e 65537 hint1 111111111... hint2 222222222...下面是完整的解题脚本我几乎在每一行都加了注释确保你能看懂每一步在做什么#!/usr/bin/env python3 # -*- coding: utf-8 -*- BUU CTF 2019 BabyRSA 解题脚本 利用Hint推导出p和q进而解密得到flag import gmpy2 from Crypto.Util.number import long_to_bytes # 步骤1定义题目给出的已知参数 # -------------------------------------------------- # 请将以下变量替换为题目实际给出的数值 n gmpy2.mpz(你的n值) # mpz是gmpy2的大整数类型计算更快 c gmpy2.mpz(你的c值) e 65537 # 公钥指数通常是这个值 hint1 gmpy2.mpz(你的hint1值) hint2 gmpy2.mpz(你的hint2值) # 步骤2利用Hint推导计算中间量t # -------------------------------------------------- # 根据推导公式 t (hint1 * 2021 - hint2 * 2020) - (2021^2 - 2020^2) # 这个t值应该能被q整除 print([*] 步骤2利用Hint计算中间量 t...) part1 hint1 * 2021 - hint2 * 2020 part2 2021**2 - 2020**2 # 注意2021^2 - 2020^2 (2021-2020)*(20212020)1*40414041 t part1 - part2 print(f part1 (hint1*2021 - hint2*2020) {part1}) print(f part2 (2021^2 - 2020^2) {part2}) print(f t part1 - part2 {t}) # 步骤3计算gcd(n, t) 得到 q # -------------------------------------------------- print([*] 步骤3计算 gcd(n, t) 以获取素数 q...) # gmpy2.gcd(a, b) 计算最大公约数 q gmpy2.gcd(n, t) # 因为n p * q且q整除t所以gcd(n,t)很可能就是q本身 print(f 计算得到的 q {q}) # 步骤4通过 n // q 得到 p # -------------------------------------------------- print([*] 步骤4通过 n // q 计算另一个素数 p...) p n // q # 整数除法 print(f 计算得到的 p {p}) # 步骤5验证 p * q 是否等于 n # -------------------------------------------------- print([*] 步骤5验证 p * q n ...) if p * q n: print( √ 验证通过素数分解正确) else: print( × 验证失败请检查前面的推导或数据输入。) exit(1) # 步骤6计算欧拉函数 φ(n) (p-1) * (q-1) # -------------------------------------------------- print([*] 步骤6计算欧拉函数 φ(n)...) phi_n (p - 1) * (q - 1) print(f φ(n) {phi_n}) # 步骤7计算私钥指数 d满足 e * d ≡ 1 (mod φ(n)) # -------------------------------------------------- print([*] 步骤7计算私钥指数 d (e关于φ(n)的模逆元)...) # gmpy2.invert(a, m) 返回 a 模 m 的逆元即满足 a*x ≡ 1 (mod m) 的 x d gmpy2.invert(e, phi_n) print(f 计算得到的 d {d}) # 可选验证加解密过程用一个小数字测试 # -------------------------------------------------- print([*] 可选步骤验证私钥有效性...) test_num gmpy2.mpz(123456) encrypted_test pow(test_num, e, n) decrypted_test pow(encrypted_test, d, n) if test_num decrypted_test: print(f √ 加解密验证通过 (测试数: {test_num})) else: print(f × 加解密验证失败) # 可能原因是 e 和 φ(n) 不互质但e65537时很少见需检查p,q是否正确 # 步骤8解密密文 c得到明文整数 m # -------------------------------------------------- print([*] 步骤8解密密文 c得到明文 m...) m pow(c, d, n) # RSA解密核心公式 m c^d mod n print(f 解密得到的整数 m {m}) # 步骤9将整数 m 转换为字节串即flag # -------------------------------------------------- print([*] 步骤9将整数 m 转换为字节串...) # 使用 long_to_bytes 函数它来自 pycryptodome 库 flag_bytes long_to_bytes(m) print(f 转换后的字节串: {flag_bytes}) # 步骤10尝试以UTF-8解码输出最终flag # -------------------------------------------------- print([*] 步骤10尝试解码并输出flag...) try: flag flag_bytes.decode(utf-8) print(f\n 恭喜成功解密出flag: {flag}) except UnicodeDecodeError: # 如果UTF-8解码失败可能flag不是纯文本或者是其他编码 print(f UTF-8解码失败。原始字节的十六进制表示为: {flag_bytes.hex()}) print(f 请尝试其他解码方式或检查flag格式如是否包含flag{前缀。)4.3 脚本执行与结果分析将脚本中的n, c, hint1, hint2替换为题目实际给出的数值后运行脚本。如果一切顺利你将在控制台看到一步步的计算过程和最终的flag。这里有一个极其重要的实操心得运行脚本后务必关注以下几个检查点q的值打印出的q应该是一个很大的整数通常和p位数相同并且是一个素数可以用gmpy2.is_prime(q)快速验证一下。如果q打印出来是1或者一个很小的数那说明gcd(n, t)的计算结果不对很可能是因为你的hint1或hint2数值抄错了或者题目用的不是2020和2021这两个数字有些变种题会改用其他数字。p*q n验证这个验证必须通过否则后续计算毫无意义。测试加解密用一个小数字测试可以快速验证你计算出的(n, d)是否能正确解密。如果失败最常见的原因是e和φ(n)不互质导致d不存在。这时需要回头检查p和q的推导是否正确。Flag格式解密出的字节串如果能用utf-8解码成可读字符串并且包含flag{字样基本就成功了。如果不能解码可能是flag被进行了二次编码如base64、hex需要进一步处理。5. 常见问题排查与进阶思考即使跟着步骤做你也可能会遇到一些坑。这里我总结了几类常见问题及其解决方法。5.1 脚本运行报错与解决ModuleNotFoundError: No module named gmpy2解决方法确保已正确安装gmpy2。对于Windows用户如果pip install gmpy2失败可以尝试访问https://www.lfd.uci.edu/~gohlke/pythonlibs/#gmpy下载对应Python版本和系统位数的.whl文件然后用pip install 文件名.whl安装。ModuleNotFoundError: No module named Crypto解决方法你安装的可能是pycrypto它已过时。请卸载后安装pycryptodomepip uninstall crypto pycryptodome然后pip install pycryptodome。计算出的q是1或者p*q ! n这是最可能遇到的问题。首要检查百分之九十的原因是数据输入错误。请逐字核对从题目中拷贝的n, c, hint1, hint2的数值一个标点、一个换行都不能错。特别是hint1和hint2它们通常非常长容易在复制时丢失开头或结尾的数字。检查题目数字我们的推导基于2020和2021这两个数字。有些题目是变种可能使用其他数字比如2022和2023。请仔细阅读题目源代码task.py确认它里面写的是2020和2021还是其他数字。如果是其他数字需要修改脚本中对应的部分。检查推导公式如果数据没错数字也没错那可能是推导公式不适用于这道题。这时需要重新审视题目给出的hint表达式尝试其他数学变换。例如可以尝试计算gcd(n, hint1 - pow(2021, e, n))之类的组合看看是否能直接得到p或q的因子。UnicodeDecodeErrorwhen decoding flag解密出的m转换成字节后可能不是直接的utf-8文本。首先打印flag_bytes.hex()查看十六进制。如果开头是666c61677b即flag{的ASCII hex那么后面部分可能就是flag内容但可能混合了不可见字符。尝试flag_bytes.decode(‘ascii’, errors‘ignore’)忽略非ASCII字符。可能flag被用base64或hex编码过。观察字节串如果末尾有可能是base64。可以用import base64; base64.b64decode(flag_bytes)尝试解码。最直接的方法将m转换为16进制字符串hex(m)[2:]然后看能否从中识别出可读的ASCII字符。5.2 算法理解深化与变种题应对成功解出这道题后不要停留在“照抄代码”的层面。试着回答下面几个问题你的理解会更上一层楼为什么gcd(n, t)大概率等于q而不是n或其他数因为t是q的倍数根据我们的推导但不是p的倍数除非极其巧合。n的因子只有p和q。所以n和t的最大公约数就是它们共有的质因子即q。如果题目给的hint是pow(a*p b, q, n)和pow(c*p d, q, n)其中a,b,c,d是已知常数该如何推导方法是通用的。我们可以尝试构造线性组合(hint1 * c - hint2 * a)目标是消去p的高次项最终得到一个能被q整除的表达式。具体系数需要根据a,b,c,d的值来设定。除了这种方法还有别的思路吗有。因为n是p*q我们可以考虑在模p和模q两个维度上分别建立方程。例如由hint1 ≡ (a*pb)^q ≡ b^q (mod p)可得hint1 - b^q ≡ 0 (mod p)所以p能整除(hint1 - b^q)。但我们不知道b^q。不过我们可以计算hint1^e mod n这可能会引入更复杂的式子。通常出题人会设计好数字让线性组合的方法成为最简洁的路径。5.3 工具与资源推荐工欲善其事必先利其器。除了上面的脚本掌握以下工具能让你的CTF密码学解题效率倍增Factordb (factordb.com)在线大数分解数据库。遇到RSA题第一反应就是把n贴进去查一下说不定已经被分解好了。RsaCtfTool (GitHub开源)一个功能强大的RSA攻击工具集集成了数十种针对不安全RSA的攻击方法如维纳攻击、共模攻击、小d攻击等。对于已知n, e, c的情况它可以自动尝试各种攻击。SageMath一个基于Python的数学软件系统包含强大的数论和代数运算功能。对于更复杂的数学推导和方程求解Sage是终极武器。Python交互环境 (Jupyter Notebook/IPython)强烈建议在Notebook中分步运行上述脚本。可以方便地查看中间变量的值进行各种试探性计算对于理解过程和调试至关重要。最后我想说的是CTF密码学尤其是RSA其魅力在于将抽象的数学转化为实实在在的“开锁”过程。BabyRSA只是一个开始后面还有Coppersmith攻击、Rabin加密、OAEP填充等更复杂的内容。但万变不离其宗核心永远是理解算法原理、寻找题目弱点、并用代码实现攻击。希望这篇超详细的指南能帮你扎实地迈出第一步。当你看到flag{...}在屏幕上弹出的那一刻那种通过智慧与代码战胜挑战的成就感正是CTF最吸引人的地方。