RSA 明文高位泄露:Coppersmith 一元小根恢复 m 的未知低位
crypto/rsa · verified
一句话结论
已知 RSA 明文 m 的高位、只缺末尾 k 位时,把 m = m_hi·2^k + x 代入密文方程得到模 n 的一元多项式 f(x) = (m_hi·2^k + x)^e - c,当未知位数 k 小于 Coppersmith 小根界(约 n^(1/e))时,用 small_roots 可直接恢复 x。
原理
- 密文满足
m^e ≡ c (mod n)。把m拆成已知高位与未知低位:m = m_hi·2^k + x,其中0 ≤ x < 2^k。 - 代入后得到
f(x) = (m_hi·2^k + x)^e - c ≡ 0 (mod n),即m是f模n的一个小根。 - Coppersmith 一元小根定理:首一多项式
f次数为e时,若|x| < n^(1/e),可在多项式时间内求出小根。e=3时未知位数需小于约n的三分之一位数;1024 位模数下约 341 bit,示例只缺 100 bit,余量充足。 - 根恢复后
m = m_hi·2^k + x,再转字节即得明文。 - 若已知的是明文低位而不是高位,可设
m = x·2^k + m_lo,未知量x是高位部分,同样可构造多项式求小根;此时要求的是x的绝对值足够小。
触发条件
- 已知
n、e、c,以及m的连续高位(或可拼出高位)。 - 未知低位位数
k小于 Coppersmith 界;e越小越容易。 f的首项系数在模n下可逆(e次项系数为 1,通常自动满足)。- 能运行 Sage 的
small_roots或等价格算法。
利用步骤
- 确认泄露的是明文高位,估计未知位数
k,把已知部分左移k位得到m_hi·2^k。 - 在
PolynomialRing(Zmod(n))中构造f = (m_hi·2^k + x)^e - c。 - 调
f.small_roots(X=2^k);若失败,检查k是否超过界、是否应改用beta或增大格参数。 - 对每个候选根
x回代pow(m_hi·2^k+x, e, n) == c校验。 - 把整数转字节,按题目格式提取 flag。
PoC
from gmpy2 import *
from Crypto.Util.number import *
n = ...
c = ...
m_hi = ... # 已知的明文高位
SHIFT = 100 # 未知低位位数
PR.<x> = PolynomialRing(Zmod(n))
f = (m_hi * 2^SHIFT + x)^3 - c
roots = f.small_roots(X=2^SHIFT)
assert roots
x = int(roots[0])
m = m_hi * 2^SHIFT + x
assert pow(m, 3, n) == c % n
print(long_to_bytes(m))
变体与关联
- 变体:
e=3/5/7时分别对应约n^(1/3)、n^(1/5)、n^(1/7)的未知位上限;e越大可容忍的缺失位越少。 - 变体:已知明文低位时改设
m = x·2^k + m_lo,求高位x;若高位数值不小,需要重新评估界。 - 变体:明文由多个字段拼接、只有中间一段未知时,可把未知段当作一个整体变量。
- 关联:[[crypto-rsa-e3-small-plaintext-integer-cube-root]](完全不知道高位、密文未模约减时直接开立方)、[[crypto-rsa-partial-prime-high-bits-coppersmith]](同类小根用于素数因子)、[[crypto-rsa-affine-broadcast-crt-coppersmith]](多模数 CRT 后再求小根)。
检测与防御
- 防御:使用 OAEP 等随机化填充,使明文整数不呈现“已知高位 + 小未知段”的结构。
- 防御:不要向外部泄露明文的任何连续比特;调试日志、报错信息、截断输出都可能成为泄露源。
- 检测:代码/接口中出现明文前缀、截断的十六进制串、或
m >> k之类的字段;CTF 中看到“已知 flag 前缀”与密文即可按本卡尝试。 - 响应:确认明文部分泄露后按密钥失陷处理,轮换密钥并审计同密钥下的历史密文。