Coppersmith攻击实战：利用已知高位破解RSA漏洞

1. 项目概述：当RSA遇上Coppersmith

在CTF的密码学赛题里，RSA几乎是必考项。常规的RSA攻击，比如分解大素数、共模攻击、低加密指数攻击，大家可能都玩腻了。但出题人总会想方设法给你“放点水”，比如故意泄露密钥的一部分信息。这时候，一个听起来很酷的攻击方法就登场了：Coppersmith攻击。它专门用来对付这种“已知部分密钥”的RSA漏洞，尤其是“已知高位”或“已知低位”的情况。简单说，就是你知道私钥d、模数n的因子p或q，甚至是明文m的某一段比特，但不知道完整的值。Coppersmith方法能利用这些零碎的信息，像拼图一样，把缺失的部分给“算”出来。

我第一次在实战中遇到这种题时，感觉就像拿到了一张藏宝图，但关键坐标被墨水涂掉了一半。硬猜？256位的素数，枚举到宇宙热寂也猜不完。但如果你知道这个坐标的前80位或者后80位数字，情况就完全不同了。Coppersmith攻击就是那个能帮你从已知的80位，精确还原出剩下176位的“数学显微镜”。它背后的核心是基于格的约简算法（LLL算法），能在多项式时间内找到满足特定模方程的小根。对于CTFer而言，你不需要完全理解LLL那复杂的数学证明，但你必须会用SageMath这个强大的数学工具库，把问题“喂”给它，然后坐等它吐出flag。

这篇文章，我就从一个实战者的角度，拆解如何利用Coppersmith攻击破解RSA已知高位/低位漏洞。我会用具体的赛题例子，手把手带你写Sage脚本，并分享我在调试过程中踩过的那些坑。无论你是刚接触CTF密码学的新手，还是想深化对Coppersmith理解的老手，相信都能从中找到可以直接“抄作业”的实战经验。

2. 核心原理：为什么Coppersmith能“猜”出缺失的比特？

在深入脚本之前，我们必须先搞懂Coppersmith攻击到底在做什么。知其然，更要知其所以然，这样遇到变种题时你才能灵活应对。

2.1 从一道经典赛题说起

假设我们遇到一个RSA题，给出的信息如下：

• 模数n = p * q（一个非常大的合数，通常1024位或以上）
• 公钥e（通常是65537）
• 密文c
• 额外信息：素数p的高位（Most Significant Bits, MSB）是已知的。比如，p是256位的数，题目给出了它的前200位。

我们的目标：恢复完整的p，从而分解n，计算出私钥d，最终解密得到明文m。

没有额外信息时，分解n是计算上不可行的。但有了p的高200位，未知的只有56位。最笨的办法是暴力枚举这56位，计算量是2^56，依然巨大。Coppersmith攻击则能将这个问题转化为一个在多项式时间内可解的问题。

2.2 将问题转化为数学方程

设已知的p的高位部分为p_high，未知的低位部分为x。那么完整的p可以表示为：p = p_high * 2^k + x其中，k是未知低位x的比特长度（在这个例子里是56）。

因为p是n的因子，所以有：n ≡ 0 (mod p)这意味着n能被p整除。我们可以构造一个多项式：f(x) = p_high * 2^k + x这个多项式在模p下有一个根x0（即真实的未知低位），并且满足f(x0) ≡ 0 (mod p)。

关键点来了：x0是一个比较小的数（因为只有56位）。Coppersmith定理告诉我们，对于一个模N（这里N=n，但定理应用时我们通常用p本身或其上界）已知的单变量多项式f，如果它在模N的某个因子p下有一个足够小的根，那么我们可以在多项式时间内找到这个根。

2.3 LLL算法与格的直观理解

Coppersmith方法的实现依赖于LLL（Lenstra–Lenstra–Lovász）格基约简算法。你可以把“格”想象成一个高维空间里由一组基向量张成的所有整系数线性组合的集合。LLL算法能在这组基向量中，找到一组“几乎正交”且“很短”的新基向量。

在我们的问题里，我们会用已知的多项式f(x)和模数n，构造一个格（一个矩阵）。这个格的某个很短向量，就编码了我们要求的解x0。LLL算法通过约简这个格，把这个短向量找出来。SageMath的small_roots()函数，就是封装了这套复杂的构造和计算过程。

实操心得：对于CTF比赛，你99%的情况不需要自己从头构造格。Sage的small_roots()就是你的“瑞士军刀”。你的核心任务是：1. 正确理解题目给出了哪部分信息（p的高位？低位？d的位？）。2. 根据信息正确地构造出多项式f(x)。3. 合理设置small_roots()的参数（主要是根的边界X）。

2.4 不同类型“已知部分”的建模

除了已知p的高位，常见的变种还有：

1. 已知p的低位（LSB）：设已知低位为p_low，未知高位为x。则p = x * 2^k + p_low。多项式为f(x) = x * 2^k + p_low。
2. 已知d的低位：私钥d满足e*d ≡ 1 (mod φ(n))。已知d的低位，可以推导出关于k（未知高位）的一个方程，进而构造多项式。这通常更复杂一些。
3. 已知明文m的高位或低位：在已知部分明文的情况下攻击，常用于填充预言攻击的变种。

无论哪种类型，核心思路都是一致的：利用已知部分，将未知部分设为变量，构造一个在模某个数（p,n,M等）下有“小根”的多项式，然后调用small_roots()求解。

3. 实战拆解：已知p高位的Sage脚本编写与详解

理论讲得再多，不如一行代码。我们用一个模拟的赛题环境，来一步步编写并剖析攻击脚本。

3.1 模拟题目数据生成

首先，我们模拟出题人生成题目的过程，这样你就能完全理解数据的来源。

# 模拟数据生成脚本 (仅为理解用，比赛时你拿到的是n, e, c, p_high) from Crypto.Util.number import * import random # 生成一个256位的素数p p = getPrime(256) # 生成一个256位的素数q q = getPrime(256) n = p * q e = 65537 phi = (p-1)*(q-1) d = inverse(e, phi) # 模拟要加密的flag m = bytes_to_long(b"flag{Coppersmith_is_powerful!}") c = pow(m, e, n) # 假设题目泄露了p的高200位 p_high = p >> 56 # 右移56位，得到高200位 # 或者更精确地，获取p的比特长度，取前200位对应的数值 # p_bit_len = p.bit_length() # 256 # high_bit_len = 200 # p_high = p >> (p_bit_len - high_bit_len) print(f"模拟题目给出的数据:") print(f"n = {n}") print(f"e = {e}") print(f"c = {c}") print(f"p_high = {p_high}") print(f"# 注意：p_high是整数形式，不是字符串。") print(f"# p的真实值（用于验证）: {p}")

运行后，你会得到类似下面的输出（数值是随机的）：

n = 123456789...（一个很大的数） e = 65537 c = 987654321...（一个很大的数） p_high = 123456789...（一个200位的大整数）

比赛时，你拿到的就是n,e,c,p_high这四个值。你的任务就是根据p_high恢复p。

3.2 Coppersmith攻击Sage脚本

现在，我们在SageMath环境中编写攻击脚本。确保你安装了SageMath，或者使用在线的SageCell。

# Coppersmith攻击已知p高位的Sage脚本 # 给定 n, e, c, p_high (p的高位) # 1. 从题目中复制过来的数据 n = 0xabcdef... # 替换为实际的n e = 65537 c = 0xdeadbeef... # 替换为实际的c p_high = 0x123456... # 替换为实际的p_high，整数形式 # 2. 设置参数 # p的完整比特长度 p_bit_length = 256 # 你需要根据题目提示或n的位数推断，比如n是512位，p和q通常各256位 # 已知的高位比特数 high_bit_length = 200 # 未知的低位比特数 unknown_bit_length = p_bit_length - high_bit_length # 56 # 3. 构造多项式 f(x) = p_high * 2^k + x # 其中 k 是未知部分的比特长度 k = unknown_bit_length # 定义多项式环，变量为x，模数为n（注意：这里是在整数环Z上定义多项式，small_roots内部会处理模） P.<x> = PolynomialRing(Zmod(n)) # p = p_high * 2^k + x f = p_high * (2^k) + x # 4. 寻找小根 # X 是根的上界，我们设定为 2^k，因为未知的x小于2^k X = 2^k # 调用small_roots函数，beta参数通常设为0.4~0.5，这里我们设0.48 # epsilon参数控制计算精度，默认即可 roots = f.small_roots(X=X, beta=0.48) # 5. 检查并恢复p if roots: x0 = roots[0] # 找到的小根，即p的未知低位 p_recovered = p_high * (2^k) + int(x0) # 验证找到的p是否能整除n if n % p_recovered == 0: print(f"[+] 成功恢复p!") print(f"p = {p_recovered}") # 计算q和私钥d q_recovered = n // p_recovered phi_recovered = (p_recovered - 1) * (q_recovered - 1) d_recovered = inverse_mod(e, phi_recovered) # 解密 m_recovered = pow(c, d_recovered, n) # 将整数转换为字节 from Crypto.Util.number import long_to_bytes flag = long_to_bytes(m_recovered) print(f"[+] 解密后的flag: {flag}") else: print(f"[-] 恢复的p无法整除n，可能参数设置有误。") else: print(f"[-] 未找到小根。请检查：") print(f" 1. p_high是否正确？") print(f" 2. p_bit_length和high_bit_length设置是否正确？") print(f" 3. 可以尝试调整beta值（如0.49, 0.5）或增加small_roots的epsilon参数。")

3.3 脚本关键点解析与避坑指南

这段脚本看似简单，但每个参数背后都有讲究，这里是我踩过坑后总结的经验：

1. p_bit_length的确定：这是最容易出错的地方。题目不一定会直接告诉你p的位数。你需要根据n的位数来推断。如果n是512位，那么p和q通常各256位。如果n是1024位，p和q通常各512位。有时题目会使用不平衡的素数，这就需要结合p_high的数值来反推。一个技巧：计算p_high.bit_length()，它应该非常接近high_bit_length。如果不确定，可以稍微高估p_bit_length（比如设大一点），但X的上界也会随之变大，可能导致求解失败。

2. high_bit_length的精确计算：p_high是作为一个整数给出的。你需要知道这个整数对应的是p的多少位。例如，如果p是256位，p_high是前200位，那么p_high的比特长度应该就是200（或非常接近200，因为最高位是1）。用p_high.bit_length()来确认。

3. 多项式f(x)的构造：这是核心中的核心。

   • 已知高位：p = p_high * 2^k + x。k是未知低位的比特长度。p_high需要左移k位。
   • 已知低位：p = x * 2^k + p_low。k是已知低位的比特长度。x是未知高位。务必分清左移还是右移，这是最常见的错误。

4. small_roots()参数设置：

   • X: 根的上界。必须大于等于真实根x0的绝对值。通常设为2^k（k是未知部分的比特长度）。宁可设大，不可设小。设小了肯定找不到根；设大了只会增加计算量，但算法通常仍能工作（除非大太多超出能力范围）。
   • beta: 一个介于0和1之间的参数，与因子p的大小有关。beta约等于log(p)/log(N)。在RSA中，p和q大小相近，所以p ≈ sqrt(n)，即log(p) ≈ 0.5 * log(n)，因此beta通常设为0.5或略小（如0.48,0.49）。如果p和q大小相差很大（不平衡RSA），需要相应调整beta。
   • epsilon: 一个小的正数，默认值通常就够用。如果求解失败，可以尝试调小epsilon（如epsilon=0.01），这会让算法搜索更努力，但耗时更长。

5. 验证环节必不可少：找到根x0后，一定要计算p_recovered并检查n % p_recovered == 0。因为small_roots()可能找到的是其他满足多项式的小根，不一定是我们要的那个。只有能整除n的p才是正确的。

踩坑实录：有一次比赛，我所有参数都设对了，但就是跑不出结果。折腾了一个多小时，最后发现是p_high的数据复制错了，里面混了一个换行符。教训：从题目文件复制大整数时，务必检查其类型和值。在Sage里用print(hex(p_high))和题目给的十六进制对比一下，能避免这种低级错误。

4. 攻击变种与脚本适配

实战中，题目不会总是乖乖地给你p的高位。下面我们看看其他几种常见变种，以及如何修改脚本来应对。

4.1 已知p的低位（LSB）

假设题目给出的是p的低l位，记为p_low。

建模：设未知的高位为x。则p = x * 2^l + p_low。多项式：f(x) = x * 2^l + p_low。根的上界：X = 2^(p_bit_length - l)，因为x的比特长度是p_bit_length - l。

Sage脚本修改部分：

# 已知p_low和低位比特长度l p_low = 0x... # 题目给出的p低位 l = 64 # 已知的低位比特数，例如64位 unknown_bit_length = p_bit_length - l k = l # 注意：这里的k是已知低位的比特长度，用于构造多项式 P.<x> = PolynomialRing(Zmod(n)) # p = x * 2^l + p_low f = x * (2^k) + p_low # 这里k=l X = 2^(unknown_bit_length) # 根x的上界是未知高位的最大值 roots = f.small_roots(X=X, beta=0.48)

4.2 已知私钥d的低位

这种题目难度更高一些。我们已知私钥d的低l位d_low。回忆关系式：e*d ≡ 1 (mod φ(n))，其中φ(n) = (p-1)*(q-1) = n - (p+q) + 1。

我们可以写出：e*d = 1 + k*φ(n)，k是一个较小的整数（通常与e同数量级）。 设d = d_low + x*2^l（x是未知高位）。 代入得：e*(d_low + x*2^l) ≡ 1 (mod φ(n))。 但φ(n)未知。我们利用φ(n)与n的关系：φ(n) ≈ n（因为p和q很大，p+q相对很小）。更精确地，我们可以对等式模e来消去k？不，更常见的做法是构造一个关于x和k的多变量方程，然后用Coppersmith的多变量版本来解。但这对新手来说太复杂。

更实用的方法（已知d低位，且e较小）： 当e较小（比如3，65537也算较小）时，k的范围很小。我们可以枚举k（从1到e-1）。对于每个k，我们有：e*d ≡ 1 (mod φ(n))=>e*d = 1 + k*φ(n)=>φ(n) = (e*d - 1) / k因为d = d_low + x*2^l，所以φ(n) = (e*(d_low + x*2^l) - 1) / k又因为φ(n) = n - (p+q) + 1，且p*q = n。通过φ(n)可以求出p+q = n - φ(n) + 1，进而解一元二次方程求出p和q。

但这里φ(n)表达式里还有未知的x。我们可以注意到，φ(n)必须非常接近n，且是整数。(e*d - 1)必须能被k整除。我们可以通过枚举k和x的高位可能性来逼近。然而，这本质上还是利用了d低位信息，结合枚举和Coppersmith。

对于CTF，更常见的简化题设是：已知d的低位，且额外知道d的大致范围（比如d小于某个值），这样可以直接构造关于x的多项式。如果遇到纯已知d低位的题，建议直接搜索相关Writeup，通常需要更复杂的格构造。作为入门，我们优先掌握已知p高位/低位的场景。

4.3 已知明文m的高位或低位（Franklin-Reiter相关消息攻击变种）

这属于Coppersmith的另一种应用场景。假设你知道了加密前的明文m的某一部分（比如flag的格式是flag{...}，你知道"flag{"对应的数值），那么你可以构造多项式f(x) = (已知部分 + x)^e - c (mod n)，其中x是未知的明文部分，c是密文。然后寻找满足f(x) ≡ 0 (mod n)的小根x。

Sage脚本示例（已知明文高位）：

n = 0x... e = 65537 c = 0x... known_part = bytes_to_long(b"flag{") # 已知的明文高位 unknown_bit_len = ... # 未知明文的比特长度 P.<x> = PolynomialRing(Zmod(n)) # 假设明文 m = (known_part << unknown_bit_len) + x f = ( (known_part << unknown_bit_len) + x )^e - c X = 2^unknown_bit_len roots = f.small_roots(X=X) if roots: x0 = roots[0] m_recovered = (known_part << unknown_bit_len) + int(x0) print(long_to_bytes(m_recovered))

5. 调试技巧与常见问题排查

即使脚本看起来正确，也可能因为各种原因跑不出结果。下面是我在实战中总结的排查清单。

5.1 问题排查速查表

5.2 高级调试：观察与验证

1. 打印关键中间变量：在调用small_roots前，打印p_bit_length,high_bit_length,k,X,beta以及f多项式。确保它们符合你的预期。

   print(f"p_bit_length: {p_bit_length}") print(f"high_bit_length: {high_bit_length}") print(f"k (unknown bits): {k}") print(f"Root bound X: {X} (approx 2^{log(X,2)})") print(f"Polynomial f: {f}")

2. 验证已知部分：计算(p_high << k).bit_length()，它应该接近p_bit_length。如果差很多，说明移位位数k可能算反了。

3. 尝试更激进的参数：如果标准参数不行，可以尝试：

   # 增加epsilon，让搜索更细致（但更慢） roots = f.small_roots(X=X, beta=0.49, epsilon=0.05) # 或者尝试更小的beta（如果怀疑p比sqrt(n)小很多） roots = f.small_roots(X=X, beta=0.4)

4. 分割未知部分：如果未知部分刚好在边界上，可以尝试“猜”几位。例如，未知部分有60位，你可以假设你知道其中4位（比如全是0），那么未知部分就变成56位，再用Coppersmith攻击。这需要写循环去枚举几种可能性。

5.3 环境与工具准备

• SageMath安装：本地安装能获得最好的性能。可以从官网下载，或者用包管理器（如apt install sagemath,brew install sage）。
• 在线替代方案：
  • SageCell: 最方便的在线Sage环境，适合快速测试。但对于大型格运算可能超时。
  • Cocalc: 一个在线的协作计算环境，支持Sage，性能比SageCell好。
• 备用方案：如果Sage不给力，可以用Python的sympy库或专门的数论库，但small_roots这样的高级函数通常只有Sage和少数专业库有。在CTF中，Sage是事实标准。

6. 从解题到出题：深入理解Coppersmith的边界

作为解题者，我们关心怎么用工具。但如果你想深入一层，或者自己出题，就必须理解Coppersmith方法的极限在哪里。

6.1 能力边界：多少未知比特是可恢复的？

这是一个关键问题。Coppersmith不是万能的，它恢复未知比特的能力与以下因素有关：

• 模数N的大小：N越大，能恢复的未知比特比例通常越小。
• 因子p的大小（beta参数）：beta越小（即p相对于N越小），能恢复的未知比特数越多。
• 多项式的次数：次数越高，能力越弱。

对于最常见的RSA情况（n=p*q,p和q大小相近，即beta≈0.5），已知p高位攻击的经典结论是：当未知的低位比特数小于p比特长度的约50%时，攻击是有效的。更精确地说，对于beta=0.5，small_roots通常能处理到p比特长度的48%左右。

这意味着，对于一个256位的p，如果你知道至少约130位（2560.52），那么剩下的约126位（2560.48）可以用Coppersmith恢复。题目中给出200位高位，只留56位未知，是绰绰有余的。

6.2 出题思路与防攻击设计

理解了攻击边界，你就可以从出题人角度思考：

• 放水题：给出p的高位，未知部分远小于50%。这是标准的Coppersmith入门题。
• 中等题：给出p的中间一段连续比特，或者不连续的一些比特。这需要更巧妙的建模，可能要将未知部分分成两个变量来处理。
• 难题：接近边界的情况。例如，p是512位，只给出260位高位，需要恢复252位。这可能需要调整beta和epsilon，或者利用其他信息（如p和q的特殊形式）。
• 防攻击：要让Coppersmith失效，最直接的方法就是确保泄露的比特数不足以达到恢复阈值。或者，使用非常大的素数，使得即使泄露50%，剩余未知部分的绝对比特数仍然巨大，超出计算能力。

6.3 与其他攻击方法的结合

在实际CTF或安全审计中，Coppersmith很少孤立使用。它常与其他漏洞结合：

• 侧信道攻击：通过计时、功耗分析等手段，可能泄露密钥的某些比特，再结合Coppersmith进行恢复。
• 错误注入：在解密或签名过程中注入错误，可能获得关于私钥的信息片段。
• 网络协议漏洞：例如，在某些密钥交换协议中，可能部分密钥信息被泄露。

掌握Coppersmith，为你打开了一扇门，让你能理解并利用这些“不完整泄露”漏洞，这是现代密码学攻击中非常有力的一类技术。

最后，我个人的体会是，Coppersmith攻击在CTF密码学中属于“套路清晰，但细节致命”的类型。把原理搞懂，把脚本模板准备好，比赛时就能快速套用。最花时间的往往不是写脚本，而是分析题目到底给了什么信息、如何正确地建模成多项式。多找几道不同变种的题目练手，形成自己的“武器库”，下次再遇到RSA已知部分位的题，你就能一眼看穿本质，十分钟内拿下flag。