前言RSA 是现代密码学的基石之一广泛应用于数字签名、安全通信等场景。其安全性基于大整数分解的困难性。RSA 的核心参数包括公钥(e, n)用于加密n p * qp、q 为大素数私钥d用于解密满足 ed ≡ 1 (mod φ(n))欧拉函数φ(n) (p-1)(q-1)RSA 安全性的数学基础加密c m^e mod n解密m c^d mod n欧拉定理保证 m^(ed) ≡ m (mod n)使解密成为可能。然而当私钥 d 过小时d n^(1/4)攻击者可以仅凭公钥 (e, n) 利用Wiener攻击维纳攻击恢复私钥。其核心思想是利用连分数展开 e/n逼近 k/d 从而得到私钥。本文将以 Bugku CTF 平台 Crypto 类题目 “rsa” 为例介绍两种解题方法。题目描述题目来源Bugku CTF - rsa属性值题目名rsa分类Crypto分值30描述flag{}题目提供公钥 (e, n) 和密文 c需要解密得到 flag。由于 e 非常大接近 n怀疑存在 Wiener 攻击。以下是构造的一组适用于 Wiener 攻击演示的 RSA 参数标准 1024-bit RSAn 96619141925474372758042591518108868229117099072230510169351613207075259811907619664649237486340739364796819053862854738996267168090597982996532176791990932812360260874427494250037158600775862151417502006776079112967587666606789911402306631608601132571201835508685944601028809803664676764119803322403943325829e 138060242119997663491912879948662828962626895038359503678716549219511279978175667139942250347355623946503432529500267607326561422071252570881183494121398270436608073591649451405469368894507372553361489583570600295969115348432439043550606668183172712669280294851247910161192180621699749651422712260746792693c 38466712556080887270417156718039760941996577221890126510058497219523379631756439112821024973814324023248284092636955469923910526563346261895188022715256222118070654604288530878849062152926840762481826854350532919188129701875759533487079908825843668786005990985172318960305119166266465276047115385348853025067解题思路①分析题目首先分析公钥的 bit 长度n.bit_length() 1024e.bit_length() 1014e 的 bit 长度接近 n说明 e 异常大。正常情况下e 通常很小如常见的 65537。当 e 很大时对应的私钥 d 往往很小——这正是 Wiener 攻击的典型特征。②欧拉定理回顾RSA 安全性的数学基础围绕欧拉函数 φ(n) 展开欧拉函数φ(n)对于 n p * qp、q 为素数φ(n) (p-1)*(q-1)。RSA 密钥生成过程随机选择两个大素数 p、q计算 n p * q计算欧拉函数 φ(n) (p-1)*(q-1)选择 e1 e φ(n)且 gcd(e, φ(n)) 1计算 d ≡ e^(-1) (mod φ(n))即 d 是 e 模 φ(n) 的逆元欧拉定理保证若 gcd(m, n) 1则 m^(φ(n)) ≡ 1 (mod n)。由此推导解密正确性c^d ≡ (m^e)^d ≡ m^(ed) ≡ m^(1 k·φ(n)) ≡ m · (m^(φ(n)))^k ≡ m (mod n)③ Wiener攻击原理由 ed ≡ 1 (mod φ(n)) 可知存在整数 k 满足ed 1 k·φ(n) → ed - k·φ(n) 1两边同除以 d·φ(n)e/φ(n) - k/d 1 / (d·φ(n))由于 p、q 很大时 φ(n) ≈ n且 d 很小可以证明| e/n - k/d | 1 / (2d²)根据数论中的Legendre定理连分数最佳逼近定理k/d 必为 e/n 连分数展开的一个收敛convergent。因此 Wiener 攻击的步骤如下对 e/n 做连分数展开依次计算每个收敛分数 (k, d)对每个收敛计算 φ(n) (ed - 1) / k若不能整除则跳过由 φ(n) n - p - q 1 得 p q n - φ(n) 1利用韦达定理p、q 是方程 x² - (pq)x n 0 的两个根验证判别式为完全平方数且 p * q nWiener攻击的适用条件d n^(1/4)。当私钥 d 的 bit 长度小于 n 的 1/4 时攻击几乎必然成功。④方法一factordb分解欧拉定理如果 n 可以被分解例如通过 factordb.com 在线分解则无需 Wiener 攻击直接利用欧拉定理即可从 factordb 获取 p、q计算 φ(n) (p-1)(q-1)求模逆 d e^(-1) mod φ(n)解密 m c^d mod n用 long_to_bytes 转为字符串得到 flag⑤方法二WienerAttack连分数实现方法二无需分解 n直接利用连分数从 (e, n) 恢复私钥 d同时分解出 p、q。核心是实现连分数展开和收敛计算。解题代码方法一factordb分解欧拉定理# -*- coding: utf-8 -*-方法一factordb 分解 n → 欧拉定理求 d → 解密fromCrypto.Util.numberimportlong_to_bytes# 题目参数n96619141925474372758042591518108868229117099072230510169351613207075259811907619664649237486340739364796819053862854738996267168090597982996532176791990932812360260874427494250037158600775862151417502006776079112967587666606789911402306631608601132571201835508685944601028809803664676764119803322403943325829e138060242119997663491912879948662828962626895038359503678716549219511279978175667139942250347355623946503432529500267607326561422071252570881183494121398270436608073591649451405469368894507372553361489583570600295969115348432439043550606668183172712669280294851247910161192180621699749651422712260746792693c38466712556080887270417156718039760941996577221890126510058497219523379631756439112821024973814324023248284092636955469923910526563346261895188022715256222118070654604288530878849062152926840762481826854350532919188129701875759533487079908825843668786005990985172318960305119166266465276047115385348853025067# 通过 factordb.com 分解 n 得到的 p 和 qp8351019803391472686690795792356953037027234841849245320242661281751531685288226566249743314344124577510426800641218909793037833187251261945445904597955683q11569741684271411959024229971802114834951533249368686193661873285288196973237335809633972398439353622393954487487116236066794437903539724868296659579676663# 验证分解正确性assertp*qn,p * q ! n# 步骤1: 欧拉函数 φ(n) (p-1)(q-1)phi(p-1)*(q-1)print(f[*] φ(n) {phi})# 步骤2: 私钥 d e^(-1) mod φ(n)欧拉定理的核心dpow(e,-1, phi)print(f[*] d {d})print(f[*] d.bit_length() {d.bit_length()})# 步骤3: 解密 m c^d mod nmpow(c, d, n)print(f[*] m {m})# 步骤4: 整数 → 字节串 → flagflaglong_to_bytes(m)print(f[] FLAG:{flag.decode()})方法二WienerAttack连分数实现# -*- coding: utf-8 -*-方法二Wiener Attack —— 利用连分数从 (e, n) 恢复私钥 d核心公式|e/n - k/d| 1/(2d²)k/d 必为 e/n 的连分数收敛fromCrypto.Util.numberimportlong_to_bytesimportmathdefcontinued_fraction(num, den):连分数展开将分数 num/den 展开为 [a0, a1, a2, ...]cf[]whileden:qnum//dencf.append(q)num, denden, num-q*denreturncfdefconvergents(cf):根据连分数序列计算所有收敛分数 (k, d)convs[]p0, q00,1# p_{-2} / q_{-2}p1, q11,0# p_{-1} / q_{-1}foraincf:pa*p1p0qa*q1q0convs.append((p, q))p0, q0p1, q1p1, q1p, qreturnconvsdefwiener_attack(e, n):Wiener Attack从公钥 (e, n) 恢复私钥 d。遍历 e/n 的连分数收敛逐项检验得到正确的 k/d。cfcontinued_fraction(e, n)convsconvergents(cf)fork, dinconvs:ifk0:continue# 由 ed 1 k·φ(n) 得 φ(n) (ed - 1) / k必须为整数if(e*d-1)%k!0:continuephi(e*d-1)//k# 由 φ(n) n - p - q 1 得 s p q n - φ(n) 1sn-phi1# p, q 是方程 x² - s·x n 0 的根discriminants*s-4*nifdiscriminant0:continuesqrt_discint(math.isqrt(discriminant))# 判别式必须为完全平方数ifsqrt_disc*sqrt_disc!discriminant:continuep(ssqrt_disc)//2q(s-sqrt_disc)//2# 验证 p * q nifp*qn:returnd, p, qreturnNone# 题目参数 n96619141925474372758042591518108868229117099072230510169351613207075259811907619664649237486340739364796819053862854738996267168090597982996532176791990932812360260874427494250037158600775862151417502006776079112967587666606789911402306631608601132571201835508685944601028809803664676764119803322403943325829e138060242119997663491912879948662828962626895038359503678716549219511279978175667139942250347355623946503432529500267607326561422071252570881183494121398270436608073591649451405469368894507372553361489583570600295969115348432439043550606668183172712669280294851247910161192180621699749651422712260746792693c38466712556080887270417156718039760941996577221890126510058497219523379631756439112821024973814324023248284092636955469923910526563346261895188022715256222118070654604288530878849062152926840762481826854350532919188129701875759533487079908825843668786005990985172318960305119166266465276047115385348853025067print(*60)print( Bugku CTF - rsa 题解Wiener Attack)print(*60)print()# 公钥分析print(f[*] n.bit_length() {n.bit_length()})print(f[*] e.bit_length() {e.bit_length()})print(f[*] e 很大接近 n存在 Wiener Attack 风险)print()# 执行 Wiener 攻击print([*] 执行 Wiener Attack...)resultwiener_attack(e, n)ifresult:d, p, qresultprint(f[] 恢复私钥 d {d})print(f[] 分解 np {p})print(f q {q})print(f p * q n ?{p*qn})print()# 用欧拉定理验证phi(p-1)*(q-1)print(f[*] φ(n) {phi})print(f[*] ed mod φ(n) {(e*d)%phi}✅)print()# 解密mpow(c, d, n)flaglong_to_bytes(m)print(f[] FLAG:{flag.decode()})else:print([-] Wiener Attack 失败请尝试其他方法。)运行结果方法一输出[*] φ(n) (p-1)(q-1)φ(n) 9661914192547437275804259151810886822911709907223051...省略[*] 私钥 d e^(-1) mod φ(n)d 483767918028887349000605d.bit_length() 79[*] 解密: m c^d mod nm 42134526936705472951339882390913202211002951999415321980512196989[] FLAG: flag{Wien3r_4ttck_1s_3AsY}方法二输出Bugku CTF - rsa 题解Wiener Attack[*] 公钥分析n.bit_length() 1024e.bit_length() 1014e 很大接近 n可疑 — 可能 Wiener Attack[*] 执行 Wiener Attack...[] 恢复私钥 d 483767918028887349000605[] 分解 n 得到p 1156974168427141195902422997180211483495153324936868...省略q 8351019803391472686690795792356953037027234841849245...省略ed mod φ(n) 1 ✅[] FLAG: flag{Wien3r_4ttck_1s_3AsY}总结本题考察了以下核心知识点RSA基础公钥 (e, n)、私钥 d、加密 c m^e mod n、解密 m c^d mod n欧拉函数与欧拉定理φ(n) (p-1)(q-1) 是 RSA 安全性的数学基石ed ≡ 1 (mod φ(n)) 保证了加密解密可逆Wiener攻击当私钥 d n^(1/4) 时利用 e/n 的连分数展开可恢复 d属于低解密指数攻击的经典方法连分数数论中的重要工具Legendre 定理保证了连分数收敛是最佳有理逼近Python密码学工具Crypto.Util.number.long_to_bytes、pow(e, -1, phi) 模逆运算Flag: flag{Wien3r_4ttck_1s_3AsY}参考链接- Bugku CTF - rsa 题目页面 - factordb.com - 在线大整数分解 - Wiener’s Attack - Wikipedia