背包密码体制

背包密码体制(Knapsack Cryptosystem)是一类基于背包问题构造的公钥密码方案。它的基本思想是:将明文比特串映射为一个整数,再通过一组权重的线性组合生成密文。

1. 背包问题

经典背包问题可以表述为:给定一组正整数

\[ a_1, a_2, \dots, a_n \]

以及一个目标值 (W),判断是否存在一组二进制变量 (x_i \in 0,1),使得

\[ \sum_{i=1}^{n} x_i a_i = W \]

如果允许穷举所有 (2^n) 种组合,那么该问题可以直接求解;但当 (n) 较大时,穷举代价会迅速增长,因此背包问题具有较高的计算复杂度。

背包密码体制正是利用了这一点:对外公开一个看似难以求解的背包实例,使攻击者难以从密文恢复明文。

2. 基本加密思想

设明文是一个 (n) 位二进制串

\[ x = (x_1, x_2, \dots, x_n), \quad x_i \in 0,1 \]

给定一组公开权重

\[ a_1, a_2, \dots, a_n \]

则可以把密文构造为:

\[ C = \sum_{i=1}^{n} x_i a_i \]

从形式上看,这就是把明文比特作为系数,去选择性地累加某些权重。

如果这些权重没有额外结构,那么从 (C) 反推出 (x) 一般是困难的,这正是背包密码的设计基础。

3. 超递增序列

为了便于解密,可以构造一类特殊的序列,称为超递增序列(superincreasing sequence)。它满足:

\[ a_i > \sum_{k=1}^{i-1} a_k, \quad i=2,3,\dots,n \]

也就是说,每一项都大于前面所有项之和。

例如:

\[ 1,\ 3,\ 6,\ 11,\ 23,\ 45 \]

就是一个超递增序列,因为它满足:

\[ 3 > 1, \quad 6 > 1+3, \quad 11 > 1+3+6, \]

依次类推。

3.1 为什么它容易解密

如果使用超递增序列加密,那么解密可以从后向前进行:

  • 如果当前密文 (C) 大于某一项 (a_i),则说明对应的 (x_i = 1)
  • 否则,说明 (x_i = 0)

确定 (x_i) 后,再令

\[ C \leftarrow C - x_i a_i \]

继续判断下一项即可。

由于每一项都大于前面所有项之和,所以这种贪心判断是正确的。

4. 简单超递增背包体制

设私钥为一个超递增序列:

\[ w_1, w_2, \dots, w_n \]

给定明文比特串 (x_1, x_2, \dots, x_n),加密为:

\[ C = \sum_{i=1}^{n} x_i w_i \]

解密时,按从后向前的顺序恢复:

  1. 判断 (C) 是否大于 (w_n)
  2. 若是,则 (x_n = 1),并令 (C \leftarrow C - w_n)
  3. 否则 (x_n = 0)
  4. 对 (w_{n-1}, w_{n-2}, \dots, w_1) 重复上述过程

这种方案的缺点也很明显:如果直接公开超递增序列,那么攻击者同样可以用贪心算法轻松解密,因此它不能直接作为公钥方案使用。

5. 由私钥到公钥

为了让系统具备公钥密码体制的特点,通常会对超递增序列进行变换。

一种经典做法是:

  • 选取超递增序列 (w_1, w_2, \dots, w_n)
  • 选取模数 (m),满足
\[ m > \sum_{i=1}^{n} w_i \]
  • 再选取整数 (r),使得
\[ \gcd(r,m)=1 \]

然后构造公开序列:

\[ a_i \equiv r w_i \pmod m \]

此时:

  • (w_i) 是私钥中的结构化序列
  • (a_i) 是公开发布的背包序列

5.1 加密

对明文比特串 (x_1,\dots,x_n),密文为:

\[ C = \sum_{i=1}^{n} x_i a_i \]

5.2 解密

解密时,先利用 (r) 的模逆:

\[ r^{-1} \pmod m \]

将密文恢复到私钥背包对应的形式:

\[ C' \equiv C \cdot r^{-1} \pmod m \]

然后对超递增序列 (w_i) 使用贪心算法恢复明文。

6. Merkle-Hellman 背包密码体制

最著名的背包公钥密码体制是 Merkle-Hellman Knapsack Cryptosystem。其核心思路就是:

  1. 选一个超递增序列作为私钥
  2. 通过模乘变换生成看似随机的公开序列
  3. 用公开序列加密
  4. 用私钥结构高效解密

这种设计在早期被认为很有希望,因为公开背包看起来像一个一般的 NP 难问题实例。

7. 一个简单例子

假设私钥超递增序列为:

\[ W = (2,3,7,14,30) \]

选择模数和乘数:

\[ m = 61, \quad r = 17 \]

则公开序列为:

\[ A_i \equiv 17W_i \pmod{61} \]

即:

\[ A = (34, 51, 58, 55, 22) \]

若明文比特串为:

\[ X = (1,0,1,0,1) \]

则密文为:

\[ C = 34 + 58 + 22 = 114 \]

解密时,先计算:

\[ r^{-1} \pmod{61} = 18 \]

然后:

\[ C' \equiv 114 \cdot 18 \pmod{61} \equiv 39 \]

注意到:

\[ 39 = 2 + 7 + 30 \]

因此对应的明文比特串正是 (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. 总结

背包密码体制的核心思路是将明文编码为若干二进制系数,再通过权重求和形成密文。它的关键点在于:

  • 一般背包问题求解困难
  • 超递增序列可以高效解密
  • 公钥方案需要对私钥结构进行隐藏
  • 经典方案存在较明显的安全缺陷

因此,背包密码体制更适合作为密码学发展史中的重要实例来理解,而不是现代主流加密方案。