4.4 背包算法

第一个推广的公开密钥加密算法是Ralph Merkle和Martin Hellman开发的背包算法，它只能用于加密。背包算法的安全性基于背包问题，这是一个NP完全问题。尽管目前已经有攻击基本Merkle-Hellman体制的多项式时间算法，但该算法表示了如何将NP完全问题用于公开密钥算法，从这个意义上讲，它还是值得研究的。

4.4.1 背包问题和背包算法的思想

背包问题可以描述如下：给定重量分别为a1，a2，…，an的n个物品，装入一个背包中，要求重量等于一个给定值。那么，究竟是那些物品？这个问题可以形式化地描述为一个0-1 背包问题：给定一个正整数S和一个背包向量A =（a1，…，an），其中ai是正整数，问是否存在满足方程S =∑aixi的二进制向量X =（x1，…，xn）？这是一个NP完全问题，因为对于给定的子集易于验证其和是否为S。然而，找到一个子集使其和为S要困难得多，因为有2n个可能的子集，试验所有子集的时间复杂性为T = O（2n），目前的算法解决这个问题所需要的时间与n呈指数增长。

背包问题用于公钥密码学的基本做法是假设明文为X，S为密文。奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能。容易的背包可以修改成难解的背包，公开密钥使用难解的背包，可以很容易地用来加密，但不能解密，私钥使用易解的背包，可以很容易地解密消息，不知道私钥的人只能求解难解的背包问题。

4.4.2 超递增背包

容易解的背包问题是：如果物品重量的列表为一个超递增序列，则此背包问题容易解决。超递增序列是满足下列特征的序列：其中每个元素都大于前面所有元素的和。我们把满足下列条件的背包ai >∑aj（j = 1，2，…，i-1），也称为简单背包。超递增背包的求解过程为：从最大的ai开始，如果S大于这个数，则减去ai，记xi为1，否则记xi为0，如此下去，直到最小的ai。

例如，背包序列{2，3，6，13，27，52}，求解70的背包，结果为{2，3，13，52}，所以，密文70对应的明文为110101。

4.4.3 转换背包

我们把简单背包用做私钥，如何产生相应的公钥呢？具体的转换做法为：

选择一个整数m >∑ai（i = 1，2，…，n），然后选择一个与m互素的整数w，进行计算ai′=wai（mod m）（i = 1，2，…，n），这里的ai′是伪随机分布的，这样得到的背包是非超递增背包，即一般的背包。一般的背包问题是一个困难的问题，没有已知的快速算法。要确定一个元素是否在背包中的一般方法是依次测试所有可能的解，直到找到正确的解。

4.4.4 Merkle-Hellman公钥算法

Merkle-Hellman公钥算法的加解密过程可以描述如下。

加密：

● 将明文分为长度为n的块X =（x1，x2，…，xn）。

● 然后用公钥A′=（a1′，a 2′，…，an′），将明文变为密文S = E（X）=

解密：

● 先计算S′= w-1S mod m。

● 再求解简单背包问题。

选择一个简单背包作为私钥，例如{2，3，6，13，27}。令w = 31，m = 105，进行下列计算：

2×31mod105=62

3×31mod105=93

6×31mod105=81

13×31mod105=88

27×31mod105=102

这样就得到一个一般背包{62，93，81，88，102}，我们将它作为公钥。

假设要加密一个二进制消息，首先将它分成长度与背包序列等长的块。1表示元素在背包中，0表示不在，对每个明文，计算对应的密文。如消息为011001101010111，用前面的背包加密。

密文93 + 81 = 174

01100对应于93 + 81 = 174

11010对应于62 + 93 + 88 = 243

10111对应于62 + 81 + 88 +102 = 333

则密文为174，243，333。

消息的合法接收者知道私钥{2，3，6，13，27}与w和m的值。解密时，先计算w-1，满足w（w-1）=1mod m，可以使用扩展的Euclid算法，求得w-1=61。

然后进行解密计算

174×61 mod 105=9=3+6，对应于01100

243×61 mod 105=18=2+3+13，对应于11010

333×61 mod 105=48=2+6+13+27，对应于10111

因此，消息= 011001101010111。

一个只有5 个元素的背包序列，即使不是超递增的，也不难解。实际的背包应该包括至少250个元素。超递增背包中的每项应该有100到200位长，模应该有200到400位长。实际实现时，用随机序列发生器来产生这些值。这样的背包才能抵抗强力攻击。