CTF选手必看：RSA算法从数学原理到实战解题技巧（附常见题型解析）

CTF选手必看RSA算法从数学原理到实战解题技巧附常见题型解析1. RSA算法核心数学原理RSA算法的安全性建立在大整数分解难题和欧拉定理之上。理解以下数学概念是解题基础欧拉函数φ(n)对于np×qp、q为质数φ(n)(p-1)(q-1)。例如当p13,q17时φ(221) (13-1)×(17-1) 192模反元素d满足e×d ≡ 1 mod φ(n)的整数d。Python计算示例from gmpy2 import invert d invert(e, phi) # 求e的模逆元加解密过程加密c ≡ m^e mod n解密m ≡ c^d mod n关键点当n超过1024位时暴力分解在现有计算能力下不可行但CTF中往往存在特殊场景漏洞2. 密钥生成与参数关系标准密钥生成流程步骤计算内容示例值1选择大质数p,qp61, q532计算np×q32333计算φ(n)(61-1)×(53-1)31204选择e与φ(n)互质e175计算d≡e⁻¹ mod φ(n)d2753常见错误配置p,q过近导致Fermat分解φ(n)与e不互质d过小导致Wiener攻击3. CTF常见题型与解法3.1 基础参数泄露已知p,q,e求ddef get_d(p, q, e): phi (p-1)*(q-1) return inverse(e, phi)已知p,q,e,c求md get_d(p, q, e) m pow(c, d, p*q)3.2 中国剩余定理优化当已知dpd mod (p-1)和dqd mod (q-1)时def crt_decrypt(p, q, dp, dq, c): q_inv inverse(q, p) m1 pow(c, dp, p) m2 pow(c, dq, q) h (q_inv*(m1 - m2)) % p return m2 h*q3.3 低指数攻击e3小明文攻击for k in range(10**6): m, exact iroot(c k*n, 3) if exact: return m广播攻击相同e不同ndef chinese_remainder(n, c): total 0 N product(n) for ni, ci in zip(n, c): Ni N // ni total ci * Ni * inverse(Ni, ni) return total % N m_e chinese_remainder(n_list, c_list) m, exact iroot(m_e, e)4. 进阶攻击手法4.1 共模攻击当相同m用不同e加密需gcd(e1,e2)1def common_modulus(e1, e2, c1, c2, n): gcd, a, b gcdext(e1, e2) if a 0: c1 inverse(c1, n) a -a if b 0: c2 inverse(c2, n) b -b return pow(c1,a,n) * pow(c2,b,n) % n4.2 维纳攻击当d (1/3)N^(1/4)时的解法def wiener_attack(e, n): # 连分数展开求收敛分数 conv continued_fraction(e/n).convergents() for frac in conv: k, d frac.numerator(), frac.denominator() if k 0: continue phi (e*d -1)//k # 解方程x^2 - (n-phi1)x n 0 b n - phi 1 disc b*b - 4*n if disc 0: p (b isqrt(disc))//2 if n % p 0: return d5. 实战案例解析5.1 已知n,e,dp,c解题def dp_leak(n, e, dp, c): for x in range(1, e): if (dp*e -1) % x 0: p ((dp*e -1) // x) 1 if n % p 0: q n // p d inverse(e, (p-1)*(q-1)) return pow(c, d, n)5.2 多素数RSA解密当np×q×r时phi (p-1)*(q-1)*(r-1) d inverse(e, phi) m pow(c, d, n)6. 工具与优化技巧推荐工具组合RsaCtfTool自动化攻击框架python RsaCtfTool.py --publickey key.pem --uncipherfile cipher.binGMPY2大整数运算加速SageMath高级数论计算性能优化建议使用pow(c,d,n)而非c**d%n预计算常用参数并行化爆破过程7. 防御与出题思路安全参数选择原则p,q至少1024位p,q差值要大e建议用65537d不能过小CTF出题常见陷阱故意泄露dp/dq使用不安全素数设置特殊参数关系非标准编码方式掌握这些核心原理和实战技巧后90%的CTF RSA题型都能迎刃而解。建议在BUUCTF等平台实践RSAROLL、RSA1等经典题目加深理解。