1. 项目概述当RSA的私钥“太短”时会发生什么如果你玩过CTFCapture The Flag中的密码学题目或者对RSA公钥密码体制有一定了解那你肯定知道一个安全的RSA系统其私钥指数d必须足够大。教科书和无数安全文章都会告诫我们千万不要使用小私钥d。但这句话背后具体意味着什么攻击者是如何利用一个“小”的d来攻破整个加密体系的更重要的是在实际的CTF赛题中我们如何识别这种漏洞并亲手实现攻击来拿到Flag这就是“RSA低解密指数攻击”Wiener‘s Attack要回答的核心问题。它不是一种对RSA算法本身的理论否定而是针对密钥生成过程中一个特定且危险的错误所发起的精准打击。简单来说当公钥指数e很大比如接近模数N而私钥指数d相对很小时攻击者无需分解大整数N仅凭公开的(N, e)就可以在多项式时间内计算出私钥d从而解密任何密文。听起来很神奇对吧这背后的数学原理源于连分数理论。攻击者将e/N作为一个有理数计算其连分数展开那些渐进分数中就极有可能隐藏着k/d其中k是某个未知整数。一旦猜中私钥d便唾手可得。在CTF实战中这通常表现为题目给了你一个巨大的e比如e和N位数相同而N本身又无法被常规工具分解。这时你的第一反应就应该转向Wiener攻击或其更强大的变种如Boneh-Durfee攻击。本篇文章我将从一个CTF老兵的角度带你从连分数的数学原理开始一步步拆解Wiener攻击的每一个环节。我们不仅会弄懂“为什么能攻击”更会聚焦于“如何实施攻击”包括手算理解、Python脚本实现、SageMath的“作弊”使用以及在实际解题中如何快速判断攻击场景、处理边界情况和调试脚本。无论你是刚接触密码学的学生还是想在CTF密码学领域精进的赛手这篇从理论到实战的完整指南都将为你提供可直接复现的“武器库”。2. 攻击原理深度拆解从连分数到私钥恢复要理解低解密指数攻击我们不能只停留在“调用脚本”的层面。知其然更要知其所以然这能帮助你在脚本出错时进行调试甚至根据题目变形修改攻击条件。整个攻击的基石是数论中的连分数和Legendre定理。2.1 核心数学关系推导首先我们回顾RSA密钥生成的核心等式。私钥d是公钥e关于欧拉函数φ(N) (p-1)(q-1)的模逆元即e * d ≡ 1 (mod φ(N))这意味着存在一个整数k使得e * d k * φ(N) 1将等式改写一下e * d - k * φ(N) 1现在我们引入一个关键的近似。对于大素数p和qN p*q而φ(N) (p-1)(q-1) N - (pq) 1。由于p和q都很大(pq)相对于N来说很小大约在√N量级。因此我们可以近似认为φ(N) ≈ N。将这个近似代入上面的等式e * d - k * N ≈ 1两边同时除以d * Ne/N - k/d ≈ 1/(d*N)由于1/(d*N)是一个非常小的数这表明e/N和k/d这两个分数非常接近。这就是攻击的突破口公开的e/N是未知分数k/d的一个极好的有理近似。2.2 连分数与渐进分数登场数论告诉我们要找到一个有理数来近似另一个实数连分数展开是最佳工具之一。对于分数e/N我们可以计算它的连分数展开并得到一系列渐进分数。例如对于实数x其连分数展开为[a0; a1, a2, a3, ...]那么其渐进分数p_n / q_n会逐步逼近x。一个关键定理是如果一个分数p/q满足|x - p/q| 1/(2q²)那么p/q必定是x的某个渐进分数。回到我们的场景设x e/N。我们有| e/N - k/d | | (e*d - k*N) / (N*d) | | 1 - k*φ(N) | / (N*d) ≈ 1/(N*d)因为e*d - k*φ(N)1为了使k/d是e/N的渐进分数我们需要满足1/(N*d) 1/(2*d²)即d (1/2) * √N。这就是经典的Wiener攻击定理如果私钥指数d (1/3) * N^(1/4)一个更宽松的充分条件源于更精确的推导那么k/d将出现在e/N的连分数展开的渐进分数中。注意这里(1/3) * N^(1/4)是一个经验性的强约束。在实际中即使d略大于此值攻击也可能成功这取决于p和q的具体差值。但这是判断题目是否适用Wiener攻击的首要标准。2.3 从渐进分数到私钥验证攻击流程因此变得清晰计算e/N的连分数展开得到一系列渐进分数k_i / d_i。对于每一个候选的(k_i, d_i)我们假设d_i就是私钥dk_i就是对应的k。根据等式e*d - 1 k*φ(N)我们可以计算φ(N) (e*d_i - 1) / k_i。如果k_i能整除(e*d_i - 1)那么我们就得到了一个候选的φ(N)。有了N和φ(N)我们可以解一元二次方程x² - (N - φ(N) 1)*x N 0。这个方程的解就是p和q。如果解出的p和q是整数并且满足p*q N那么恭喜你你找到了正确的d_i、p和q。私钥恢复成功。整个攻击最精妙的地方在于它完全不需要暴力尝试计算连分数和验证方程解的过程非常高效即使对于2048位的N也能在瞬间完成。3. 实战环境搭建与工具选型在真正动手解题之前准备好顺手的工具至关重要。针对RSA低解密指数攻击我们主要有三种武器纯Python实现、SageMath内置函数、以及现成的攻击脚本库。我将逐一分析其优劣和适用场景。3.1 环境准备Python与核心库对于大多数CTF环境或个人学习Python是最灵活的选择。你需要以下库gmpy2提供高精度整数运算和数论函数如invert,gcd,is_prime速度远超Python原生整数。这是RSA相关计算的基石。sympy或libnum用于解一元二次方程或者进行一些符号运算。libnum是一个CTF密码学常用库非常轻量。pycryptodome有时用于最后的解密验证但非必须。安装命令非常简单pip install gmpy2 sympy libnum如果你的环境无法安装gmpy2比如在一些在线Python环境可以尝试使用pow函数配合Python原生整数但性能会下降且无法处理极大的数。强烈建议在本地或可控环境配置好gmpy2。3.2 神器SageMathSageMath是一个集成了众多数学软件如Maxima, GAP, PARI/GP的庞然大物对于数论和密码学研究来说是“终极武器”。它的优势在于内置攻击实现对于Wiener攻击SageMath常常一行命令就能解决d wiener_attack(e, N)。这依赖于其强大的数论库。交互式环境方便你一步步探索数据测试想法。更强大的Coppersmith方法对于更复杂的场景如已知部分私钥Sage是首选。缺点是体积庞大安装复杂。对于比赛中的快速解题如果环境提供SageMath如很多在线CTF平台请毫不犹豫地使用它。你可以通过sage -python来在Sage环境中运行Python脚本或者直接在Sage Notebook中操作。3.3 现成脚本与自主实现网络上有很多优秀的RSA攻击脚本合集比如开头提到的yifeng-lee/RSA-In-CTF。在实战中我建议理解并拥有自己的基础版脚本自己动手实现一个Wiener攻击脚本代码在下节给出这能让你深刻理解每一步在做什么遇到变种题目时能灵活修改。收集强大的工具库将RSA-In-CTF这类项目克隆到本地作为“武器库”备用。里面的脚本通常经过优化能处理更多边界情况。区分使用场景在时间紧迫的比赛中直接调用成熟脚本在学习和复盘时使用自己的脚本并添加详细注释。实操心得我习惯在本地建立一个ctf_tools文件夹里面按密码学、逆向、Web等分类存放各种脚本和工具。对于RSA我会有一个rsa_attacks.py的文件里面用函数封装好各种攻击方法包括我们接下来要实现的wiener_attack。这样遇到题目时我只需要导入函数传入N, e, c即可极大提升效率。4. 攻击脚本实现与逐行解析现在让我们抛开“黑盒”亲手打造一个Wiener攻击脚本。我将提供一个功能完整、注释详细的Python实现并逐行解释其逻辑。4.1 连分数展开与渐进分数计算这是攻击的第一步。我们需要一个函数将分数e/N展开为连分数序列[a0, a1, a2, ...]并由此计算出所有的渐进分数(numerator_k, denominator_d)。import gmpy2 from math import isqrt, gcd import sympy def continued_fraction(e, n): 计算 e/n 的连分数展开序列。 返回一个列表代表连分数 [a0; a1, a2, ...] cf [] while n: q e // n # 商即连分数的一项 cf.append(q) e, n n, e - q * n # 更新余数进行下一步欧几里得算法 return cf def convergents(cf): 根据连分数展开序列 cf生成所有的渐进分数 (k, d)。 使用递推公式 h_{-2}0, h_{-1}1 k_{-2}1, k_{-1}0 h_n a_n * h_{n-1} h_{n-2} k_n a_n * k_{n-1} k_{n-2} 返回的分数为 h_n / k_n hh, kk [0, 1], [1, 0] # 初始化递推序列 for q in cf: hn q * hh[-1] hh[-2] kn q * kk[-1] kk[-2] hh.append(hn) kk.append(kn) yield hn, kn # 每次生成一个渐进分数 (k, d) # 注意这里生成的序列包含初始项通常我们从索引2开始使用。关键点解析continued_fraction函数本质上是欧几里得算法辗转相除的记录过程。每次的商q就是连分数的一项。convergents函数使用了标准的递推关系来计算渐进分数的分子(hh, 对应我们理论中的k)和分母(kk, 对应d)。这里用yield生成器是为了节省内存因为连分数可能很长但我们只需要遍历一次。4.2 主攻击函数验证与私钥恢复有了渐进分数我们就可以遍历它们尝试恢复私钥。def wiener_attack(e, n): 执行Wiener攻击尝试从 (e, n) 中恢复私钥 d。 返回 (d, p, q) 如果成功否则返回 None。 cf continued_fraction(e, n) convergents_list list(convergents(cf)) # 遍历所有渐进分数跳过前两个初始值 for k, d in convergents_list[2:]: # 条件1: d 必须是正数且不能是1平凡解 if d 0: continue # 条件2: 根据理论k 和 d 应该互质且 (e*d - 1) 能被 k 整除 if gcd(k, d) ! 1: continue if (e * d - 1) % k ! 0: continue # 计算候选的 phi(N) phi (e * d - 1) // k # 根据 N 和 phi(N) 求解 p 和 q # 由 phi (p-1)(q-1) N - (pq) 1得 sum pq N - phi 1 # 由 p*q N, pq sum可构造方程 x^2 - sum*x N 0 sum_pq n - phi 1 # 计算判别式 delta sum^2 - 4*N delta sum_pq * sum_pq - 4 * n if delta 0: continue sqrt_delta, is_perfect gmpy2.isqrt_rem(delta) # 使用gmpy2的高精度开方 if not is_perfect 0: # 如果delta不是完全平方数则p,q不是整数 continue # 求解 p 和 q p (sum_pq sqrt_delta) // 2 q (sum_pq - sqrt_delta) // 2 # 最终验证p和q是否为正整数且乘积等于N if p 0 and q 0 and p * q n: # 可选验证p和q是否为素数用gmpy2.is_prime但可能较慢 # if gmpy2.is_prime(p) and gmpy2.is_prime(q): return int(d), int(p), int(q) return None逐行解析与避坑指南遍历起点convergents_list[2:]。这是因为递推生成的前两项(0,1)和(1,0)是初始值没有实际意义跳过它们可以提高效率。关键验证步骤(e * d - 1) % k ! 0。这是核心过滤条件。如果k不能整除(e*d - 1)那么计算出的phi就不是整数直接跳过。判别式检查delta sum_pq * sum_pq - 4 * n。这里必须使用高精度整数运算否则可能溢出。我们使用gmpy2.isqrt_rem来同时计算平方根和余数通过余数是否为0来判断delta是否为完全平方数。这是比int(delta**0.5)更精确和高效的方法。最终验证p * q n。这是必不可少的步骤。因为即使前面所有条件都满足也可能出现数学上成立但p和q并非真正因子的情况尽管概率极低。这一步确保了结果的正确性。素数验证gmpy2.is_prime(p)。这是一个可选的强化验证但对于非常大的数如2048位素性检测可能非常耗时。在CTF解题中只要p*qN且p和q是大于1的整数基本可以确定成功。可以根据题目时间要求决定是否开启。4.3 完整的解题脚本示例假设我们从一个CTF题目中获取了以下数据模数N、巨大的公钥指数e、以及密文c。我们的完整攻击流程如下import gmpy2 from Crypto.Util.number import long_to_bytes # 题目给出的数据 N 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929 e 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929 c 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L # 注意以上N, e, c是示例实际值可能不同。这里e和N看起来一样大是典型的Wiener攻击场景。 print([*] 正在尝试Wiener攻击...) result wiener_attack(e, N) if result: d, p, q result print(f[] 攻击成功) print(f d {hex(d)}) print(f p {hex(p)}) print(f q {hex(q)}) # 使用恢复的私钥解密 m pow(c, d, N) try: flag long_to_bytes(m).decode(utf-8) print(f[] 解密后的明文 (flag): {flag}) except: print(f[] 解密后的数字 (可能需其他处理): {hex(m)}) else: print([-] Wiener攻击失败。可能d不满足攻击条件或需要尝试Boneh-Durfee等更强攻击。)这个脚本整合了攻击和解密的全过程。运行后如果攻击成功你将直接看到私钥d、因子p和q以及解密后的Flag。5. CTF实战案例分析与变种识别掌握了原理和脚本我们来看看如何在真实的CTF比赛中应用。Wiener攻击的题目通常有比较明显的特征但出题人也会设置一些陷阱和变种。5.1 经典题型特征识别当你拿到一个RSA题目首先应该快速检查以下几点判断是否可能适用Wiener攻击公钥指数e异常大这是最明显的标志。通常e取65537。如果题目给出的e与模数N的位数相同比如都是2048位或者e的大小与N处于同一数量级立即将Wiener攻击列入候选。模数N无法分解尝试用yafu或factordb.com分解N如果短时间内无法分解p和q都是安全的大素数则更倾向于侧信道攻击如Wiener。题目描述暗示有时题目名或描述会包含“Wiener”、“small d”、“big e”等关键词。私钥格式如果题目除了公钥(N, e)还给出了私钥文件但无法直接使用或者给出了dp、dq等参数需要结合其他信息判断。实战检查清单[ ]e的位数是否接近或等于N的位数[ ] 计算d的理论上限(1/3)*N^(1/4)估算其十进制位数。如果d可能很小例如对于1024位Nd大约在256位以下攻击希望很大。[ ] 快速运行一遍你的wiener_attack脚本看是否能秒出结果。5.2 一个简化版实战模拟假设题目给出N 905101396550406500611146680205302889792711232352292205803111222229123657123 e 65537 c 123456789... (密文)这个e是正常的65537显然不是Wiener攻击的目标。但如果题目给出N 同上 e 905101396550406500611146680205302889792711232352292205803111222229123657120 c 123456789...你会发现e只比N小一点点这非常可疑。计算(1/3)*N^(1/4)大约为(1/3)* (2^256)^(1/4) ≈ 2^64这是一个很小的数。此时运行我们的脚本很可能瞬间得到d。5.3 变种与进阶当Wiener攻击失效时Wiener攻击的条件d (1/3)*N^(1/4)有时过于严格。在实际中d可能略大于这个界限导致经典Wiener攻击失败。此时我们需要更强大的工具Boneh-Durfee攻击这是Wiener攻击的加强版将d的界提升到了d N^(0.292)。其核心思想也是基于连分数和格基规约LLL算法但数学上更复杂。在SageMath中通常有内置函数或简单脚本可以实现。如果你的Wiener脚本失败了下一步就是尝试Boneh-Durfee。# 在SageMath中可能只需要这样取决于环境 # d attack(N, e) # 使用某个Boneh-Durfee攻击的实现对于Python你可以寻找实现了LLL算法的库如fpylll但配置较为复杂。在CTF中更常见的做法是直接将N和e粘贴到在线的Sage计算环境或本地Sage中运行攻击脚本。已知部分私钥攻击如果题目给出了d的低位LSB或者dp、dq可能适用Coppersmith攻击。这需要不同的脚本。e和d都很大如果e和d都很大那可能根本不是低解密指数漏洞需要重新审视题目。避坑技巧在比赛中时间就是生命。我建议建立一个决策流看e的大小。如果e巨大先跑一遍Wiener脚本10秒内。如果不成功立即尝试用SageMath进行Boneh-Durfee攻击。如果SageMath也不行或者没有环境再回头仔细分析其他可能性如共模攻击、因子碰撞等。6. 常见问题排查与调试心得即使理论清晰脚本在手实战中依然会遇到各种问题。下面是我在多次CTF比赛中总结出的常见问题及解决方案。6.1 攻击脚本运行无结果症状脚本运行后遍历了所有渐进分数最终返回None。可能原因与排查步骤d不满足攻击条件这是最可能的原因。重新计算(1/3)*N^(1/4)的位数确认d是否真的“小”。有时e虽然大但d可能并不小。数据格式错误确保你从题目中提取的N,e,c是完整的整数。常见错误包括漏掉了十六进制前缀0x或末尾的L在Python 2中常见。将数字以字符串形式读入没有转换为int。复制粘贴时引入了不可见字符如空格、换行。调试方法打印N.bit_length()和e.bit_length()检查它们的位数是否正常如1024, 2048, 4096。脚本逻辑错误在wiener_attack函数中检查判别式delta的计算和开方是否正确。确保使用的是高精度整数Python的int或gmpy2.mpz。e和N不互质虽然RSA要求gcd(e, φ(N)) 1但理论上gcd(e, N)也可能不为1尽管极其罕见。可以先检查gmpy2.gcd(e, N)是否为1。6.2 攻击成功但解密出乱码症状脚本输出了d,p,q并且p*q N验证通过但解密出的m转成字节后不是可读的flag。可能原因与解决方案解密结果不是文本Flag可能不是直接的ASCII或UTF-8文本。它可能是一个数字需要进一步处理如作为下一个RSA的明文。一段Base64编码的数据。一个文件的十六进制表示。处理方法不要直接decode(‘utf-8’)。先输出hex(m)或long_to_bytes(m)的原始字节用file命令或binwalk分析或者尝试多种解码方式base64, hexlify等。填充问题原始的RSA加密可能使用了PKCS#1 v1.5或OAEP填充。直接解密得到的是带填充的数据需要去除填充才能得到明文。在CTF中纯教科书式RSA无填充更常见但需注意。密文c错误确认你使用的密文c是正确的。有时题目会给多个密文或者需要从网络流量、文件格式中提取。6.3 使用SageMath时的注意事项函数名差异不同版本的SageMath或不同来源的脚本攻击函数名可能不同如wiener_attack,attack,hastads_attack等。需要查看脚本的具体实现或文档。环境依赖确保SageMath环境已正确安装并且包含了必要的数论包。在线Sage环境如Cocalc有时会有计算限制。输入格式Sage中通常直接支持大整数。将N和e以整数或十六进制形式Sage会自动转换传入函数即可。6.4 性能优化与小技巧渐进分数遍历上限连分数展开可能产生成千上万个渐进分数。理论上d出现在前几十个渐进分数中的概率极高。可以在循环中加入一个计数器例如只遍历前200个以节省时间。max_iterations 200 for i, (k, d) in enumerate(convergents_list[2:]): if i max_iterations: break # ... 后续验证代码并行计算对于超大的数验证每个候选(k, d)时解一元二次方程是独立的可以尝试用多进程并行加速。但对于CTF题目通常单线程秒出无需复杂优化。日志输出在调试时可以在循环内打印当前尝试的d的位数观察其增长情况。如果d很快增长到远超N^(1/4)那么攻击很可能失败。最后分享一个我个人的习惯在解出任何一道RSA题目后无论用什么方法我都会尝试用恢复出的私钥d去加密一个已知的明文比如数字12345看是否能得到对应的密文再用公钥解密回来。这是一个快速的双向验证能确保你的整个密钥对(N, e, d)在数学上是完全正确的避免在后续步骤中浪费时间去调试一个根本不对的私钥。密码学攻击就像开锁当你听到“咔哒”一声p*qN验证通过别急着庆祝再用钥匙拧两下确认门真的开了这才是稳妥的做法。