1. 项目概述一次经典的RSA密码学实战复盘最近在整理过去的CTFCapture The Flag比赛题目时我又翻出了这道来自QCTF2018的“Xman-RSA”。这道题在当年算是一个中等偏上的密码学挑战它没有用那些特别刁钻的数学难题来为难选手而是非常扎实地考察了对RSA算法核心原理的理解以及面对不完整或异常密钥信息时的分析能力。对于想深入理解RSA或者准备入门CTF密码学方向的朋友来说这道题是一个绝佳的练手材料。它就像一份精心设计的“病例”让你亲手诊断一个RSA密钥到底“病”在哪里并最终恢复出明文。今天我就带大家完整地复盘一遍解题思路和实操过程不仅告诉你“怎么做”更会深入剖析“为什么这么做”。简单来说题目通常会给你一个加密脚本、一个公钥文件可能包含模数n和公钥指数e以及一个密文文件。你的任务就是破解这个RSA加密拿到里面的flag。这道题的特殊之处在于它往往不会直接给你一个可以轻易分解的n或者一个非常规的e导致直接攻击失效而是需要你综合利用多种RSA的已知攻击手段和对pem格式密钥的解析能力。下面我们就从最基础的准备开始一步步拆解。2. 环境准备与题目文件初探2.1 必要的工具与库工欲善其事必先利其器。处理这类RSA题目你不需要一个多么庞大的渗透测试套件但几个核心的Python库和工具是必不可少的。我的工作环境通常是Linux如Kali或Ubuntu但macOS和Windows配合WSL也完全没问题。首先确保你的Python环境建议Python 3.6以上安装了以下库pycryptodome/Crypto 这是处理RSA加密解密、密钥解析的主力库。通常使用pip install pycryptodome来安装。注意安装后导入模块时使用from Crypto.PublicKey import RSA。gmpy2 一个高性能的多精度算术库对于处理RSA涉及的大整数运算如模逆、大数分解尝试至关重要。安装它可能需要一些系统依赖在Ubuntu上可以尝试sudo apt install libmpc-dev后再pip install gmpy2。sympy 一个符号数学库它的factorint函数对于尝试分解较小的n或有特殊性质的n很有帮助。rsatool和RsaCtfTool 这两个是CTF中专门用于攻击RSA的瑞士军刀。前者可以用于生成和操纵RSA密钥后者集成了数十种针对RSA的攻击方式。我通常会把RsaCtfTool克隆到本地备用。你可以通过git clone https://github.com/Ganapati/RsaCtfTool.git获取它。除了Python库一个好用的命令行计算器也很有帮助比如bc或者python交互式环境本身。另外熟悉openssl命令对于解析和检查PEM格式的密钥文件非常有帮助。2.2 题目文件解析通常你会拿到类似以下结构的文件包pubkey.pem: 一个PEM格式的公钥文件。flag.enc: 一个二进制文件里面存储着用上述公钥加密后的密文。有时还会有encryption.py: 用于生成上述文件的加密脚本。我们的第一步永远是仔细阅读所有文件。用文本编辑器打开pubkey.pem它看起来是这样的-----BEGIN PUBLIC KEY----- MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAz6e4C6Aem8FwC9bJ6R3 ... -----END PUBLIC KEY-----这就是标准的RSA公钥格式。我们需要从中提取出模数n和公钥指数e。用Python提取是最直接的方式from Crypto.PublicKey import RSA with open(pubkey.pem, r) as f: key RSA.import_key(f.read()) n key.n e key.e print(fn {n}) print(fe {e}) print(fn的比特长度: {n.bit_length()})运行后你会得到n和e的具体数值。这是整个解题过程的起点所有后续分析都基于这两个数。同时检查一下flag.enc文件的大小。因为RSA加密是对明文进行分组加密如果明文也就是flag很短密文文件通常也很小。用ls -l flag.enc或wc -c flag.enc查看其字节数。这个信息有时能提示你明文的长度。注意有些题目可能会提供畸形的pubkey.pem比如e值异常大甚至等于n或者n本身不是一个有效的RSA模数例如它可能是一个素数而非两个大素数的乘积。第一步的解析就能帮你快速识别这类异常。3. 核心思路拆解RSA的常见脆弱点拿到n和e之后我们就像侦探拿到了关键证据。RSA的安全性建立在“大数分解难题”上即给定n难以在有效时间内分解出它的两个质因子p和q。因此CTF中RSA题目的攻击路径几乎都是围绕如何绕过这个难题或者利用密钥生成、使用过程中的不当之处展开的。对于这道“Xman-RSA”我们需要系统性地排查以下几种常见情况3.1 模数n过小或存在已知漏洞如果n的比特长度很短比如小于512位那么在现代计算机上利用sympy或在线分解网站如 factordb.com有可能在短时间内直接分解。这是最理想的情况。即使n较大如1024位也需检查它是否是某些已知的脆弱素数生成的或者是否有公开的分解记录。3.2 公钥指数e过大或过小e过小如e3 如果明文m很小使得m^e n那么加密过程c m^e mod n实际上就等于m^e因为没有取模运算。此时直接对密文c开e次方根即可得到明文。即使m^e略大于n也可能通过低加密指数攻击如Coppersmith攻击恢复。e过大接近n 这可能暗示私钥指数d很小从而存在低解密指数攻击Wiener攻击或Boneh-Durfee攻击。这类攻击通过e和n来逼近d。3.3 共模攻击如果题目给出了多组(n, e)和对应的密文但它们的n相同而e不同且互质那么就可能存在共模攻击。利用扩展欧几里得算法可以从两个不同的加密结果中恢复出明文。这道题通常只给一组所以这个可能性较低但思路要具备。3.4 因数碰撞在CTF中出题人有时会使用一个固定的素数p来生成多个不同的n。如果你有多个n计算它们的最大公约数GCD很可能就能直接找到这个公共的质因子p。即使只有当前一个n如果这个n曾经在其他题目或公开数据中出现过也可能通过GCD与已知数据库碰撞出因子。3.5 密钥文件格式本身蕴含信息这是本题的一个潜在考点。PEM格式的pubkey.pem是ASN.1编码的。有时出题人可能会在生成密钥时将额外的信息比如提示、甚至p和q的一部分通过某种方式编码进去或者故意损坏文件结构需要你去修复和解析。用openssl asn1parse -in pubkey.pem命令可以深入查看其ASN.1结构有时会有意外发现。解题的通用流程是先尝试最简单直接的攻击如小n分解不行再尝试数学攻击如Wiener攻击同时结合对密钥文件的深度解析。下面我们就进入实操环节。4. 实操过程从分析到解密假设我们通过第一步提取到了如下信息此为示例实际数值会不同n 123456789...(一个1024位的整数)e 65537(这是最常见的公钥指数)4.1 第一步尝试直接分解n首先评估n的位数。如果是768位以下可以尝试用sympy.factorint(n)进行分解。如果sympy卡住可以尝试使用yafu这个专门的大数分解工具或者提交到 factordb.com 查询。如果n是1024位或更大直接分解在比赛时间内通常不可行除非题目故意用了弱质数。这时我们需要记录下n和e进入下一步分析。4.2 第二步检查e的取值如果e 3或e 5等很小的数立即尝试低加密指数攻击。用gmpy2的iroot函数对密文整数c开e次方。import gmpy2 with open(flag.enc, rb) as f: c int.from_bytes(f.read(), big) # 将密文文件读成整数 for k in range(1000): # 尝试可能的 k*n 偏移 m, is_exact gmpy2.iroot(c k*n, e) if is_exact: print(fFound m with k{k}: {m}) # 将m转换为字节串 flag int(m).to_bytes((m.bit_length() 7) // 8, big) print(flag) break如果e非常大比如和n位数相同那么就要怀疑是否是低解密指数d攻击。可以使用RsaCtfTool来尝试 Wiener 攻击python RsaCtfTool/RsaCtfTool.py -n 你的n -e 你的e --uncipherfile flag.enc --attack wiener4.3 第三步深度解析公钥文件如果前两步都无效那么焦点就要回到pubkey.pem文件本身。使用openssl进行深度解析openssl rsa -pubin -in pubkey.pem -text -noout这个命令会以文本形式输出公钥的各个组件包括模数n和指数e有时还能看到密钥的ASN.1结构标识。对比之前Python解析出的n和e看是否一致。更深入一步使用 ASN.1 解析openssl asn1parse -in pubkey.pem你会看到一串序列号SEQUENCE和整数INTEGER的嵌套结构。标准的RSA公钥ASN.1结构是SEQUENCE { SEQUENCE { OBJECT IDENTIFIER rsaEncryption (1 2 840 113549 1 1 1) NULL } BIT STRING (封装了另一个SEQUENCE) SEQUENCE { INTEGER (模数 n) INTEGER (公钥指数 e) } }你需要仔细观察每个INTEGER字段的值。有时出题人会在这里“藏”东西。比如额外的整数 在n和e之后可能还有第三个、第四个整数。这不符合标准但可能包含了p、q、d或其他提示信息。被修改的编码 BIT STRING 的长度或内容可能被篡改导致常规解析失败需要手动修正。“伪装”的n和e 解析出来的第一个INTEGER可能不是真正的n或者e被放在了奇怪的位置。实操心得 我遇到过一道题openssl rsa -text命令报错“无法读取公钥”但asn1parse却能正常输出结构。结果发现公钥的BIT STRING里包含了三个INTEGER第三个整数就是p和q的其中一个所以当常规方法走不通时一定要用asn1parse这把“手术刀”把文件解剖开来看。4.4 第四步利用已知信息攻击如果通过ASN.1解析我们得到了额外的整数x那么它可能是什么如果x比较小且n % x 0那么x就是n的一个因子。如果x很大可能是d、dpd mod p-1、dqd mod q-1或qinvq关于p的模逆元之一。这些信息如果泄露同样可以导致RSA被完全破解。例如如果得到了dp d mod (p-1)并且e不大我们可以通过枚举k并计算gcd(pow(g, e*dp, n) - g, n)来尝试分解n其中g是一个随机整数通常取2。4.5 第五步解密与Flag获取一旦我们成功分解n得到p和q或者通过其他方式计算出了私钥参数d解密就水到渠成了。计算私钥参数from Crypto.Util.number import inverse p ... # 分解得到的p q ... # 分解得到的q n p * q e 65537 phi (p-1)*(q-1) d inverse(e, phi) # 计算私钥指数d然后使用私钥解密from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP # 或 PKCS1_v1_5 # 方法1使用PKCS1_OAEP填充解密现代常用 key RSA.construct((n, e, d, p, q)) cipher PKCS1_OAEP.new(key) with open(flag.enc, rb) as f: ciphertext f.read() plaintext cipher.decrypt(ciphertext) print(plaintext) # 方法2如果加密时使用了无填充或自定义填充可能需要手动计算 # c int.from_bytes(ciphertext, big) # m pow(c, d, n) # plaintext int(m).to_bytes((m.bit_length() 7) // 8, big) # 注意直接计算需要处理可能的填充字节PKCS1_v1_5等填充模式会有固定的开头字节。重要提示 CTF中RSA加密flag时经常使用无填充pow(m, e, n)或者简单的字节转换。如果使用PKCS1_OAEP解密失败报错“解密错误”很可能是加密时没有使用标准填充。此时应该尝试手动计算m pow(c, d, n)然后将整数m转换为字节。转换后的字节串开头可能是b\x00\x02...PKCS1 v1.5填充或者是直接的flag明文如bflag{...。5. 常见问题与排查技巧实录在实际操作中你肯定会遇到各种报错和意外情况。下面我整理了几个最常见的“坑”及其解决方法。5.1 问题Crypto模块导入失败表现ModuleNotFoundError: No module named Crypto或ModuleNotFoundError: No module named Crypto.PublicKey原因 通常是因为安装了pycrypto已废弃而非pycryptodome。解决pip uninstall pycrypto pip uninstall crypto # 全部卸载干净 pip install pycryptodome在代码中导入语句保持不变from Crypto.PublicKey import RSA。如果还不行可以尝试在Python交互环境中检查Crypto.__file__的路径确认安装正确。5.2 问题gmpy2安装失败表现 在pip install gmpy2时编译错误提示缺少mpir.h等头文件。原因 缺少底层的C数学库依赖。解决以Ubuntu/Debian为例sudo apt update sudo apt install libgmp-dev libmpc-dev libmpfr-dev pip install gmpy2对于macOS可以使用brew install gmp mpfr libmpc后再安装。5.3 问题分解出的p和q验证失败表现 你得到了p和q但计算p * q不等于题目给的n或者计算d时报错“没有模逆元”。原因分解错误得到的p和q不是真正的因子。从ASN.1中提取的整数顺序理解有误可能把n和e搞混了或者提取了错误的字段。题目给的n本身可能就不是标准的RSA模数比如是三个素数的乘积即多素数RSA。解决重新检查分解过程。对于大数使用yafu或factordb的结果更可靠。仔细核对ASN.1解析结果。标准顺序是第一个INTEGER是n第二个是e。用openssl asn1parse -i -in pubkey.pem-i参数使输出缩进可以更清晰地看到层级。计算gcd(p, n)和gcd(q, n)看是否都能整除n。如果p和q是因子那么p*q必须严格等于n。如果n是多个素数的乘积你需要找到所有的素因子。私钥计算方式也会不同使用phi (p1-1)*(p2-1)*...。5.4 问题解密后得到乱码表现 成功计算出m pow(c, d, n)但转换成字节后是乱码开头不是预期的flag{。原因填充问题 最常见的坑。加密时可能使用了PKCS1 v1.5或OAEP填充解密后的明文前面有填充字节。你需要去掉这些填充。对于PKCS1 v1.5明文通常从第一个\x00字节之后开始。字节序问题int.to_bytes()和int.from_bytes()默认使用大端序big。但有些加密实现可能使用小端序little。如果解密结果看起来是倒序的flag可以尝试换一下。密文读取错误flag.enc文件可能包含非密文内容比如一行十六进制字符串或Base64编码。你需要先将其解码为原始字节。解决# 假设 m 是解密得到的整数 bytes_m m.to_bytes((m.bit_length() 7) // 8, big) # 尝试处理PKCS1 v1.5填充寻找第二个\x00第一个是版本号00第二个是分隔符 if b\x00 in bytes_m: # 找到第一个非零的\x00之后的部分 # PKCS1 v1.5 格式: 00 02 [随机非零填充] 00 [明文] try: # 跳过前两个字节00 02然后找到下一个00 index bytes_m.index(b\x00, 2) plaintext bytes_m[index1:] print(fAfter PKCS1 v1.5 unpadding: {plaintext}) except ValueError: plaintext bytes_m else: plaintext bytes_m # 如果还不像flag尝试小端序 if not plaintext.startswith(bflag{): bytes_m_le m.to_bytes((m.bit_length() 7) // 8, little) print(fLittle-endian try: {bytes_m_le}) # 检查文件原始内容 with open(flag.enc, rb) as f: raw f.read() print(fRaw ciphertext (hex): {raw.hex()}) # 如果看起来像hex字符串如4d5a...则解码 try: if all(c in b0123456789abcdefABCDEF for c in raw.strip()): ciphertext bytes.fromhex(raw.decode()) print(fDecoded from hex: {ciphertext.hex()}) except: pass5.5 问题RsaCtfTool攻击失败表现 使用RsaCtfTool运行各种攻击如wiener, hastad, boneh_durfee都返回失败。原因题目不属于这些典型攻击的范畴。工具的参数使用不当或者需要更长的超时时间。题目需要组合多种技巧单纯依赖自动化工具不行。解决仔细阅读RsaCtfTool的输出看它尝试了哪些攻击失败原因是什么。手动实现或寻找其他脚本尝试更多攻击如Pollards p-1 算法或Williams p1 算法特别是当n的因子p或q满足p-1或p1是光滑数时。回归基础重新审视n和e以及公钥文件。99%的CTF-RSA题目其突破口都藏在n、e或密钥文件本身的信息里或者是这些信息的简单组合。6. 总结与高阶技巧延伸复盘完“Xman-RSA”这道题我们可以清晰地看到一条CTF-RSA题目的通用分析路径解析密钥 - 检查参数 - 尝试分解 - 深度分析文件结构 - 应用特定攻击模型 - 处理解密填充。这道题的价值在于它很可能将突破口设置在“深度分析文件结构”这一步考察选手对RSA密钥编码格式的熟悉程度。对于想进一步提升的朋友我分享几个高阶技巧和练习方向学习ASN.1与DER编码 RSA密钥的PEM格式是Base64编码的DERDistinguished Encoding Rules数据。花点时间了解ASN.1的基本类型SEQUENCE, INTEGER, BIT STRING等和DER编码规则你就能手动解析和构造任何密钥文件这对于处理畸形密钥题目至关重要。掌握Coppersmith相关攻击 这是现代CTF密码学中对付RSA的利器。当你知道明文的一部分比如flag格式是flag{开头或者知道p或q的一部分高位或低位字节时Coppersmith方法可以在多项式时间内恢复出完整的未知部分。SageMath是实现这些攻击的绝佳环境。关注非整数RSA变种 有些题目会使用e和d不是整数的RSA比如基于四元数或者模数n是多项式环上的元素。这需要更抽象的代数知识但一旦掌握解题能力会提升一个档次。最后也是最重要的心得保持耐心和细致。密码学题目尤其是RSA往往就像解谜。每一个数字、每一处编码都可能是线索。当你卡住时不妨把已知的所有信息n, e, 密文c文件hexdump都写在纸上或者用注释写在代码里反复观察它们之间的关系。很多时候突破口就藏在那些你一开始认为“理所当然”或“无关紧要”的细节里。