文章总结： 湖湘杯2016RSA题给出原始n,e,d却用新模数new_n加密flag；作者先利用ed≡1modφ(n)随机分解得p,q，再发现destory函数仅用900位随机数与2048位质数异或致高1148位不变，遂以Coppersmith定理在56%已知比特下多项式时间恢复new_p,new_q，重算私钥解密获flag。文章详述RSA基础、概率分解、Coppersmith原理与Sage实现，指出短密钥XOR长数据的信息泄露陷阱并给出安全建议。 综合评分： 95 文章分类： CTF,漏洞分析,密码学,安全建设,实战经验
湖湘杯2016-简单的RSA：从部分信息到完整攻破
原创
破镜安全
破镜安全
2025年12月25日 08:00 四川
湖湘杯2016-简单的RSA：从部分信息到完整攻破
0x01 题目概览
题目名称：简单的RSA（湖湘杯2016）
题目给出了一个Python脚本和三组关键数据：
- 原始RSA参数：n, e, d
- 修改后的模数：new_n
- 加密的flag：enc_flag
乍一看，题目给出了私钥d，似乎可以直接解密。但仔细观察会发现，flag是用new_n加密的，而我们手头的d是基于原始n的私钥。这就是问题的关键所在。
0x02 题目代码分析
让我们先来看看题目的核心代码：
def destory(x, num):
while True:
dt = getRandomNBitInteger(num)
r = x ^ dt
if isPrime(r):
return r
p = getPrime(2048)
q = getPrime(2048)
n = p*q
e = 0x10001
phi_n = (p-1)*(q-1)
d = invmod(e, phi_n)
# 破坏原始质因数
new_p = destory(p, 900)
new_q = destory(q, 900)
new_n = new_p * new_q
c = pow(flag, e, new_n)
代码的执行流程如下：
- 生成2048位的质数p和q
- 计算标准RSA参数n, e, d并输出
- 调用
destory函数”破坏”p和q，得到new_p和new_q - 用new_n = new_p * new_q作为新模数加密flag
题目的巧妙之处在于：给了我们原始的私钥d，但加密用的是新的模数new_n。要解密flag，我们必须找到new_n对应的私钥，而这需要我们能够分解new_n。
0x03 destory函数的秘密
destory函数是这道题的核心，让我们深入分析它的行为：
def destory(x, num):
while True:
dt = getRandomNBitInteger(num) # 生成900位随机数
r = x ^ dt # 与x进行异或
if isPrime(r): # 如果结果是质数则返回
return r
函数接收一个质数x（即p或q）和位数num（这里是900），然后：
- 生成一个900位的随机整数dt
- 计算r = x XOR dt
- 如果r是质数，返回r；否则重新生成dt
异或操作的比特级分析
这里的关键是理解异或（XOR）操作的性质。对于二进制数，异或操作是按位进行的：
- 0 XOR 0 = 0
- 0 XOR 1 = 1
- 1 XOR 0 = 1
- 1 XOR 1 = 0
当我们将2048位的p与900位的dt进行异或时，会发生什么？
p (2048位): [高1148位][低900位]
dt (900位): [000...000][低900位]
由于dt只有900位，它的高位（第901位及以上）都是0。在异或操作中：
- p的高1148位与0异或，结果保持不变
- p的低900位与dt的低900位异或，结果会发生变化
结论：new_p和p只在低900位不同，高1148位完全相同！
这个发现至关重要。我们可以通过p的高1148位来推测new_p的高1148位，因为它们是相同的。
0x04 RSA密码学基础回顾
在展开攻击之前，让我们快速回顾RSA的数学基础。
RSA加密系统
密钥生成：
- 选择两个大质数p和q
- 计算n = p × q
- 计算欧拉函数φ(n) = (p-1)(q-1)
- 选择公钥指数e，满足gcd(e, φ(n)) = 1
- 计算私钥d = e^(-1) mod φ(n)
加密与解密：
- 加密：c = m^e mod n
- 解密：m = c^d mod n
正确性证明： 根据欧拉定理，对于gcd(m, n) = 1，有： m^φ(n) ≡ 1 (mod n)
因为ed ≡ 1 (mod φ(n))，所以ed = 1 + kφ(n)，因此： c^d = (m^e)^d = m^(ed) = m^(1+kφ(n)) = m · (m^φ(n))^k ≡ m · 1^k = m (mod n)
RSA的安全性
RSA的安全性基于大整数分解的困难性。如果攻击者能够将n分解为p和q，就可以计算φ(n)，进而求出私钥d。
对于2048位的RSA模数，目前没有已知的高效分解算法。但如果我们能获得关于p或q的部分信息，情况就会完全不同。
0x05 攻击策略构建
通过分析，我们发现了三个可利用的突破点：
突破点1：已知(n, e, d)可以分解n
虽然题目没有直接给出p和q，但给了我们完整的RSA参数(n, e, d)。这看似没什么用，但实际上存在一个经典的攻击方法。
数学原理：
由于d是e在模φ(n)下的逆元，我们知道： ed ≡ 1 (mod φ(n))
这意味着： ed = 1 + kφ(n) = 1 + k(p-1)(q-1)
其中k是某个正整数（通常很小）。
设k’ = ed – 1，则k’是φ(n)的倍数。我们可以将k’写成： k’ = 2^t × s，其中s是奇数
利用这个性质，结合随机性测试，我们可以找到n的因子。
算法步骤：
- 计算k’ = ed – 1
- 分解k’ = 2^t × s（s为奇数）
- 随机选择g ∈ [2, n-1]
- 计算x = g^s mod n
- 计算gcd(x-1, n)
- 如果结果既不是1也不是n，则找到了因子
为什么这个方法有效？
这个算法的理论基础来自于Miller-Rabin素性测试的思想。对于合数n = pq：
由于ed ≡ 1 (mod φ(n))，我们有： g^(ed-1) ≡ 1 (mod n)
根据中国剩余定理，这等价于： g^(ed-1) ≡ 1 (mod p) 且 g^(ed-1) ≡ 1 (mod q)
当我们计算g^s mod n时（其中s = k’/2^t），有较大概率使得：
- g^s ≡ 1 (mod p) 但 g^s ≢ 1 (mod q)，或者
- g^s ≢ 1 (mod p) 但 g^s ≡ 1 (mod q)
此时gcd(g^s – 1, n)会恰好等于p或q。
理论分析表明，对于随机选择的g，这个算法的成功概率至少为1/2。
突破点2：已知new_p的高1148位
从destory函数的分析，我们知道new_p和p只在低900位不同。这意味着：
已知信息：new_p的高1148位 未知信息：new_p的低900位 已知比例：1148/2048 = 56.05%
当我们知道一个数的56%时，是否有办法恢复完整的数？答案是：有，使用Coppersmith定理。
突破点3：Coppersmith部分信息攻击
Coppersmith定理（1996年）是密码分析中的强大工具，它能够在已知部分信息的情况下恢复完整信息。
定理陈述（简化版）：
设N是一个整数，f(x)是一个模N的单变量多项式。如果存在一个小根x0（|x0| < X），使得： f(x0) ≡ 0 (mod p)
其中p是N的一个未知因子，且p ≥ N^β，那么我们可以在多项式时间内找到x0。
理论条件：X < N^(β^2)
应用到本题：
在我们的场景中：
-
N = new_n = new_p × new_q
-
我们知道new_p ≈ N^0.5（因为new_p和new_q大小相近）
-
我们可以将new_p表示为：new_p = p_high × 2^900 + x
-
p_high是已知的（从p的高1148位得到）
-
x是未知的（0 ≤ x < 2^900）
构造多项式： f(x) = p_high × 2^900 + x
这个多项式在模new_p下有根：x0 = new_p的低900位
检验Coppersmith条件：
- β ≈ 0.5（因为new_p ≈ sqrt(new_n)）
- X = 2^900
- N^(β^2) = new_n^0.25 ≈ 2^1024
- X = 2^900 < 2^1024 = N^(β^2) ✓
条件满足！理论上可以使用Coppersmith方法恢复new_p。
Coppersmith算法的实现：
Coppersmith算法基于LLL格基约化。虽然理论很深奥，但SageMath提供了现成的实现：small_roots方法。
使用时需要注意几个参数：
- X：未知量的上界
- beta：因子的大小，p ≈ N^beta
- epsilon：调整参数，影响算法精度
在实践中，beta的理论值是0.5，但由于LLL是启发式算法，可能需要略微调小（如0.49）以提高成功率。
0x06 实战解题
有了理论基础，现在开始实际操作。
第一步：从(n, e, d)恢复质因数p和q
首先实现分解算法：
# 给定的参数
n = 0x73cec712124b33c0294e01eb52e8c3cd2fe9ddbcbf457b3b950360063dfae42c...
e = 0x10001
d = 0x37f2646fd190ad1e9f95c50d97cf4590a21e1c766bfd382cafafa2bb41442ce9...
# 计算 ed - 1
k = e * d - 1
# 分解为 2^t * s 的形式
t = 0
while k % 2 == 0:
k = k // 2
t = t + 1
print(f"ed - 1 = 2^{t} * k")
# 输出：ed - 1 = 2^6 * k
# 随机选择基，寻找因子
found = False
while not found:
g = randint(2, n-1)
x = power_mod(g, int(k), n)
p = gcd(x - 1, n)
if 1 < p < n:
found = True
q = n // p
print(f"成功分解n!")
break
# 验证
assert p * q == n
运行结果：
ed - 1 = 2^6 * k
经过1-2次尝试，成功分解n!
验证：p * q == n ✓
成功！我们恢复了原始的质因数p和q。虽然题目没有直接给出，但通过已知的(n, e, d)，我们成功计算出来了。
为什么这么快？
这个算法每次尝试的成功概率约为1/2，因此期望只需要2次左右的尝试。这比暴力分解n（需要2^1024次运算）要高效得多。
第二步：使用Coppersmith方法恢复new_p和new_q
现在我们有了p，可以利用它来攻击new_p。
关键观察：
p的二进制表示： [高1148位][低900位]
new_p的二进制表示： [高1148位][低900位']
^^^^^^^^ 这部分相同！
构造攻击：
pbits = 2048 # p是2048位质数
kbits = 900 # 被修改的位数
# 获取p的高位（清除低900位）
p_high = p >> kbits
print(f"已知的高位：{pbits - kbits} = 1148位")
print(f"未知的低位：{kbits} = 900位")
print(f"已知比例：{(pbits - kbits) / pbits * 100:.2f}%")
# 构造多项式
# new_p = p_high * 2^900 + x，其中x是未知的低900位
PR.<x> = PolynomialRing(Zmod(new_n))
f = p_high * 2^kbits + x
# 使用Coppersmith方法
X = 2^kbits # x的上界
beta = 0.49 # 因子大小参数
epsilon = 0.05 # 精度参数
roots = f.small_roots(X=X, beta=beta, epsilon=epsilon)
if roots:
print(f"找到 {len(roots)} 个根")
for root in roots:
new_p_candidate = int(p_high * 2^kbits + root)
# 验证是否是new_n的因子
if new_n % new_p_candidate == 0:
new_p = new_p_candidate
new_q = new_n // new_p
print(f"成功恢复new_p和new_q!")
break
# 验证
assert new_p * new_q == new_n
运行结果：
已知的高位：1148位
未知的低位：900位
已知比例：56.05%
尝试 beta = 0.5 ... 失败
尝试 beta = 0.49 ... 成功！
找到 1 个根
成功恢复new_p和new_q!
验证：new_p * new_q == new_n ✓
关于beta参数的说明：
理论上，当new_p ≈ sqrt(new_n)时，beta应该设为0.5。但在实践中，LLL算法是启发式的，可能需要稍微调小beta值以提高成功率。
这就像是给算法留一些”安全边界”。beta=0.49意味着我们假设因子稍微小一点，这样算法会更加”努力”地寻找，成功率会提高。
计算复杂度：
small_roots方法的复杂度主要取决于LLL格基约化，对于我们的参数，运行时间通常在数十秒到几分钟之间（取决于硬件）。这比直接分解2048位RSA模数（几乎不可能）要可行得多。
第三步：计算新私钥并解密flag
有了new_p和new_q，剩下的就是标准RSA解密流程：
enc_flag = 0x3b0487110b2d61683fc9e65717d6431281c25ceda38915c9c2ff1601...
# 计算新的欧拉函数
phi_new = (new_p - 1) * (new_q - 1)
# 计算新的私钥
d_new = inverse_mod(e, phi_new)
# 验证私钥正确性
assert (e * d_new) % phi_new == 1
print("私钥计算正确!")
# 解密flag
flag_int = power_mod(enc_flag, d_new, new_n)
flag = long_to_bytes(int(flag_int))
print(f"Flag: {flag}")
运行结果：
私钥计算正确!
Flag: b'flag{6b1ff461dc15e5476cafe887189178e3924dad84}'
成功解密！
0x07 深入理解Coppersmith定理
Coppersmith定理是这道题的核心技术，值得我们深入探讨。
定理的直观理解
想象你在玩一个猜数字游戏：
- 有一个2048位的秘密数字
- 我告诉你这个数字的前1148位
- 你需要猜出完整的数字
如果只是暴力穷举，你需要尝试2^900 ≈ 10^271次。这在计算上是不可行的。
但如果这个秘密数字恰好是某个已知大数N的因子，情况就不同了。Coppersmith定理告诉我们，在这种特殊情况下，我们可以在多项式时间内找到答案。
定理的数学基础
Coppersmith定理建立在以下数学工具之上：
1. Howgrave-Graham定理：
如果多项式h(x)满足：
- h(x0) = 0在整数上成立（不是模运算）
- ||h(xX)|| < N / sqrt(d)，其中d是多项式的次数
那么h(x0) ≡ 0 (mod N)也成立。
2. LLL格基约化算法：
LLL算法可以找到格中的短向量。通过巧妙地构造格，我们可以找到满足Howgrave-Graham条件的多项式。
3. 构造格的艺术：
Coppersmith的天才之处在于如何构造格。对于我们的多项式f(x) = p_high * 2^900 + x，我们构造一系列相关的多项式，形成一个格。LLL算法在这个格中找到短向量，这些短向量对应满足条件的多项式。
为什么需要beta参数？
beta参数表示因子p的大小：p ≈ N^beta
- 如果p很大（接近N），那么分解N很容易（试除法就行）
- 如果p很小，那么X可以更大（可以恢复更多未知位）
- beta=0.5表示两个因子大小相近，这是最困难的情况
Coppersmith定理给出的界限是：X < N^(β^2)
在我们的例子中：
- β ≈ 0.5
- N^(β^2) = N^0.25 ≈ 2^1024
- X = 2^900 < 2^1024 ✓
理论上可行，实践中也确实成功了。
epsilon参数的作用
epsilon是一个小的调整参数，用于在理论界和实际性能之间权衡：
- 更小的epsilon：更接近理论界限，但计算时间更长
- 更大的epsilon：偏离理论界限更多，但成功率可能下降
通常设置为0.01-0.05之间。
0x08 异或操作的密码学陷阱
这道题的另一个教训是：不要低估简单操作的安全影响。
异或操作的特性
异或（XOR）在密码学中有广泛应用，它有很多优秀的性质：
- 可逆性：a ⊕ b ⊕ b = a
- 速度快：直接的位运算
- 均匀性：对于随机输入，输出也是随机的
但它也有一个致命缺陷：局部性。
局部性导致的信息泄露
当用一个短的随机数与长数异或时，只有参与运算的位会改变：
原始数据: [A][B][C][D][E][F][G][H]
异或掩码: [0][0][0][0][0][X][Y][Z]
结果: [A][B][C][D][E][F'][G'][H']
^^^^^^^^^^^^^^^^ 这部分不变！
在本题中：
- 原始数据：2048位的质数p
- 异或掩码：900位的随机数
- 结果：高1148位完全不变
这种信息泄露正是Coppersmith攻击的关键。
正确的密钥变换方式
如果题目想要真正”销毁”p，应该怎么做？
方案1：完全重新生成
def destory(x, num):
# 忽略x，直接生成新的质数
return getPrime(2048)
方案2：使用哈希函数
def destory(x, num):
# 使用密码学哈希函数
seed = sha256(str(x).encode()).digest()
# 基于seed生成新的质数
return generate_prime_from_seed(seed, 2048)
方案3：充分混淆
def destory(x, num):
# 确保修改所有位
dt = getRandomNBitInteger(2048) # 与x等长
r = x ^ dt
if isPrime(r):
return r
关键是：任何密钥派生或变换操作，都必须充分混淆所有位，不能留下可预测的部分。
0x09 完整解题代码
将以上所有步骤整合，完整的解题脚本如下：
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
from Crypto.Util.number import long_to_bytes
# 题目给定的数据
n = 0x73cec712124b33c0294e01eb52e8c3cd2fe9ddbcbf457b3b950360063dfae42cbbe9855bd986bcfea0948fadfb252f5e2ff3c982ff47afb6596a496636f1fc5ecfe9f5db7620b23fe9e30d230aa9299ab9a78bfb5e0630fd1149259b2b2104ea65d2e27b89785e4bf01d0594d9f94575cbcc3383f63c5aabe4d5b48eb761cce3ab21689b3f3155b5f15efee240d5ac149318ff80bd72a75fccdc57402aa197b472d98758019df8e9edb31bda82967dc66bcad845df824775eeb66ee304664d7929e8405122f9b0a5406887729dbe9760eb62dd7018087723c07c07082d1d51035fb211a9fc6d8fb5b3ee5bb91af5e3d0b89addce289041a5683a1fe7dc06a3bae283062ba3febdd987b5ac9b9a8ae4b8b02b804accc0a413bb144680fd8d0d8d8bebe176e5a9121f7653c31ede984d234ccce50e688f7048a0bfdfc84004c006ae912c4d4e514c200883e8dabaeb4bf57a5f628eb4bd2e6688d9b7688bc3eed4ce03831be5044dedbd5fddc43a3274b26c990a0e444fcf4a607de59c4906dfd1ea111920c38b4a365c5838e9cf1a22b146aa7afbc6e2e29ebe35aee4bf4d2fbe186c0f359c71f80b8f6298ad38619168d5986a857f558017c546d6df896c690896601aabd48398e957b77ef0e15d6cda339050b74cda3328c34c889306d089efc95ff467a4a775d3e104642cd9819f002b5db8c5f39b4e8d1a83007276b8a0b7
e = 0x10001
d = 0x37f2646fd190ad1e9f95c50d97cf4590a21e1c766bfd382cafafa2bb41442ce9839aac47944e288de6abfec1b17be4675f492a47f3e600f85a3823df9299d32f46c8a372f39d961f9471914e257f55cf1ef3d7878783fc34b61e1d61da332879c8d9597b0f0dac988916ac349e1d73b615cfbfef778ceeccee4f63dc32b1b7d7213c9199b6acb1d8a5141c94d777a29b89f8e0aea457788eaa9ca43626a24c74ebab355c89e3747626d4899745d148500c91416c782f2b30c9332f5cd32a4d3144d2a407ce9acc00f99dc619d425586285350cff734cdba9d4fad636d7fcbabfa382965005d8343e36ffe72604e557bae5044435ad990b6dca6d922e64387cee4abc0574d2eeeb42dda977be1e1064f6a6b00e78db75a7bf8e6e0c2ac3c6a52b2e6670cad3c907d990e53a7a311ef7b097c7644ff6f2bf96573e47d33031eeabf22620bdbc254a8fff8b0fa6f90d320c45e8d9094c26401f78560e16f77d6e09bc219c9849f1b68dc84ed36eb0cec7df16c4672c16a6b704ef2185ce04539f08688b72d48f9491e55be0095ee74f9622e8ae6835381e2efcd520cd02d1eeeb09bc11ab75bc903053102bc92718f2bf8691561a40026e53e950674f712aaef8cc69360df54c1af8b1f4aef997371b8a108e9b193a51002fe8d61f3991153e7ebd9593d68cd03b2f252c3d9d7a5bf802dcd150bd86028bd3b07cb415b767d716c1
new_n = 0x73cec712124b33c0294e01eb52e8c3cd2fe9ddbcbf457b3b950360063dfae42cbbe9855bd986bcfea0948fadfb252f5e2ff3c982ff47afb6596a496636f1fc5ecfe9f5db7620b23fe9e30d230aa9299ab9a78bfb5e0630fd1149259b2b2104ea65d2e27b89785e4bf01d0594d9f94575cbcc3383f63c5aabe4d5b48eb761cce3ab21689b3f3155b5f15efee240d5ac11cee2acbd019de7c06f607ea618b5cd735b5a6972d2b446a12ff58cf8314822fa5ea09d0963acd00441b2a1b37aca01d7f39052927db98a0bd5ca1c49a7ad67923e3aac30ecd33cc8b4b30a40cdb3acc721ee5da53a02977cee959affe672a668525eb78df96af0a14f4ac04fab68efa8eabe9535e1064a5fc2ff7cac9520210311db0c3bf91101bc55a67a81e4f69364c724ee6ad6bdc301df642c9392e9befa4ff0d65481adb6feac251cd207044587da9710809700246cb3c63e659a97249f5e7418568e37db2fb2c1115e719d6682bb2e89b4e23d40ba4c532f289e10e0b89a5647c486a09b9e376844171b229d74f871004d4945a702a391a04ac704f43809e972891e6ab33b3c0f03f0b6f9ae005b26be6e647a1865c727277423f59a595187ffbfea13501e23b6b57ef115eaa6febcb207a3112628652a39578847241c33989e84607b0f683b30ddf773348b07360b063d9120a397809591ca18a04cd32ad9cbfe0494ed3ae8d2c5b43fdb51cb
enc_flag = 0x3b0487110b2d61683fc9e65717d6431281c25ceda38915c9c2ff16013066e8cbe9d5f6c1f05988333d96e861f1b216f85d537aa70f603b3d20487a18c5e0d3a03556be88f984f508803f4bb25300149e805204c91f7aea038e545cf588a29bcb20113f81b16d9aacdbd820aa48615a5227ab2f329423da0a254c8f318dff4a7b75cf48e5ac18abc2975fee111ee56297fd7778b49320f6427227f21c08391d7429c49b399c366db38467a339229048e50735dff071bf89dbbab22997071a6b5a16935f5b65032f2cefb9c670cddd1470f6bf16d7c46d0fff22b82b2c1d867f4faa60e5daaad35a15ac0413a17beb5371a06f22c646336ae5e5738cfc5e997860056fb8bf1e02f27031ecd2b7983df510c4cdebbc644ea49e99e2376b89a90be8c89e4995c6689cc39d01fcc8ffef416e49684c0a01fdffab4613cb8eddbfa9e14d9b2daca6ad57c4e440a049d04b915ecfd64095c549bb9d22fb502a740a7373c1961c8cb7a58604bcbca3e5a97e28d5f498061db7cfbf07085ec84f47856e88992ab08870cbdb050431260861d0bcc9bbdf9a4164b8581f1f67e86ab854db1769418e300d73cf902509c76969473d0ee1b70c3b24085942fa9782507b359ffe049b18832610b4555b9bfe8eeae14cec53ab21881475f81069a6a33d6e38e3825eeb13874da8f0c91160712090a092286ea3838d88020e459f795783ad099367
print("[*] Step 1: 从 (n, e, d) 恢复质因数 p 和 q")
print("="*60)
# 利用 e*d - 1 = k*phi(n)
k = e * d - 1
# 分解为 2^t * k
t = 0
while k % 2 == 0:
k = k // 2
t = t + 1
print(f"[+] ed - 1 = 2^{t} * k")
# 随机基方法寻找因子
found = False
attempt = 0
while not found:
attempt += 1
g = randint(2, n-1)
x = power_mod(g, int(k), n)
p = gcd(x - 1, n)
if 1 < p < n:
found = True
q = n // p
print(f"[+] 经过 {attempt} 次尝试，成功分解 n!")
print(f"[+] 验证: p * q == n ? {p * q == n}")
break
print()
print("[*] Step 2: 使用 Coppersmith 方法恢复 new_p 和 new_q")
print("="*60)
pbits = 2048
kbits = 900
# 获取p的高位
p_high = p >> kbits
print(f"[+] p 的位数: {pbits}")
print(f"[+] 被修改的位数: {kbits}")
print(f"[+] 已知的高位部分: {pbits - kbits} 位")
print(f"[+] 已知比例: {(pbits - kbits) / pbits * 100:.2f}%")
# 构造多项式
PR.<x> = PolynomialRing(Zmod(new_n))
f = p_high * 2^kbits + x
X = 2^kbits
new_p = None
new_q = None
# 尝试不同的beta值
for beta_val in [0.5, 0.49, 0.48, 0.4]:
print(f"[*] 尝试 beta = {beta_val}")
try:
roots = f.small_roots(X=X, beta=beta_val, epsilon=0.05)
if roots:
print(f"[+] 找到 {len(roots)} 个可能的根")
for root in roots:
new_p_candidate = int(p_high * 2^kbits + root)
if new_n % new_p_candidate == 0:
new_p = new_p_candidate
new_q = new_n // new_p
print(f"[+] 成功恢复 new_p!")
print(f"[+] 验证: new_p * new_q == new_n ? {new_p * new_q == new_n}")
break
if new_p:
break
except Exception as ex:
print(f"[-] beta={beta_val} 失败")
continue
if new_p and new_q:
print()
print("[*] Step 3: 计算新的私钥 d' 并解密")
print("="*60)
# 计算新的欧拉函数值
phi_new = (new_p - 1) * (new_q - 1)
# 计算新的私钥
d_new = inverse_mod(e, phi_new)
# 验证
assert (e * d_new) % phi_new == 1
print(f"[+] 验证: e * d' ≡ 1 (mod phi(new_n)) ? True")
# 解密flag
flag_int = power_mod(enc_flag, d_new, new_n)
flag = long_to_bytes(int(flag_int))
print(f"[+] Flag: {flag}")
print()
print("="*60)
print("[*] 解题完成!")
else:
print("[-] 恢复失败")
运行脚本：
sage solve.sage
输出：
[*] Step 1: 从 (n, e, d) 恢复质因数 p 和 q
============================================================
[+] ed - 1 = 2^6 * k
[+] 经过 1 次尝试，成功分解 n!
[+] 验证: p * q == n ? True
[*] Step 2: 使用 Coppersmith 方法恢复 new_p 和 new_q
============================================================
[+] p 的位数: 2048
[+] 被修改的位数: 900
[+] 已知的高位部分: 1148 位
[+] 已知比例: 56.05%
[*] 尝试 beta = 0.5
[*] 尝试 beta = 0.49
[+] 找到 1 个可能的根
[+] 成功恢复 new_p!
[+] 验证: new_p * new_q == new_n ? True
[*] Step 3: 计算新的私钥 d' 并解密
============================================================
[+] 验证: e * d' ≡ 1 (mod phi(new_n)) ? True
[+] Flag: b'flag{6b1ff461dc15e5476cafe887189178e3924dad84}'
============================================================
[*] 解题完成!
0x10 知识点总结
通过这道题，我们学到了以下关键知识点：
1. 从已知(n,e,d)分解RSA模数
核心思想：利用ed ≡ 1 (mod φ(n))的关系，通过随机性测试找到n的因子。
适用场景：
- 已知完整的RSA公私钥对
- 需要恢复质因数p和q
算法复杂度：期望O(log n)次尝试，每次尝试成功概率≥1/2
实际应用：
- CTF题目中常见
- 实际系统中，私钥泄露通常意味着系统已完全被攻破
2. Coppersmith部分信息攻击
核心思想：当知道RSA质因数的部分比特时，可以使用格基约化算法恢复完整的因数。
理论条件：
- 已知信息比例需要超过某个阈值（与beta相关）
- 对于beta=0.5（两个因子大小相近），需要知道约25%以上的比特
实现工具：SageMath的small_roots方法
参数调优：
- beta：因子大小，理论值vs实际值
- epsilon：精度与性能的权衡
- X：未知量的上界
实际应用：
- 侧信道攻击（如缓存攻击）可能泄露部分密钥比特
- 错误的密钥派生方案
- 密钥重用场景
3. 异或操作的密码学特性
优点：
- 可逆性
- 计算速度快
- 某些情况下的随机性
缺点：
- 局部性：只影响参与运算的位
- 可能导致信息泄露
正确使用：
- 一次一密（OTP）：密钥长度≥明文长度
- 流密码：使用密码学安全的伪随机数生成器
- 不要用短密钥XOR长数据
错误使用（本题）：
- 用900位随机数XOR 2048位数据
- 导致高位信息泄露
4. RSA密钥管理的安全实践
密钥生成：
- 使用密码学安全的随机数生成器
- 确保p和q的质量（不要太接近，不要有小因子等）
密钥存储：
- 私钥d必须严格保密
- 使用硬件安全模块（HSM）存储关键密钥
密钥更新：
- 定期更换密钥
- 旧密钥与新密钥必须完全独立
- 不要重用任何密钥材料
密钥销毁：
- 彻底覆写内存中的密钥数据
- 不要通过简单的位运算”修改”密钥
0x11 安全建议
基于本题的分析，我们可以得出以下安全建议：
对于密码系统设计者
- 不要低估部分信息泄露的危害
- 即使只泄露密钥的一部分，也可能导致完全破解
- Coppersmith定理表明，泄露25-50%的密钥比特就足以恢复完整密钥
- 密钥派生必须使用密码学哈希
- 不要使用XOR、移位等简单运算
- 使用HKDF、PBKDF2等标准密钥派生函数
- 密钥更新应该完全独立
- 新密钥和旧密钥之间不应有任何数学关系
- 最好的方式是完全重新生成
- 实施纵深防御
- 不要依赖单一的安全假设
- 即使某个参数泄露，系统仍应保持安全
对于CTF选手和安全研究员
- 熟悉经典攻击技术
- 从已知(n,e,d)分解n
- Coppersmith部分信息攻击
- 侧信道攻击
- 格基约化应用
- 掌握必要的工具
- SageMath：强大的数学工具
- Python密码学库：PyCrypto、cryptography
- 在线资源：factordb.com、CyberChef等
- 培养密码分析思维
- 寻找非预期的信息泄露
- 分析算法的数学性质
- 思考”如果我知道X，能否推导出Y？”
- 理解理论与实践的差距
- 理论安全≠实际安全
- 注意实现细节（如beta参数的调整）
- 多实践，积累经验
0x12 拓展思考
如果修改的位数更多会怎样？
假设destory函数修改的不是900位，而是1100位：
- 已知位数：2048 – 1100 = 948位
- 已知比例：948/2048 ≈ 46.3%
此时Coppersmith攻击可能失败，因为已知信息不足。攻击难度会显著增加。
如果只给了e和new_n呢？
如果题目不给d，只给(e, new_n, enc_flag)，这道题会变得困难得多：
- 无法直接分解原始n得到p和q
- 无法获得new_p的高位信息
- 可能需要寻找其他突破点（如小公钥指数攻击、低加密指数广播攻击等）
Coppersmith定理的其他应用
Coppersmith定理不仅可以攻击RSA，还有很多其他应用：
- 攻击低加密指数的RSA（e=3时的Hastad广播攻击）
- 分解特殊形式的大整数
- 求解模方程
- 密码分析中的各种场景
0x13 总结
这道题虽然名为”简单的RSA”，但实际上涵盖了多个深入的密码学知识点：
- RSA的数学基础：欧拉定理、模运算、质因数分解
- 经典攻击技术：从(n,e,d)恢复因子的概率算法
- 现代密码分析：Coppersmith定理及其应用
- 实现细节：参数调优、算法实现
通过层层分析，我们成功地：
- 从给定的(n, e, d)恢复了原始质因数p和q
- 利用destory函数的漏洞（XOR的局部性）获得new_p的部分信息
- 应用Coppersmith定理恢复完整的new_p和new_q
- 计算新私钥并解密flag
这个过程充分展示了现代密码分析的思路：观察、分析、建模、攻击。
密码学的魅力在于，看似简单的操作可能隐藏着深刻的数学原理，而看似安全的设计可能存在致命的漏洞。只有深入理解密码学的数学基础，才能真正评估系统的安全性。
最后，引用Bruce Schneier的名言： “Anyone can invent an encryption algorithm they themselves can’t break; it’s much harder to invent one that no one else can break.”
（任何人都能发明一个自己无法破解的加密算法；但要发明一个别人也无法破解的算法，就困难得多了。）
这道题完美地诠释了这句话的含义。
Flag: flag{6b1ff461dc15e5476cafe887189178e3924dad84}
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：破镜安全 破镜安全《湖湘杯2016-简单的RSA：从部分信息到完整攻破》
版权声明
本站仅做备份收录，仅供研究与教学参考之用。
读者将信息用于其他用途的，全部法律及连带责任由读者自行承担，本站不承担任何责任。
评论