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

.頁(yè)眉.頁(yè)腳..重新認(rèn)識(shí)背包公鑰密碼的安全性摘要:針對(duì)背包密碼屢被破譯的局面,分析了其中原因。指出背包公鑰序列是由初始序列變換而來(lái)的,初始序列由易解背包形成,存在著冗余度,因此背包公鑰序列不可能是完全隨機(jī)的,利用這些冗余度是破譯成功的必要條件,目前大多數(shù)被破譯的背包密碼只使用了模乘運(yùn)算等混亂技術(shù),這不足以隱藏初始序列的冗余度。為此引入了加法擴(kuò)散技術(shù),以分散初始序列的冗余度,使攻擊者在破譯過(guò)程中難以利用,舉實(shí)例說(shuō)明了項(xiàng)內(nèi)擴(kuò)散和項(xiàng)間擴(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)域的研究熱點(diǎn),被認(rèn)為是最有前途的密碼算法。背包密碼的安全性是基于求子集和問(wèn)題的困難性,設(shè)計(jì)思想是把易解背包問(wèn)題偽裝成一個(gè)看似困難的背包問(wèn)題,其方法就是使用陷門(mén)。陷門(mén)信息作為私鑰僅被合法接收者掌握,運(yùn)用它可以把該問(wèn)題恢復(fù)成一個(gè)易解背包問(wèn)題,通過(guò)解該易解背包可重構(gòu)明文;而對(duì)非法接收者來(lái)說(shuō),從密文恢復(fù)明文就相當(dāng)于解一個(gè)困難的背包問(wèn)題。但存在著以下難題:如果陷門(mén)隱藏得不充分,則攻擊者可以從公鑰出發(fā)求解出對(duì)應(yīng)的陷門(mén)信息;如果隱藏得充分,則背包密度可能降低。coster等[2]證明背包密度小于0.9408的背包密碼都易遭受低密度子集和攻擊；而若背包密度大于1,又造成解密不唯一。因此,構(gòu)造一個(gè)安全的背包密碼異常困難,目前其中的絕大多數(shù)都被破譯了,普遍認(rèn)為背包密碼的前景暗淡[3-4]。

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

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

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

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

2.2混亂和擴(kuò)散

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

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

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

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

2.3模乘運(yùn)算

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

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

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

b≡wu(modm)

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

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

b=wu-k*m(2)

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

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

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

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

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

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

2.4加法擴(kuò)散

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

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

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

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

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

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

下面運(yùn)用模乘運(yùn)算和中國(guó)剩余定理,結(jié)合項(xiàng)內(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中遺留的冗余度,但這些冗余度都被隱藏了,破譯者無(wú)法利用,文獻(xiàn)[13]所展示的攻擊法無(wú)法成功。即使攻擊者從公鑰出發(fā)追蹤到a′i,由于a′i是模m加運(yùn)算后的余,也不能通過(guò)聯(lián)立方程組的方法解出ai。

5結(jié)語(yǔ)

在背包密碼普遍不被看好的情況下,本文以新的視角對(duì)其進(jìn)行研究和分析。本文認(rèn)為,背包公鑰序列是由初始序列變換來(lái)的,初始序列代表著易解背包,具有一定的規(guī)律和特性,故背包公鑰序列不可能是完全隨機(jī)的。這些規(guī)律和特性形成初始序列的冗余度,利用此冗余度是破譯成功的必要條件?？梢詫⒊跏夹蛄锌醋餍杓用艿奈谋?變換看作加密過(guò)程,公鑰序列看作密文。背包公鑰算法的安全性有兩個(gè)方面:一是保證背包密度,抵御低密度子集和攻擊；二是優(yōu)化變換過(guò)程,使攻擊者難以從公鑰出發(fā)利用初始序列的冗余度。目前大多數(shù)被破譯的背包公鑰密碼只使用了屬混亂技術(shù)的模乘運(yùn)算,不能充分隱藏初始序列的冗余度,本文引入加法擴(kuò)散技術(shù),進(jìn)一步隱藏初始序列的冗余度,使攻擊者難以利用。以實(shí)際例子說(shuō)明了兩種加法擴(kuò)散技術(shù),即項(xiàng)內(nèi)擴(kuò)散技術(shù)和項(xiàng)間擴(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]王保倉(cāng),韋永壯,胡予濮.基于隨機(jī)背包的公鑰密碼[j].電子與信息學(xué)報(bào),2010,32(7):1580-1584.

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

[7]王保倉(cāng),巨春飛.對(duì)一個(gè)背包公鑰密碼的格攻擊[j].計(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