Crypto-Knapsack Problem
背包密码体制
背包密码体制(Knapsack Cryptosystem)是一类基于背包问题构造的公钥密码方案。它的基本思想是:将明文比特串映射为一个整数,再通过一组权重的线性组合生成密文。
1. 背包问题
经典背包问题可以表述为:给定一组正整数
以及一个目标值 (W),判断是否存在一组二进制变量 (x_i \in 0,1),使得
如果允许穷举所有 (2^n) 种组合,那么该问题可以直接求解;但当 (n) 较大时,穷举代价会迅速增长,因此背包问题具有较高的计算复杂度。
背包密码体制正是利用了这一点:对外公开一个看似难以求解的背包实例,使攻击者难以从密文恢复明文。
2. 基本加密思想
设明文是一个 (n) 位二进制串
给定一组公开权重
则可以把密文构造为:
从形式上看,这就是把明文比特作为系数,去选择性地累加某些权重。
如果这些权重没有额外结构,那么从 (C) 反推出 (x) 一般是困难的,这正是背包密码的设计基础。
3. 超递增序列
为了便于解密,可以构造一类特殊的序列,称为超递增序列(superincreasing sequence)。它满足:
也就是说,每一项都大于前面所有项之和。
例如:
就是一个超递增序列,因为它满足:
依次类推。
3.1 为什么它容易解密
如果使用超递增序列加密,那么解密可以从后向前进行:
- 如果当前密文 (C) 大于某一项 (a_i),则说明对应的 (x_i = 1)
- 否则,说明 (x_i = 0)
确定 (x_i) 后,再令
继续判断下一项即可。
由于每一项都大于前面所有项之和,所以这种贪心判断是正确的。
4. 简单超递增背包体制
设私钥为一个超递增序列:
给定明文比特串 (x_1, x_2, \dots, x_n),加密为:
解密时,按从后向前的顺序恢复:
- 判断 (C) 是否大于 (w_n)
- 若是,则 (x_n = 1),并令 (C \leftarrow C - w_n)
- 否则 (x_n = 0)
- 对 (w_{n-1}, w_{n-2}, \dots, w_1) 重复上述过程
这种方案的缺点也很明显:如果直接公开超递增序列,那么攻击者同样可以用贪心算法轻松解密,因此它不能直接作为公钥方案使用。
5. 由私钥到公钥
为了让系统具备公钥密码体制的特点,通常会对超递增序列进行变换。
一种经典做法是:
- 选取超递增序列 (w_1, w_2, \dots, w_n)
- 选取模数 (m),满足
- 再选取整数 (r),使得
然后构造公开序列:
此时:
- (w_i) 是私钥中的结构化序列
- (a_i) 是公开发布的背包序列
5.1 加密
对明文比特串 (x_1,\dots,x_n),密文为:
5.2 解密
解密时,先利用 (r) 的模逆:
将密文恢复到私钥背包对应的形式:
然后对超递增序列 (w_i) 使用贪心算法恢复明文。
6. Merkle-Hellman 背包密码体制
最著名的背包公钥密码体制是 Merkle-Hellman Knapsack Cryptosystem。其核心思路就是:
- 选一个超递增序列作为私钥
- 通过模乘变换生成看似随机的公开序列
- 用公开序列加密
- 用私钥结构高效解密
这种设计在早期被认为很有希望,因为公开背包看起来像一个一般的 NP 难问题实例。
7. 一个简单例子
假设私钥超递增序列为:
选择模数和乘数:
则公开序列为:
即:
若明文比特串为:
则密文为:
解密时,先计算:
然后:
注意到:
因此对应的明文比特串正是 (X = (1,0,1,0,1))。
再用超递增序列 (W) 做贪心分解:
- (39 \ge 30),第 5 位为 1,剩余 (9)
- (9 < 14),第 4 位为 0
- (9 \ge 7),第 3 位为 1,剩余 (2)
- (2 < 3),第 2 位为 0
- (2 \ge 2),第 1 位为 1,剩余 (0)
由此恢复出原始比特串。
这个例子中,公开序列和私钥序列之间的对应关系是严格一致的,因此加密和解密过程可以完整闭合。
8. 安全性问题
背包密码体制曾经受到过较多研究,但后来发现许多早期方案存在明显缺陷,尤其是 Merkle-Hellman 方案。其主要问题包括:
- 公开背包与私钥结构之间关系过于简单
- 公开序列可能被格基方法分析
- 某些参数选择下容易被还原出私钥结构
因此,经典背包密码体制并没有像 RSA 那样长期成为主流公钥算法。
9. 背包密码与格攻击
公开背包问题虽然表面上看像 NP 难问题,但如果参数设计不当,往往会暴露额外结构。例如:
- 序列具有近似超递增特征
- 模数和乘数选择不理想
- 公开向量之间存在可利用关系
这类结构可以被格方法利用,从而恢复原始私钥或明文。
10. 总结
背包密码体制的核心思路是将明文编码为若干二进制系数,再通过权重求和形成密文。它的关键点在于:
- 一般背包问题求解困难
- 超递增序列可以高效解密
- 公钥方案需要对私钥结构进行隐藏
- 经典方案存在较明显的安全缺陷
因此,背包密码体制更适合作为密码学发展史中的重要实例来理解,而不是现代主流加密方案。










