♧ Godown 安全知识树

乱序超递增私钥背包:升序排序恢复超递增结构贪心求解,再按原下标把 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 时尤其明显,错序会得到乱码)。

利用步骤

  1. 复制原列表 pub,升序排序得到 a(保留 pub 用于回填)。
  2. 若有模变换:对每个密文块 c 计算 w = c·n⁻¹ mod m;否则 w = W。
  3. 从 a 的最大项倒序贪心:w ≥ a_k 则该元素入选并 w -= a_k,否则不选。
  4. 对每个被判定过的元素 a_k,用 pub.index(a_k) 得到它在原列表中的下标 id,把 1/0 写到输出向量 b[id]。
  5. 校验最终 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)按私钥级别保护,不以任何可推断顺序/结构的形式外泄。
  • 加固:教学演示中把「顺序」也视为密钥的一部分,避免同时公开元素集合与目标值;对解密实现做位序回填的单元测试,防止错序输出被误判为算法失败。