CTF中RSA非常规题型解析

CTF中RSA非常规题型解析 概述 本文档总结了CTF竞赛中RSA加密算法的非常规题型解法，这些题目不需要高深算法知识，但需要创造性思维和灵活运用RSA基础知识。 基础知识回顾 在深入非常规题型前，先回顾RSA的基本原理： 密钥生成 ： 选择两个大素数p和q 计算n = p × q 计算φ(n) = (p-1)(q-1) 选择e满足1 < e < φ(n)且gcd(e, φ(n)) = 1 计算d ≡ e⁻¹ mod φ(n) 加密 ：c ≡ mᵉ mod n 解密 ：m ≡ cᵈ mod n 非常规题型分类与解法 1. 小指数攻击 场景 ：当加密指数e非常小(如e=3)且明文m较小时 攻击方法 ： 由于mᵉ < n，直接对密文c开e次方即可得到明文 即使mᵉ > n，但mᵉ mod n = mᵉ - kn，可以尝试k=0,1,2...直到找到整数解 防御 ：使用适当填充(如OAEP)确保m足够大 2. 共模攻击 场景 ：相同明文用相同n不同e加密 条件 ： 两个密文c₁ ≡ mᵉ¹ mod n c₂ ≡ mᵉ² mod n gcd(e₁, e₂) = 1 攻击方法 ： 使用扩展欧几里得算法找到r,s使得e₁r + e₂s = 1 计算m ≡ c₁ʳ × c₂ˢ mod n 3. 已知高位攻击(Coppersmith) 场景 ：已知明文或私钥的部分比特 攻击方法 ： 使用Coppersmith算法构造方程求解 例如已知p的高位比特，可以构造方程并求解剩余部分 4. Wiener攻击 场景 ：私钥d较小时(d < 1/3 × n¹/⁴) 攻击方法 ： 利用连分数展开e/n逼近k/d 测试可能的k/d候选 5. 广播攻击(Hastad) 场景 ：相同明文用相同小e加密发送给多个接收者(不同n) 条件 ： c₁ ≡ mᵉ mod n₁ c₂ ≡ mᵉ mod n₂ ... cₖ ≡ mᵉ mod nₖ 攻击方法 ： 使用中国剩余定理(CRT)计算c ≡ mᵉ mod (n₁n₂...nₖ) 由于mᵉ < ∏nᵢ，可直接开e次方得m 6. Franklin-Reiter相关消息攻击 场景 ：两个明文满足线性关系，如m₂ = a×m₁ + b 攻击方法 ： 构造多项式f₁(x) = xᵉ - c₁ f₂(x) = (a×x + b)ᵉ - c₂ 计算gcd(f₁, f₂)得到(x - m₁) 7. 选择密文攻击 场景 ：攻击者可以获取解密oracle 攻击方法 ： 选择任意r，计算c' ≡ c × rᵉ mod n 获取m' ≡ (c')ᵈ mod n 计算m ≡ m' × r⁻¹ mod n 8. 素数重用攻击 场景 ：多个密钥对共享一个素数 条件 ： n₁ = p × q₁ n₂ = p × q₂ 攻击方法 ： 计算gcd(n₁, n₂) = p 分解n₁和n₂ 实战技巧 参数检查 ： 检查n是否可分解(小素数、相同素数、Fermat分解等) 检查e是否过小或过大 检查是否存在不正确的参数生成 特殊构造 ： 寻找参数间的数学关系 尝试将问题转化为方程求解 考虑使用格基约化等高级数学工具 工具使用 ： SageMath：内置多种数论函数和攻击实现 RsaCtfTool：自动化RSA攻击工具 factordb：在线分解数据库 防御建议 使用足够大的密钥长度(≥2048位) 使用安全的随机数生成器 使用标准填充方案(如OAEP) 避免重复使用素数 选择适当的e值(通常65537) 实现时防止侧信道攻击 总结 CTF中的RSA非常规题型考察对算法原理的深入理解和创造性思维。掌握这些攻击方法不仅有助于竞赛，也能加深对RSA安全性的理解，在实际应用中避免类似漏洞。