由于棋盤覆蓋的特殊性和靈活性，使得將其用于文件加密，可以大大增強信息的安全性。即使將該加密算法公之于眾，想通過密文和部分明文得到密匙幾乎是一件不可能的事情。

一、棋盤覆蓋的工作原理

定義1：在一個2k×2k個方格組成的棋盤中，如果恰有一個方格與其它方格不同，則稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤，顯然，特殊方格在棋盤上出現(xiàn)的位置有4k種情形．因此，對vk≥o，有4k種不同的特殊棋盤。

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

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

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

（1）設k>0，將2k×2k棋盤分割為4個2k-1×2k-1的子棋盤；

（2）特殊方格必位于4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，我們可以用—個L型骨牌覆蓋這3個較小子棋盤的會合處，
這3個子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的特殊方格，從而將原問題轉(zhuǎn)化為4個較小規(guī)模的棋盤覆蓋問題；

（3）遞歸地使用這種分割，直至棋盤簡化為1×1棋盤。

2、棋盤覆蓋實例

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

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

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

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

從結果可以看出，不同特殊棋盤上相應的格子里有很多內(nèi)容是相同的。

3、遞歸算法的改進

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

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

二、用棋盤覆蓋實現(xiàn)文件加密的原理

1、棋盤大小的選擇

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

假設某個待加密的文件的大小為filesize，那么棋盤的大小為4k，其中k= min{n4n≥filesize。n∈z｝。

2、根據(jù)棋盤對文件進行加密的過程

為了簡單起見，我們不妨對文件進行逐個字節(jié)加密。具體的文件加密過程：

（1）測量出要加密的文件的大小為filesize；

（2）順序讀出文件的內(nèi)容；

（3）假設讀出文件的第i個字節(jié)的內(nèi)容為ch，則可以通過i計算出棋盤上具體的格子位置，具體方法是：

然后通過ch=ch×board[ row] [col] mod256實現(xiàn)ch的加密，其中×表示加密運算。board[i][j]表示棋盤上第i行和第j列的格子的骨牌號；

（4）將加密后的密文依次寫入密文文件中。

3、根據(jù)棋盤對文件進行解密的過程

跟上述的文件加密過程相反，我們必須對密文進行逐個字節(jié)解密，具體的文件解密過程：

（1）測量出要解密的文件的大小為filesize；

（2）順序讀出文件的內(nèi)容；

（3）假設讀出文件的第i個字節(jié)的內(nèi)容為ch，則可以通過i計算出棋盤上具體的格子位置，具體方法是：

然后通過ch=ch+board[ row][ col] mod256實現(xiàn)ch的解密，其中0表示解密運算，board [i][j]表示棋盤上第i行和第j列的格子的骨牌號；

（4）將解密后的明文依次寫入明文文件中。

admin

收藏 海報分享