已知格式前后缀的子集和:CVP 格约减恢复 64 位二进制明文
ctf/crypto · verified
一句话结论
enc = Σ pubkey[i]·bit[i] mod p 且明文二进制位是 0/1、flag 的固定前缀 LitCTF{ 与后缀 } 已知时,把已知位的贡献从 enc 中扣除,剩余未知位构成标准子集和;用「单位阵 + 加权向量」构造格并把常数项配成 1/2 的 CVP 嵌入后 LLL,即可直接读出 64 位 0/1 解。
原理
- 子集和(背包)问题是 NP 难的,但当维数不大且解是 0/1 短向量时,格约减能在多项式时间内找到它(Lagarias-Odlyzko 攻击)。
- 已知前缀/后缀的比特后,把它们对应的
pubkey[i]从enc中减掉,未知位只剩 64 个;同时enc与Σ pubkey[i]·bit[i]相差整数倍p,需枚举商k(s = enc + k·p),k的取值由已知位贡献的量级估出初值k0,只需在其附近小范围搜索。 - 构造格
L = [[I_n, N·W^T], [1/2·1_n, N·s]], 其中W = pubkey[未知位]、N ≈ sqrt(n)为放大系数、1/2·1_n一行用于把「解向量」平移到±1/2的对称位置。 - 若
x是 0/1 解,则向量(x - 1/2·1, 0)属于格:(x - 1/2·1)·1_n = ±1/2之和只有n/2个±1/2;格中该向量长度为O(sqrt(n)),而随机向量长度约为N·|pubkey|,相差悬殊。LLL 约减后取前n个分量,把±1/2还原成 0/1 即得明文位。 - 为什么用
1/2平移:0/1 向量没有「短」的几何特征(长度为sqrt(64)),但x - 1/2各分量恒为±1/2,方差最小,LLL 才能稳定约出;这是把 CVP 转成 SVP 的标准技巧。
触发条件
- 背包向量
pubkey个数(位长)与模数p已知,明文位数不超过约 100(维数过高时 LLL 失效); - 明文的固定格式(flag 前后缀)已知,可扣除对应比特;
- 解是严格 0/1 且无噪声(
enc精确等于加权和模p)。
利用步骤
- 把已知前缀/后缀转成比特串,计算其对
enc的贡献sum_known,并估计商k0 = sum_known // p。 - 对
k在k0附近小范围枚举(几十次内),令s_ = enc + (k + k0)·p - sum_known。 - 取未知位对应的
pubkey子集W,构造上面的格L并LLL。 - 对每个约减基向量取前
n个分量,分别尝试x + 1/2与1/2 - x,若结果集合为{0,1}则按 8 位一组转 ASCII,拼回前缀/后缀即为 flag。 - 若一次 LLL 未命中,调整
N(如ceil(sqrt(n)))或扩大k的搜索范围。
PoC
from Crypto.Util.number import long_to_bytes, bytes_to_long
from sage.all import matrix, identity_matrix, ones_matrix, ZZ, QQ, ceil, sqrt
p = 173537234562263850990112795836487093439
s = 82516114905258351634653446232397085739 # enc
pubkey = [...] # 长度 = flag 位数
w = pubkey[8 * 7 - 1:-8] # 去掉已知前缀/后缀后的未知位
n = len(w)
N = ceil(sqrt(n))
front = bin(bytes_to_long(b'LitCTF{'))[2:]
end = bin(bytes_to_long(b'}'))[2:]
sum_front = sum(pubkey[i] * int(front[i]) for i in range(len(front)))
sum_end = sum(pubkey[i + 127 - 7] * int(end[i]) for i in range(len(end)))
k0 = (sum_front + sum_end) // p
E = identity_matrix(ZZ, n)
W = matrix(QQ, 1, n, w)
for k in range(70):
s_ = s + (k + k0) * p - (sum_front + sum_end)
L = block_matrix([[E, N * W.T], [ones_matrix(QQ, 1, n) / 2, N * s_]])
M = L.LLL()
for i in range(65):
for sign in (1, -1):
bits = [(v + sign * QQ(1, 2)) for v in M[i][:n]]
if set(bits).issubset({0, 1}):
bs = ''.join(str(int(b)) for b in bits)
print('LitCTF{' + ''.join(chr(int(bs[j:j+8], 2)) for j in range(0, len(bs), 8)) + '}')
变体与关联
- 变体:明文含噪声或非 0/1 小系数时,用「小系数背包」并通过
N调参;维数更大时可分批(分块)求解再利用已知前缀拼接。 - 变体:
enc不是模p而是整数(无模约减)时是纯 SVP,直接对[[I, N·W^T]]约减即可。 - 关联:[[ctf-crypto-hnp-2h-continued-fraction-kannan-embedding]](同类 CVP→SVP 嵌入)、[[ctf-crypto-lll-hidden-short-vector-kannan-embedding-lwe]](Kannan 嵌入)。
- 边界:维数过大(>150)或明文位分布无结构(无法估
k)时需改用 BKZ 或更多已知信息。
检测与防御
- 检测(CTF 视角):看到「每位乘一个大素数再求和取模」且明文字符集已知,直接套格攻击而不是爆搜。
- 防御(实现视角):不要用低维背包做加密;若必须,使用带随机化的背包(Merkle-Hellman 已被攻破),维数需远高于可约减范围并加入噪声。