CTF选手必看：5种常见RSA攻击手法实战解析（附Python脚本）

CTF密码学进阶：RSA攻击手法全解与实战脚本

引言：RSA在CTF中的核心地位

在当今CTF竞赛的密码学挑战中，RSA算法始终占据着举足轻重的地位。作为非对称加密的经典实现，RSA题目往往考察选手对数论基础、算法原理和漏洞利用的综合能力。本文将深入剖析CTF中高频出现的5种RSA攻击手法，从数学原理到Python实现，为参赛者提供一套完整的解题工具箱。

不同于传统的理论讲解，我们将采用"漏洞成因-识别特征-攻击脚本"的三段式解析，配合可直接复用的代码片段。这些技术经过各大CTF赛事的实战检验，包括：

• 已知因子的私钥推导
• 低加密指数的小明文攻击
• 共模攻击的巧妙破解
• 模不互素的高效利用
• 中国剩余定理的灵活应用

1. 基础攻击：已知p/q/e求d

数学原理与漏洞成因

当RSA的素数因子p和q泄露时，整个加密系统的安全性将土崩瓦解。根据RSA密钥生成原理：

φ(n) = (p-1)*(q-1) d ≡ e⁻¹ mod φ(n)

攻击者可以直接计算私钥d，从而解密任何密文。

实战识别特征

• 题目明确给出p、q、e的值
• 通过其他攻击方式（如n分解）获得p和q
• 关键提示："given the prime factors..."

Python自动化脚本

from gmpy2 import invert def calculate_d(p, q, e): phi = (p-1)*(q-1) d = invert(e, phi) return d # 示例参数 p = 473398607161 q = 4511491 e = 17 d = calculate_d(p, q, e) print(f"Calculated d: {d}")

典型例题解析

以[BUUCTF-Crypto]RSA为例：

1. 题目给出p=473398607161, q=4511491, e=17
2. 通过上述脚本计算得到d=125631357777427553
3. 最终flag格式为flag{125631357777427553}

2. 低加密指数攻击

攻击场景分类

2.1 小明文攻击（e=3）

当e较小且明文m满足mᵉ < n时，可直接开e次方恢复明文。

from gmpy2 import iroot from Crypto.Util.number import long_to_bytes def small_e_attack(c, e): m, exact = iroot(c, e) if exact: return long_to_bytes(m) return None # 示例 c = 912559294096157050635751565309942189123 e = 3 print(small_e_attack(c, e))

2.2 低加密指数广播攻击

当相同的明文用相同的e加密，发送给多个接收者时：

from functools import reduce from gmpy2 import invert def crt(remainders, modules): N = reduce(lambda x,y: x*y, modules) result = 0 for r, n in zip(remainders, modules): Ni = N // n inv = invert(Ni, n) result += r * Ni * inv return result % N def broadcast_attack(c_list, n_list, e): m_e = crt(c_list, n_list) m, exact = iroot(m_e, e) if exact: return m return None

3. 共模攻击（Common Modulus Attack）

攻击原理

当相同的明文用相同的n但不同的e加密，且gcd(e₁,e₂)=1时，可通过扩展欧几里得算法恢复明文。

识别特征

• 两组密文使用相同的n
• 两个e值互质
• 题目描述出现"same message"

自动化脚本

from gmpy2 import gcdext def common_modulus_attack(c1, c2, e1, e2, n): gcd, s1, s2 = gcdext(e1, e2) if s1 < 0: c1 = invert(c1, n) s1 = -s1 if s2 < 0: c2 = invert(c2, n) s2 = -s2 m = (pow(c1, s1, n) * pow(c2, s2, n)) % n return m

4. 模不互素攻击

漏洞本质

当两个n共享一个素因子时，可以通过计算gcd(n₁,n₂)快速分解模数。

实战脚本

from gmpy2 import gcd def shared_factor_attack(n1, n2): p = gcd(n1, n2) if p != 1: return p, n1//p, n2//p return None

5. 中国剩余定理加速解密

优化场景

当已知p、q、dp、dq时，可以显著加快解密速度：

def crt_decrypt(c, p, q, dp, dq): q_inv = invert(q, p) m1 = pow(c, dp, p) m2 = pow(c, dq, q) h = (q_inv*(m1 - m2)) % p return m2 + h*q

防御措施与实战建议

安全实现要点

1. 使用足够大的素数（至少2048位）
2. 避免低加密指数（e≥65537）
3. 确保随机数生成质量
4. 实施填充标准（OAEP）

CTF解题checklist

1. 检查n是否可分解
2. 验证e是否过小
3. 寻找模数共享情况
4. 分析是否存在共模
5. 检查参数间特殊关系

结语：从解题到出题

掌握这些攻击手法后，不仅可以高效解决CTF挑战，更能深入理解RSA的实际安全边界。建议尝试：

1. 修改脚本处理不同参数格式
2. 组合多种攻击手法解题
3. 设计自己的RSA挑战题目

这些实战经验将帮助你在CTF竞赛中建立明显的竞争优势，同时深化对密码学安全的理解。记住，真正的精通来自于将理论转化为实践的能力。