1. 项目概述从一道CTF题看RSA加密的实战拆解今天想和大家复盘一道来自BUUCTF平台的每日打卡题日期是2021年5月18日。这道题本身是一个典型的RSA加密挑战但它的价值远不止于解出一个Flag。对于刚接触CTFCapture The Flag安全竞赛的朋友或者对密码学、尤其是非对称加密RSA感兴趣的学习者来说这道题提供了一个近乎完美的微型实战场景。它不像那些庞杂的综合渗透测试而是聚焦于一个核心点给你加密后的数据密文和公开的密钥参数如何利用数学原理和工具将其还原为原始信息明文。这个过程就是一次对RSA算法从理论到实践的深度穿越。RSA算法作为现代网络通信的基石之一从HTTPS的握手到软件的数字签名无处不在。但在教科书里它是一堆数学公式在CTF题里它变成了一个等待被“打开”的锁。这道2021年的老题恰好卡在了一个非常经典的知识点上涉及到大数分解的脆弱性。通过拆解它我们不仅能学会使用openssl、Python的Crypto库等工具更能直观理解“为什么参数的选择如此重要”、“为什么过短的密钥不再安全”。无论你是想入门CTF密码学方向还是希望加固自己对加密算法的理解跟着这道题的思路走一遍收获会比单纯看理论大得多。下面我就以解题为主线把其中涉及的核心原理、工具操作和避坑经验毫无保留地分享出来。2. 题目核心与RSA算法原理快速回顾拿到任何一道CTF的密码学题目尤其是RSA第一步永远不是急着运行脚本而是仔细阅读题目描述提取所有给出的参数。通常题目会提供一个flag.enc加密后的flag文件和一个public.key公钥文件有时也会直接给出模数n和公钥指数e。这道题便是如此。2.1 RSA加密的基本流程RSA的安全性建立在“大数分解难题”之上。简单来说我给你两个大质数p和q的乘积n你想从n倒推出p和q在计算上是极其困难的。整个加解密过程围绕几个核心参数展开选择两个大质数p和q。计算模数n p * q。n的长度比特数就是常说的密钥长度如2048位。计算欧拉函数φ(n) (p-1)*(q-1)。这个值在生成私钥时至关重要但必须保密。选择公钥指数e通常是一个较小的质数如65537 (0x10001)满足1 e φ(n)且e与φ(n)互质。计算私钥指数d是e模φ(n)的模逆元即满足(d * e) % φ(n) 1。d就是私钥的核心部分。公钥由(n, e)组成用于加密。加密过程ciphertext plaintext ^ e mod n。私钥由(n, d)组成用于解密。解密过程plaintext ciphertext ^ d mod n。在CTF题目中我们作为攻击者目标就是利用题目可能给出的任何弱点比如n太小、p和q很接近、e很大导致d很小等来恢复出私钥d从而解密flag.enc。2.2 本题的突破口分析对于“BUUCTF 每日打卡 2021-5-18”这道题其经典之处在于它给出的RSA公钥中的模数n并不大。通过openssl命令解析公钥文件后我们可以直接得到n和e。如果n的数值较小例如小于768位或1024位那么在当今的计算能力下完全有可能在可接受的时间内几秒到几分钟通过在线大数分解数据库如 factordb.com或本地工具如 yafu将其分解为p和q。一旦成功分解n得到p和q我们就能计算出φ(n) (p-1)*(q-1)进而根据公式d gmpy2.invert(e, φ(n))计算出私钥指数d。有了私钥解密便是水到渠成。所以这道题的核心解题链路非常清晰获取参数 - 分解n - 计算私钥 - 解密。它完美地演示了当RSA密钥长度不足时其安全性是如何土崩瓦解的。3. 实操步骤详解从公钥到Flag下面我们进入具体的操作环节。我会假设你有一个基本的Linux环境Windows下可用WSL或Git Bash并安装了Python3和必要的库。3.1 第一步提取公钥中的n和e通常题目会给出一个public.pem或pub.key文件。我们使用OpenSSL这个瑞士军刀来查看其内容。# 查看公钥的详细文本信息可以看到模数和指数Base64编码格式 openssl rsa -pubin -in public.pem -text -noout执行后你会看到类似这样的输出Public-Key: (256 bit) Modulus: 00:c2:63:7f:45:be:... (很长一串十六进制) Exponent: 65537 (0x10001)这里的关键信息是Modulus: 这就是模数n以十六进制表示。注意输出的十六进制可能带有冒号分隔也可能没有。我们需要将其转换为一个十进制大整数。Exponent: 公钥指数e绝大多数情况下是65537。实操要点OpenSSL输出的十六进制我们需要将其整理成一个连续的字符串去掉冒号和空格并去掉可能存在的00:前缀然后通过Python转换为十进制整数。例如如果输出是00:c2:63:7f那么有效的十六进制串是c2637f。3.2 第二步分解模数n这是解题最关键的步骤。将上一步得到的十进制大整数n尝试进行因数分解。在线分解推荐首选访问factordb.com这个网站直接将n的十进制数值粘贴到查询框。如果这个n曾经被其他人分解过或者它本身很小数据库里很可能已经有结果了。网站会直接返回p和q。本地工具分解如果在线数据库没有结果或者你想在离线环境下操作可以使用yafu这个强大的因数分解工具。对于小于256位的nyafu的factor()函数通常能很快搞定。# 启动yafu交互界面 ./yafu # 在yafu提示符下输入 factor(你的n的十进制数值)分解成功后它会输出p和q的值。注意事项如果题目中的n非常大比如2048位以上那么这道题大概率不是考分解而是考察其他RSA攻击方式如共模攻击、低加密指数攻击、维纳攻击等。本题因为是“每日打卡”难度且年份较早所以n较小分解是可行路径。3.3 第三步计算私钥并解密成功获取p和q后我们就可以在Python中计算私钥并解密了。这里需要用到gmpy2或pycryptodome库来处理大数运算。首先确保安装必要库pip install pycryptodome gmpy2然后使用以下Python脚本进行解密from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 # 1. 填入你从题目中获取的值 n 123456789... # 替换为你的模数n (十进制大整数) e 65537 # 通常是这个值 p ... # 替换为分解得到的质数p q ... # 替换为分解得到的质数q # 2. 计算私钥参数 phi (p - 1) * (q - 1) d int(gmpy2.invert(e, phi)) # 计算私钥指数d # 3. 构建私钥对象 key RSA.construct((n, e, d, p, q)) # 4. 读取加密的flag文件 with open(flag.enc, rb) as f: ciphertext f.read() # 5. 解密注意填充方式CTF中常见PKCS1_v1_5或无填充 # 方案A如果加密使用了PKCS1_OAEP填充现代标准 cipher PKCS1_OAEP.new(key) plaintext cipher.decrypt(ciphertext) print(fFlag (PKCS1_OAEP): {plaintext.decode()}) # 方案B如果加密是简单的“明文^e mod n”即无填充或自定义填充需要直接计算 # cipher_int bytes_to_long(ciphertext) # plain_int pow(cipher_int, d, n) # plaintext long_to_bytes(plain_int) # print(fFlag (Raw): {plaintext.decode()})核心细节解析填充方案这是解密时最容易出错的地方。标准的RSA加密为了安全性会对明文进行填充如PKCS1_v1_5或OAEP。CTF题目中为了简化有时会使用无填充的“教科书式RSA”。如果使用PKCS1_OAEP解密报错ValueError: Ciphertext with incorrect length.很可能意味着加密时未使用标准填充。此时需要尝试方案B的直接模幂运算。construct方法RSA.construct()函数非常强大它允许我们直接传入(n, e, d, p, q)等元组来构建一个RSA密钥对象而无需从文件加载。文件读取务必以二进制模式(rb)读取flag.enc因为密文是二进制数据。运行脚本后正确的Flag通常就会打印在终端上格式可能为flag{...}或BUUCTF{...}。4. 深入原理为什么分解n就能破解RSA上面我们完成了实操但知其然更要知其所以然。为什么分解n是RSA的“命门”这需要回到RSA的数学基础。RSA的解密密钥d是通过公式d ≡ e^(-1) (mod φ(n))计算得到的。而φ(n) (p-1)*(q-1)。在整个公钥体系中n是公开的但p和q是保密的。因此攻击者无法直接计算φ(n)。大数分解难题的假设是给定一个由两个大质数相乘得到的合数n想要在合理时间内找出原来的p和q是计算不可行的。只要这个假设成立攻击者就无法从公开的n求得φ(n)也就无法计算出私钥d。然而这个“计算不可行”是相对于n的长度而言的。随着计算机计算能力的提升和算法如数域筛法的改进过去认为安全的密钥长度现在可能已经不再安全。例如早在1999年512位的RSA密钥就被成功分解。目前对于一般用途2048位是基准线需要长期安全的应用则推荐3072位或4096位。这道题使用的n长度较短正是刻意违背了“大数”的前提使得分解在瞬间完成从而直观展示了密钥长度不足的风险。在实际的CTF比赛中你会遇到各种围绕n、e、d、p、q关系做文章的变种题例如共模攻击相同的n不同的e加密了同一明文。低加密指数攻击e非常小如3且明文也很小导致m^e n加密等于没加密。维纳攻击当私钥d相对较小时可以通过连分数逼近的方法在多项式时间内破解。p和q过于接近导致|p-q|很小可以通过费马分解法快速分解n。理解这些攻击的本质都离不开对RSA数学模型的深刻把握。这道基础分解题是打开这扇大门的第一把钥匙。5. 工具链与常见问题排查在实战中工具用得不顺手或者遇到意外错误是常事。这里我整理了一份从解题到调试的常用工具链和问题排查指南。5.1 必备工具链清单OpenSSL: 处理各种编码、查看解析密钥、转换格式的万金油。除了查看公钥还能将公钥/私钥在不同格式PEM, DER间转换。Python3 Crypto/Pycryptodome库: 主要的计算和脚本编写环境。Pycryptodome是PyCrypto的一个维护良好的分支功能更全。GMPY2: 一个提供高精度快速大数运算的Python库在计算模逆、大数幂模运算时比Python原生整数运算快得多处理非常大的数字时几乎是必备的。Factordb (在线) / Yafu (本地): 如前所述用于分解n。对于本地分解Yafu非常强大它集成了多种先进的分解算法。RSACTFTool / RsaCtfTool: 这是一个用Python写的集成化RSA攻击工具包。当你面对一道RSA题没有头绪时可以尝试用它自动攻击。它内置了数十种攻击方式包括低指数、共模、维纳攻击、以及尝试从各种格式的文件中自动提取参数等。对于新手来说这是一个“开箱即用”的神器。python RsaCtfTool.py --publickey public.pem --uncipherfile flag.enc5.2 高频错误与解决方案即使按照步骤操作你也可能会遇到以下问题。这里是我的“踩坑”记录问题1openssl rsa -pubin -in public.pem -text -noout命令报错“Expecting: PUBLIC KEY”。原因公钥文件的格式不对。可能是文件开头结尾的标记不正确或者它实际上是一个包含公钥的证书.crt文件。解决检查文件内容。标准的PEM格式公钥以-----BEGIN PUBLIC KEY-----开头。如果是证书使用命令openssl x509 -in public.crt -pubkey -noout | openssl rsa -pubin -text -noout来提取并查看公钥。有时题目给的公钥是SSH格式ssh-rsa AAAAB3...需要先转换为PEM格式。可以用ssh-keygen -f public.key -e -m pem public.pem转换。问题2分解n后用Python脚本解密报错ValueError: Ciphertext with incorrect length。原因这是最典型的填充模式不匹配错误。PKCS1_OAEP解密期望密文长度等于密钥长度字节数。如果加密时使用的是无填充或PKCS1_v1_5填充用OAEP解密就会失败。解决尝试使用PKCS1_v1_5模式from Crypto.Cipher import PKCS1_v1_5; cipher PKCS1_v1_5.new(key)。如果还不行大概率是“教科书式RSA”无填充。直接使用plain_int pow(cipher_int, d, n)计算如3.3节中的方案B。注意ciphertext需要先通过bytes_to_long()转换成整数。问题3计算出的私钥d是负数或者解密得到乱码。原因n分解错误这是最根本的原因。请务必核对p * q是否等于原始的n。φ(n)计算错误确保是(p-1)*(q-1)而不是p*q-1或其他。密文文件读取错误确保以二进制模式(‘rb’)读取且文件内容完整。e值错误虽然99%是65537但仍有题目会使用其他e如3、17。用OpenSSL确认e的值。解决建议写一个简单的验证脚本print(fCheck n p*q: {n p*q}) print(fCheck (d*e) % phi 1: {(d*e) % phi 1})如果第一个检查为False立刻回头检查分解步骤。如果第二个为False检查phi的计算和gmpy2.invert函数的使用。问题4使用在线分解网站没有结果yafu分解也很慢。原因说明这道题的n可能并不小或者出题人特意选用了能抵抗快速分解的素数。这道题可能不是考分解。解决重新审视题目。检查e是否特别大可能导致d小适用维纳攻击是否有多个公钥文件可能考共模攻击密文c是否非常小可能考低加密指数攻击此时应该转向使用RsaCtfTool进行自动化测试或者系统学习其他RSA攻击模型。6. 从解题到精通RSA在CTF中的进阶考点解出这道基础题只是一个开始。BUUCTF以及其他CTF平台上有大量更深入的RSA题目它们像一个个精心设计的谜题考察你对算法各个维度的理解。以下是一些常见的进阶考点和思路6.1 多种攻击场景与识别特征攻击类型题目典型特征核心思路与工具模数分解模数n较小如1024位或p、q有缺陷如相近、光滑数。使用factordb、yafu分解。共模攻击给出两个或多个公钥(n, e1),(n, e2)加密了同一明文m。利用扩展欧几里得算法找到re1 se2 1计算c1^r * c2^s mod n m。低加密指数攻击公钥指数e很小如3并且明文m满足m^e n。直接对密文c开e次方根。低加密指数广播攻击相同的明文m用相同的e但不同的n加密得到多个密文c_i。利用中国剩余定理(CRT)求解满足所有同余式的m^e再开方。维纳攻击私钥d较小满足d (1/3) * n^(1/4)。利用连分数展开逼近e/n来快速计算出d。p-1光滑或p1光滑素数p满足p-1或p1的因子都是小质数光滑数。使用Pollard‘s p-1 或 Williams‘s p1 算法分解n。泄露部分私钥题目给出了私钥d的一部分位或者p、q的高位/低位。使用Coppersmith定理进行格基规约攻击恢复完整的密钥。6.2 实战思维养成面对一道新的RSA题我通常会遵循以下排查流程信息收集用openssl、binwalk、strings等工具仔细查看所有给定文件不放过任何注释、额外数字或文本。参数提取准确提取所有n,e,c密文以及任何可能的p,q,d的片段。初步尝试尝试分解nfactordb。检查e是否很小如3。检查是否有多个n或e。工具辅助将参数喂给RsaCtfTool让它自动尝试所有已知攻击。数学分析如果工具无效回到数学本身。分析n的位数e和c的大小关系思考可能存在的数学关系如d小p和q有特殊关系。搜索与学习将题目中的关键特征如n的特殊值、e的特定值或错误信息进行搜索很可能在CTF Writeup解题报告中找到类似思路。6.3 资源推荐与持续学习练习平台BUUCTF、CTFHub、攻防世界ADWorld都提供了丰富的密码学题目按难度分类非常适合循序渐进。学习资料除了经典的《应用密码学》外我强烈推荐阅读CTF选手写的Writeup。GitHub上有很多集合搜索“CTF RSA Writeup”能找到大量实战案例。社区交流遇到难题时在相关的CTF社区或论坛如看雪论坛、先知社区提问往往能获得高手的关键指点。回过头看这道“每日打卡”题它就像RSA世界的“Hello World”。通过它我们跑通了一个完整的“识别-分析-攻击-解密”流程掌握了最基本的工具链。更重要的是我们理解了RSA安全性的核心假设及其脆弱条件。在后续挑战更复杂的题目时你会不断重温并深化这些基础概念。密码学学习没有捷径就是一道题一道题地啃一个概念一个概念地磨。每解一道题你对那些看似抽象的数学原理的理解就会更具体一分。