王防修,周 康

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

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

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

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

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

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

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

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

1.1 用分治法對一個特殊棋盤進行覆蓋的原理

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

1.2 棋盤覆蓋實例

設棋盤覆蓋的遞歸算法如下.

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

圖2 棋盤分割

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

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

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

從結果可以看出,不同特殊棋盤上相應的格子里有很多內容是相同的.

1.3 遞歸算法的改進

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

圖4 特殊方格坐標 (1,1)所對應的棋盤覆蓋

與圖3中特殊方格坐標 (1,1)所對應的棋盤覆蓋相比較,棋盤中的內容有很大差別.正是因為這種差別,后面所說的加密算法就是充分利用這一點來達到目的的.

2 用棋盤覆蓋實現文件加密的原理

2.1 棋盤大小的選擇

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

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

2.2 根據棋盤對文件進行加密的過程

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

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

2.3 根據棋盤對文件進行解密的過程

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

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

3 密匙分析

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

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

4 算法改進

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

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

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

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

4.2 文件中不同字符加密對象的選擇

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

在具體為文件中的某個字符選擇加密對象時,我們可以通過隨機函數來實現隨機選擇棋盤中對應的某個格子.

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

因此,為了給當前的字符選擇棋盤中具體的格子來進行加密,可以通過下列迭代函數組實現隨機選擇.

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

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

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

由前面的分析可以知道,對于相同大小的棋盤,即使特殊方格相同,如果采用不同遞歸覆蓋算法,那么棋盤中的骨牌號有很大差別.總共有 24種遞歸覆蓋算法,具體加密時,只需選擇其中的一種,只有知道是哪一種遞歸覆蓋算法,才能夠對密文進行解密.

5 算法分析

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

6 結束語

本文通過對棋盤覆蓋的介紹,從原理上說明將其用于文件加密的可行性.雖然我們在此處采用的是對稱性加密,但由于密匙空間太大,非法用戶很難通過計算機計算出加密的密匙.實踐表明,應用本文所述方法對文件進行加密,可以大大增強信息傳輸的安全性.

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

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

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

[4] 陳運.信息加密原理[M].成都：電子科技大學出版社,1990.

[5] 張周.我國企業(yè)開始重視網絡安全[J].計算機世界 (A9版),2000(3).

[6] 盧開澄.計算機密碼學 (第三版)[M].北京：清華大學出版社,2003.