乱序超递增私钥背包:升序排序恢复超递增结构贪心求解,再按原下标把 0/1 位写回打乱前的顺序
ctf/crypto · draft
一句话结论
题目给出的「私钥」是一组被打乱顺序的超递增序列元素时,不能按题面顺序贪心;必须先升序排序恢复超递增结构、从最大项倒序贪心求出被选中的元素集合,再用每个被选元素在原列表中的下标 pub.index(a) 把 0/1 位写回原位置,才能得到与原始序列元素一一对应的明文位串。
原理
- 贪心唯一性依赖超递增顺序:只有「当前项大于前面所有项之和」时,
W ≥ a_k才能推出b_k = 1、W < a_k推出b_k = 0。乱序后前缀和不再小于当前项,按原序比较W与a_i不再具有判定意义,贪心失效。 - 排序不改变解集:背包解是「选中哪些元素」的集合,与元素排列顺序无关。升序排序后该列表严格满足
a'_k > Σ_{i<k} a'_i,贪心可唯一确定被选中集合。 - 位序与原始列表绑定:明文第
i位对应原列表第i个元素,所以求解后必须做「元素值 → 原下标」映射回填。超递增序列严格递增,元素两两不同,index映射无歧义。 - 若题目还叠加了模变换(公钥
d_i = a_i·n mod m、密文块),则先对每块做W = c·n⁻¹ mod m,再进入排序贪心流程;模变换与排序互不影响。 - 与「顺序正确」的背包解密区别:本场景多出排序 + 下标回填两步,若省略回填直接按排序后顺序输出位串,得到的比特流会错位、无法还原明文。
触发条件
- 题面给出一组数(被称为私钥/背包元素)与目标
W或密文块,且这组数升序排序后满足严格超递增; - 元素互不相同(保证值到下标映射唯一);
- 明文位序按题面列表原始顺序解释(拼字节/ASCII 时尤其明显,错序会得到乱码)。
利用步骤
- 复制原列表
pub,升序排序得到a(保留pub用于回填)。 - 若有模变换:对每个密文块
c计算w = c·n⁻¹ mod m;否则w = W。 - 从
a的最大项倒序贪心:w ≥ a_k则该元素入选并w -= a_k,否则不选。 - 对每个被判定过的元素
a_k,用pub.index(a_k)得到它在原列表中的下标id,把 1/0 写到输出向量b[id]。 - 校验最终
w == 0(否则说明序列不超递增或参数有误);按 8 位一组及题目约定转字节/flag。
PoC
def decrypt_shuffled(pub, w):
a = sorted(pub) # 恢复超递增顺序
b = [None] * len(pub)
for x in reversed(a): # 从最大项倒序贪心
idx = pub.index(x) # 值唯一 -> 原下标
if w >= x:
w -= x
b[idx] = 1
else:
b[idx] = 0
assert w == 0
return b
pub = [10256, 299892, 78079, 158237, 325493403, 39577,
2705097, 5549493, 914840, 56822699, 109710911, 19185489]
w = 329321410
print(decrypt_shuffled(pub, w))
# [1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0]
已在本地用纯数论脚本核对:排序后序列确为超递增,求解余数为 0 且加权和等于 W。
变体与关联
- 关联:顺序正确、无打乱的 Merkle-Hellman 私钥解密见 [[ctf-crypto-superincreasing-knapsack-merkle-hellman-decrypt]];本卡是其乱序输入变体,额外需要排序与下标回填。
- 变体:元素若可能重复,
index映射不再唯一,需依赖题目额外线索(位置约束、校验和)消歧;严格超递增序列本身排除重复。 - 变体:多块明文时每块分别求解后按块序拼接;注意位序(MSB/LSB first)与补位约定。
- 变体:若打乱发生在公钥上而私钥仍有序,则公钥顺序决定加密位序,解密输出需按公钥原序解释,思路相同。
- 边界:只给公钥、无超递增私钥时不能贪心,属低密度子集和,需格攻击路线,见 [[ctf-crypto-subset-sum-known-prefix-lll-cvp]]。
检测与防御
- 检测(CTF 识别):题面给出的一组数排序后满足
a_k > Σ_{i<k} a_i,但题面顺序与之不同,且要求输出位串/明文——即「乱序超递增背包」特征。 - 检测(真实环境):自定义背包类加解密实现中,私钥元素以无序集合/字典形式存储,且解密代码直接按存储顺序做贪心(错误实现)或依赖排序回填(本卡逻辑);密钥材料以明文出现即视为泄露。
- 防御:不要在生产中使用 Merkle-Hellman/背包类自定义公钥密码,改用标准算法;私钥参数(超递增序列、
m、n)按私钥级别保护,不以任何可推断顺序/结构的形式外泄。 - 加固:教学演示中把「顺序」也视为密钥的一部分,避免同时公开元素集合与目标值;对解密实现做位序回填的单元测试,防止错序输出被误判为算法失败。