陈成钢

(天津城建大学 理学院，天津 300384)

1 背包问题

1.1 背包问题定义

公钥密码系统一直是密码学研究的重要领域之一。1979年，Merkle和Hellman［1］提出背包公钥密码体制，由于背包序列在转换机制上有弱点，1983年Shamir［2］完全破译了Merkle-Hellman的背包公钥密码体制。但由于基于背包问题的公钥密码系统加解密速度快，许多更加复杂的公钥密码系统被提了出来［3-5］。同样，许多破译背包系统地方法也被提了出来［3］［6］［7］。本文利用密钥的超可达性，提出了一个新的确定的破解背包公钥密码体制的方法。

所谓背包问题:即给定重量分别为a1，a2，…，an的n个物品，现在能否把这n个物品中的几件放入一个背包中使之等于一个给定的重量L?

其中a1，a2，…，an和L都是正整数。

显然，背包问题的求解是NP完全问题，如果直接对其求解，以n=100为例，用每秒搜索107种的计算机进行穷举，一年只能完成3.1536×1014次，而完成所有的搜索，共需2100÷(3.1536×1014)

=4.02×1015(年)，这在时间上显然是不允许的。

1.2 递增、超递增序列

我们称a1，a2，…，an为递增(超递增)序列，如果它满足

称满足上式的A=(a1，a2，…，an)为递增(超递增)向量。

1.3 超递增背包问题的求解

并非所有的背包问题都是难解的，如果背包密钥A=(a1，a2，…，an)为超递增，那么此背包问题就是超递增背包问题。对于超递增背包问题有快速的求解方法:

(1)设L0=L，比较L0与an，如果L0≥an，那么取xn=1，否则，取xn=0;

(2)设L1=L0-xnan，比较L1与an-1，如果L1≥an-1，那么取xn-1=1，否则，取xn-1=0;

(3)如此下去，得到一系列的Li，xi，i=n，n-1，…，1，则向量X=(x1，x2…，xn)就是要求的解(明文)。

例如:L=120，A=(3，5，11，31，75，140)，那么由上面的方法可解得X=(1，0，1，1，1，0)。

2 背包公钥密码体制

公钥密码体制也叫非对称的密码体制，它是这样设计的:用作加密的密钥不同于用作解密的密钥，而且解密的密钥不能根据加密密钥计算出来(至少在合理假定的时间内)。……