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

陳成鋼

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

1 背包問題

1.1 背包問題定義

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

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

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

顯然，背包問題的求解是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 背包公鑰密碼體制

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

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

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 預備知識

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

定義3.1稱A=(a1，a2，…，an)為背包向量，如果ai，i=1，2，…，n為正整數(shù)，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為正整數(shù)，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)是超可達的當且僅當存在互素的正整數(shù)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，可得如下破譯方法:

首先，求滿足下面條件的正整數(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有干擾點，則對A的所有干擾點i(3.2)式都成立;

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

其次，由上面三元組(A，z，m)擁有，求滿足下面條件的非負整數(shù)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?，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可進一步求得k=3，p=38，t=23，C=(2，3，12，18)。由(C，t，p)和 2.3 的解密方法易得

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

4 結(jié)束語

與統(tǒng)計分析破譯法相比，本文介紹的破譯方法更簡單、快速，具有更高的使用價值。同時，我們會發(fā)現(xiàn)破譯所得解密密鑰可能不唯一。例如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］何敬民，盧開澄.背包公鑰密碼系統(tǒng)的安全性與設計［J］.清華大學學報:自然科學版，1988，28(1):89-97.

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

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