从CTF实战出发：剖析RSA公钥泄露与弱质因数分解的致命组合

1. CTF中的RSA挑战从公钥泄露到flag获取第一次参加CTF比赛时我遇到了一道RSA相关的密码学题目。当时看着那个key.pub文件和base64编码的密文完全不知道从何下手。后来经过多次实战才发现这类题目其实有一套标准解题流程。今天我就以cr4-poor-rsa这道经典赛题为例带你完整走一遍RSA公钥泄露攻击的全过程。RSA作为最常用的非对称加密算法在CTF密码学挑战中出现的频率极高。它的安全性基于大整数分解的困难性但当参数设置不当时这种安全性就会土崩瓦解。在实战中我们经常遇到的情况是给你一个公钥文件一段加密数据然后让你找出隐藏的flag。听起来简单但其中涉及的知识点可不少。2. 初始分析提取RSA公钥参数2.1 公钥文件的结构解析拿到题目附件后我发现里面有两个关键文件flag.b64和key.pub。这个key.pub就是典型的RSA公钥文件格式如下-----BEGIN PUBLIC KEY----- ME0wDQYJKoZIhvcNAQEBBQADPAAwOQIyUqmeJJ7nzzwMv5Y6AJZhdyvJzfbh4/v8 bkSgel4PiURXqfgcOuEyrFaD01soulwyQkMCAwEAAQ -----END PUBLIC KEY-----这个看似随机的字符串其实包含了RSA加密所需的所有公开参数。要提取其中的模数n和指数e我们可以使用Python的Crypto库from Crypto.PublicKey import RSA with open(./key.pub, rb) as file: key file.read() pub RSA.importKey(key) n pub.n e pub.e print(n , n) print(e , e)运行后我们得到了n 833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019 e 655372.2 为什么e通常是65537细心的你可能注意到了这里的e值是655372^161。这个数字在RSA中非常常见原因有三它足够大避免了小指数攻击二进制表示只有两个1计算效率高作为费马素数与φ(n)互质的概率很高在CTF题目中e值很少成为突破口我们的注意力应该集中在模数n上。3. 破解RSA的关键分解模数n3.1 为什么分解n就能破解RSARSA的安全性依赖于大整数分解的困难性。如果我们能分解n得到p和q就可以计算出φ(n)(p-1)(q-1)进而求出私钥d ≡ e⁻¹ mod φ(n)。在本题中n的值是 833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019这个数字看起来很大但在现代计算机面前它其实小得可怜。我们可以尝试用一些在线工具来分解它。3.2 使用FactorDB分解nFactorDB是一个强大的因数分解数据库对于常见的、较小的n值它通常已经存储了分解结果。我们把n值提交上去http://factordb.com/index.php?query833810193564967701912362955539789451139872863794534923259743419423089229206473091408403560311191545764221310666338878019果然它立即返回了分解结果p 863653476616376575308866344984576466644942572246900013156919 q 9654453043269981947982822288424847324384571705959995234269013.3 为什么这个n这么容易被分解这就是题目名称poor-rsa的含义。在实际应用中RSA的模数n应该有至少2048位约600位十进制数而这里的n只有154位。此外题目可能故意使用了强度不足的质数生成方法使得n更容易被分解。4. 计算私钥并解密密文4.1 计算私钥参数d有了p和q我们就可以计算φ(n)和私钥d了import gmpy2 p 863653476616376575308866344984576466644942572246900013156919 q 965445304326998194798282228842484732438457170595999523426901 e 65537 phi_n (p - 1) * (q - 1) d gmpy2.invert(e, phi_n) print(d , d)输出d 5212506466630563917687643665176186553122753746686924303210646345665335683739699904653130929284555469898329619055783754734.2 解密密文获取flag现在万事俱备我们可以用私钥来解密密文了。首先看一下flag.b64文件内容Ni45iH4UnXSttNuf0Oy80G5J7tm8sBJuDNN7qfTIdEKJow4siF2cpSbP/qIWDjSiw解密过程分为两步先用base64解码再用RSA解密import rsa import base64 # 生成私钥对象 priv rsa.PrivateKey(n, e, d, p, q) # 读取并解密密文 with open(./flag.b64, rb) as file: cipher file.read() cipher base64.b64decode(cipher) flag rsa.decrypt(cipher, priv).decode() print(flag)最终我们得到了flagALEXCTF{SMALL_PRIMES_ARE_BAD}5. 防御措施与实战建议5.1 如何避免RSA被这样破解从这道题目中我们可以学到几个重要的安全经验使用足够大的密钥长度至少2048位重要场景推荐4096位使用强质数生成算法避免使用简单的随机数生成器定期更换密钥即使密钥强度足够也应定期更换不要公开不必要的密钥信息最小化信息公开原则5.2 CTF中的常见变种在实际CTF比赛中RSA题目可能会有各种变种比如使用相同的n但不同的e加密多条消息e值非常小导致的小指数攻击p和q非常接近导致费马分解法生效使用中国剩余定理加速解密遇到这类题目时核心思路依然是分析公钥参数寻找弱点然后针对性攻击。多练习几道类似题目后你会发现这类挑战其实有章可循。