RSA 素数比特分段残缺:一元/二元/三元 Coppersmith 按未知块数分档求解
crypto/rsa · verified
一句话结论
题目只给出素数 p 的若干比特段(高位+低位、或中间 768 bit、或 5 段里 3 段各 64 bit 全缺),本质都是“已知部分比特的因子分解”:未知段连续时用一元 small_roots、未知段两侧各缺一块时用二元 Coppersmith、未知段被切成 3 个独立小块时用 Herrmann-May 多元格 + Jacobian/Newton 求根,逐档升级即可把 1024 bit 的 p 拼回来。
原理
- 共同骨架:已知
N = p·q与p的比特位掩码泄漏值a,把缺失比特写成若干未知量x_i,构造模N的多项式并求其小根。因为p整除N,所以f(x) ≡ 0 (mod p),p是N的一个大因子,small_roots的界随未知比特总量与beta变化。 - 一元档(缺一段连续比特):
f(x) = p_h + x·2^k + p_l,未知量只有x一个、上界2^k。beta取 0.4~0.5 时k可达 256 bit 左右(N2048 bit)。 - 二元档(中间已知、两侧各缺一块):
f(x,y) = x·2^(1024-k) + p_m·2^k + y,两个未知量都小于2^k。用二元 Coppersmith(对y^h x^i f^j组格、LLL 后对消元结果取gcd再roots())同时解出x、y;本例两侧各 128 bit。 - 三元档(缺多段、彼此不相邻):
p被切成p1|p2|p3|p4|p5,其中p1/p3/p5各 64 bit 未知。多项式变成含 3 个变量的线性多项f = a + x0·2^960 + x1·2^480 + x2;用 Herrmann-May 的m阶移位多项式组(f^k·N^(t-k)按总次数枚举)建格、LLL(维数大时用flatter代替 Sage 的LLL)得到若干短向量多项式,再用 Jacobian + Newton 迭代或 Gröbner 基在ZZ上求公共零点。 - 为什么多元可行:LLL 后的短向量多项式与原多项式在根处同为零(相差
N的倍式),当未知量上界之积小于格的判定阈值时,这些多项式的公共根就是真实根;未知量个数多时格维数与判定阈值同时变差,所以 3×64 bit 已接近手工可解上限。 - 对齐陷阱:以上所有位移都按 bit 计;
generate_polynomial之类工具按十六进制字符模板?生成,4 bit 一格,写错一位就整条链失败。原文最后一档用一个?模板字符串生成多项式,正是这个思路的自动化。
触发条件
- 已知
N、e(此处e=65537)与p的部分比特(分段掩码泄漏)。 - 未知比特总量在 Coppersmith 界内:一元 ≤
N^(1/e)量级对应beta下的界;多元时未知量个数 ≤ 3、每块 ≤ 64 bit 较稳。 - 能运行 Sage;多元档建议装
flatter(LLL 维数上百时 Sage 自带LLL会非常慢)。 - 密文用 AES 包裹时还需要先解出
p、q才能算d。
利用步骤
- 由
a(掩码后的p)还原已知比特段:p_h = a >> (1024 - 384) << (1024 - 384)、p_l = a % 2**384之类;用mask的置零位置判断缺口长度。 - 缺一段连续比特 → 一元:
f = p_h + x*2^k + p_l,f.monic().small_roots(X=2^k, beta=0.4)。 - 中间已知、两侧各缺 → 二元:
f = x*2^(1024-k) + p_m*2^k + y,自实现bivariate(f, 2^k, 2^k, kk=4~5),用resultant+gcd求x、y。 - 缺 3 段各 64 bit → 三元:按模板生成
f(x0,x1,x2),multivariate(f, bounds, implementation="herrmann_may", algorithm="jacobian", m=5);LLL 用flatter。 - 拼回
p,q = N // p,验证p*q == N且is_prime(p);再d = inverse(e, (p-1)*(q-1))解 RSA 拿 AES key,逐层解密(原文三层嵌套,每层掩码不同,需重跑一遍)。 - 拿到的 AES key 解
part_N_encrypted之类的密文,得到下一层压缩包,递归处理直到 flag。
PoC
# sage 10.4;多元档需 flatter
from Crypto.Util.number import long_to_bytes, inverse
# ---- 一元档:缺一段连续比特 ----
p_h = a >> (1024 - 384) << (1024 - 384)
p_l = a % 2**384
R.<x> = PolynomialRing(Zmod(N))
f = p_h + x * 2**384 + p_l
r = f.monic().small_roots(X=2**256, beta=0.4)
p = p_h + int(r[0]) * 2**384 + p_l
# ---- 二元档:中间已知、两侧各缺 unknown bit ----
unknown = 128
p_m = a >> unknown
R.<x, y> = PolynomialRing(Zmod(N))
g = x * 2**(1024 - unknown) + p_m * 2**unknown + y
xr, yr = bivariate(g, 2**unknown, 2**unknown, 5) # 自实现:LLL + resultant + gcd
p = int(xr) * 2**(1024 - unknown) + p_m * 2**unknown + int(yr)
# ---- 三元档:3 段各 64 bit 未知(见上文的模板生成 + Herrmann-May)----
q = N // p
d = inverse(65537, (p - 1) * (q - 1))
print(long_to_bytes(pow(ct, d, N)))
变体与关联
- 变体:掩码形状变化时不必换算法,只需重算
p_h/p_m/p_l与未知量系数;三元档可用十六进制?模板自动生成多项式。 - 变体:多元档若 Jacobian 迭代不收敛,可改用 Gröbner 基(
I.variety(ring=ZZ))并加超时枚举子方程组。 - 关联:[[crypto-rsa-multiprime-partial-key-coppersmith]](高位泄漏 +
beta逐档下调)、[[crypto-rsa-crt-multi-modulus-high-bits-coppersmith-low-bits]](先 CRT 拼出高位再一元求低位)、[[crypto-rsa-bivariate-coppersmith-two-small-roots]](自实现二元 Coppersmith 的通用写法)。
检测与防御
- 防御:不要把素数的任何比特段(掩码结果、高位截断、分块拼接)对外输出;调试日志中打印
p & mask等于直接泄密。 - 防御:密钥生成后按位校验输出内容,禁止十六进制/十进制分段打印;CTF 之外这类“部分比特”泄漏常来自内存 dump 截断。
- 检测:代码里出现
p >> k、p & mask、bin(p)[:n]等对素数做截取并打印的位置。 - 响应:确认素数部分比特泄露后,该模数必须整体作废并重新生成密钥对。