Python实战RSA：从大素数分解到共模攻击的CTF密码学解析

1. RSA基础与CTF实战场景第一次参加CTF比赛时我盯着那道RSA密码题发了半小时呆。屏幕上只有几行看似简单的数学表达式和两个巨大的数字完全不知道从何下手。后来才知道这正是RSA在CTF竞赛中的典型呈现方式——给你足够的信息但需要找到正确的突破口。RSA作为非对称加密的黄金标准其安全性建立在大整数分解难题上。简单来说加密过程就像用公开的挂锁锁住箱子只有持有私钥的人才能打开。在CTF比赛中出题者往往会故意留后门比如设置不安全的参数或暴露特殊关系这正是我们需要寻找的攻击路径。核心三要素公钥(n,e)模数n是两个大素数的乘积e是加密指数通常为65537私钥d通过欧拉函数φ(n)计算得出加解密过程密文c ≡ m^e mod n明文m ≡ c^d mod n理解这个基础框架后我们就能开始分析CTF中的两类典型攻击场景当两个模数n共享质因数时的大素数分解攻击以及相同明文被不同公钥加密时的共模攻击。下面我用实际赛题带你逐个击破。2. 大素数分解攻击实战去年一道真实赛题给出了这样的数据n1 122471408093484796049214715641805864877685858159... n2 183898229850821196468739135876865358742142175996... c1 745228910379879307769528041716941945516689970178... # 密文 e 65537 # 加密指数2.1 攻击原理剖析正常RSA中np*q的两个质因数应该完全独立。但出题者偷懒时可能会让两个不同的n共享同一个质因数p。这时计算gcd(n1,n2)即可得到公共质因数p分别求出q1 n1/pq2 n2/p计算φ(n1)(p-1)(q1-1)用扩展欧几里得算法求私钥d ≡ e⁻¹ mod φ(n1)这就像发现两把不同的挂锁用了相同的弹簧只要拆解其中一把另一把的机关也就暴露了。2.2 Python实现细节使用gmpy2库处理大整数运算from gmpy2 import gcd, invert def break_rsa(n1, n2, c, e): p gcd(n1, n2) q1 n1 // p phi (p-1)*(q1-1) d invert(e, phi) m pow(c, d, n1) return m关键点gcd()计算最大公约数比试除法快几个数量级使用//进行整数除法避免浮点误差pow(c,d,n)的三参数形式比(c**d)%n更高效2.3 实战中的坑与解决我第一次实现时遇到了两个问题数据类型混淆从文本读取的n需要先转为mpz类型n1 mpz(122471408093484796049214715641805864877685858159...)内存溢出直接计算c**d会导致内存爆炸必须用三参数pow3. 共模攻击深度解析另一道经典题目给出了n 142277988617424018525407163328887172353325955112... e1, e2 1804229351, 17249876309 # 两个加密指数 c1 274836833869639935605940638559531294566444037182... c2 707010127634559200562437001455024085447957459342...3.1 数学基础扩展欧几里得算法当同一明文m用不同指数e1,e2加密但模数n相同时若e1与e2互质则存在e1*s e2*t 1通过扩展欧几里得算法可以求出s和t进而得到m ≡ (c1^s * c2^t) mod n3.2 Python代码实现def common_modulus_attack(e1, e2, c1, c2, n): g, s, t gcdext(e1, e2) if s 0: c1 invert(c1, n) s -s if t 0: c2 invert(c2, n) t -t m (pow(c1,s,n) * pow(c2,t,n)) % n return m注意事项需要处理负指数的情况模逆元计算使用invert()而非直接取负乘法结果必须再次取模3.3 性能优化技巧在处理2048位大数时我总结了几个提速方法预计算对于固定n可以预先计算好常用模逆元并行计算c1^s和c2^t可以多线程并行内存管理及时释放中间变量减少内存占用4. Crypto库的安装与排错新手最常卡在环境配置环节。以我踩过的坑为例4.1 正确安装姿势# 推荐使用清华镜像源 pip install pycryptodome -i https://pypi.tuna.tsinghua.edu.cn/simple4.2 常见错误解决**ImportError: No module named Crypto**的终极解决方案确认安装路径python -c import Crypto; print(Crypto.__file__)重命名文件夹mv /path/to/site-packages/crypto /path/to/site-packages/Crypto添加软链接Linux/Macln -s crypto Crypto4.3 版本兼容性建议不同Python版本对应的安装命令Python 2.x:pip install pycryptoPython 3.5:pip install pycryptodome最新版pip install cryptography5. 完整解题流程演示让我们用一道综合题目串联所有知识点题目给出n1, n2, c1 (大素数分解攻击)n, e1, e2, c1, c2 (共模攻击)5.1 分步解题第一步恢复前半段flagp gcd(n1, n2) q1 n1 // p d invert(65537, (p-1)*(q1-1)) flag_part1 long_to_bytes(pow(c1, d, n1))第二步恢复后半段flagg, s, t gcdext(e1, e2) flag_part2 long_to_bytes((pow(c1,s,n) * pow(c2,t,n)) % n)合并结果print(flag_part1 flag_part2) # 完整flag5.2 调试技巧当结果不对时检查顺序确认所有参数类型为mpz检查模逆元计算是否正确验证中间结果是否超出模数范围6. 防御措施与出题思路了解攻击方法后作为出题者可以设计更安全的题目6.1 安全参数选择素数生成应使用安全方法from Crypto.Util.number import getStrongPrime p getStrongPrime(1024)避免参数之间的任何关联6.2 题目设计技巧好的CTF密码题应该留有非暴力的数学突破口隐藏足够多的提示信息参数大小适中1024-2048位记得去年我设计的一道题通过巧妙设置让选手需要组合两种攻击方法才能解出flag这种递进式的设计往往最受欢迎。