背包问题 | GHL's Blog

给定一个由正整数列表 $(M_1,M_2,...,M_n)$ 和另一个整数 $S$ （目标和）。问题在于找到该列表的一个子集，使其元素之和恰好等于 $S$ 。

这个问题也可以用二进制向量来描述：寻找一个二进制向量 $x = (x_1,x_2,...,x_n)$ ，使得 $S=\sum_{i=1}^{n} x_i M_i$ ，向量 $x$ 中的1小时对应位置的整数 $M_i$ 被选中加入子集。

问题的困难性

一般情况：子集和问题通常是一个NP-complete问题，这意味着在计算上通常被认为是困难的

暴力破解：通过检查所有可能的 $2^n$ 个二进制向量可以找到解，但效率特别低。

碰撞算法：存在一种碰撞算法，可以将运行时间缩短到 $O(2^{2/n})$ ，但需要巨大的存储空间。

如果整数列表 $r = (r_1,r_2,...,r_n)$ 是超递增的，那么这个问题就会变得特别容易解决。

定义：一个序列是超递增的，如果每一项都大于前面所有项的和，即 $r_{i+1} \geq \sum_{j=1}^i r_j$
解法：对于超递增序列，可以使用贪心算法快速找到解，从最大元素 $r_n$ 开始，如果 $S \geq r_i$ ，则把 $x_i$ 设为1并从 $S$ 中减去 $r_i$ ，否则 $x_i$ 设为0

Merkle和Hellman利用上述特性设计了一种公钥密码系统，其核心思想是将一个“易解”的超递增子集和问题，通过模运算“伪装”成一个看似困难的一般子集和问题

密钥生成：
- 私钥：一个超递增序列 $r=(r_1,r_2,...,r_n)$ ，以及两个大整数 $A,B$ ，满足 $B > 2r_n$ 且 $gcd(A,B)=1$
- 公钥：一个伪装后的序列 $M=(M_1,M_2,...,M_n)$ ，其中 $M_i \equiv Ar_i \pmod B$ ，这个序列 $M$ 看起来不再是超递增的
加密：发送方将明文消息转化为二进制向量 $x$ ，计算密文 $S= x · M$ 发送给接受者
解密：接收方（拥有私钥 $A,B$ ），首先计算 $S'=A^{-1}S\pmod B$ 。由于 $B$ 很大，这个同余式实际上是一个等式 $S'=\sum x_ir_i$ 。接收方随后利用超递增序列 $r$ 轻松解出 $x$ 。

主要弱点：教材指出，背包密码系统的根本弱点在于，它可以被重新表述为格中寻找短向量的问题
攻击方法：攻击者可以构造一个特定的格，其中包含公钥 $M$ 和密文 $S$ 。如果使用格基规约算法（例如 LLL算法）找到了该格中的一个特定短向量，就能直接恢复出明文 $x$ 。

假设公钥序列为 $M=(M_1,M_2,...,M_n)$ ，密文为 $S$ 。攻击者希望找到二进制向量 $x=(x_1,x_2,...,x_n)$ 使得 $S=\sum_{i=1}^n x_iM_i$

构造如下 $(n+1)\times(n+1)$ 矩阵：

\begin{pmatrix} 2 & 0 & 0 & \cdots & 0 & m_{1} \\ 0 & 2 & 0 & \cdots & 0 & m_{2} \\ 0 & 0 & 2 & \cdots & 0 & m_{3} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 2 & m_{n} \\ 1 & 1 & 1 & \cdots & 1 & S \end{pmatrix}

格的基：这个矩阵的每一行构成了一个格 $L$ 的基向量。记前 $n$ 行为 $v_1,v_2,...,v_n$ 最后一行为 $v_{n+1}$ 。
目标短向量：如果存在解 $x=(x_1,x_2,...,x_n)$ ，那么格 $L$ 中必然包含一个特定的短向量 $t$ 。这个向量可以通过基向量的线性组合得到： $t = \sum_{i=1}^nx_iv_i-v_{n+1}$
向量的分量：
- 前 $n$ 格分量为 $2x_i-1$ 。由于 $x_i$ 只能是 0 或 1 ，所以这些分量的值只能是 1 或 -1。
- 最后一个分量为 $\sum x_i m_i - S$ 。因为 $x$ 是解，所以这个和等于 $S$ ，因此最后一个分量为 0
- 所以，这个特定的短向量 $t$ 的形式为 $(\pm 1,\pm 1,...,\pm 1, 0)$
这个向量 $t$ 的长度为 $\sqrt n$ ，这相对于格中其他向量（通常长度很大，与 $m_i$ 和 $S$ 的大小有关）来说非常小。使用格基规约算法（如 LLL算法）很有可能找到这个异常短的向量 $t$ ，从而恢复出 $x_i$ 的值（如果 $t$ 的第 $i$ 个分量是 1，则 $x_i=1$ ，反之为 0），破解密码系统。