陳成鋼

(天津城建大學(xué) 理學(xué)院，天津 300384)

1 背包問題

1.1 背包問題定義

公鑰密碼系統(tǒng)一直是密碼學(xué)研究的重要領(lǐng)域之一。1979年，Merkle和Hellman［1］提出背包公鑰密碼體制，由于背包序列在轉(zhuǎn)換機(jī)制上有弱點(diǎn)，1983年Shamir［2］完全破譯了Merkle-Hellman的背包公鑰密碼體制。但由于基于背包問題的公鑰密碼系統(tǒng)加解密速度快，許多更加復(fù)雜的公鑰密碼系統(tǒng)被提了出來［3-5］。同樣，許多破譯背包系統(tǒng)地方法也被提了出來［3］［6］［7］。本文利用密鑰的超可達(dá)性，提出了一個(gè)新的確定的破解背包公鑰密碼體制的方法。

所謂背包問題:即給定重量分別為a1，a2，…，an的n個(gè)物品，現(xiàn)在能否把這n個(gè)物品中的幾件放入一個(gè)背包中使之等于一個(gè)給定的重量L?

其中a1，a2，…，an和L都是正整數(shù)。

顯然，背包問題的求解是NP完全問題，如果直接對(duì)其求解，以n=100為例，用每秒搜索107種的計(jì)算機(jī)進(jìn)行窮舉，一年只能完成3.1536×1014次，而完成所有的搜索，共需2100÷(3.1536×1014)

=4.02×1015(年)，這在時(shí)間上顯然是不允許的。

1.2 遞增、超遞增序列

我們稱a1，a2，…，an為遞增(超遞增)序列，如果它滿足

稱滿足上式的A=(a1，a2，…，an)為遞增(超遞增)向量。

1.3 超遞增背包問題的求解

并非所有的背包問題都是難解的，如果背包密鑰A=(a1，a2，…，an)為超遞增，那么此背包問題就是超遞增背包問題。對(duì)于超遞增背包問題有快速的求解方法:

(1)設(shè)L0=L，比較L0與an，如果L0≥an，那么取xn=1，否則，取xn=0;

(2)設(shè)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 背包公鑰密碼體制

公鑰密碼體制也叫非對(duì)稱的密碼體制，它是這樣設(shè)計(jì)的:用作加密的密鑰不同于用作解密的密鑰，而且解密的密鑰不能根據(jù)加密密鑰計(jì)算出來(至少在合理假定的時(shí)間內(nèi))。加密密鑰能夠公開，任何人都可以用加密密鑰加密信息，但只有相應(yīng)的解密密鑰才能解密信息。

在背包公鑰密碼體制中，解密密鑰為超遞增增向量，但加密密鑰卻不是超遞增增向量，利用求解一般背包問題的復(fù)雜性，使得只有持有有解密密鑰的合法用戶才可以解密得到明文，而其他持有加密密鑰的人無法解密得到明文。

2.1 密碼的選取

2.2 加密

背包公鑰密碼的加密就是由加密密鑰B乘以明文X的轉(zhuǎn)置X'得到密文L，即

2.3 解密

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

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

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

3 背包公鑰密碼體制的一種破譯方法

3.1 預(yù)備知識(shí)

在討論破譯方法前，我們先給出以下定義、引理和定理，引理和定理的詳細(xì)證明見參考文獻(xiàn)［1］。

定義3.1稱A=(a1，a2，…，an)為背包向量，如果ai，i=1，2，…，n為正整數(shù)，n＞2。

定義3.2對(duì)于n維背包向量A=(a1，a2，…，an)，如果

成立，那么i成為A的干擾點(diǎn).

定義3.3背包向量B=(b1，b2，…，bn)是(A，z，m)可達(dá)的當(dāng)且僅當(dāng)A=(a1，a2，…，an)是超遞增向量，z，m為正整數(shù)，m≥2 且z，m互素時(shí)，其中bi=(zaimodm)i=1，2，…，n。記為

引理3.1三元組(A，z，m)擁有一個(gè)目標(biāo)(C，z，p)當(dāng)且僅當(dāng)

對(duì)A的所有干擾點(diǎn)i都成立，并且如果

成立，那么必有

定理3.1背包向量B=(b1，b2，…，bn)是超可達(dá)的當(dāng)且僅當(dāng)存在互素的正整數(shù)z，m，u＜m，maxB＜m≤2maxB;遞增向量A=(a1，a2，…，an)滿足

并且三元組(A，z，m)(zumodm=1，z＜ maxB)擁有一個(gè)目標(biāo)(C，z，p)，這個(gè)目標(biāo)滿足

3.2 破譯方法

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

首先，求滿足下面條件的正整數(shù)u，m，z和向量A:

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

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

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

(4)若A有干擾點(diǎn)，則對(duì)A的所有干擾點(diǎn)i(3.2)式都成立;

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

其次，由上面三元組(A，z，m)擁有，求滿足下面條件的非負(fù)整數(shù)t，p，k和向量C:

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

(3)tzmodp=1。

通過上面的計(jì)算可得三元組(C，z，p)，它就是三元組(A，z，m)的目標(biāo)，也就是要求的解密密鑰。利用此解密密鑰和2.3的解密方法，可以很快地由密文解出明文X，整個(gè)破譯過程完成。

3.3 破譯方法正確性的驗(yàn)證

下面給出一個(gè)實(shí)例，以驗(yàn)證3.2破譯方法的正確性:

假設(shè)給定加密密鑰B=(10，15，22，14)和明文X=(1，0，1，1)，則加密后密文L=B×X'=46?，F(xiàn)在，利用3.2破譯方法，由已知的加密密鑰B和密文L求破譯所得明文X1。

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

顯然，破譯所得明文X1和實(shí)際明文X完全相同，所以3.2破譯方法完全正確。

4 結(jié)束語

與統(tǒng)計(jì)分析破譯法相比，本文介紹的破譯方法更簡(jiǎn)單、快速，具有更高的使用價(jià)值。同時(shí)，我們會(huì)發(fā)現(xiàn)破譯所得解密密鑰可能不唯一。例如3.3所給的例子的解密密鑰(C，t，p)就有可能為((2，3，12，18)，23，38)或((2，3，13，20)，26，43)，他們的價(jià)值雖然不同，但都是正確的解密密鑰。

［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］何敬民，盧開澄.背包公鑰密碼系統(tǒng)的安全性與設(shè)計(jì)［J］.清華大學(xué)學(xué)報(bào):自然科學(xué)版，1988，28(1):89-97.

［5］羅坤杰，羅文俊.基于ECDLP的背包公鑰密碼體制［J］.信息安全與通信保密，2008(7):83-85.

［6］王衍波.一種新的背包公鑰密碼體制［J］.解放軍理工大學(xué)學(xué)報(bào)，2001(4):29-33.