CTF_RSA_Wiener攻击_Writeup

CTF Crypto题解简单RSA Wiener’s Attack 攻击 题目信息简单RSA已知N 7414571144918957894009130075076623468104787088880786848384304202195894442483334829319171712905975283178498354592957730348231637645803408251658776870887613e 5981029313933894258581971566428136415533632516605454590943812288528436693719803568404832909242493538766098852203771662822547849096234923807130087141104633c 2841604519518485432740943719011131647295050370262352921197542804113942147532827415802833252422134652832887894874295475005522089375327572415995370520766571. 解题思路 为什么选择 Wiener 攻击这是一道经典的 RSA 密码学 CTF 题。RSA 加密的安全性建立在「大整数分解难题」之上但在某些特定条件下存在快捷的侧信道攻击途径。选择 Wiener 攻击的理由e 值异常巨大观察到公钥指数e的数值与N几乎相当均为约 310 位十进制数这在标准 RSA 中是极不寻常的正常 RSA 的 e通常选取为 655372¹⁶1或 3、17 等小奇数作为公钥的一部分理应很小e 过大意味着 d 可能过小根据 RSA 的数学性质e × d ≡ 1 (mod φ(n))如果e非常大而φ(n)相对固定那么对应的私钥d就会很小 Wiener 攻击的核心条件Wiener’s Attack 适用于以下条件d (1/3) × N^(1/4)即私钥指数d相对于模数N足够小时攻击才能成功。换句话说当 d 小于 N 的四次方根的三分之一时连分数方法能够有效恢复私钥。2. 背景知识连分数什么是连分数任何一个有理数 e/N 都可以唯一表示为连分数形式e/N a₀ 1/(a₁ 1/(a₂ 1/(...)))其中 a₀, a₁, a₂, … 均为非负整数。例如 355/113 的连分数展开为[3; 7, 16]表示355/113 3 1/(7 1/16)连分数的收敛分数连分数的部分和构成一系列有理数逼近 e/N称为收敛分数Convergents记作hᵢ/kᵢ ≈ e/N关键发现这些收敛分数的分母 kᵢ 正好对应 RSA 私钥 d 的可能候选值。3. Wiener’s Attack 原理数学推导RSA 的基本等式e × d ≡ 1 (mod φ(n))即存在整数 k 使得e × d 1 k × φ(n)两边同时除以 d × φ(n)e/φ(n) - k/d 1/(d × φ(n))由于 k ≈ e×d/φ(n) ≈ e/d而 φ(n) ≈ n可得| e/n - k/d | 1/d²这意味着 k/d 是 e/n 的一个极佳有理逼近而 e/n 的所有最佳有理逼近恰好由其连分数展开的收敛分数给出。攻击流程计算 e/N 的连分数展开枚举所有收敛分数kᵢ/dᵢ其中 dᵢ 作为候选私钥验证条件检查 (e × dᵢ - 1) mod kᵢ 0恢复 φ(n)φ(n) (e × dᵢ - 1) / kᵢ分解 N利用 p q n - φ(n) 1 和 p × q n 解二次方程计算私钥 d由收敛分数直接获得4. 代码实现解析核心函数continued_fraction(x, y) — 连分数展开defcontinued_fraction(x,y):cf[]whiley:cf.append(x//y)# 记录整数部分x,yy,x%y# 辗转相除returncf通过辗转相除法提取 x/y 的连分数系数。convergents(cf) — 计算收敛分数defconvergents(cf):convs[]foriinrange(len(cf)):ifi0:h,kcf[0],1# h0/k0 a0/1elifi1:h,kcf[1]*cf[0]1,cf[1]# h1/k1 (a1*a01)/a1else:# 递推公式: hi ai*hi-1 hi-2, ki ai*ki-1 ki-2hcf[i]*convs[i-1][0]convs[i-2][0]kcf[i]*convs[i-1][1]convs[i-2][1]convs.append((h,k))returnconvs根据递推公式从连分数系数计算所有收敛分数。主攻击逻辑# 遍历所有收敛分数fork,dinconvs:# 检查 (e*d - 1) 是否能被 k 整除if(e*d-1)%k!0:continue# 计算 φ(n)phi(e*d-1)//k# 根据 pq 和 p*q 构造二次方程# x² - (pq)x pq 0bn-phi1# 这里 b p qdeltab*b-4*n# 判别式 Δ (pq)² - 4pq (p-q)²# 验证 Δ 是否为完全平方数sqrt_deltaisqrt(delta)ifsqrt_delta*sqrt_delta!delta:continue# 求根公式p(bsqrt_delta)//2q(b-sqrt_delta)//2# 验证 p, q 是否合法ifp0andq0andp*qn:returnp,q,d关键验证点(e × d - 1) mod k 0 确保 k 确实是公式中的那个 kΔ 必须为完全平方数因为 p 和 q 均为整数最终验证 p × q n 确保分解正确5. 解题结果✅ 攻击成功项目值私钥 d65537素数 p100450526476578029826767001337536289347807647561108913398620116543514585634083素数 q73813163603953908696863884310584185678105154396583546085637801292303843786911 注意这里 d 65537 2¹⁶1这正是 RSA 标准公钥指数说明本题中 e 虽然看起来很大但实际上 e × d ≈ N攻击成功找到了标准私钥。 解密得到明文明文十进制: 11859814988219572398902824910735964098597031196539320808215595041976292804539261转换后发现为十六进制编码的字符串。 Flagflag{0f3j003f03j0f3f030f3-f3f3f3}6. 完整解题代码frommathimportisqrtdefwiener_attack(e,n):Wieners attack: 针对 e 较大、d 较小的 RSA 进行攻击defcontinued_fraction(x,y):计算 x/y 的连分数展开cf[]whiley:cf.append(x//y)x,yy,x%yreturncfdefconvergents(cf):从连分数系数计算所有收敛分数convs[]foriinrange(len(cf)):ifi0:h,kcf[0],1elifi1:h,kcf[1]*cf[0]1,cf[1]else:hcf[i]*convs[i-1][0]convs[i-2][0]kcf[i]*convs[i-1][1]convs[i-2][1]convs.append((h,k))returnconvs# 展开 e/n 的连分数cfcontinued_fraction(e,n)convsconvergents(cf)# 枚举所有收敛分数尝试恢复私钥fork,dinconvs:ifk0:continueif(e*d-1)%k!0:continuephi(e*d-1)//k bn-phi1deltab*b-4*nifdelta0:continuesqrt_deltaisqrt(delta)ifsqrt_delta*sqrt_delta!delta:continuep(bsqrt_delta)//2q(b-sqrt_delta)//2ifp0andq0andp*qn:returnp,q,dreturnNone,None,None# RSA 参数N7414571144918957894009130075076623468104787088880786848384304202195894442483334829319171712905975283178498354592957730348231637645803408251658776870887613e5981029313933894258581971566428136415533632516605454590943812288528436693719803568404832909242493538766098852203771662822547849096234923807130087141104633c284160451951848543274094371901113164729505037026235292119754280411394214753282741580283325242213465283288789487429547500552208937532757241599537052076657# 执行攻击p,q,dwiener_attack(e,N)ifdisnotNone:print(fd {d})print(fp {p})print(fq {q})# 解密mpow(c,d,N)m_hexhex(m)[2:]iflen(m_hex)%2!0:m_hex0m_hex flagbytes.fromhex(m_hex).decode(utf-8)print(fFlag:{flag})else:print(Wieners attack 失败)7. 经验总结 学到的知识点RSA 中 e 过大的危险性虽然 e 通常选择为 65537但如果实现不当或为了特殊用途而选择过大的 e会导致 Wiener 攻击可行连分数在密码学中的应用连分数展开能够高效地找到有理数的最佳有理逼近Wiener 攻击的局限性要求 d (1/3) × N^(1/4)当 d 较大时攻击会失败️ 防御建议始终使用标准的公钥指数如 65537确保私钥 d 足够大使用足够的密钥长度至少 2048 bits CTF 常用工具工具用途Python gmpy2高精度计算RsaCtfTool全自动 RSA 攻击工具factordb.com在线大整数分解