基于棋盤覆蓋的文件加密方法
admin 由于棋盤覆蓋的特殊性和靈活性，使得將其用于文件加密，可以大大增強(qiáng)信息的安全性。即使將該加密算法公之于眾，想通過(guò)密文和部分明文得到密匙幾乎是一件不可能的事情。
一、棋盤覆蓋的工作原理
定義1：在一個(gè)2k×2k個(gè)方格組成的棋盤中，如果恰有一個(gè)方格與其它方格不同，則稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤，顯然，特殊方格在棋盤上出現(xiàn)的位置有4k種情形．因此，對(duì)vk≥o，有4k種不同的特殊棋盤。
定義2：所謂棋盤覆蓋，是指要用如圖1所示的4種不同形態(tài)的L型骨牌覆蓋—個(gè)給定的特殊棋盤上除特殊方格以外的所有方格，且任何兩個(gè)L型骨牌不得重疊覆蓋。
因此，在任何一個(gè)2k×2k的棋盤覆蓋中，用到的L型骨牌個(gè)數(shù)恰為(4k-1)/3。
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棋盤。
2、棋盤覆蓋實(shí)例
設(shè)棋盤覆蓋的遞歸算法如下：
先將棋盤劃分為四個(gè)大小相同的子棋盤，為了敘述方便，不妨將這四個(gè)子棋盤分別稱之為：左上角子棋盤，右上角子棋盤，左下角子棋盤，右下角子棋盤，具體如圖2所示。
然后按遞歸覆蓋左上角子棋盤，遞歸覆蓋右上角子棋盤，遞歸覆蓋左下角子棋盤，遞歸覆蓋右下角子棋盤的順序覆蓋整個(gè)棋盤。
當(dāng)k=3，則得到如圖3所示的不同特殊棋盤的棋盤覆蓋。
從結(jié)果可以看出，不同特殊棋盤上相應(yīng)的格子里有很多內(nèi)容是相同的。
3、遞歸算法的改進(jìn)
上述兩種不同特殊方格的棋盤覆蓋的內(nèi)容之所以大同小異，會(huì)不會(huì)是由于采用相同的遞歸算法造成的呢？因此，不妨按遞歸覆蓋右上角子棋盤，遞歸覆蓋左上角子棋盤，遞歸覆蓋右下角子棋盤，遞歸覆蓋左下角子棋盤的順序覆蓋整個(gè)棋盤，則得到如圖4所示的結(jié)果。
與圖3中特殊方格坐標(biāo)(1，1)所對(duì)應(yīng)的棋盤覆蓋相比較，棋盤中的內(nèi)容有很大差別，正是因?yàn)檫@種差別，后面所說(shuō)的加密算法就是充分利用這一點(diǎn)來(lái)達(dá)到目的的。
二、用棋盤覆蓋實(shí)現(xiàn)文件加密的原理
1、棋盤大小的選擇
所謂棋盤大小的選擇，實(shí)質(zhì)上就是k值的合理選擇。為了實(shí)現(xiàn)文件到棋盤的單射，棋盤格子的個(gè)數(shù)至少必須等于文件的大小。只有當(dāng)文件的大小為4k（其中忌k整數(shù)），棋盤的大小才與文件的大小相一致.事實(shí)上，文件的大小往往不可能為4k，因此，棋盤的大小一般要比文件大，雖然只要棋盤比文件大，都可以實(shí)現(xiàn)文件到棋盤的單射，但考慮到大的棋盤所占的內(nèi)存空間也越大，因此我們一般選擇比相應(yīng)文件要大的較小棋盤。
假設(shè)某個(gè)待加密的文件的大小為filesize，那么棋盤的大小為4k，其中k= min{n4n≥filesize。n∈z｝。
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）將加密后的密文依次寫入密文文件中。
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的解密，其中0表示解密運(yùn)算，board [i][j]表示棋盤上第i行和第j列的格子的骨牌號(hào)；
（4）將解密后的明文依次寫入明文文件中。
小知識(shí)之遞歸算法
遞歸算法是把問(wèn)題轉(zhuǎn)化為規(guī)?？s小了的同類問(wèn)題的子問(wèn)題。然后遞歸調(diào)用函數(shù)（或過(guò)程）來(lái)表示問(wèn)題的解。
