背包加密算法之非超遞增序列
admin 為了提高背包加密體制的安全性，在對(duì)MH背包公鑰及Shamir攻擊、低密度攻擊方法進(jìn)行深入研究的基礎(chǔ)上，我們提出了一種基于超遞增序列的背包加密算法，對(duì)針對(duì)原始背包的超遞增性攻擊起到了很好的抵抗作用。
一、構(gòu)造無(wú)沖突非超遞增序列
傳統(tǒng)背包加密體制的設(shè)計(jì)思想都是從一個(gè)簡(jiǎn)單的背包問(wèn)題出發(fā)，把一個(gè)易解的背包偽裝成一個(gè)看似困難的背包，這里所說(shuō)的易解背包就是一個(gè)超遞增序列，序列中的元素要滿足第n項(xiàng)(n>1)大于前(n-1)項(xiàng)的和。超遞增序列容易構(gòu)造，使用方便，但它已被證明存在嚴(yán)重的不安全性，而提高其安全性的一個(gè)途徑就是使用非超遞增序列，但使用一般的非超遞增序列會(huì)產(chǎn)生加密“沖突”。如，使用序列(2，4，6，8，10)構(gòu)造背包，把(10100)和(00010)利用MH公鑰系統(tǒng)進(jìn)行加密，密文都是8，這給解密帶來(lái)了困難。若能夠構(gòu)造出無(wú)沖突的非超遞增序列，并把其應(yīng)用于背包公鑰加密體制中，則加密系統(tǒng)的安全性將會(huì)得到提高。
定義1 對(duì)于一個(gè)嚴(yán)格遞增的正 A=(a1，a2，…，an），如果對(duì)任意的1≤k≤n，均有a1+a2+…+ak-1<ak，則序列A稱為超遞增序列，否則序列A稱為非超遞增序列。
定義2 對(duì)于一個(gè)嚴(yán)格遞增的正整數(shù)序列A=(a1，a2，…，an），如果存在1≤i1，i2…iv≤n及1≤j1，j2…jv≤n，且{1≤i1，i2…iv}n{j1，j2…jv}=φ，使得aj1+aj2…+ajv=ai1+ai2…+aiv，則該序列A稱為沖突序列，反之A稱為無(wú)沖突序列。
定義3 如果一個(gè)序列既是非超遞增序列，又是無(wú)沖突序列，則稱該序列為無(wú)沖突非超遞增序列。
根據(jù)上述定義可知，序列{1，3，6，13，27，52}是一個(gè)超遞增序列，而序列{3，5，7，13，27，54}、{4，5，7，9，16，38}均是非超遞增序列，但序列{4，5，7，9，16，38}中存在沖突，因而不是無(wú)沖突非超遞增序列。
下面我們給出一種構(gòu)造無(wú)沖突非超遞增序列的新方法。
定理1 若正整數(shù)序列A=(a1，a2，…，an）滿足以下條件：
(1)an<an+1；
(2)a2+…+an<an+1<a1+a2+…+an。 則序列A為無(wú)沖突的非超遞增序列。 證明：設(shè)序列A的長(zhǎng)度為k，對(duì)k進(jìn)行數(shù)學(xué)歸納證明： (1)當(dāng)k=2時(shí)，顯然有a2>a1，序列中無(wú)沖突項(xiàng)；
(2)當(dāng)k=3時(shí)，因?yàn)閍1+a2>a3+a2>a1，則a1，a2，a3，(al+a2)，(a1+a3)，(a2+a3)，(a1+a2+a3)互不相等，所以序列中無(wú)沖突項(xiàng)；
(3)假設(shè)k≤n時(shí)結(jié)論都成立，下面證明當(dāng)k=n+l時(shí)，序列也滿足無(wú)沖突項(xiàng)要求。
假設(shè)序列a1，a2，…，an，an+1中有沖突項(xiàng)，即存在：
1)若等號(hào)兩邊均無(wú)an+1項(xiàng)，則與歸納假設(shè)矛盾；
2)若等號(hào)兩邊均有an+1項(xiàng)，則兩邊同時(shí)減去an+1項(xiàng)，此時(shí)與1)-樣，產(chǎn)生矛盾。
3)若等號(hào)兩邊僅有一邊含有an+1項(xiàng)，不失一般性，有：
若Ai1+ai2，+…ain-1=0，則：a1+a2...+an>an+1>a2+...an可知等號(hào)不成立；
若Ai1+ai2，+…ain-1≠0，則：
但是由于A>C，B>D，因而上式不成立，產(chǎn)生矛盾。
故當(dāng)k=n+1時(shí)，序列滿足無(wú)沖突項(xiàng)要求。
由(1)，(2)可知，對(duì)于任意長(zhǎng)度的正整數(shù)序列均滿足無(wú)沖突項(xiàng)要求，即A是一個(gè)無(wú)沖突的非超遞增序列，定理得證。
二、背包加密算法之非超遞增序列
基于滿足定理1的無(wú)沖突的非超遞增序列，下面給出一個(gè)改進(jìn)的背包公鑰加密算法，它的思想和MH背包加密體制的思想基本一樣，但在產(chǎn)生私鑰時(shí)使用無(wú)沖突的非超遞增序列。
1、公鑰和私鑰的產(chǎn)生
(1)由收信方產(chǎn)生一個(gè)長(zhǎng)度為n隨機(jī)正整數(shù)序列Y=(y1，y2，…，yn)。
(2)構(gòu)造一個(gè)滿足定理1的無(wú)沖突非超遞增序列A=[al，a2，…，an]，同時(shí)產(chǎn)生模數(shù)P：
(3)收信方根據(jù)非超遞增序列A和模數(shù)P及隨機(jī)序列Y構(gòu)造出序列B=(b1,b2,...bn)，其中bi滿足bi=ai+Pyi(i=1，2，…，n)，即B=A+PY。
(4)收信方將B作為公鑰公開(kāi)，將A和P作為私鑰保存，并將隨機(jī)向量Y銷毀。
2、加密和解密過(guò)程
(1)加密過(guò)程
發(fā)信方用公鑰B對(duì)二進(jìn)制消息M=[m1，m2，…，mn]進(jìn)行加密，得到密文C=b1m1+b2m2，...,+bnmn。
(2)解密過(guò)程
收信方用私鑰A=[a1，a2，…，an]和模數(shù)P對(duì)密文C=b1m1+b2m2，...,+bnmn進(jìn)行解密，得到：
由于私鑰A=[a1，a2，…，an]是全局遞增序列但不是超遞增序列，要求得明文M，需按以下步驟進(jìn)行：
求得的M=[m1，m2，…，mn]即為明文。
3、舉例驗(yàn)證
假設(shè)接收方選定非超遞增序列A=[5，7，11，19，41，79]，發(fā)送方要發(fā)送明文M=[1，1，1，0，0，1]，執(zhí)行以下步驟：
(1)根據(jù)A求得模數(shù)P=163；
(2)由系統(tǒng)產(chǎn)生隨機(jī)向量Y= [657，3029，7568，2935，5995，2097]；
(3)接收方用Y和P將非超遞增序列A轉(zhuǎn)換為普通的隨機(jī)序列B；
(4)接收方將B作為公鑰，將A和P作為私鑰，并銷毀Y；
(5)發(fā)送方利用公鑰B加密明文M=[1，1，1，0，0，1]，得到密文C= 2176315，并將C發(fā)送給接收方；
(6)接收方對(duì)接收到的密文C=2176315，根據(jù)私鑰P=163，計(jì)算出Mr= 2176315(mod163)= 102，并由循環(huán)（*）求得解密明文M。
需要特別注意的是：在普通背包解密中，若檢測(cè)到23>19時(shí)，直接得到23-19=4，并將此處的明文置為1，但在本文解密算法中，需要與a1作比較，因此要跳過(guò)19，并將明文置為0。
另外，由于非超遞增序列和超遞增序列的性質(zhì)一樣，只有唯一解，所以只要找到一個(gè)解，不必再進(jìn)行其他嘗試。
該方法有效地避免了利用非超遞增序列構(gòu)造背包的過(guò)程中出現(xiàn)的難題，同時(shí)還具有高的安全性能，在抵抗Shamir攻擊和低密度攻擊方面都具有良好的性能。
小知識(shí)之公鑰加密公鑰加密，也叫非對(duì)稱（密鑰）加密（public key encryption），屬于通信科技下的網(wǎng)絡(luò)安全二級(jí)學(xué)科，指的是由對(duì)應(yīng)的一對(duì)唯一性密鑰（即公開(kāi)密鑰和私有密鑰）組成的加密方法。它解決了密鑰的發(fā)布和管理問(wèn)題，是目前商業(yè)密碼的核心。在公鑰加密體制中，沒(méi)有公開(kāi)的是明文，公開(kāi)的是密文，公鑰，算法。
