CTF密码学实战：Python脚本解密RSA与AES的完整指南

1. 项目概述从CTF实战到Python脚本的密码学解密之旅如果你玩过CTFCapture The Flag网络安全竞赛或者对数据安全感兴趣那你一定绕不开RSA和AES这两个名字。它们就像是密码学世界的“倚天剑”和“屠龙刀”一个负责非对称加密在密钥交换和数字签名领域称王另一个则统治着对称加密是数据机密性的基石。在CTF的Crypto密码学赛题中RSA和AES更是常客从简单的模数分解到复杂的侧信道攻击花样百出。但很多新手朋友一看到加密算法、数学公式和Python代码就头大感觉无从下手。这篇内容就是为你准备的。我们不谈高深的理论推导直接从CTF实战中最常见的场景出发手把手教你如何用Python的Crypto库更准确地说是pycryptodome来搞定RSA和AES的解密。我会把我在实际解题和项目开发中踩过的坑、总结的技巧毫无保留地分享出来。无论你是想入门CTF密码学还是需要在工作中快速实现一个加解密工具这篇文章都能给你提供一套清晰、可复现的“操作手册”。我们的目标很明确让你看完就能写脚本写了就能跑通跑通就能解出题或者完成任务。2. 环境准备与核心库选型解析工欲善其事必先利其器。在开始写解密脚本之前一个稳定、功能齐全的Python密码学环境是第一步。这里面的门道可能比你想象的多一点。2.1 为什么是pycryptodome而不是pycrypto很多老教程会推荐安装pycrypto但我要告诉你千万别再装这个了。pycrypto项目早在2014年就停止了维护存在已知的安全漏洞并且对新版Python的支持也很差。它的继任者就是pycryptodome这是一个几乎完全兼容pycryptoAPI 的替代品但功能更强大、维护更积极、安全性更高。在CTF和实际开发中pycryptodome是事实上的标准。安装命令很简单pip install pycryptodome如果你遇到网络问题可以使用国内的镜像源加速例如pip install pycryptodome -i https://pypi.tuna.tsinghua.edu.cn/simple安装成功后在Python中通常这样导入from Crypto.Cipher import AES和from Crypto.PublicKey import RSA。注意模块名是Crypto这保持了与旧pycrypto的兼容性让你迁移代码几乎无痛。2.2 辅助工具库让你的脚本更强大除了核心的加密库以下几个工具库能极大提升你脚本的效率和解决问题的能力gmpy2/sympy这是RSA解题的“核武器”。当RSA的模数N不大时你可以用sympy的factorint函数尝试分解。但当N很大题目却给出了某些特殊条件比如p和q很接近或者p/q的某些位泄露时gmpy2这个高性能多精度算术库就是必备的。它提供了接近C语言速度的大整数运算能力用于实现Coppersmith攻击等高级手段。安装pip install gmpy2。如果安装困难sympy的数学计算功能也能解决大部分中等难度的问题。requests/pwntools用于与远程服务器交互。很多CTF题目是给你一个网络服务的地址和端口你需要写脚本自动连接、接收数据、计算后再发送回去。requests适合HTTP/HTTPS协议而pwntools是CTF专属神器能处理TCP/UDP等原始套接字通信内置了很多方便的函数。安装pip install requests pwntools。base64/binasciiPython标准库自带的编码解码模块。题目给的密钥、密文、向量经常是Base64或十六进制hex格式的你需要熟练使用base64.b64decode()、binascii.unhexlify()来转换以及对应的编码函数将处理后的结果发送回去。注意在导入时确保你导入的是正确的模块。曾经有朋友误装了crypto首字母小写这个无关的包导致代码报错找不到模块。认准Crypto首字母大写。3. RSA解密实战从基础到进阶攻击RSA的安全性基于大整数分解的困难性。但在CTF中出题人总会“不小心”设置一些弱点让我们利用。下面我们从最基础的场景开始逐步深入。3.1 场景一已知私钥或分解最基础这是最简单的场景。题目可能直接给你私钥文件private.pem或者给出了素数p和q。操作步骤读取密钥或参数。如果给的是PEM格式的私钥from Crypto.PublicKey import RSA with open(private.pem, r) as f: private_key RSA.import_key(f.read())如果给的是p,q,e,c密文import math p 101 q 113 e 65537 c 123456 # 示例密文 n p * q phi (p-1)*(q-1) # 计算私钥指数d即e关于phi的模逆元 d pow(e, -1, phi) # Python 3.8 可以直接用内置函数 # 对于更早的Python版本可以使用扩展欧几里得算法 # from Crypto.Util.number import inverse # d inverse(e, phi)执行解密。使用私钥或计算出的参数进行解密。# 方法1使用构建的私钥对象如果已导入 # plaintext private_key.decrypt(c) # 方法2使用计算出的d直接进行模幂运算 m pow(c, d, n) # m就是解密后的整数明文转换明文。解密得到的m通常是一个大整数需要转换成可读的字符串。from Crypto.Util.number import long_to_bytes flag long_to_bytes(m).decode(utf-8, errorsignore) # 尝试UTF-8解码 print(flag)实操心得long_to_bytes和bytes_to_long加密时用是Crypto.Util.number模块里的两个宝贝函数负责在Python大整数和字节串之间无缝转换务必熟练掌握。3.2 场景二模数N分解factordb与yafu当题目只给了n,e,c时核心就是分解n得到p和q。在线数据库查询首先访问 factordb.com 输入模数n。这个网站收录了大量已知分解的整数如果是CTF出题人从数据库里选的数很可能直接就能查到分解结果。这是你的第一反应。本地工具分解如果factordb查不到就需要尝试本地分解。对于小于256位的n约77个十进制数字可以尝试用sympy。import sympy n 1234567890123456789012345678901234567890 factors sympy.factorint(n) print(factors) # 输出如 {p1: exp1, p2: exp2...}对于更大的n比如512位sympy可能会非常慢甚至卡死。这时就需要更专业的工具比如yafuYet Another Factorization Utility。它是一个命令行工具自动化集成了多种高效的分解算法如Pollard-rho, ECM, SIQS等。使用方法通常是将n保存到一个文件如num.txt内容就是factor(你的n)然后在命令行运行yafu-x64.exe factor() -batchfile num.txt。yafu对于CTF中常见的512位、768位RSA分解效率很高。获取分解结果并解密从yafu或sympy的输出中得到p和q后回到场景一的步骤计算d并解密。踩坑记录有时yafu分解出的因子可能不止两个如果n是多个素数的乘积即Multi-prime RSA你需要将所有素数因子乘起来验证是否等于n。私钥指数d的计算公式变为phi (p1-1)*(p2-1)*...*(pk-1)d inverse(e, phi)。解密公式m pow(c, d, n)依然不变。3.3 场景三利用特殊漏洞共模、低指数、广播攻击等当常规分解走不通时就要考虑RSA本身的应用或参数设置是否存在漏洞。3.3.1 共模攻击条件相同的明文m用相同的模数n但不同的公钥指数e1和e2加密得到密文c1和c2。原理如果e1和e2互素通常都是根据扩展欧几里得算法存在整数s1和s2使得e1*s1 e2*s2 1。那么m (c1^s1 * c2^s2) mod n。Python实现from Crypto.Util.number import inverse, long_to_bytes import math n ... # 公共模数 e1, c1 ... e2, c2 ... # 扩展欧几里得算法求系数 gcd, s1, s2 extended_gcd(e1, e2) # 需要自己实现或使用gmpy2.gcdext # 确保s1或s2为负数时计算对应的密文的模逆元 if s1 0: c1 inverse(c1, n) s1 -s1 if s2 0: c2 inverse(c2, n) s2 -s2 m (pow(c1, s1, n) * pow(c2, s2, n)) % n flag long_to_bytes(m)3.3.2 低加密指数攻击比如e3条件公钥指数e很小如3明文m满足m^e n。原理此时加密过程c m^e没有经过模n的截断所以直接对密文c开e次方根即可得到m。Python实现import gmpy2 from Crypto.Util.number import long_to_bytes c ... # 密文 e 3 # 使用gmpy2的iroot进行整数开方 m, is_exact gmpy2.iroot(c, e) if is_exact: flag long_to_bytes(int(m))注意事项如果m^e只是略大于n可能可以通过枚举小范围的k尝试对c k*n开方即m iroot(c k*n, e)。3.3.3 广播攻击条件相同的明文m用相同的公钥指数e通常较小如3但不同的模数n1, n2, ..., nk加密得到密文c1, c2, ..., ck。原理根据中国剩余定理CRT可以构造一个方程m^e ≡ C (mod N)其中N n1*n2*...*nk。当m^e N时就可以像低加密指数攻击一样直接开方。Python实现通常使用sympy.ntheory.modular.crt函数来求解中国剩余定理得到C然后再对C开e次方根。3.4 场景四Coppersmith攻击与高位泄露这是CTF中较难但非常经典的题型。题目可能只泄露了素数p的高位或低位或者泄露了私钥d的一部分。核心思想是利用已知的部分信息构造一个关于未知部分的整数方程然后利用Coppersmith方法在模数n下求解小根。典型描述“在RSA加密中把素数 p 的高位给泄漏了。”攻击方案思路 假设n p * q我们知道p的高位是pH即p pH x其中x是未知的低位部分且相对较小。 那么我们可以构造多项式f(x) pH x在模p下的根x0满足f(x0) ≡ 0 (mod p)。由于p是n的一个因子所以这个等式在模n下也成立但不一定为0。Coppersmith定理告诉我们如果这个根x足够小小于n的 β次方通常 β0.5我们就可以在多项式时间内找到它。实操工具我们通常不手写Coppersmith算法而是使用现成的库。sage数学软件是首选其内置的small_roots()函数非常强大。在Python环境中我们可以用python-sage库如果环境允许或者使用RSAwienerHacker、owiener等专门针对RSA攻击的Python脚本中的相关实现。更常见的是在CTF比赛中直接编写Sage脚本。一个简化的Sage脚本示例# 假设在SageMath环境中运行 n ... # 模数 pH ... # p的高位例如已知前200位 # 假设p是512位已知高位200位那么未知低位x的位数约为312位 # 我们需要构造多项式 f(x) pH x # p的高位需要左移到正确的位置。假设pH是已知的高位数值。 # 更常见的写法是p_known pH unknown_bits kbits 312 # 未知的低位位数 p_known pH # 这里pH应该是已经左移了未知位数后的值或者直接是高位数值 PR.x PolynomialRing(Zmod(n)) f x p_known roots f.small_roots(X2^kbits, beta0.4) # X是根的上界beta通常取0.4~0.5 if roots: x0 roots[0] p p_known x0 if n % p 0: print(Found p:, p) q n // p # 后续计算phi, d, 解密...关键点p_known的构造需要小心。如果题目说“泄露了p的高位”通常意味着给出了p的十进制或十六进制表示的前面一部分。你需要将其转换为整数然后左移足够的位数未知低位所占的比特数使其对齐到p的完整比特长度。4. AES解密实战模式、填充与密钥处理AES是一种对称加密算法密钥长度可以是128、192或256位。在CTF中AES的挑战往往不在于破解算法本身目前是安全的而在于错误的使用方式比如模式选择不当、初始向量IV管理不善、填充规则被绕过等。4.1 核心概念澄清模式与填充在调用Crypto.Cipher.AES.new()时你必须指定两样东西模式和初始化向量如果需要。模式决定了AES如何对多块数据进行加密。ECB最简单的模式每块独立加密。绝对不要用于需要保密性的场景因为它会导致相同的明文块产生相同的密文块图案会泄露。CTF中如果看到AES-ECB往往提示你可以利用这个特性。CBC最常用的模式之一。每个明文块在加密前会与前一个密文块进行异或操作。需要一个随机的、不可预测的IV。IV不需要保密但必须随机且唯一。CTR将块密码变为流密码。需要一个Nonce类似IV和计数器。它可以并行加密且不需要填充。GCM、CCM认证加密模式同时提供机密性和完整性。在热词中看到的“aes ccm”就属于此类。填充AES块大小是16字节。如果明文不是16的整数倍就需要填充。pycryptodome默认使用PKCS#7填充。例如一个15字节的数据会填充1个值为\x01的字节一个16字节的数据会额外填充一个完整的16字节块每个字节值为\x10。解密后库会自动去除填充。4.2 场景一已知密钥和IV的CBC解密这是最直接的场景。题目给你密钥key、初始向量IV和密文ciphertext。操作步骤from Crypto.Cipher import AES from Crypto.Util.Padding import unpad # 用于去除填充 import base64 # 假设给定的数据是Base64编码的 key_b64 AAAAAAAAAAAAAAAAAAAAAA # 示例16字节的base64 iv_b64 BBBBBBBBBBBBBBBBBBBBBB ciphertext_b64 ... # 解码 key base64.b64decode(key_b64) iv base64.b64decode(iv_b64) ciphertext base64.b64decode(ciphertext_b64) # 创建AES解密器模式为CBC cipher AES.new(key, AES.MODE_CBC, iv) # 解密并去除填充 try: decrypted_padded cipher.decrypt(ciphertext) plaintext unpad(decrypted_padded, AES.block_size) # AES.block_size 16 print(plaintext.decode(utf-8)) except ValueError as e: print(f解密或解填充失败: {e}) # 可能是密钥/IV错误或者填充不正确注意事项AES.new()的参数顺序是(key, mode, iv)。对于不需要IV的模式如ECB则省略iv参数。decrypt()方法返回的是解密后的数据但可能还带着PKCS#7填充字节。必须使用unpad()来移除它们。如果unpad()抛出ValueError说明填充格式不对很可能密钥或IV是错误的。4.3 场景二无IV或IV可推导ECB、CTR等ECB模式直接省略IV参数。cipher AES.new(key, AES.MODE_ECB) decrypted_padded cipher.decrypt(ciphertext) plaintext unpad(decrypted_padded, AES.block_size)CTF技巧ECB模式会暴露数据模式。如果题目是加密了一张图片你可以通过观察密文的重复块来推断明文图片的结构甚至替换块来篡改图片内容。CTR模式CTR模式需要一个nonce随机数和一个计数器。pycryptodome中你可以直接传入一个完整的initial_value或者分别指定nonce和initial_value此时initial_value是计数器起始值。更常见的用法是题目会给你一个相当于IV的东西你可以将其作为nonce并假设计数器从0开始。# 假设 given_iv 作为 nonce cipher AES.new(key, AES.MODE_CTR, noncegiven_iv, initial_value0) # CTR模式是流加密不需要填充 plaintext cipher.decrypt(ciphertext)重要CTR模式下绝对不要重复使用相同的nonce, key对来加密不同的消息否则会导致流密钥重用安全性完全丧失。CTF中有时会利用这一点。4.4 场景三Padding Oracle攻击CBC模式这是CBC模式一个非常经典的攻击。条件攻击者能够向一个服务提交密文并能够得知解密后填充是否有效例如服务返回“解密错误”或“填充错误”。原理简述攻击者可以篡改密文块的字节利用服务返回的填充有效/无效信息逐个字节地推导出中间状态值从而计算出明文。这个攻击完全不需要知道密钥Python脚本框架 你需要实现一个函数能够与目标服务器交互提交密文并判断返回是否表示“填充错误”。import requests def is_padding_ok(ciphertext_hex): 向目标服务器发送密文返回True表示填充正确False表示填充错误 url http://target.com/decrypt data {ciphertext: ciphertext_hex} resp requests.post(url, datadata) # 根据服务器返回信息判断可能是状态码不同也可能是返回内容包含特定字符串 return padding error not in resp.text # 然后使用Padding Oracle攻击算法如PoC||GTFO中的经典算法来逐字节解密。 # 这里不展开完整算法代码但思路是从最后一个块开始篡改前一个密文块或IV # 爆破最后一个填充字节的值利用服务器的反馈进行判断。实操心得实现Padding Oracle攻击脚本是对你编程能力和对CBC模式理解的一次很好考验。网上有很多现成的攻击脚本如padbuster的Python版但理解原理后自己写一遍收获更大。关键点在于控制好字节异或的操作和服务器反馈的判断逻辑。5. 脚本编写实战与调试技巧把各个模块组合成一个能稳定运行的脚本并处理好各种边界情况才是真正的实战能力。5.1 一个完整的CTF RSA解题脚本示例假设题目通过网络连接给出n,e,c我们需要分解n假设不大解密后把明文发回去。#!/usr/bin/env python3 from pwn import * # 使用pwntools进行网络交互 from Crypto.Util.number import long_to_bytes, bytes_to_long import sympy # 1. 连接题目服务器 r remote(ctf.example.com, 12345) # 2. 接收数据。格式需要根据题目调整这里假设服务器一行行发送 n, e, c n_line r.recvline().decode().strip() e_line r.recvline().decode().strip() c_line r.recvline().decode().strip() # 提取数字可能包含前缀如n n int(n_line.split()[1].strip()) e int(e_line.split()[1].strip()) c int(c_line.split()[1].strip()) print(f[*] Got n: {n}) print(f[*] Got e: {e}) print(f[*] Got c: {c}) # 3. 尝试分解n print([*] Trying to factor n...) factors sympy.factorint(n) if len(factors) 2 and all(exp 1 for exp in factors.values()): p, q list(factors.keys()) print(f[] Factorization success! p{p}, q{q}) else: print([-] Factorization failed or n has more than 2 prime factors.) exit(1) # 4. 计算私钥d并解密 phi (p-1)*(q-1) d pow(e, -1, phi) # Python 3.8 m pow(c, d, n) flag long_to_bytes(m).decode(utf-8, errorsignore) print(f[] Decrypted message: {flag}) # 5. 发送flag回服务器如果需要 r.sendlineafter(bGive me the flag:, flag.encode()) print(r.recvall().decode())5.2 调试与错误排查清单写脚本不可能一次成功以下是常见的错误和排查思路错误现象可能原因排查方法ModuleNotFoundError: No module named Cryptopycryptodome未安装或安装不正确pip list检查是否安装。确认导入时是Crypto不是crypto。ValueError: Data must be padded to 16 byte boundary in CBC mode密文长度不是16的倍数检查密文解码是否正确。可能是Base64或Hex解码出错或者传输中丢失了字符。ValueError: Padding is incorrect.密钥、IV错误或密文被篡改确认密钥和IV的编码、长度AES-128是16字节。尝试用题目给的示例验证加解密流程。RSA解密得到乱码解密出的整数m转换字节时不对1. 尝试long_to_bytes(m).hex()看是否是flag的hex格式。2. 尝试long_to_bytes(m)[::-1]可能字节序反了。3. 检查解密过程是否正确特别是phi的计算和模逆运算。分解n时间过长或内存溢出n太大如1024位以上或工具算法不适用1. 先上 factordb 查询。2. 检查题目是否有其他提示如p、q接近p-1光滑等换用特定算法yafu的-one或-factor选项。3. 考虑是否不是分解思路而是其他攻击共模、低指数等。网络脚本收不到数据或卡住题目交互协议理解错误1. 用nc命令手动连接服务器摸清交互流程。2. 在脚本中多加入print或r.interactive()进行调试。3. 注意recvuntil()和recvline()的使用可能有多余的空行或提示符。5.3 性能优化小贴士大数运算用gmpy2涉及大量模幂运算如pow(c, d, n)时gmpy2比Python原生整数运算快几个数量级。避免重复计算在循环中需要重复使用的值如phi,d先计算好。使用bytes而非str加解密接口处理的是字节串。在内部逻辑中尽量使用bytes类型减少编解码次数。合理处理异常使用try...except包裹可能出错的部分如网络超时、解码错误让脚本更健壮并给出有用的错误信息。6. 从解题到理解密码学的安全本质通过以上实战我们不仅学会了写脚本更应该理解这些攻击为何能成功从而在以后自己设计系统时避免犯同样的错误。RSA安全核心在于n难以分解。因此必须使用足够长目前建议至少2048位且随机生成的素数p和q。任何对p、q的约束如接近、低位相同、由特定算法生成或对参数e、d的特殊选择如过小都可能引入致命漏洞。AES算法本身是安全的但模式选择和密钥管理是关键。禁止使用ECB模式存储或传输敏感数据。CBC模式的IV必须随机且不可预测最好使用密码学安全的随机数生成器CSPRNG生成。密钥必须保密且足够随机。认证加密模式如GCM是更优选择它能同时防止密文被篡改。最后再分享一个我常用的测试习惯在写出一个解密脚本后我会先用已知答案的简单数据跑一遍比如用脚本加密一个字符串再用同一个脚本解密回来确保基础流程正确。然后再去处理题目给的复杂数据。这个“自检”步骤能帮你排除掉很多低级的编码或逻辑错误把精力集中在真正的密码学问题上。密码学实战就像解谜工具和脚本是你的放大镜和钥匙但对原理的深刻理解才是照亮迷宫的那盏灯。