重新認(rèn)識背包公鑰密碼的安全性

.頁眉.頁腳..重新認(rèn)識背包公鑰密碼的安全性摘要:針對背包密碼屢被破譯的局面,分析了其中原因。指出背包公鑰序列是由初始序列變換而來的,初始序列由易解背包形成,存在著冗余度,因此背包公鑰序列不可能是完全隨機(jī)的,利用這些冗余度是破譯成功的必要條件,目前大多數(shù)被破譯的背包密碼只使用了模乘運(yùn)算等混亂技術(shù),這不足以隱藏初始序列的冗余度。為此引入了加法擴(kuò)散技術(shù),以分散初始序列的冗余度,使攻擊者在破譯過程中難以利用,舉實例說明了項內(nèi)擴(kuò)散和項間擴(kuò)散兩種擴(kuò)散技術(shù)。分析表明,運(yùn)用擴(kuò)散技術(shù)后,能抵御目前已知的攻擊方法。

關(guān)鍵詞:背包公鑰密碼;冗余度;模乘運(yùn)算;混亂;擴(kuò)散

securityreconsiderationofknapsackpublickeycryptosystem

dingyanyan,feixiangdong,panyu*

(

schoolofeconomicsandmanagement,nanjinguniversityoftechnology,nanjingjiangsu210009,china

)

abstract:

concerningthesituationthatknapsackpublickeycryptosystemhasbeenbrokenrepeatedly,thispaperanalyzedthecause.itisexpoundedthataknapsackpublickeysequenceisgeneratedbytransforminganinitialsequencecomposedofaneasyknapsackproblemwithredundancy;hence,aknapsackpublickeysequenceisunlikelycompletelyrandom.currently,mostbrokenknapsackcryptosystemsonlyuseconfusion,suchasmodularmultiplication,soasnottoconcealtheredundancyoftheinitialsequenceadequately.itisnecessarytoutilizetheredundancyforbreakingacryptosystem.therefore,additiondiffusionwasintroducedinthispapertodiffusetheredundancyofaninitialsequence,sothatanadversarycannotmakeuseoftheredundancywhenbreakingacryptosystem.inneritemdiffusionandinteritemdiffusionwereillustrated.theanalysisindicatesthecryptosystemissecureagainsttheknownattackswithdiffusion.

keywords:

knapsackpublickeycryptosystem;redundancy;modularmultiplication;confusion;diffusion

0引言

背包密碼自1978年提出[1]直到20世紀(jì)90年代,一直是公鑰密碼領(lǐng)域的研究熱點,被認(rèn)為是最有前途的密碼算法。背包密碼的安全性是基于求子集和問題的困難性,設(shè)計思想是把易解背包問題偽裝成一個看似困難的背包問題,其方法就是使用陷門。陷門信息作為私鑰僅被合法接收者掌握,運(yùn)用它可以把該問題恢復(fù)成一個易解背包問題,通過解該易解背包可重構(gòu)明文;而對非法接收者來說,從密文恢復(fù)明文就相當(dāng)于解一個困難的背包問題。但存在著以下難題:如果陷門隱藏得不充分,則攻擊者可以從公鑰出發(fā)求解出對應(yīng)的陷門信息;如果隱藏得充分,則背包密度可能降低。coster等[2]證明背包密度小于0.9408的背包密碼都易遭受低密度子集和攻擊；而若背包密度大于1,又造成解密不唯一。因此,構(gòu)造一個安全的背包密碼異常困難,目前其中的絕大多數(shù)都被破譯了,普遍認(rèn)為背包密碼的前景暗淡[3-4]。

背包公鑰序列有別于隨機(jī)數(shù)序列，因為前者是由初始序列變換而來的,并以此隱藏陷門?？梢园殉跏夹蛄锌醋鞅患用艿南?初始序列到公鑰的變換過程可以看成是加密過程,背包公鑰序列看作加密后的密文。從計算復(fù)雜性理論上講,如果加密過程(初始序列到公鑰的變換過程)是安全的,那么從密文(公鑰)出發(fā)破譯該算法的時間和空間復(fù)雜性極大,直至等價于求解一個npc問題,那么該算法被認(rèn)為是一個安全的背包公鑰密碼。

初始序列由易解背包形成,具有一定規(guī)律和特性,如mh背包[1]中初始序列的超遞增性，王氏密碼中初始序列差值的超遞增性。這些規(guī)律和特性形成初始序列的冗余度[8],冗余度作為算法的一部分,是公開的。背包公鑰序列作為初始序列變換的最終結(jié)果,殘留著這些冗余度。事實上,任何公鑰密碼的公鑰必然隱藏著全部或部分私鑰信息,不存在完全隨機(jī)的公鑰。

如果初始序列是隨機(jī)數(shù)序列,其冗余度為零,由于破譯者無法搜尋和驗證密鑰,即使是僅進(jìn)行一次模乘運(yùn)算的mh背包[1]都是無法破譯的,無論是格攻擊法[7],還是shamir攻擊法[9],都必須利用初始序列的冗余度進(jìn)行破譯。利用初始序列的冗余度是破譯成功的必要條件。其中,shamir攻擊法的唯一解距離為4,即攻擊者至少需要利用超遞增初始序列中的4項。

一個背包公鑰算法是安全的,其必要條件是能夠防止破譯者從公鑰出發(fā)利用初始序列的冗余度。

2.2混亂和擴(kuò)散

shonnon[8]提出了隱藏被加密消息中冗余度的兩種方法:混亂和擴(kuò)散。

混亂是指在加密過程中使明文、密鑰以及密文之間的關(guān)系盡可能復(fù)雜,以掩蓋明文和密文之間的關(guān)系?；痉椒ㄊ谴?用密文字符代替明文字符。除非對密鑰長度沒限制,如“一次一密”,否則僅用混亂是不夠的。

擴(kuò)散是指使每一位明文的變化盡可能多地影響到密文的變化,將明文冗余度分散到密文中;也指將每一位密鑰的影響盡可能擴(kuò)展到較多的密文中?；痉椒ㄊ菗Q位(又稱置換)。通常單獨用擴(kuò)散也易被破譯。

不論是“混亂”還是“擴(kuò)散”,都必須是可逆的,即經(jīng)過逆向操作能還原初始數(shù)據(jù)。

2.3模乘運(yùn)算

混亂實現(xiàn)的方式有多種[10]:

數(shù)據(jù)加密標(biāo)準(zhǔn)（dataencryptionstandard,des）采用s盒,國際數(shù)據(jù)加密算法（internationaldataencryptionalgorithm,idea）采用模乘運(yùn)算。背包公鑰適合采用模乘運(yùn)算實現(xiàn)混亂。

模乘運(yùn)算表示為:

b≡wu(modm)

其中:m為模,w為乘數(shù),u為被乘數(shù),b為模m的余。

存在如下關(guān)系:

b=wu-k*m(2)

其中k為某個正整數(shù)。

背包密碼系統(tǒng)中的模乘運(yùn)算為乘法群運(yùn)算,在一個整數(shù)域中,用一個整數(shù)代替另一整數(shù)。

其優(yōu)點是當(dāng)w和u較大時,雪崩效應(yīng)明顯,即w或u變化一位,將引起b的劇烈變化。

缺點是變換為線性:被乘數(shù)u中的每位同等擴(kuò)張后取模p的余,各位之間仍然在模p整數(shù)域中保持著原有的關(guān)系,u中的存在冗余度,被完整地傳遞到b中,易被破譯者利用。如:u和m存在公因子g,從式(2)可知,g也是b的因子。

即使通過多次模乘運(yùn)算構(gòu)造多重mh背包,仍不能充分隱藏初始序列的冗余度,破譯者能夠從公鑰序列出發(fā)利用該冗余度,進(jìn)而破譯[11]。

王氏密碼僅運(yùn)用中國剩余定理進(jìn)行一次迭代變換,關(guān)系如下:

2.4加法擴(kuò)散

如上所述,僅依靠混亂技術(shù)還不能確保安全,需要引進(jìn)擴(kuò)散技術(shù),以分散初始序列的冗余度,使得破譯者難以利用。

擴(kuò)散技術(shù)有多種類型[10],基本方法是換位,如des,但對于背包密碼來說,換位將引起加法進(jìn)位的改變,難以還原,故換位法不適用;idea采用模加、模異或運(yùn)算實現(xiàn)擴(kuò)散。

背包公鑰密碼的背包值是初始序列各項及其變換形式的子集和。鑒于加法易于通過逆運(yùn)算減法恢復(fù)原值,因此,初始序列的冗余度適合采取加法的方式來實現(xiàn)擴(kuò)散。

不同背包公鑰的初始序列所包含的冗余度是不同的,為分散這些冗余度所采用的加法擴(kuò)散技術(shù)也是不同的,必須依具體情況而定,但總體原則有兩條:一是在模乘運(yùn)算的基礎(chǔ)上,進(jìn)一步加強(qiáng)雪崩效應(yīng);二是使破譯者從公鑰出發(fā)難以利用初始序列的冗余度。

從形態(tài)上分,加法擴(kuò)散技術(shù)分為項內(nèi)擴(kuò)散和項間擴(kuò)散技術(shù)。將一項分成兩部分,相互疊加,隱藏冗余度,稱為項內(nèi)擴(kuò)散;各項之間相互疊加,隱藏冗余度,稱為項間擴(kuò)散。

3基于項內(nèi)擴(kuò)散技術(shù)的背包公鑰密碼

下面運(yùn)用模乘運(yùn)算和中國剩余定理,結(jié)合項內(nèi)擴(kuò)散技術(shù),構(gòu)造新型背包公鑰密碼。

4.4.2私鑰恢復(fù)攻擊

模m′群有如下關(guān)系:

w′-1a”i-tim′=a′i;1≤i≤k

破譯者可以從公鑰出發(fā),運(yùn)用格基規(guī)約算法[6]推算出ti,但由于m′是保密的,破譯者要繼續(xù)下去,需要利用a”i或a′i中遺留的冗余度,但這些冗余度都被隱藏了,破譯者無法利用,文獻(xiàn)[13]所展示的攻擊法無法成功。即使攻擊者從公鑰出發(fā)追蹤到a′i,由于a′i是模m加運(yùn)算后的余,也不能通過聯(lián)立方程組的方法解出ai。

5結(jié)語

在背包密碼普遍不被看好的情況下,本文以新的視角對其進(jìn)行研究和分析。本文認(rèn)為,背包公鑰序列是由初始序列變換來的,初始序列代表著易解背包,具有一定的規(guī)律和特性,故背包公鑰序列不可能是完全隨機(jī)的。這些規(guī)律和特性形成初始序列的冗余度,利用此冗余度是破譯成功的必要條件。可以將初始序列看作需加密的文本,變換看作加密過程,公鑰序列看作密文。背包公鑰算法的安全性有兩個方面:一是保證背包密度,抵御低密度子集和攻擊；二是優(yōu)化變換過程,使攻擊者難以從公鑰出發(fā)利用初始序列的冗余度。目前大多數(shù)被破譯的背包公鑰密碼只使用了屬混亂技術(shù)的模乘運(yùn)算,不能充分隱藏初始序列的冗余度,本文引入加法擴(kuò)散技術(shù),進(jìn)一步隱藏初始序列的冗余度,使攻擊者難以利用。以實際例子說明了兩種加法擴(kuò)散技術(shù),即項內(nèi)擴(kuò)散技術(shù)和項間擴(kuò)散技術(shù)。分析表明,運(yùn)用了擴(kuò)散技術(shù)后,攻擊者難以利用初始序列的冗余度,目前已知的破譯方法不再奏效。

參考文獻(xiàn):

[1]

merklerc,hellmanmh.hidinginformationandsignaturesintrapdoorknapsacks[j].ieeetransactionsoninformationtheory,1978,24(5):525-530.

[2]costermj,jouxa,lamacchiaba,etal.improvedlowdensitysubsetsumalgorithms[j].computationalcomplexity,1992,2(2):111-128.

[3]odlyzkoam.theriseandfallofknapsackcryptosystems[eb/ol].[20100510]./~odlyzko/doc/arch/knapsack.survey.pdf.

[4]laimk.knapsackcryptosystems:thepastandthefuture[eb/ol].[20110915]./~mingl/knapsack.html.

[5]王保倉,韋永壯,胡予濮.基于隨機(jī)背包的公鑰密碼[j].電子與信息學(xué)報,2010,32(7):1580-1584.

[6]lenstraak,lenstrahw,jr,lovaszl.factoringpolynomialswithrationalcoefficients[j].mathematischeannalen,1982,261(4):513-534.

[7]王保倉,巨春飛.對一個背包公鑰密碼的格攻擊[j].計算機(jī)應(yīng)用研究,2010,27(4):1466-1492.

[8]shannonce.communicationtheoryofsecrecysystems[j].bellsystemtechnicaljournal,1949,28(4):656-715.

[9]shamira.apolynomialtimealgorithmforbreakingthebasicmerklehellmancryptosystem[j].ieeetransactionsoninformationtheory,1984,30(5):699-704.

[10]schneierb.應(yīng)用密碼學(xué)[m].吳世忠,祝世雄,張文政,等譯.北京:機(jī)械工業(yè)出版社,2000:185-250.

[11]lagariasjc.knapsackpublickeycryptosystemsanddiophantineapproximation[c]//proceedingsofcrypto83.berlin