1. 项目概述当RSA不再是“绝对安全”在密码学的世界里RSA算法长久以来都被视为非对称加密的基石是构建现代互联网信任体系的关键组件。从HTTPS的握手到SSH的登录再到数字签名它的身影无处不在。很多开发者甚至是一些安全工程师都习惯于将其视为一个“黑盒”——生成一对密钥公钥加密私钥解密只要密钥足够长比如2048位似乎就高枕无忧了。然而在实际的渗透测试、CTF竞赛或是遗留系统的安全审计中我们常常会遇到一些“非标准”的RSA实现。这些实现可能因为追求性能、兼容老协议或是开发者对密码学理解不深而引入了各种脆弱性。这时RSA的“坚不可摧”就变成了一个危险的错觉。这个项目正是要撕开这个错觉。它不是一个教你如何“黑掉”正常RSA的指南而是一份针对脆弱RSA实现场景的实战手册。核心目标很明确当你手头只有一些零散的信息——可能是一个PEM格式的公钥文件、几条截获的密文、或者一些关于加密过程的边信道信息——如何利用Python这把瑞士军刀抽丝剥茧还原出明文或私钥。标题中的“7种场景”涵盖了从最基础的信息泄露公钥提取参数到需要一定数学技巧的攻击如维纳攻击形成了一个由浅入深的完整链条。对于安全研究人员、CTF选手以及对密码学实战感兴趣的程序员来说掌握这些场景的识别与利用意味着你能在看似铜墙铁壁的加密数据面前找到那条隐藏的裂缝。2. 核心攻击场景全景解析RSA的安全性建立在“大数分解难题”和“模幂运算的逆运算困难”之上。但当算法在实现和应用过程中偏离了理想假设攻击面便随之产生。下面我们系统性地拆解这七种经典攻击场景的内在逻辑与前置条件。2.1 场景一公钥信息提取与基础参数解析这是所有攻击的起点也是最常被忽略的一步。很多时候我们拿到的不是一个直接的(n, e)对而是一个PEM文件、一段Base64编码的字符串或者内嵌在代码、配置文件中的密钥片段。为什么这是突破口RSA的公钥本质上就是两个数字模数n一个大素数的乘积和公钥指数e。任何攻击都需要以这两个参数为基础。提取过程就是将这些各种格式的“外壳”剥掉拿到核心的数学参数。实操要点与工具选择在Python中我们有多种武器库。对于标准的PEM格式公钥Crypto.PublicKey.RSA.import_key()是最直接的方法。但实战中更常见的是各种“变体”。例如从SSH的authorized_keys文件中提取其格式是ssh-rsa AAAAB3NzaC1yc2E...这其实是经过特定编码的。这时我们可以使用pycryptodome库或者更底层的asn1crypto库来解析其中的ASN.1结构。from Crypto.PublicKey import RSA # 场景1: 从PEM文件读取 with open(public.pem, r) as f: pem_data f.read() pub_key RSA.import_key(pem_data) n, e pub_key.n, pub_key.e print(fn {n}\ne {e}) # 场景2: 从Base64字符串解析常见于网络传输或配置 import base64 from Crypto.Util.asn1 import DerSequence b64_key MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAzX7p1wM9Q3J7... der base64.b64decode(b64_key) # 尝试解析PKCS#1格式 seq DerSequence() seq.decode(der) if len(seq) 2: # PKCS#1 格式: (n, e) n, e seq[0], seq[1]注意不是所有Base64字符串都是直接的DER编码。它可能是PEM去掉了头尾-----BEGIN PUBLIC KEY-----也可能是其他格式如OpenSSH格式。解析失败时需要结合上下文判断格式并可能需要进行手动解析。2.2 场景二模数分解攻击当n过小或存在缺陷这是最“正统”的攻击思路既然RSA的安全性依赖于np*q难以分解那么如果n不够大或者p和q非常接近或者存在其他数学缺陷分解就变得可行。核心原理与工具实战对于较小的n如小于512位我们可以直接使用本地工具如yafu或在线数据库如factordb.com。在Python中sympy库的factorint函数可以处理小整数的分解。但对于更大的n我们需要更高效的算法。import sympy from math import isqrt n 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 # 方法1: 使用sympy适用于较小n factors sympy.factorint(n) # 例如 {37975227936943673922808872755445627854565536638199: 1, 40094690950920881030683735292761468389214899724061: 1} p, q list(factors.keys()) # 方法2: 费马分解法当p和q接近时高效 def fermat_factorization(n): a isqrt(n) 1 b2 a*a - n while not isqrt(b2)**2 b2: a 1 b2 a*a - n b isqrt(b2) return a - b, a b p, q fermat_factorization(n)为什么费马分解有效如果p和q接近那么它们的平均数(pq)/2与sqrt(n)很接近。设a (pq)/2,b (p-q)/2则有n a^2 - b^2。费马分解就是从a ceil(sqrt(n))开始逐步增加a检查a^2 - n是否为完全平方数b^2。一旦找到p ab,q a-b。2.3 场景三共模攻击Common Modulus Attack想象一个糟糕的场景一个系统用同一对p, q生成了多个密钥对即多个用户共享同一个模数n但拥有不同的公钥指数e1, e2和对应的私钥d1, d2。这听起来很荒谬但在一些老旧或设计不当的系统中确实存在。攻击的数学基础假设同一消息m用两个公钥(n, e1)和(n, e2)加密得到密文c1 ≡ m^e1 mod n和c2 ≡ m^e2 mod n。如果e1和e2互素通常都是素数所以大概率互素根据贝祖定理存在整数s1, s2使得e1*s1 e2*s2 1。那么我们可以计算(c1^s1 * c2^s2) mod n ≡ m^(e1*s1) * m^(e2*s2) mod n ≡ m^(e1*s1 e2*s2) mod n ≡ m^1 mod n m注意s1或s2可能是负数。如果是负数我们需要先计算模逆元。例如若s1为负则计算c1_inv modinv(c1, n)然后计算(c1_inv^(-s1) * c2^s2) mod n。Python实现from Crypto.Util.number import long_to_bytes, bytes_to_long import gmpy2 def common_modulus_attack(c1, c2, e1, e2, n): # 使用扩展欧几里得算法求系数s1, s2 gcd, s1, s2 gmpy2.gcdext(e1, e2) if gcd ! 1: raise ValueError(e1 and e2 必须互素) # 处理负数指数 if s1 0: c1 gmpy2.invert(c1, n) s1 -s1 if s2 0: c2 gmpy2.invert(c2, n) s2 -s2 # 计算 m c1^s1 * c2^s2 mod n m (pow(c1, s1, n) * pow(c2, s2, n)) % n return long_to_bytes(m) # 示例 n 0x共同的模数... e1, c1 0x10001, 0x密文1... e2, c2 0x10003, 0x密文2... message common_modulus_attack(c1, c2, e1, e2, n) print(f还原的消息: {message})2.4 场景四低加密指数攻击如e3为了提升加密效率一些系统会使用非常小的公钥指数e比如3。当e很小并且明文m也很小满足m^e n时加密过程c m^e mod n实际上退化为c m^e因为m^e还没有模数n大取模无效果。此时直接对密文c开e次方根即可得到明文。攻击条件与扩展明文填充不当如果明文m没有经过随机填充直接加密且m较小则攻击成立。广播攻击Hastad广播攻击如果同一消息m用相同的低指数e如3加密但发送给e个不同的接收者使用不同的模数n1, n2, n3那么我们可以利用中国剩余定理CRT构造一个关于m^e的同余方程组最终直接求解m^e的整数解再开方得到m。这比单纯e3且m^3n的条件更常见。低加密指数广播攻击Python示例import gmpy2 from functools import reduce def crt(remainders, moduli): 中国剩余定理实现 total 0 prod reduce(lambda a, b: a*b, moduli) for r_i, n_i in zip(remainders, moduli): p prod // n_i total r_i * gmpy2.invert(p, n_i) * p return total % prod # 假设同一消息m用e3加密生成3组密文和模数 e 3 ciphers [c1, c2, c3] # 三个密文 moduli [n1, n2, n3] # 三个不同的模数 # 利用CRT求解 m^3 mod (n1*n2*n3) m_cubed crt(ciphers, moduli) # 由于 m^3 n1*n2*n3 (通常情况)所以 m_cubed 就是精确的 m^3 m, exact gmpy2.iroot(m_cubed, e) # 开三次方根 if exact: print(f还原的消息: {long_to_bytes(int(m))})2.5 场景五维纳攻击Wiener‘s Attack这是本项目的一个重点也是一种非常精妙且在实际中可能遇到的攻击。它针对的是私钥指数d过小的情况。为了提高解密或签名速度开发者可能会刻意选择一个较小的d。维纳攻击告诉我们如果d (1/3) * n^(1/4)那么攻击者可以仅从公钥(n, e)中高效地恢复出私钥d。背后的数学原理简述RSA的密钥生成满足e*d ≡ 1 mod φ(n)其中φ(n) (p-1)*(q-1)。这意味着存在一个整数k使得e*d k*φ(n) 1。将等式两边同时除以d*φ(n)得到e/φ(n) - k/d 1/(d*φ(n))。由于φ(n)非常接近n因为p和q都很大所以e/n是k/d的一个非常好的近似。数论中的连分数理论告诉我们一个有理数的“好”的近似值会出现在其连分数展开的收敛子中。因此我们可以计算e/n的连分数展开并依次尝试每一个收敛子k’/d’检查d’是否就是正确的私钥d。Python实现维纳攻击import gmpy2 from Crypto.Util.number import long_to_bytes def wiener_attack(e, n): 维纳攻击实现 # 计算 e/n 的连分数展开 def continued_fractions(e, n): cf [] while n: q e // n cf.append(q) e, n n, e - q * n return cf # 根据连分数展开计算收敛子 def convergents(cf): convergents [] for i in range(len(cf)): num, den 1, 0 for j in range(i, -1, -1): num, den cf[j] * num den, num convergents.append((num, den)) return convergents cf continued_fractions(e, n) convergents_list convergents(cf) for k, d in convergents_list: if k 0: continue # 检查条件ed ≡ 1 mod φ(n) 的近似 # 根据 ed - 1 kφ(n)可以推导出 φ(n) (ed-1)/k # 然后通过 φ(n) 求解 p, q if (e * d - 1) % k ! 0: continue phi (e * d - 1) // k # 根据 φ(n) (p-1)(q-1) n - (pq) 1建立一元二次方程 # sum_pq n - phi 1 # product_pq n # 方程: x^2 - sum_pq*x n 0 sum_pq n - phi 1 discriminant sum_pq * sum_pq - 4 * n if discriminant 0: continue sqrt_disc, exact gmpy2.iroot(discriminant, 2) if not exact: continue p (sum_pq sqrt_disc) // 2 q (sum_pq - sqrt_disc) // 2 if p * q n: return d, p, q return None # 使用示例 e 67994682464925517847561377525734815980381 n 9516311845790656153499716760847001433441357 result wiener_attack(e, n) if result: d, p, q result print(f攻击成功私钥d: {d}) print(f分解结果: p{p}, q{q})实操心得维纳攻击的实现对精度要求很高必须使用大整数运算库如gmpy2。在CTF中题目往往会给出一个明显很大的e因为d小根据e*d ≡ 1 mod φ(n)e就会很大这是一个强烈的提示信号。另外攻击成功后不仅能得到d还能直接分解n。2.6 场景六选择密文攻击与填充预言Padding Oracle这种攻击针对的是实现层面的漏洞而非数学难题。在许多使用RSA进行传输加密的场景中会先对明文进行填充如PKCS#1 v1.5然后再加密。如果服务器在解密后对于填充错误的密文和填充正确但内容错误的密文返回不同的错误信息例如一个返回“解密错误”一个返回“格式错误”那么它就泄露了一个“预言机”Oracle。攻击者可以利用这个侧信道信息通过不断发送精心构造的密文并观察服务器响应逐步推算出原始明文。基本思想Bleichenbacher攻击假设我们有密文c其对应的明文m符合PKCS#1 v1.5填充格式。攻击者可以不断构造新的密文c (s^e * c) mod n发送给服务器。因为Decrypt(c) (c)^d (s^e * c)^d s * m mod n。通过观察服务器对Decrypt(c)的填充验证结果成功或失败攻击者可以逐步缩小m可能的数值区间最终确定m。这个过程完全自动化并且对于2048位的RSA也只需要数十万次查询在现代计算机上是可以完成的。工具与实现手动实现完整的Bleichenbacher攻击较为复杂通常会使用像python-paddingoracle这样的库或者CTF中的专用脚本。其核心是一个二分搜索的变种利用Oracle的反馈来调整搜索空间。2.7 场景七侧信道与故障攻击概念延伸这属于更高级的物理攻击范畴但在一些特定场景如分析智能卡、硬件安全模块的题目中可能出现。侧信道攻击不直接攻击算法而是通过分析设备执行加解密操作时的功耗、电磁辐射、时间差异等信息来推断密钥。故障攻击则是在计算过程中例如签名时故意引入故障如电压毛刺、时钟抖动导致设备输出错误的签名利用这个错误签名和正确签名的关系来恢复私钥。在CTF中的常见形式可能会给你一个“有缺陷”的签名实现或者提供多组在轻微扰动下产生的签名/密文要求你恢复密钥。这类题目通常需要更深入的数学知识如针对RSA-CRT的故障攻击分析。3. 实战演练从一道CTF题看复合攻击让我们结合热搜词中提到的那个具体场景来一次综合实战“某个老旧的认证网关会把用户登录时生成的令牌写入审计日志。为了兼容两套接口同一个用户的令牌会以两种格式出现一种带有固定开头另一种带有固定结尾。管理员只找到了两条被同一把rsa公钥加密后的日志以及这两种格式的固定部分。请还原日志里真正变化的那段内容。”1. 问题拆解已知同一把RSA公钥(n, e)两条密文c1, c2。已知明文有两种固定格式。设变化的令牌部分为m固定开头为prefix固定结尾为suffix。那么两条明文可能是m1 prefix m格式A固定开头m2 m suffix格式B固定结尾目标求m。2. 攻击思路分析这既不是共模攻击模数相同但这里是同一公钥加密了不同明文也不是低指数攻击。我们注意到明文m1和m2共享了中间部分m且prefix和suffix已知。这构成了一个已知部分明文的攻击场景。我们可以利用Coppersmith相关消息攻击或其变种。更直接的方法是利用代数关系。将明文视为大整数。则有c1 ≡ (P M)^e mod n其中P bytes_to_long(prefix)c2 ≡ (M S)^e mod n其中S bytes_to_long(suffix)M bytes_to_long(m)我们有两个多项式在模n下f1(x) (P x)^e - c1f2(x) (x S)^e - c2我们寻找它们的公共根x M mod n。由于e通常很小如65537我们可以计算这两个多项式的最大公因式GCD。如果M的长度位数小于n的位数那么在整数域而非模n域上计算GCD很可能就直接得到(x - M)这个因子。3. Python实现from Crypto.Util.number import bytes_to_long, long_to_bytes import gmpy2 # 题目给出的数据 (示例值需替换为实际值) n 0xabcdef... # 模数 e 65537 c1 0x密文1... c2 0x密文2... prefix buser # 示例固定开头 suffix broleguest # 示例固定结尾 P bytes_to_long(prefix) S bytes_to_long(suffix) # 在整数环上定义多项式使用sympy import sympy x sympy.symbols(x) poly1 sympy.Pow(P x, e) - c1 poly2 sympy.Pow(x S, e) - c2 # 计算两个多项式的GCD gcd_poly sympy.gcd(poly1, poly2) # GCD结果应该是一个线性多项式如 (x - M) roots sympy.solve(gcd_poly, x) for root in roots: if root.is_integer and root 0: M int(root) print(f找到可能的令牌M: {long_to_bytes(M)}) break注意事项这种方法在e较大时多项式展开会非常庞大计算GCD可能内存不足。此时可以使用基于结式Resultant或使用Zmod(n)环上更高效的Coppersmith方法通过SageMath实现更简单。但在CTF中如果e是常规的65537且prefix和suffix不长上述方法在本地往往可行。4. 工具链搭建与调试技巧工欲善其事必先利其器。一个高效的RSA破解环境能让你事半功倍。1. 核心Python库pycryptodome/Crypto最常用的密码学库用于标准的密钥导入、加密解密操作。注意pycryptodome是pycrypto的维护分支。gmpy2绝对必备。提供高性能的大整数mpz运算支持开方、模逆、素数检测、GCD等速度远超Python原生整数。维纳攻击、分解等操作依赖它。sympy符号计算库用于多项式运算、小整数分解、解方程等在已知部分明文攻击中很有用。libnum一个CTF密码学工具库封装了很多常用函数如bytes_to_long,long_to_bytes,gcd,invmod等非常方便。安装命令pip install pycryptodome gmpy2 sympy # libnum 有时需要从源码安装或使用 pip install libnum2. 分解工具本地yafu功能强大的整数分解工具支持多种算法。在线factordb.com查询已知分解的数据库。网站alpertron.com.ar/ECM.HTM提供基于ECM等算法的在线分解器对于中等大小的数很有效。3. 调试与思考流程信息收集拿到题目首先提取所有数字。可能是十六进制、十进制、Base64。统一转为十进制大整数备用。参数检查看n的大小尝试用factordb或yafu分解。看e的大小如果e3或e很小考虑低加密指数攻击或广播攻击。看e是否巨大如果e和n差不多大提示d可能很小考虑维纳攻击。是否有多个n或e判断是共模、广播还是共享素数。关系分析分析密文与明文之间、多个密文之间、多个密钥之间是否存在数学关系如线性关系、共用参数。选择工具根据以上分析选择对应的攻击脚本或编写代码。结果验证解密或恢复出的明文是否是可读的字符串如包含flag{、CTF等或者是否能进一步用于解密其他数据。常见问题排查gmpy2安装失败在Windows上可能需要从Unofficial Windows Binaries for Python Extension Packages网站下载对应版本的.whl文件进行安装。脚本运行内存/时间爆炸检查算法复杂度。例如直接对n进行暴力分解是不可行的。维纳攻击的连分数展开收敛很快如果长时间没结果可能不是维纳攻击的场景。解密出来是乱码可能是编码问题。尝试long_to_bytes()的结果用utf-8、ascii、latin-1等多种编码解码或者直接hex()查看是否为flag格式。5. 防御视角如何避免自己的RSA被破解作为开发者了解攻击手段是为了更好地防御。从这些攻击场景中我们可以总结出以下安全实践使用足够长的密钥目前推荐至少2048位重要系统考虑3072或4096位。使用标准的公钥指数就使用e65537。它不大不小既避免了低指数攻击计算效率也高且二进制表示中1的位数少平方乘算法效率高。使用安全的随机数生成器生成p和q确保p和q长度相同、差异很大并且p-1和q-1都有大素因子以抵抗特定的分解算法。绝不重复使用模数n每个密钥对应独立的p和q。务必使用标准的填充方案如加密用OAEP签名用PSS。绝对不要使用“教科书式RSA”即无填充。私钥指数d不能小虽然能加速解密但会引入维纳攻击的风险。密钥生成时应确保d的位数大约为n位数的一半。实现上要恒定时间、无侧信道确保加解密操作的时间不依赖于密钥或明文避免提供Padding Oracle。最后记住密码学的一个基本原则不要自己发明密码系统。使用经过广泛审查的成熟库如Python的cryptography库并严格按照其文档和最佳实践来使用。这些攻击之所以存在往往是因为人们在实现或应用标准算法时无意或有意地偏离了安全轨道。这份指南正是为了帮助你识别并理解那些危险的偏离。