對一種背包公鑰密碼改進方案的安全性分析

夏偉 潘瑜

1青海師范大學計算機學院 青海 810000 2江蘇理工學院計算機工程學院 江蘇 213001

0 引言

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

1 王氏密碼的改進算法

1.1 算法介紹

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

1.2 算法描述

1.2.1 密鑰生成算法

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

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

(3)運用乘數w，對序列B中的bi進行模乘運算，將B轉換成D序列：

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

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

(5)選整數t，滿足：

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

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

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

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

1.2.2 加密算法

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

1.2.3 解密算法

再運用超遞增初始序列B計算得到明文。

2 安全性分析

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

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

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

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

為了進一步說明文獻[1]中的改進算法仍然是不安全的，下面我們對王氏密碼的改進算法進行攻擊實驗，以實驗數據來證明這一點。

3 格規約攻擊方法

3.1 格規約攻擊的算法設計

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

構造格L如下：

(2)調用LLL算法，得到格L的規約基B。

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

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

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

分析此啟發式格規約攻擊所需要花費的時間：

調用LLL算法需要的時間為n6log5(n)≈n6log5，

∞實際的運行時間遠遠小于這個時間，而掃描找到需要的那個向量所要花費的時間為O(n2)，所以此啟發式格規約攻擊所需要花費的時間在多項式時間內，n=1024的時候大約6個多小時就可以得到結果。

3.2 格規約攻擊計算實驗

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

具體參數值如下：

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

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

測試結果如下：

明文m=7607287771

轉換成二進制為：

通過尋找算法，可以找到規約基B中存在這么一個向量，首項為0，尾項為1，中間項為1或-1：

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

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

以上僅運用一組參數進行了實驗，為表明計算實驗的有效性，表1中列出了選取不同參數時的實驗結果，可以看出文獻[1]中的這種改進方案不能抵抗格規約攻擊。

表1 不同參數下的格規約攻擊實驗的結果

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

4 結束語

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

[1]丁燕艷,費向東,潘郁.重新認識背包公鑰密碼的安全性[J].計算機應用.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].西安電子科技大學學報:自然科版.2008.

[5]何敬民,盧開澄.背包公鑰系統的安全性與設計[J].清華大學學報.自然科學版.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].計算機應用研究.2012.

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