1. 项目概述从零到一用Python脚本破解一道RSA题目如果你刚接触CTFCapture The Flag夺旗赛看到“Crypto”密码学和“RSA”这两个词是不是觉得头大感觉这玩意儿全是数学深不可测。别怕今天我就带你用Python像拼乐高一样一步步拆解一道经典的RSA题目。我们的目标不是让你立刻成为密码学专家而是让你亲手体验一次“破解”的快感理解RSA在CTF中最常见的攻击面。这次我们实战的靶子是攻防世界BUUCTF上的一道入门级题目“cr4-poor-rsa”。题目名字里的“poor”简陋已经给了我们提示它的RSA实现有缺陷。我们的任务就是找到这个缺陷并用Python脚本把它变成我们想要的Flag。为什么选择Python因为它语法简洁库丰富是CTF选手和网络安全从业者的“瑞士军刀”。你不需要深厚的数学功底只要会基本的Python语法跟着我的思路和代码就能看懂并复现整个破解过程。这篇文章会假设你是个编程新手但充满好奇心和动手欲望。我会解释每一个步骤“为什么要这么做”而不仅仅是“怎么做”。当你成功跑通脚本拿到Flag的那一刻你会对RSA有一个截然不同的、非常具体的认识。2. RSA基础与CTF常见攻击面解析在动手写脚本之前我们必须先搞懂我们在对付什么。RSA是一种非对称加密算法它基于一个简单的数论事实将两个大质数相乘很容易但把它们的乘积再分解回原来的两个质数却极其困难。2.1 RSA加密解密的核心流程想象一下RSA就像一把特殊的锁和钥匙。生成钥匙密钥对随机选择两个非常大的质数p和q。计算它们的乘积n p * q。这个n就是模数长度比特数决定了密钥的强度。计算欧拉函数φ(n) (p-1)*(q-1)。选择一个整数e作为公钥指数通常取65537。条件是1 e φ(n)且e与φ(n)互质最大公约数为1。计算d作为私钥指数使得(e * d) % φ(n) 1。即d是e模φ(n)的乘法逆元。至此公钥就是(n, e)可以公开。私钥是(n, d)或(p, q, d)必须严格保密。加密过程 假设明文是一个数字m文本信息需要先转换成数字。用公钥(n, e)加密c ≡ m^e (mod n)。得到的c就是密文。解密过程 用私钥(n, d)解密m ≡ c^d (mod n)。就能恢复出明文m。整个安全性的基石在于攻击者只知道公开的(n, e)和密文c想要求出私钥d就必须知道φ(n)而想知道φ(n)就必须分解n得到p和q。对于足够大的n比如2048位以上分解在现有计算能力下是不可行的。2.2 CTF中RSA题目的常见“命门”既然理论上RSA很安全那CTF题目考我们什么考的就是实现上的失误或特殊场景的漏洞。对于“cr4-poor-rsa”这类入门题常见的攻击面有模数n过小这是最经典的“poor”。如果n只有256位或512位以现代计算机的算力完全可以在短时间内暴力分解。这就是我们这道题的核心。共模攻击如果相同的明文m用相同的n但不同的e加密得到两个密文c1和c2且e1和e2互质则可以恢复明文。此题不涉及。低加密指数攻击如果公钥指数e非常小比如3而明文m也很小可能导致m^e n。此时加密操作c m^e mod n实际上没有取模直接c m^e对c开e次方就能得到m。低解密指数攻击如果私钥指数d过小可以通过Wiener攻击等方式破解。此题不涉及。因数碰撞如果多个RSA密钥使用了相同的质数p或q通过计算最大公约数GCD可以快速分解它们的n。已知高位攻击如果私钥d的部分比特位泄露可能危及整个密钥安全。对于我们手头的“cr4-poor-rsa”题目名字和附件信息已经强烈暗示了第一种情况模数n太小可以直接分解。我们的攻击思路因此非常清晰下载题目附件 - 提取公钥参数n和e- 尝试分解n得到p和q- 计算私钥d- 用私钥解密给出的密文 - 得到Flag。注意在真实的网络安全领域攻击一个正确实现且使用足够长密钥如2048位以上的RSA系统是极其困难的。CTF题目旨在教育让我们理解这些算法的边界和错误使用的后果切勿用于非法用途。3. 实战环境准备与题目附件分析工欲善其事必先利其器。我们不需要复杂的IDE一个能运行Python的环境和几个关键的库就够了。3.1 Python环境与必要库安装首先确保你的电脑安装了Python 3.6或以上版本。打开命令行Windows上是CMD或PowerShellMac/Linux上是Terminal输入python --version或python3 --version检查。我们需要两个核心库gmpy2这是一个高性能的数学库尤其擅长大整数运算和素数相关操作分解小模数n的速度远快于Python原生整数运算。pycryptodome或Crypto这是一个功能强大的密码学工具库我们主要用它来解析RSA公钥文件格式。安装它们pip install gmpy2 pycryptodome如果安装gmpy2遇到困难特别是在Windows上可以去 gmpy2的官方页面 查找对应你Python版本和系统的预编译轮子.whl文件进行安装。对于这道题如果实在装不上gmpy2用Python原生的大整数运算也可以只是分解速度会慢一点。3.2 下载并解构“cr4-poor-rsa”题目附件从攻防世界BUUCTF下载“cr4-poor-rsa”的题目附件。通常附件是一个压缩包解压后你会看到类似这样的文件public.key- 一个PEM格式的RSA公钥文件。flag.enc- 一个二进制文件里面是用上述公钥加密后的密文。我们的第一步是读取并解析公钥文件拿到关键的n和e。实操步骤1使用Python解析公钥from Crypto.PublicKey import RSA # 读取公钥文件 with open(public.key, r) as f: key_data f.read() # 导入公钥 pub_key RSA.import_key(key_data) # 提取模数n和公钥指数e n pub_key.n e pub_key.e print(f模数 n (hex): {hex(n)}) print(f模数 n (十进制, 长度): {n} ({n.bit_length()} bits)) print(f公钥指数 e: {e})运行这段代码你会得到类似下面的输出数值是示例模数 n (hex): 0xaa...很长一串十六进制 模数 n (十进制, 长度): 123456789... (256 bits) 公钥指数 e: 65537关键点解析n.bit_length()会告诉我们模数的比特长度。如果输出是256或512那恭喜你这几乎肯定是可以分解的。如果是1024可能需要更长时间或更强的算力。2048及以上对于这道入门题来说基本不可能。e是65537这是RSA中最常用、最安全的标准公钥指数之一说明出题人没有在e上设置陷阱。拿到n和e我们就拿到了打开第一道门的钥匙。接下来就是最核心的一步分解n。4. 核心攻击分解模数n并计算私钥这是整个破解过程的“心脏”。我们确认n很小比如256位那么就可以利用在线数据库或本地工具进行分解。4.1 利用在线数据库快速分解对于非常小的n通常小于768位最快的方法不是自己算而是去“查表”。有一个著名的网站叫FactorDB它收集了海量已知的因数分解结果。你可以将n的十进制或十六进制值提交上去查询。操作方法将上一步打印出的n的十进制值那一长串数字复制。访问 FactorDB 网站。在搜索框粘贴n的值点击查询。如果幸运网站会直接返回p和q的值。为什么能查到因为这些小的n可能被其他研究者或题目使用过早已被分解并收录进数据库。这是一种“知识型”攻击在CTF中非常常见且有效。4.2 使用Python本地分解如果在线数据库没有结果或者你想体验完整的破解流程就需要本地分解。我们将使用gmpy2库。实操步骤2分解模数nimport gmpy2 from Crypto.Util.number import long_to_bytes, bytes_to_long # 假设我们从第一步得到了 n # n pub_key.n (这里用示例值代替实际请用你读取到的n) # 示例一个很小的n仅用于演示真实题目n会大很多但可分解 # n 3233 # 实际题目n很大这里仅为演示流程 print(f开始尝试分解 {n.bit_length()} 位的模数 n...) # 方法1使用gmpy2的next_prime和整除试探适用于小n # 这不是最优方法但对于可分解的n通常有效 def factorize_n(n): # 这是一个简单的试除法变种从2开始找因子 # 对于CTF题目中的小ngmpy2自带的分解函数可能更快 # 但请注意对于超过一定位数的n此方法会极慢或无效 root gmpy2.isqrt(n) 1 # 我们尝试从2开始以2为步长递增只检查奇数 # 实际上对于RSA的p和q它们都是大质数且相差不会特别大。 # 更高效的方法是使用专门的分解算法如Pollards rho。 # 这里为了演示原理使用一个简单循环。 # 警告对于真实题目中的n如256位这个循环可能永远跑不完。 # 因此下面我们直接调用gmpy2的分解函数如果可用或使用更智能的方法。 # 实际上对于CTF中的“poor RSA”n通常小到可以用以下命令快速分解 # 使用 sympy 库 from sympy import factorint; factors factorint(n) # 或者使用 factordb 在线查询。 # 由于简单循环不现实我们这里模拟一个已分解成功的情景。 # 假设我们已经通过factordb.com查到了p和q # 从 factordb 获取的 p 和 q (你需要替换成实际值) p 123456791 # 示例质数p q 987654323 # 示例质数q # 验证 p * q 是否等于 n if p * q n: print(f分解成功) print(fp {p}) print(fq {q}) else: print(错误提供的 p 和 q 的乘积不等于 n。请检查分解结果。) exit() # 计算欧拉函数 φ(n) (p-1)*(q-1) phi (p - 1) * (q - 1) # 计算私钥指数 d即 e 模 φ(n) 的乘法逆元 # 条件 e * d ≡ 1 (mod φ(n)) d gmpy2.invert(e, phi) print(f私钥指数 d 计算完成: {d})关键点解析与避坑分解是瓶颈对于256位的n本地分解可能只需几秒到几分钟对于512位可能需要更长时间或更多内存。永远不要尝试在本地分解一个1024位或以上的RSA模数那可能耗费你一生的时间。gmpy2.invert(e, phi)这个函数计算的是模逆元即满足(e * d) % phi 1的d。这是恢复私钥的关键一步。验证分解结果务必检查p * q n。这是防止后续计算出错的保险丝。实操心得在CTF中遇到RSA题目第一步永远是print(n.bit_length())。如果n小于等于512位立刻想到分解。优先去FactorDB等网站查询这往往是最快的方式。本地分解可以作为备选但要知道其局限性。5. 解密密文与Flag提取现在我们手握私钥(n, d)密文文件flag.enc就像上了锁的宝箱而d就是唯一的钥匙。5.1 读取并解密密文密文文件flag.enc通常是二进制格式里面存储的就是加密后的数字c。我们需要读取它并将其转换为整数进行处理。实操步骤3解密获得明文# 读取密文文件 with open(flag.enc, rb) as f: # 注意是 rb 二进制读取 ciphertext f.read() # 将二进制密文转换为整数 c c bytes_to_long(ciphertext) print(f密文 c (整数): {c}) # 使用私钥指数 d 和模数 n 进行解密 # RSA解密公式 m ≡ c^d (mod n) m pow(c, d, n) # Python的pow函数支持模幂运算非常高效 print(f解密后的明文 (整数): {m}) # 将整数明文转换回字节串即我们可读的文本 plaintext long_to_bytes(m) print(f解密后的明文 (字节): {plaintext})代码细节解读open(flag.enc, rb)用二进制模式rb打开文件确保读取的字节原封不动。bytes_to_long()这是Crypto.Util.number中的函数将字节序列转换成一个大整数。因为RSA加密操作的对象是整数。pow(c, d, n)这是Python的内置函数计算c的d次方再对n取模。它使用了模幂运算优化算法如平方乘算法即使c,d,n都非常大计算速度也很快。千万不要用(c ** d) % n这会先计算一个天文数字般的中间结果导致内存溢出。long_to_bytes()将解密得到的整数m转换回字节串。这个字节串很可能就是Flag或者包含Flag的文本。5.2 处理解密结果与Flag格式化运行解密脚本后plaintext变量里存储的就是解密后的结果。但它不一定就是完美的Flag。常见情况与处理技巧直接输出可读字符串最理想的情况plaintext直接就是像flag{this_is_a_sample_flag}这样的字符串。直接print(plaintext.decode())即可。包含不可见字符或乱码有时解密出的字节串开头或结尾可能有填充字符如PKCS#1 v1.5填充。你可以尝试打印其十六进制形式查看print(plaintext.hex())。Flag可能藏在中间某段。常见的Flag格式有flag{...}、FLAG{...}、ctf{...}等你可以用if bflag{ in plaintext:来搜索。结果是数字需要进一步转换极少数情况下明文m本身可能代表另一个编码如ASCII码。如果plaintext看起来像一堆数字尝试将其作为整数再转换成字符。针对“cr4-poor-rsa”的最终脚本整合 将前面所有步骤整合成一个完整的脚本solve.py#!/usr/bin/env python3 # -*- coding: utf-8 -*- 攻防世界 cr4-poor-rsa 解题脚本 使用方法将 public.key 和 flag.enc 放在同目录运行本脚本。 from Crypto.PublicKey import RSA from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 def main(): # 1. 解析公钥获取 n 和 e print([*] 正在解析公钥文件...) with open(public.key, r) as f: pub_key RSA.import_key(f.read()) n pub_key.n e pub_key.e print(f [] n {n}) print(f [] n (比特长度) {n.bit_length()}) print(f [] e {e}) # 2. 分解 n (此处需要你根据实际情况填入分解得到的p和q) # 通常通过 factordb.com 查询得到 print([*] 请手动分解n或从factordb.com获取p和q。) # 示例你必须替换成题目实际的p和q: # p 123456791 # q 987654323 # 请取消下面三行的注释并填入正确的p和q # p 填入你的p # q 填入你的q # if p * q ! n: # print([-] 错误p * q ! n) # return # 假设我们已经有了正确的 p 和 q # 计算 phi 和 d phi (p - 1) * (q - 1) d gmpy2.invert(e, phi) print(f[] 私钥指数 d 计算完成) # 3. 读取并解密密文 print([*] 正在解密密文...) with open(flag.enc, rb) as f: c bytes_to_long(f.read()) m pow(c, d, n) flag long_to_bytes(m) # 4. 输出结果 print([] 解密完成) print( * 30) try: print(f明文 (文本): {flag.decode()}) except UnicodeDecodeError: print(f明文 (字节可能含不可见字符): {flag}) print(f明文 (十六进制): {flag.hex()}) print( * 30) if __name__ __main__: main()运行这个脚本前你需要完成最关键的一步填入从FactorDB或本地分解得到的正确p和q。一旦填入脚本就会自动完成后续所有计算并输出Flag。6. 常见问题、调试技巧与扩展思考即使跟着步骤做你也可能会遇到一些问题。这里我总结几个常见的坑和解决方法。6.1 问题排查清单ModuleNotFoundError: No module named Crypto原因没有正确安装pycryptodome库。解决运行pip install pycryptodome。注意导入时是from Crypto.PublicKey import RSA但安装的包名是pycryptodome。gmpy2安装失败原因gmpy2依赖GMP或MPIR数学库在某些系统上编译安装较复杂。解决Windows在 这里 下载对应你Python版本和系统架构的.whl文件然后用pip install 下载的文件名.whl安装。macOS使用Homebrew先安装GMPbrew install gmp然后再pip install gmpy2。放弃gmpy2如果只是分解很小的n可以尝试用Python原生整数运算配合sympy库pip install sympy使用sympy.factorint(n)进行分解。对于计算模逆元可以用pow(e, -1, phi)Python 3.8 支持。分解n失败或时间过长原因n可能比想象中大或者本地算法效率太低。解决首先确认n.bit_length()。如果是768位以上可能不是简单的分解题需要考虑其他攻击方式如共模、低指数等。务必优先使用FactorDB在线查询。可以尝试其他在线分解工具或本地工具如yafu速度更快。解密出的明文是乱码原因p和q填错了导致计算出错的d。密文文件flag.enc读取方式不对比如用了文本模式r而不是二进制模式rb。题目可能对明文进行了额外编码或填充。解决双重检查p * q n是否严格成立。检查文件读取代码。打印plaintext.hex()仔细查看输出。Flag可能以666c61677b“flag{”的十六进制开头。尝试搜索bflag或bCTF等关键字。脚本运行没报错但没输出Flag原因可能解密出的整数m需要进一步处理。解决在解密后除了转字节还可以尝试print(m)直接输出整数看是不是一个很长的数字。这个数字本身可能就是Flag有些题目Flag是数字格式。或者尝试将这个整数转换成十六进制hex(m)看看是否有可读的ASCII字符。6.2 扩展思考从这道题能学到什么成功破解“cr4-poor-rsa”只是一个开始。通过这个实战你应该建立起对RSA最基本的攻击直觉密钥长度是关键在CTF中看到小n就想分解。在现实世界中RSA密钥长度推荐至少2048位3072或4096位用于更高安全需求。工具链是生产力熟悉Python、Crypto、gmpy2/sympy、FactorDB这些工具能极大提升解题效率。理解比套用更重要你知道为什么分解了n就能算出d吗因为d依赖于φ(n)而φ(n) (p-1)(q-1)。这是RSA安全的根本也是它最脆弱的环节。下一步学什么掌握了基础分解你可以继续探索其他RSA攻击类型比如共模攻击写脚本实现扩展欧几里得算法恢复明文。低加密指数攻击当e3且明文很小时直接对密文开三次方。Wiener攻击当私钥d较小时的一种攻击。广播攻击相同的明文用相同的e但不同的n加密。最后别忘了CTF的精神是学习和挑战。这道“简陋的RSA”题目就像一把钥匙为你打开了密码学挑战的大门。当你下次再看到RSA时不会只是一头雾水而是会下意识地去检查n的位数思考可能的攻击路径。这种主动分析的思维才是最重要的收获。