1. RSA基础回顾与CTF常见题型在CTF比赛中RSA加密算法出现的频率极高。简单来说RSA的安全性基于大整数分解的困难性——给定一个由两个大素数p和q相乘得到的N想要逆向分解出p和q极其困难。我们先看几个最基础的题型已知(p,q,e)求d这是最基础的情况直接计算欧拉函数φ(n)(p-1)(q-1)然后求e的模反元素d即可。Python代码示例import gmpy2 p 447685307 q 2037 e 17 phi (p-1)*(q-1) d gmpy2.invert(e, phi) print(d)已知(p,q,e,c)求m在上一题基础上用私钥d解密密文c。实际操作中要注意大数运算的优化m gmpy2.powmod(c, d, p*q) # 比pow(c,d,p*q)更快已知(e,dp,n,c)求m这是2019年BJDCTF的真题。dpd mod (p-1)这个信息很关键可以通过遍历k值爆破pfor k in range(1, e): if (e*dp-1)%k 0 and n%((e*dp-1)//k1)0: p (e*dp-1)//k 1 break2. 自动化工具RsaCtfTool实战当面对未知的RSA题目时RsaCtfTool这个神器能自动识别适用的攻击方式。它的安装非常简单git clone https://github.com/RsaCtfTool/RsaCtfTool.git cd RsaCtfTool pip install -r requirements.txt常用攻击命令示例# 基础解密自动尝试所有攻击方式 python RsaCtfTool.py --publickey key.pub --uncipherfile ciphertext # 指定Wiener攻击 python RsaCtfTool.py --attack wiener --publickey key.pub # 从n和e创建公钥 python RsaCtfTool.py --createpub -n 1234567 -e 65537我曾在一道CTF题中遇到n特别大2048位的情况手动分解几乎不可能。使用工具的factordb攻击模式发现这个n已经被其他人分解过并上传到在线数据库3秒就拿到了p和q。3. 进阶攻击手法剖析3.1 Wiener攻击小私钥d当私钥d很小时具体说是d 1/3 * N^(1/4)可以通过连分数展开来破解。实战中可以用这个判断条件if d.bit_length() (n.bit_length()//4 - 10): print(可能适用Wiener攻击)RsaCtfTool内部实现用的是Pablo Celayes的算法核心是利用Legendre定理逼近d的值。3.2 共模攻击如果相同的明文用相同的n但不同的e加密且e1和e2互质就能通过扩展欧几里得算法找到a和b使得ae1 be2 1然后计算m (pow(c1,a,n) * pow(c2,b,n)) % n我在一道CTF中遇到过e13, e265537的情况用这个手法直接拿到了flag。3.3 低加密指数攻击当e很小时比如e3可能出现m^e n的情况此时直接对c开e次方就能得到明文m gmpy2.iroot(c, e)[0]更复杂的情况是m^e n但不够大可以通过爆破k值for k in range(100000): if gmpy2.iroot(c k*n, e)[1]: m gmpy2.iroot(c k*n, e)[0] break4. CTF实战案例解析让我们看一个综合性的CTF题目改编自2022年RealWorldCTF题目给出n 178...8372048位e 65537c 893...423hintp和q都是光滑数smooth number解题步骤使用RsaCtfTool的pollard p-1攻击python RsaCtfTool.py --publickey key.pub --attack pollard_p-1工具在30秒内找到了p因为p-1的质因数都很小计算q n//p用常规方法解密得到flag踩坑提醒遇到n无法分解时一定要检查是否使用了相同的n共模攻击是否dp/dq泄露是否p和q非常接近费马分解是否使用了特殊素数如回文素数5. 防御措施与出题思路了解攻击手法后出高质量的RSA题目需要注意确保p和q足够大至少1024位避免使用特殊形式的素数e的选择要适当不要太小也不要与φ(n)不互质可以加入padding增加难度对于CTF选手我的建议是准备一个RSA解题checklist熟悉至少三种不同的分解算法掌握Python的gmpy2库和SageMath收集常见CTF的n分解记录factordb最后分享一个实用技巧遇到特别大的n时可以先尝试在https://factordb.com/查询是否已被分解。我在三次不同的比赛中都因为这个技巧快速拿到了分数。