對一種背包公鑰密碼改進(jìn)方案的安全性分析

夏偉 潘瑜

1青海師范大學(xué)計(jì)算機(jī)學(xué)院 青海 810000 2江蘇理工學(xué)院計(jì)算機(jī)工程學(xué)院 江蘇 213001

0 引言

自1978年Merkle和Hellman首先提出了一個(gè)現(xiàn)在稱為M-H背包體制的密碼算法之后，基于背包的密碼一直是密碼研究者研究的熱點(diǎn)，研究人員設(shè)計(jì)出許多基于背包問題的密碼方案。雖然M-H背包方案以及它的一些改進(jìn)算法在20世紀(jì)80年代初被Shamir等人給破譯了，但隨后仍有不少其他改進(jìn)方案被提出來。既然基于背包的公鑰密碼體制不安全，為什么大量的研究人員還在進(jìn)行研究，提出改進(jìn)方案呢？分析其中原因，發(fā)現(xiàn)有三點(diǎn)：第一，背包密碼體制加解密非常迅速，實(shí)用性很強(qiáng)；第二，背包密碼本身是基于背包問題的，背包問題的NPC(NP完全性)特性使其完全可以應(yīng)用到加密體制中去；第三，現(xiàn)實(shí)中有很多資源受限制的應(yīng)用環(huán)境，比如內(nèi)存受限，時(shí)間受限等等，這些都為背包密碼提供了很好的實(shí)用環(huán)境。所以，背包密碼體制的研究者依然層出不窮，他們都想找到一種相對比較安全的改進(jìn)算法來實(shí)現(xiàn)背包密碼算法的安全應(yīng)用。

1 王氏密碼的改進(jìn)算法

1.1 算法介紹

丁燕艷等人在文獻(xiàn)[1]中對王氏密碼進(jìn)行了安全性分析，說明了僅通過模乘運(yùn)算與中國剩余定理構(gòu)造的背包公鑰算法都是不安全的，原因在于不能充分隱藏初始序列的冗余，存在安全漏洞。他們提出了要引進(jìn)擴(kuò)散技術(shù)，以分散初始序列的冗余度，使破譯者難以利用，從而提出了王氏密碼的一種改進(jìn)算法。

1.2 算法描述

1.2.1 密鑰生成算法

(1)取超遞增初始序列：

(2)選互素的正整數(shù)w和m，滿足公式(1)：

(3)運(yùn)用乘數(shù)w，對序列B中的bi進(jìn)行模乘運(yùn)算，將B轉(zhuǎn)換成D序列：

其中di(i=1，2，…，n)最大長度可以為n+1位。

(4)對di進(jìn)行不對稱分組：di的長度以n+1位計(jì)(如高位不足，以0計(jì))，左起在第j位分為左右兩部分，形成ui和vi位數(shù)分別為j位和n+1-j位，其中：

(5)選整數(shù)t，滿足：

(6)選互素的正整數(shù)p和q，滿足：

運(yùn)用中國剩余定理，生成公鑰A=(a1,a2,…,an)。

私鑰為：p,q,t,w-1,m。

初始序列B作為固定值嵌入在算法中。

1.2.2 加密算法

二進(jìn)制明文x=(x1,x2,…,xn)，xi為0或1，被加密為：

1.2.3 解密算法

再運(yùn)用超遞增初始序列B計(jì)算得到明文。

2 安全性分析

文獻(xiàn)[1]中提到必須猜測到公式(5)中的 t獲得公式(3)中的D序列后才能運(yùn)用格規(guī)約攻擊，本文考慮的是在沒有得到D序列的情況下，只通過已知的公鑰和密文來構(gòu)造格，根據(jù)文獻(xiàn)[8]的方法進(jìn)行啟發(fā)式格規(guī)約攻擊。

由于這類算法都是基于背包的，它的密文都是iiax∑的形式，明文都是0或1，所以密文與明文之間的關(guān)系總可以模擬出來，而LLL算法正可以進(jìn)行這種模擬，例如構(gòu)造一個(gè)格：

由上面構(gòu)造的格L的形式，進(jìn)行LLL規(guī)約后，如果存在首項(xiàng)為0，尾項(xiàng)為1的規(guī)約基，必定有k1a1+k2a2+…+kkak=c(這里的k1,k2,…,kk是規(guī)約過程中的系數(shù))。若中間項(xiàng)為1時(shí)，對應(yīng)行的系數(shù)為1；若中間項(xiàng)為-1時(shí)，對應(yīng)的行的系數(shù)為0，則此時(shí)K=(k1,k2,…,kk)就是我們要得到的明文序列。

文獻(xiàn)[1]中還提出了一種對何-盧背包公鑰密碼系統(tǒng)的改進(jìn)算法，我們依然可以根據(jù)上面的啟發(fā)式格規(guī)約攻擊來攻擊它，通過此方案的算法描述得到一組公鑰與明文，從而得到密文，再構(gòu)造格，用LLL算法來直接恢復(fù)它的明文。成功的比例比較大，雖不能百分之百攻破，但其不安全性也顯而易見了。

為了進(jìn)一步說明文獻(xiàn)[1]中的改進(jìn)算法仍然是不安全的，下面我們對王氏密碼的改進(jìn)算法進(jìn)行攻擊實(shí)驗(yàn)，以實(shí)驗(yàn)數(shù)據(jù)來證明這一點(diǎn)。

3 格規(guī)約攻擊方法

3.1 格規(guī)約攻擊的算法設(shè)計(jì)

(1)根據(jù)算法描述可以求出一組公鑰A=(a1,a2,…an)，然后取一隨機(jī)明文X=(x1,x2,…,xn)，從而得到一組密文c=a1x1+a2x2+…+anxn。

構(gòu)造格L如下：

(2)調(diào)用LLL算法，得到格L的規(guī)約基B。

(3)在規(guī)約基B中尋找首項(xiàng)為0，尾項(xiàng)為1，中間項(xiàng)為1或-1的規(guī)約基，如公式(15)所示：

Bi,0=0，Bi,n+1=1，Bi,j=1or?1(i≠j,i,j=0,1,…,n+1)(15)

(4)如果在規(guī)約基B中找到這樣的向量，則輸出明文X=(x1，x2，…，xk)，數(shù)學(xué)表達(dá)如公式(16)：

分析此啟發(fā)式格規(guī)約攻擊所需要花費(fèi)的時(shí)間：

調(diào)用LLL算法需要的時(shí)間為n6log5(n)≈n6log5，

∞實(shí)際的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于這個(gè)時(shí)間，而掃描找到需要的那個(gè)向量所要花費(fèi)的時(shí)間為O(n2)，所以此啟發(fā)式格規(guī)約攻擊所需要花費(fèi)的時(shí)間在多項(xiàng)式時(shí)間內(nèi)，n=1024的時(shí)候大約6個(gè)多小時(shí)就可以得到結(jié)果。

3.2 格規(guī)約攻擊計(jì)算實(shí)驗(yàn)

為了進(jìn)一步說明上述啟發(fā)式格規(guī)約攻擊的有效性，可以利用NTL算法庫來進(jìn)行計(jì)算實(shí)驗(yàn)驗(yàn)證，限于文章篇幅，這里僅通過n=32來進(jìn)行驗(yàn)證說明。

具體參數(shù)值如下：

背包密度=n/=0.9696969697(“||”表示的是比特長度)

其中對公式(3)中D分割的比例按照的是文獻(xiàn)[1]中例子的比例，

測試結(jié)果如下：

明文m=7607287771

轉(zhuǎn)換成二進(jìn)制為：

通過尋找算法，可以找到規(guī)約基B中存在這么一個(gè)向量，首項(xiàng)為0，尾項(xiàng)為1，中間項(xiàng)為1或-1：

根據(jù)公式(16)可以恢復(fù)出明文X：

通過對照，恢復(fù)出的明文X正好與原明文m一致，從而說明攻擊成功。

以上僅運(yùn)用一組參數(shù)進(jìn)行了實(shí)驗(yàn)，為表明計(jì)算實(shí)驗(yàn)的有效性，表1中列出了選取不同參數(shù)時(shí)的實(shí)驗(yàn)結(jié)果，可以看出文獻(xiàn)[1]中的這種改進(jìn)方案不能抵抗格規(guī)約攻擊。

表1 不同參數(shù)下的格規(guī)約攻擊實(shí)驗(yàn)的結(jié)果

通過多次計(jì)算實(shí)驗(yàn)可以發(fā)現(xiàn)，運(yùn)用啟發(fā)式格規(guī)約攻擊能以不可忽略的概率直接恢復(fù)出明文，即使那些沒有完全成功的實(shí)驗(yàn)中，也都可以恢復(fù)出大部分明文，從而說明這樣的背包公鑰改進(jìn)算法仍然是不安全的。

4 結(jié)束語

本文對文獻(xiàn)[1]中兩種改進(jìn)背包公鑰方案的安全性進(jìn)行了分析，根據(jù)不同的參數(shù)，在高背包密度下對其中一種方案進(jìn)行了啟發(fā)式的格規(guī)約攻擊，攻擊時(shí)間均在多項(xiàng)式時(shí)間內(nèi)，通過計(jì)算實(shí)驗(yàn)驗(yàn)證了格規(guī)約攻擊的有效性，從而說明這兩種方案都是不安全的，存在潛在的漏洞與威脅。根據(jù)對背包密碼本身的特性，本文作者大膽猜測只要是基于背包的公鑰密碼算法，不管怎樣隱藏冗余，都會為攻擊者留下一定的信息，總存在著安全威脅，總可以通過格規(guī)約攻擊以不可忽略的概率恢復(fù)出全部或部分明文。在接下來的研究中，將通過理論分析來證明上面的猜測。

[1]丁燕艷,費(fèi)向東,潘郁.重新認(rèn)識背包公鑰密碼的安全性[J].計(jì)算機(jī)應(yīng)用.2012.

[2]Merkle R C,Hellman M H.Hiding information and signatures in trapdoor knapsacks[J].IEEE Transaction on Information Theory,1978.

[3]SHAMIR A.A polynomial-time algorithm for breaking the basic Merkle-Hellman cryptosystem[J].IEEE Transactions on Information Theory,1984.

[4]王保倉,韋永壯,胡予璞.基于中國剩余定理的快速公鑰加密算法[J].西安電子科技大學(xué)學(xué)報(bào):自然科版.2008.

[5]何敬民,盧開澄.背包公鑰系統(tǒng)的安全性與設(shè)計(jì)[J].清華大學(xué)學(xué)報(bào).自然科學(xué)版.1988.

[6]Coster M J,Joux A,LaM acchia B A,etal.Improved low-density subset sum algorithms[J],Computational Complexity,1992.

[7]LENSTRA A K,LENSTRA H W,Jr OVASZ L.Factoring polynomials with rational coefficients[J].Mathematische Annalen,1982.

[8]古春生,于志敏,景征俊.基于隨機(jī)背包公鑰密碼的格攻擊[J].計(jì)算機(jī)應(yīng)用研究.2012.

[9]SHOUP V.NTL.a library for doing number theory[EB/OL].(2009-08-14).http://shoup.net/ntl/.