RSA算法在CTF竞赛中的实战应用与解题技巧

1. RSA算法基础回顾RSA算法作为非对称加密的黄金标准其安全性建立在大整数分解难题之上。我们先快速过一遍核心公式密钥生成选择两个大质数p、q计算np*q欧拉函数φ(n)(p-1)(q-1)选择e满足1eφ(n)且gcd(e,φ(n))1计算d≡e⁻¹ mod φ(n)加密/解密加密c ≡ mᵉ mod n解密m ≡ cᵈ mod n在CTF中我们常遇到的是给出部分参数求解其他参数的情况。比如已知p、q、e求d可以直接用Python的gmpy2库计算import gmpy2 d gmpy2.invert(e, (p-1)*(q-1))2. CTF常见题型与实战技巧2.1 基础参数题型已知p、q、e、c求m 这是最基础的题型解题流程如下计算φ(n)(p-1)(q-1)求d ≡ e⁻¹ mod φ(n)解密m ≡ cᵈ mod n实战脚本示例from Crypto.Util.number import long_to_bytes p 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483 q 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407 e 65537 c 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034 phi (p-1)*(q-1) d pow(e, -1, phi) m pow(c, d, p*q) print(long_to_bytes(m))2.2 中国剩余定理应用当给出p、q、dp、dq、c时dp ≡ d mod (p-1)dq ≡ d mod (q-1)可以使用CRT加速解密def rsa_crt(p, q, dp, dq, c): qinv pow(q, -1, p) m1 pow(c, dp, p) m2 pow(c, dq, q) h (qinv * (m1 - m2)) % p return m2 h * q2.3 低加密指数攻击场景当e3且明文m较小时可能满足mᵉ n此时直接开方即可from gmpy2 import iroot c 0x9e84763bdbe246fad0a9cd52fda6233e6128a6210efaf3e6dea4fe272f78ad1f8f5cc7022f62f4f542341128e42d6fd10e67c5f96edbd243917c0151289f7228e44019b8c65a541d7306b398465e26b69cab36cc61e4ac094832b4299bbaf4630b722a0fb4f1997053be97e926f94afb55a0bb6ef00ab694e2f595d9eb8ca96c49f5cbbe194529f68a1aaf6f5151484b471285ba8fc8cd30b55612f35a74dc68e255c363579a80d27ce5090873ac719ba59f2492c91fd28bcce26b6a02bae005cbbd2a4cfe5b93442be8664d2313d412e7e09f545c64b7b74bbc408b6e574d0d300135cba8d6c1d73737d59baca9992ede644d856eb4cfcda562a75743e4b491 m iroot(c, 3)[0] print(bytes.fromhex(hex(m)[2:]))3. 进阶攻击手法3.1 共模攻击条件相同的n不同的e且gcd(e1,e2)1from math import gcd def common_modulus(e1, e2, c1, c2, n): g, a, b gmpy2.gcdext(e1, e2) if a 0: c1 gmpy2.invert(c1, n) a -a if b 0: c2 gmpy2.invert(c2, n) b -b return pow(c1,a,n) * pow(c2,b,n) % n3.2 Wiener攻击针对d较小的情况d 1/3 * N⁰·²⁵使用连分数展开def wiener_attack(e, n): # 连分数展开 def cf_expansion(e, n): cf [] while n: q e // n cf.append(q) e, n n, e - q * n return cf # 渐进分数计算 def convergents(cf): convs [] for i in range(len(cf)): num, den 1, 0 for j in range(i, -1, -1): num, den cf[j]*num den, num convs.append((num, den)) return convs cf cf_expansion(e, n) convs convergents(cf) for k, d in convs: if k 0: continue phi (e*d - 1) // k b n - phi 1 delta b*b - 4*n if delta 0: p (b gmpy2.isqrt(delta)) // 2 if n % p 0: return d return None4. 实战工具链推荐分解nfactordb.com在线数据库yafu本地分解工具msieve适合大数分解计算工具Python的gmpy2库SageMath内置各种数论函数综合工具RsaCtfTool自动化攻击框架python RsaCtfTool.py --publickey key.pem --uncipherfile ciphertext编码转换CyberChef在线编解码工具Python的libnum库5. 典型CTF题解析5.1 已知dp泄露给出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 phi (p-1)*(q-1) d pow(e, -1, phi) return pow(c, d, n)5.2 多素数RSA当npqr时φ(n)(p-1)(q-1)(r-1)解密流程相同但需要分解出三个因子n 544187306850902797629107353619267427694837163600853983242783 # 通过factordb分解得到 p,q,r 67724172605733871, 11571390939636959887, 694415063702720454699679 phi (p-1)*(q-1)*(r-1) d pow(e, -1, phi)6. 防御与出题思路了解攻击手段后出题时应注意使用足够大的密钥至少2048位避免使用小e如3确保随机数生成质量不要泄露任何额外信息如dp/dq对于CTF选手建议收集整理常见攻击脚本熟悉Python的gmpy2/libnum库掌握基本的数论知识善用在线分解工具最后提醒所有示例中的数字均为演示用实际CTF中参数会大得多。遇到实际问题时耐心分析参数特点是解题关键。