一种确定的背包公钥密码体制的破译方法

陈成钢

(天津城建大学 理学院，天津 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 背包公钥密码体制

公钥密码体制也叫非对称的密码体制，它是这样设计的:用作加密的密钥不同于用作解密的密钥，而且解密的密钥不能根据加密密钥计算出来(至少在合理假定的时间内)。加密密钥能够公开，任何人都可以用加密密钥加密信息，但只有相应的解密密钥才能解密信息。

在背包公钥密码体制中，解密密钥为超递增增向量，但加密密钥却不是超递增增向量，利用求解一般背包问题的复杂性，使得只有持有有解密密钥的合法用户才可以解密得到明文，而其他持有加密密钥的人无法解密得到明文。

2.1 密码的选取

2.2 加密

背包公钥密码的加密就是由加密密钥B乘以明文X的转置X'得到密文L，即

2.3 解密

背包公钥密码由密文L和解密密钥(C，t，p)求得明文X的解密方法如下:

(1)先求间接密文L'=ztmodp;

(2)由间接密文L'和超递增序列C，用1.3超递增背包的解密方法，可求得明文向量X.

3 背包公钥密码体制的一种破译方法

3.1 预备知识

在讨论破译方法前，我们先给出以下定义、引理和定理，引理和定理的详细证明见参考文献［1］。

定义3.1称A=(a1，a2，…，an)为背包向量，如果ai，i=1，2，…，n为正整数，n＞2。

定义3.2对于n维背包向量A=(a1，a2，…，an)，如果

成立，那么i成为A的干扰点.

定义3.3背包向量B=(b1，b2，…，bn)是(A，z，m)可达的当且仅当A=(a1，a2，…，an)是超递增向量，z，m为正整数，m≥2 且z，m互素时，其中bi=(zaimodm)i=1，2，…，n。记为

引理3.1三元组(A，z，m)拥有一个目标(C，z，p)当且仅当

对A的所有干扰点i都成立，并且如果

成立，那么必有

定理3.1背包向量B=(b1，b2，…，bn)是超可达的当且仅当存在互素的正整数z，m，u＜m，maxB＜m≤2maxB;递增向量A=(a1，a2，…，an)满足

并且三元组(A，z，m)(zumodm=1，z＜ maxB)拥有一个目标(C，z，p)，这个目标满足

3.2 破译方法

给定加密密钥B=(b1，b2，…，bn)和密文L，由引理3.1和定理3.1，可得如下破译方法:

首先，求满足下面条件的正整数u，m，z和向量A:

(1)u＜m，maxB＜m≤2maxB且u，m互素;其中 maxB是b1，b2，…，bn中最大的数;

(2)uzmodm=1，且z＜maxB;

(3)A=(a1，a2，…，an)(ai=(ubimodm)，i=1，2，…，n)递增;

(4)若A有干扰点，则对A的所有干扰点i(3.2)式都成立;

(5)若 (3.3)式都成立，则(3.4)式成立;

其次，由上面三元组(A，z，m)拥有，求满足下面条件的非负整数t，p，k和向量C:

(1)C=(c1，c2，…，cn)(ci=ai+k［zai/m］，i=1，2，…n)超递增;

(3)tzmodp=1。

通过上面的计算可得三元组(C，z，p)，它就是三元组(A，z，m)的目标，也就是要求的解密密钥。利用此解密密钥和2.3的解密方法，可以很快地由密文解出明文X，整个破译过程完成。

3.3 破译方法正确性的验证

下面给出一个实例，以验证3.2破译方法的正确性:

假设给定加密密钥B=(10，15，22，14)和明文X=(1，0，1，1)，则加密后密文L=B×X'=46。现在，利用3.2破译方法，由已知的加密密钥B和密文L求破译所得明文X1。

由3.2 破译步骤，首先可求得m=23，u=14，z=5，A=(2，3，9，12);其次，由所得m，u，z，A可进一步求得k=3，p=38，t=23，C=(2，3，12，18)。由(C，t，p)和 2.3 的解密方法易得

显然，破译所得明文X1和实际明文X完全相同，所以3.2破译方法完全正确。

4 结束语

与统计分析破译法相比，本文介绍的破译方法更简单、快速，具有更高的使用价值。同时，我们会发现破译所得解密密钥可能不唯一。例如3.3所给的例子的解密密钥(C，t，p)就有可能为((2，3，12，18)，23，38)或((2，3，13，20)，26，43)，他们的价值虽然不同，但都是正确的解密密钥。

［1］Merkl R C，Hellman M E.Hiding information and signatures in trapdoor knapsacks［J］.IEEE Trans.on lnfo.Theory，1978，24(5):525-530.

［2］Shamir A.A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem［C］.Symp.Found.Computer Sci，1983(23):145-152.

［3］Brickell E F，Odlyzko A M.Cryptanalysis:A Survey of Recent Results［J］.Proc.IEEE，1988(76):578-593.

［4］何敬民，卢开澄.背包公钥密码系统的安全性与设计［J］.清华大学学报:自然科学版，1988，28(1):89-97.

［5］罗坤杰，罗文俊.基于ECDLP的背包公钥密码体制［J］.信息安全与通信保密，2008(7):83-85.

［6］王衍波.一种新的背包公钥密码体制［J］.解放军理工大学学报，2001(4):29-33.