CTF密码学实战用Python从零破解RSA的完整指南RSA加密算法作为现代密码学的基石在CTF竞赛中出现的频率极高。但对于刚入门的新手来说面对一堆数学符号和加密数据往往无从下手。本文将带你用Python一步步拆解RSA加密从公钥提取到最终解密完整复现攻防世界Crypto题目的解题过程。1. 理解RSA加密的基本原理RSA算法的安全性建立在大整数分解难题之上。简单来说它利用两个大质数相乘容易但反过来分解极其困难的特性。加密过程涉及三个关键参数模数n两个大质数p和q的乘积n p * q公钥e通常取65537与φ(n)互质私钥de关于φ(n)的模反元素满足 e*d ≡ 1 mod φ(n)其中φ(n)是欧拉函数对于npq的情况φ(n) (p-1)(q-1)提示在CTF中RSA题目常通过设置不安全的参数如过小的p/q来降低难度这正是我们破解的突破口。2. 准备Python密码学环境在开始破解前我们需要配置合适的Python环境。推荐使用以下工具链pip install pycryptodome gmpy2pycryptodome替代已停止维护的PyCrypto提供完整的密码学工具集gmpy2高性能大整数运算库加速模逆运算等操作如果遇到安装问题可以尝试# 对于Linux/macOS用户可能需要先安装依赖 sudo apt-get install libgmp-dev libmpfr-dev libmpc-dev # Ubuntu/Debian brew install gmp mpfr libmpc # macOS3. 提取RSA公钥参数拿到题目提供的key.pub文件后第一步是提取其中的n和e。下面是完整的Python代码from Crypto.PublicKey import RSA # 读取公钥文件 with open(key.pub, rb) as pub_file: pub_key RSA.import_key(pub_file.read()) # 获取关键参数 n pub_key.n e pub_key.e print(f模数n: {n}) print(f公钥指数e: {e})运行后会输出类似这样的结果模数n: 833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019 公钥指数e: 655374. 分解模数n获取p和q这是破解RSA最关键的步骤。对于CTF题目通常n不会太大可以使用在线工具或本地算法分解方法一使用Factordb在线分解访问factordb.com输入n值查询是否已被分解。如果幸运的话可以直接得到p和qp 863653476616376575308866344984576466644942572246900013156919 q 965445304326998194798282228842484732438457170595999523426901方法二本地使用Pollards Rho算法对于小型n可以用Python实现分解from math import gcd from random import randint def pollards_rho(n): if n % 2 0: return 2 if n % 3 0: return 3 while True: c randint(2, n-1) f lambda x: (pow(x,2,n)c) % n x, y, d 2, 2, 1 while d 1: x f(x) y f(f(y)) d gcd(abs(x-y), n) if d ! n: return d # 示例使用 n 833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019 p pollards_rho(n) q n // p print(fp {p}\nq {q})5. 计算私钥d得到p和q后计算私钥d的完整过程如下import gmpy2 p 863653476616376575308866344984576466644942572246900013156919 q 965445304326998194798282228842484732438457170595999523426901 e 65537 # 计算欧拉函数φ(n) phi (p-1)*(q-1) # 计算模反元素d d gmpy2.invert(e, phi) print(f私钥d: {d})输出结果私钥d: 5212506466630563917687643665176186553122753746686924303210646345665335683739699904653130929284555469898329619055783754736. 解密flag密文最后一步是使用私钥解密题目提供的密文。注意题目中的密文是base64编码的需要先解码from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_OAEP import base64 # 准备私钥 priv_key RSA.construct((n, e, d, p, q)) # 读取并解码密文 with open(flag.b64, r) as f: cipher base64.b64decode(f.read().strip()) # 使用PKCS#1 OAEP模式解密 cipher_rsa PKCS1_OAEP.new(priv_key) flag cipher_rsa.decrypt(cipher) print(f解密结果: {flag.decode()})如果一切顺利你将看到flag显示ALEXCTF{SMALL_PRIMES_ARE_BAD}7. 常见问题与调试技巧在实际操作中可能会遇到各种问题这里总结几个常见情况导入错误No module named Crypto确认安装的是pycryptodome而非pycryptogmpy2 not found可能需要先安装系统依赖解密失败检查是否使用了正确的填充模式OAEP或PKCS1_v1_5确认p和q的正确性可以验证n p*q性能优化对于大数运算gmpy2比Python原生整数运算快得多分解大n时可以尝试yafu等专业工具# 验证参数正确性的检查代码 assert n p * q assert (e * d) % phi 18. 扩展学习与防御思路理解了攻击方法后也应该知道如何防御密钥长度现代应用至少使用2048位RSA质数选择p和q应足够大且随机避免使用相近的质数加密填充务必使用OAEP等安全填充方案对于想进一步学习的同学推荐尝试攻防世界的其他RSA题目如babyRSA、hardRSA研究Coppersmith攻击等更高级的RSA破解技术了解基于RSA的签名算法和其潜在漏洞在最近的一次CTF比赛中我遇到一个n长达1024位的题目最初以为不可破解但发现出题人使用了相同的n加密多条消息最终通过共模攻击成功解密。这种实战经验正是通过不断练习积累的。