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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 鹿義霞;密碼研究領(lǐng)域追夢人[N];光明日報;2013年

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

6 本報記者 朱杰;奧聯(lián)科技：夯實信息安全的根基[N];中國計算機報;2008年

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

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

2 韋寶典;高級加密標準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視域下“信息安全與密碼”的實施策略研究[D];西北大學(xué);2009年

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

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

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

7 趙菲;一種基于視覺密碼的SIP身份認證方案的研究和實現(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年

，

本文編號：2287245