王防修,周 康

(武漢工業(yè)學(xué)院數(shù)理科學(xué)系,湖北武漢 430023)

隨著網(wǎng)絡(luò)化的普及,信息的傳播和共享變得更加方便,同時(shí),信息的安全性受到極大威脅.因此,盡可能地保護(hù)信息的安全是一項(xiàng)艱巨的任務(wù).目前,常用的保護(hù)信息的方法就是對(duì)文件加密[1].由于傳統(tǒng)加密算法是公開(kāi)的,根據(jù)現(xiàn)有計(jì)算機(jī)的計(jì)算能力,如果已知加密算法,一般都能夠借助計(jì)算機(jī)比較快地得到加密的密匙.由于棋盤覆蓋的特殊性和靈活性,使得將其用于文件加密,可以大大增強(qiáng)信息的安全性.即使將該算法公之于眾,想通過(guò)密文和部分明文得到密匙幾乎是一件不可能的事情.

1 棋盤覆蓋[2]的工作原理

定義 1在一個(gè) 2k×2k個(gè)方格組成的棋盤中,如果恰有一個(gè)方格與其它方格不同,則稱該方格為一特殊方格,且稱該棋盤為一特殊棋盤.

顯然,特殊方格在棋盤上出現(xiàn)的位置有 4k種情形.因此,對(duì)?k≥0,有 4k種不同的特殊棋盤.

定義 2所謂棋盤覆蓋,是指要用如圖1所示的 4種不同形態(tài)的L型骨牌覆蓋一個(gè)給定的特殊棋盤上除特殊方格以外的所有方格,且任何兩個(gè) L型骨牌不得重疊覆蓋.

圖14種不同形態(tài)的 L型骨牌

因此,在任何一個(gè) 2k×2k的棋盤覆蓋中,用到的 L型骨牌個(gè)數(shù)恰為 (4k-1)/3.

1.1 用分治法對(duì)一個(gè)特殊棋盤進(jìn)行覆蓋的原理

(1)設(shè) k＞0,將 2k×2k棋盤分割為 4個(gè) 2k-1×2k-1的子棋盤;(2)特殊方格必位于 4個(gè)較小子棋盤之一中,其余 3個(gè)子棋盤中無(wú)特殊方格.為了將這 3個(gè)無(wú)特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤,我們可以用一個(gè)L型骨牌覆蓋這 3個(gè)較小子棋盤的會(huì)合處,這 3個(gè)子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的特殊方格,從而將原問(wèn)題轉(zhuǎn)化為 4個(gè)較小規(guī)模的棋盤覆蓋問(wèn)題;(3)遞歸地使用這種分割,直至棋盤簡(jiǎn)化為 1×1棋盤.

1.2 棋盤覆蓋實(shí)例

設(shè)棋盤覆蓋的遞歸算法如下.

先將棋盤劃分為四個(gè)大小相同的子棋盤,為了敘述方便,不妨將這四個(gè)子棋盤分別稱之為：左上角子棋盤,右上角子棋盤,左下角子棋盤,右下角子棋盤.具體如圖2所示.

圖2 棋盤分割

然后按遞歸覆蓋左上角子棋盤,遞歸覆蓋右上角子棋盤,遞歸覆蓋左下角子棋盤,遞歸覆蓋右下角子棋盤的順序覆蓋整個(gè)棋盤.

當(dāng) k=3,則得到如圖3所示的不同特殊棋盤的棋盤覆蓋.

圖3 k=3時(shí)的兩種不同特殊方格的棋盤覆蓋

從結(jié)果可以看出,不同特殊棋盤上相應(yīng)的格子里有很多內(nèi)容是相同的.

1.3 遞歸算法的改進(jìn)

上述兩種不同特殊方格的棋盤覆蓋的內(nèi)容之所以大同小異,會(huì)不會(huì)是由于采用相同的遞歸算法造成的呢?因此,不妨按遞歸覆蓋右上角子棋盤,遞歸覆蓋左上角子棋盤,遞歸覆蓋右下角子棋盤,遞歸覆蓋左下角子棋盤的順序覆蓋整個(gè)棋盤,則得到如圖4所示的結(jié)果.

圖4 特殊方格坐標(biāo) (1,1)所對(duì)應(yīng)的棋盤覆蓋

與圖3中特殊方格坐標(biāo) (1,1)所對(duì)應(yīng)的棋盤覆蓋相比較,棋盤中的內(nèi)容有很大差別.正是因?yàn)檫@種差別,后面所說(shuō)的加密算法就是充分利用這一點(diǎn)來(lái)達(dá)到目的的.

2 用棋盤覆蓋實(shí)現(xiàn)文件加密的原理

2.1 棋盤大小的選擇

所謂棋盤大小的選擇,實(shí)質(zhì)上就是 k值的合理選擇.為了實(shí)現(xiàn)文件到棋盤的單射[3],棋盤格子的個(gè)數(shù)至少必須等于文件的大小.只有當(dāng)文件的大小為 4k(其中 k為整數(shù)),棋盤的大小才與文件的大小相一致.事實(shí)上,文件的大小往往不可能為 4k.因此,棋盤的大小一般要比文件大.雖然只要棋盤比文件大,都可以實(shí)現(xiàn)文件到棋盤的單射,但考慮到大的棋盤所占的內(nèi)存空間也越大,因此我們一般選擇比相應(yīng)文件要大的較小棋盤.

假設(shè)某個(gè)待加密的文件的大小為 filesize,那么棋盤的大小為 4k,其中 k=min{n|4n≥filesize,n∈Z}.

2.2 根據(jù)棋盤對(duì)文件進(jìn)行加密的過(guò)程

為了簡(jiǎn)單起見(jiàn),我們不妨對(duì)文件進(jìn)行逐個(gè)字節(jié)加密.具體的加密過(guò)程：(1)測(cè)量出要加密的文件的大小為 filesize;(2)順序讀出文件的內(nèi)容;(3)假設(shè)讀出文件的第 i個(gè)字節(jié)的內(nèi)容為 ch,則可以通過(guò) i計(jì)算出棋盤上具體的格子位置,具體方法是

然后通過(guò) ch=ch?board[row][col]mod256實(shí)現(xiàn) ch的加密,其中?表示加密運(yùn)算,board[i][j]表示棋盤上第 i行和第 j列的格子的骨牌號(hào);(4)將加密后的密文依次寫入密文文件中.

2.3 根據(jù)棋盤對(duì)文件進(jìn)行解密的過(guò)程

跟上述的加密過(guò)程相反,我們必須對(duì)密文進(jìn)行逐個(gè)字節(jié)解密.具體的解密過(guò)程：(1)測(cè)量出要解密的文件的大小為 filesize;(2)順序讀出文件的內(nèi)容;(3)假設(shè)讀出文件的第 i個(gè)字節(jié)的內(nèi)容為 ch,則可以通過(guò) i計(jì)算出棋盤上具體的格子位置,具體方法是

然后通過(guò) ch=ch⊕board[row][col]mod256實(shí)現(xiàn) ch的解密,其中⊕表示解密運(yùn)算,board[i][j]表示棋盤上第 i行和第 j列的格子的骨牌號(hào);(4)將解密后的明文依次寫入明文文件中.

3 密匙分析

如果獲得通過(guò)上述方法加密的密文和部分密文所對(duì)應(yīng)的明文[4],同時(shí)又知道加密算法,那么要得到密匙是一件很容易的事情.首先,通過(guò)密文文件的大小,可以計(jì)算出棋盤的大小.如果知道該棋盤的特殊方格所處的位置,則該特殊棋盤的覆蓋唯一確定.因此,密文對(duì)應(yīng)棋盤的特殊方格所處的行號(hào)和列號(hào)就是文件加密的密匙.由加密與解密的過(guò)程知道,此處的加密算法是對(duì)稱性的,即加密與解密的密匙相同.如果棋盤大小為 4k,則特殊方格所處的位置有4k種可能.因此,只要知道兩個(gè)字節(jié)的密文所對(duì)應(yīng)的明文,則只要用解密算法最多嘗試執(zhí)行 4k次,就可以得到密匙.

通過(guò)以上分析,說(shuō)明僅僅用棋盤覆蓋還不足以顯示它在文件加密中的威力.必須對(duì)現(xiàn)有算法加以改進(jìn),才能真正體現(xiàn)棋盤覆蓋對(duì)文件加密的優(yōu)點(diǎn).

4 算法改進(jìn)

前面的算法之所以需要改進(jìn),就是通過(guò)計(jì)算機(jī)算出它的密匙比較容易.出現(xiàn)這種情況原因有三：(1)棋盤的大小可以通過(guò)文件的大小計(jì)算出來(lái);(2)字符加密的對(duì)象可以通過(guò)字符在文件中所處的位置計(jì)算出來(lái);(3)不同字符與棋盤中不同格子的骨牌號(hào)進(jìn)行加密.因此,可以通過(guò)下列方法增加密文解密的難度.

4.1 棋盤大小不受文件大小的限制

為了克服通過(guò)文件能夠計(jì)算出棋盤大小的缺點(diǎn),有必要對(duì)其進(jìn)行改進(jìn).實(shí)際上,只要滿足 2k×2k個(gè)格子的棋盤都可以,只不過(guò)此時(shí)文件中的字符與棋盤的格子之間不存在單射關(guān)系而已,但這并不影響文件的加密與解密.

因此,如果無(wú)法知道 k的具體值,那么就無(wú)法對(duì)密文進(jìn)行解密.顯然,這里的 k就是密匙的一部分.

4.2 文件中不同字符加密對(duì)象的選擇

前面關(guān)于每個(gè)字符的加密對(duì)象完全是由該字符在文件中所處的位置決定的,文件中不同位置的字符對(duì)應(yīng)棋盤中的不同格子,因此棋盤必須比文件大.而改進(jìn)后的棋盤可能比文件大也可能比文件小,當(dāng)棋盤比文件小時(shí),必然存在文件中不同位置的字符被棋盤中同一格子的骨牌號(hào)加密.為了能夠兼容任意大小的棋盤,必須對(duì)字符的加密對(duì)象作出選擇,使得在解密時(shí)也能夠選擇與加密相同的解密對(duì)象.

在具體為文件中的某個(gè)字符選擇加密對(duì)象時(shí),我們可以通過(guò)隨機(jī)函數(shù)來(lái)實(shí)現(xiàn)隨機(jī)選擇棋盤中對(duì)應(yīng)的某個(gè)格子.

由仿射密碼[5]的原理,我們可以將隨機(jī)函數(shù)定義為：e(x)=(ax+b)modm,其中 a,b∈Zm,mod表示取余運(yùn)算.

因此,為了給當(dāng)前的字符選擇棋盤中具體的格子來(lái)進(jìn)行加密,可以通過(guò)下列迭代函數(shù)組實(shí)現(xiàn)隨機(jī)選擇.

隨著 a1,b1,a2,b2的值以及 x,y初始值的不同,那么在加密過(guò)程中選擇的加密對(duì)象就會(huì)有很大的不同.此時(shí)的加密過(guò)函數(shù)為：

顯然,此時(shí)的密匙由 a1,a2,b1,b2,x,y,k組成.

4.3 棋盤遞歸覆蓋算法的選擇

由前面的分析可以知道,對(duì)于相同大小的棋盤,即使特殊方格相同,如果采用不同遞歸覆蓋算法,那么棋盤中的骨牌號(hào)有很大差別.總共有 24種遞歸覆蓋算法,具體加密時(shí),只需選擇其中的一種,只有知道是哪一種遞歸覆蓋算法,才能夠?qū)γ芪倪M(jìn)行解密.

5 算法分析

通過(guò)前面的分析,棋盤覆蓋有 24種算法,而參數(shù) x1,y1,a1,b1,a2,b2每個(gè)都有 232種可能.此外,k有 32種可能,而特殊方格有 4k種情形.因此,密匙空間[6]的大小為 24×232×232×232×232×232×232×32×4k=3×2200+2k,即可供選擇的密匙有 3×2200+2k個(gè).實(shí)踐表明,如果知道加密算法,且知道部分密文對(duì)應(yīng)的明文,要從現(xiàn)有的計(jì)算機(jī)解密出密匙是不可能的.因此,用此種方法對(duì)文件進(jìn)行加密可以大大增強(qiáng)文件的安全性.

6 結(jié)束語(yǔ)

本文通過(guò)對(duì)棋盤覆蓋的介紹,從原理上說(shuō)明將其用于文件加密的可行性.雖然我們?cè)诖颂幉捎玫氖菍?duì)稱性加密,但由于密匙空間太大,非法用戶很難通過(guò)計(jì)算機(jī)計(jì)算出加密的密匙.實(shí)踐表明,應(yīng)用本文所述方法對(duì)文件進(jìn)行加密,可以大大增強(qiáng)信息傳輸?shù)陌踩?

[1] 闞曉初.電子商務(wù)安全中的數(shù)據(jù)加密技術(shù)[J].計(jì)算機(jī)教育,2007(18).

[2] 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].北京：電子工業(yè)出版社,2006.

[3] 吳海濤.數(shù)據(jù)加密技術(shù)的研究與探討[J].科技咨詢,2007(24).

[4] 陳運(yùn).信息加密原理[M].成都：電子科技大學(xué)出版社,1990.

[5] 張周.我國(guó)企業(yè)開(kāi)始重視網(wǎng)絡(luò)安全[J].計(jì)算機(jī)世界 (A9版),2000(3).

[6] 盧開(kāi)澄.計(jì)算機(jī)密碼學(xué) (第三版)[M].北京：清華大學(xué)出版社,2003.