【摘要】：自從1978年MERKLE和HELLMAN率先提出了MH背包密碼體制以來,一直到20世紀(jì)90年代,背包密碼都是公鑰密碼方面的最熱門的研究方向,密碼學(xué)界認(rèn)為它是最有發(fā)展前途的密碼算法。它和RSA公鑰體制被認(rèn)為是兩個(gè)最具潛力的公鑰體制。公開密鑰密碼體制非常適用于微機(jī)系統(tǒng)和分布式控制的加密,現(xiàn)在已成為全世界計(jì)算機(jī)密碼學(xué)研究的重點(diǎn),而基于背包密碼公開密鑰密碼體制與公鑰密碼體制相比,具有可快速求解的特點(diǎn)。雖然超遞增背包具有相當(dāng)?shù)陌踩[患,并且現(xiàn)有的一次背包問題大多被破解,因?yàn)槠渥陨砭哂屑咏饷芩俣瓤?易于軟硬件實(shí)施等諸多優(yōu)點(diǎn),一些鐘愛于背包密碼的學(xué)者仍然在進(jìn)行不斷的探索和研究,試圖找到更為安全快速的背包公鑰密碼算法。本論文選題圍繞背包問題的安全性和效率展開。對(duì)關(guān)于背包問題的公鑰加密體制進(jìn)行了詳細(xì)的研究與分析,在原來的基礎(chǔ)上,對(duì)已有的背包密碼加密算法進(jìn)行了改進(jìn)。本文提出了一些新型的背包密碼方案,這些方案的實(shí)施既能提高背包體制的安全性不高問題,同時(shí)又能保持背包體制的優(yōu)點(diǎn),最后通過C代碼實(shí)現(xiàn)了算法。論文的主要工作包括以下幾個(gè)方面：一、關(guān)于背包問題的公鑰加密體制研究基于背包問題的背包密碼是第一個(gè)公鑰系統(tǒng)。一般背包問題的英文為Knapsack problem (KP),是一種組合優(yōu)化的NP完全問題。背包問題可以描述為：給定一組物品,每種物品都有自己的重量和價(jià)格,在限定的總重量?jī)?nèi),我們?nèi)绾芜x擇,才能使得物品的總價(jià)格最高。它的求解方法可以概括為精確算法和近似算法,其中精確算法有動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法等,近似算法有遺傳算法、貪婪法、粒子群算法、蟻群算法等。由于精確算法的時(shí)間復(fù)雜性和空間復(fù)雜性等缺點(diǎn),近年來利用近似算法求解背包問題成為重點(diǎn)。背包公鑰序列和一般的隨機(jī)序列有所不同,背包公鑰序列是由初始序列通過陷門函數(shù)生成的,而非法解密者不知道初始序列。我們可以把初始序列到背包公鑰序列的過程也看作是一個(gè)加密過程,初始序列為明文,陷門函數(shù)為加密算法,背包公鑰序列為密文,從計(jì)算的復(fù)雜度來講,如果初始序列到公鑰序列的過程被看做是沒有安全隱患的,那么從公鑰出發(fā)來逆向求解初始序列的過程(陷門函數(shù)的逆過程)可以看作是不可能的,算法實(shí)現(xiàn)起來的時(shí)間和空間復(fù)雜度極大,這樣就把該背包問題變成了一個(gè)NPC問題,相應(yīng)的,這個(gè)算法就會(huì)被看做是一個(gè)值得使用的公鑰算法。關(guān)于背包密碼的主要問題便是它們的安全性問題。自從Merkle等人提出第一個(gè)基于背包問題的公鑰密碼方案以來,研究人員設(shè)計(jì)出許多基于背包問題的密碼方案。該類方案易于受到Shamir攻擊和低密度攻擊,設(shè)計(jì)抵抗這些攻擊的新型背包公鑰密碼方案一直是公鑰密碼研究的熱點(diǎn)之一。二、設(shè)計(jì)了一種新型的背包密碼方案,即方案3.1。構(gòu)造一個(gè)新型的背包體制,實(shí)質(zhì)上就是重新選擇一個(gè)陷門函數(shù),或者在原來的基礎(chǔ)上加上一個(gè)或多個(gè)陷門函數(shù)。本論文選擇一個(gè)新的陷門函數(shù),即隨機(jī)生成一個(gè)超遞增序列A,選取數(shù)(Q,R),且滿足QR并且Q與R互素,用(Q,R)將超遞增序列A偽裝成一個(gè)序列B,二者滿足條件：通過bi對(duì)明文進(jìn)行加密,形成密文。解密者知道私人密鑰即原始的超遞增序列A,需通過關(guān)系式的逆變換,即由bi推導(dǎo)出ai即可實(shí)現(xiàn)由密文到明文的推導(dǎo),即解密操作。方案3.1具體描述為：密鑰生成算法(1) 隨機(jī)選取超遞增序列A=(a1,…,an)；(2) 隨機(jī)選取(Q,R),QR并且Q與R互素；(3) 由(A,Q,R)計(jì)算B=(b1,…,bn),使(4) 公鑰為B,私鑰為(A,Q,R)。加密算法(1) 明文為x=(x1,…,xn)∈{0,1}",接收方的公鑰為B=(b1,…,bn);(2) 將密文發(fā)送給接收方。解密算法(1) 接收方計(jì)算(2) 則有：其中(3) 對(duì)每一個(gè)可能的r值,令SA=S+r,并由(A,SA)求解x=(x1,…,xn),若能求出合法的x,則將其加入候選解集合X；(4) 若X為空集,則無(wú)解；若X中只有一個(gè)解,則其即為明文x；否則,只能確定x∈X,此時(shí)必須通過認(rèn)證手段才能唯一確定明文x。通過對(duì)算法進(jìn)行誤差分析得出：在解密過程中需要考慮到誤差若能找到誤差的上下限,則能確保解密的準(zhǔn)確性。通過對(duì)方案3.1的實(shí)例測(cè)試,驗(yàn)證了該方案的可行性。三、對(duì)方案3.1進(jìn)行的改進(jìn),即方案4.1。方案3.1有一個(gè)缺陷,那就是B中元素的大小關(guān)系與A中元素的大小關(guān)系是一致的,若bibj,則必有aiaj。因此若A是超遞增的,則B也很可能是超遞增的,這導(dǎo)致該方案很容易被破解。此可對(duì)原方案進(jìn)一步改進(jìn),思路是在方案3.1的基礎(chǔ)上再增加一個(gè)模乘變換,改進(jìn)后的方案如方案4.1：密鑰生成算法(1) 隨機(jī)選取超遞增序列A=(a1,…,an)；(2) 隨機(jī)選取0WM且gcd(M,W)=1；(3) 計(jì)算A’=(a1’,…,an’),使a'i=W·ai(mod M)；(4) 隨機(jī)選取(Q,R), QR并且Q與R互素；(5) 由(A’,Q,R)計(jì)算B=(b1,…,bn),使(6) 公鑰為B,私鑰為(A,Q,R,M).加密算法(1) 明文為x=(x1,…,xn)∈{0,1}",接收方的公鑰為B=(b1,…,bn);(2) 將密文發(fā)送給接收方。解密算法(1) 接收方計(jì)算, 則有：其中(2) 對(duì)每一個(gè)可能的r值,令s'A=S+r,計(jì)算SA=W-1·S'A(modM),然后由(A,SA)求解x=(x1,…,xn),若能求出合法的x,則將其加入候選解集合X；(3) 若X為空集,則無(wú)解；若X中只有一個(gè)解,則其即為明文x；否則,只能確定x∈X,此時(shí)必須通過認(rèn)證手段才能唯一確定明文x。改進(jìn)后的方案4.1在方案3.1的基礎(chǔ)上增加了一個(gè)模乘變換,從而提高了算法的強(qiáng)度。四、對(duì)MH方案的改進(jìn),即方案5.1。通過對(duì)MH方案的攻擊分析,可知攻擊主要是針對(duì)其私鑰背包為超遞增序列、并且公鑰背包是私鑰背包經(jīng)模乘變換得到,而模乘變換對(duì)“超遞增”特性無(wú)法有效屏蔽所致。若能通過某種途徑對(duì)超遞增的私鑰背包先行變換,使得變換后的背包不再具有超遞增屬性,然后再對(duì)之進(jìn)行模乘變換,如此便可使對(duì)MH方案的攻擊對(duì)新方案無(wú)效。但如此改進(jìn)的難點(diǎn)在于：對(duì)私鑰背包超遞增屬性的“破壞”,不應(yīng)導(dǎo)致解密無(wú)法進(jìn)行,即破壞必須是可恢復(fù)的。方案5.1的具體描述為：密鑰生成算法(1) 隨機(jī)選取δ=(δ1,…,δn)∈{0,1}";(2) 令任選超遞增背包A=(ra1,a2,…,an);(3) 隨機(jī)選取奇數(shù)0WM且gcd(M,W)=1;(4) 令 △=[M/2],計(jì)算B=(b1,…,bn),其中bi=W(ai+δi·△)(mod M)(i=1,…,n);(5) 公鑰為B,私鑰為(A,δ)。加密算法(1) 明文x=(x1…,xn)∈{0,1}";(2) 密文解密算法(1) 計(jì)算S'=W-1 s(mod M),則必有：其中0≤r’≤r(3) 對(duì)每一個(gè)可能的0≤r’≤r值,分別令SA=(S'-r')(mod M)和SA=(A'-△-r')(mod M),然后由(A,SA)求解x=(x1,…,xn),若能求出合法的x,則將其加入候選解集合x；(4) 若X為空集,則無(wú)解；若X中只有一個(gè)解,則其即為明文x；否則,只能確定x∈X,此時(shí)必須通過認(rèn)證手段才能唯一確定明文x。五、各方案應(yīng)用模式的分析、實(shí)現(xiàn)和驗(yàn)證本文根據(jù)各方案的特點(diǎn),分析了其應(yīng)用模式：在實(shí)際應(yīng)用中必須對(duì)確定算法進(jìn)行“概率性”改造,即在加密算時(shí)引入“隨機(jī)性”,以使對(duì)同一個(gè)明文的每次加密都能得到不同的密文。具體方法是在加密前對(duì)明文增加冗余信息,或在加密后對(duì)密文增加冗余信息,這里的填充應(yīng)該是隨機(jī)的,以便產(chǎn)生一個(gè)非確定的加密算法。論文使用C語(yǔ)言程序?qū)Ω鱾�(gè)算法加以實(shí)現(xiàn),并給出了關(guān)鍵實(shí)現(xiàn)代碼,從而實(shí)現(xiàn)了對(duì)算法的驗(yàn)證。
[Abstract]:......
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TN918.1

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 手足無(wú)措;性命攸關(guān)的密碼[J];中國(guó)海關(guān);2002年06期

2 周雪;;陳克非:綜合考量成為現(xiàn)有密碼主要挑戰(zhàn)[J];信息安全與通信保密;2012年05期

3 白潔;;走訪專題之密碼學(xué)界(二十) 陳運(yùn):破譯推動(dòng)密碼研究的密鑰[J];信息安全與通信保密;2012年09期

4 ;新書介紹[J];通信保密;1982年01期

5 楊義先;;具有密碼優(yōu)勢(shì)的置換類[J];計(jì)算機(jī)與網(wǎng)絡(luò);1992年Z1期

6 金中;;座談報(bào)導(dǎo)[J];通信保密;1981年04期

7 JAMESL.MASSEY;林望重;;當(dāng)代密碼學(xué)引論[J];通信保密;1990年03期

8 程貫中,林東岱,張珍;分布式密碼計(jì)算平臺(tái)的架構(gòu)設(shè)計(jì)及其實(shí)現(xiàn)[J];中國(guó)科學(xué)院研究生院學(xué)報(bào);2004年02期

9 金金;;張煥國(guó)教授談抗量子計(jì)算密碼的研究與發(fā)展[J];信息安全與通信保密;2011年08期

10 王磊,祝躍飛;分布式密碼的體系結(jié)構(gòu)和研究?jī)?nèi)容[J];電子與信息學(xué)報(bào);2005年01期

相關(guān)會(huì)議論文 前2條

1 于增貴;;DES密碼終告被破譯[A];四川省通信學(xué)會(huì)1999年學(xué)術(shù)年會(huì)論文集[C];1999年

2 劉景偉;韋寶典;呂繼強(qiáng);王新梅;;AESS盒的密碼特性分析[A];現(xiàn)代通信理論與信號(hào)處理進(jìn)展——2003年通信理論與信號(hào)處理年會(huì)論文集[C];2003年

相關(guān)重要報(bào)紙文章 前6條

1 實(shí)習(xí)生 張琪 本報(bào)記者 孫明河 魏東;王小云：搬倒兩座“密碼大廈”[N];科技日?qǐng)?bào);2005年

2 張曉晶;密碼世界舞動(dòng)的精靈[N];科學(xué)導(dǎo)報(bào);2006年

3 本報(bào)記者 伍平;密碼專家王小云做客科學(xué)大講壇[N];云南科技報(bào);2009年

4 鹿義霞;密碼研究領(lǐng)域追夢(mèng)人[N];光明日?qǐng)?bào);2013年

5 姚明 穆飛林;防不勝防的通信泄密[N];解放軍報(bào);2001年

6 本報(bào)記者 朱杰;奧聯(lián)科技：夯實(shí)信息安全的根基[N];中國(guó)計(jì)算機(jī)報(bào);2008年

相關(guān)博士學(xué)位論文 前2條

1 尹毅峰;基于多態(tài)性密碼的S-盒安全機(jī)制研究[D];西安電子科技大學(xué);2009年

2 韋寶典;高級(jí)加密標(biāo)準(zhǔn)AES中若干問題的研究[D];西安電子科技大學(xué);2003年

相關(guān)碩士學(xué)位論文 前10條

1 旦尼（LEMOTOMO-REMA-DE-MO-KPAGNAN-FREDERIC-DANIEL）;背包密碼研究[D];吉林大學(xué);2016年

2 盧錦元;防共謀欺騙視覺密碼研究[D];解放軍信息工程大學(xué);2011年

3 周瑞宏;HPM視域下“信息安全與密碼”的實(shí)施策略研究[D];西北大學(xué);2009年

4 王美一;積分攻擊的原理及應(yīng)用[D];國(guó)防科學(xué)技術(shù)大學(xué);2009年

5 沈彥;基于離散混沌系統(tǒng)的動(dòng)態(tài)分組加密算法[D];華南理工大學(xué);2013年

6 黃涵淇;級(jí)聯(lián)加密技術(shù)及其在安全電子郵件中應(yīng)用的研究[D];華南理工大學(xué);2012年

7 趙菲;一種基于視覺密碼的SIP身份認(rèn)證方案的研究和實(shí)現(xiàn)[D];西安電子科技大學(xué);2013年

8 陳冬梅;關(guān)于格的基于身份的密碼研究[D];西安電子科技大學(xué);2014年

9 代秀嬌;數(shù)據(jù)密碼編碼技術(shù)在網(wǎng)絡(luò)通信中的研究及其應(yīng)用[D];中北大學(xué);2005年

10 單憶南;基于屬性的加密算法[D];上海交通大學(xué);2010年

，

本文編號(hào)：2287245