加密算法對(duì)GIF文件壓縮率的影響

李 濤， 杜寶祥， 梁曉雯

(黑龍江大學(xué) 電子工程學(xué)院，哈爾濱 150080)

0 引 言

目前人們的溝通交流方式趨向于多元化，其中GIF文件作為一種動(dòng)畫媒體豐富了交流的方式。GIF文件同時(shí)具有占用資源小和表達(dá)信息豐富的特點(diǎn)，受到了大眾的青睞。而GIF文件在傳輸和存儲(chǔ)的過(guò)程中安全性容易受到威脅。GIF文件使用LZW壓縮編碼算法，許多專家學(xué)者基于LZW壓縮編碼算法提出一些高安全性的加密算法。Rajeev K等[1]提出一種基于LZW壓縮編碼的高容量可逆數(shù)據(jù)隱藏方案，該方案通過(guò)修改MTF編碼技術(shù)來(lái)隱藏秘密數(shù)據(jù)，并增加了覆蓋媒體元素之間的相似性。利用LZW編碼技術(shù)對(duì)生成的覆蓋數(shù)據(jù)進(jìn)行LZW編碼，以隱藏更多的秘密數(shù)據(jù)，提高了數(shù)據(jù)的加密安全性。Aruna M等[2]提出一種基于LZW壓縮技術(shù)和彩色編碼技術(shù)的大容量數(shù)據(jù)的加密方案。該技術(shù)利用轉(zhuǎn)發(fā)郵件平臺(tái)隱藏秘密數(shù)據(jù)。該算法首先對(duì)秘密數(shù)據(jù)進(jìn)行壓縮，然后將壓縮后的秘密數(shù)據(jù)隱藏在郵件地址和郵件封面信息中。通過(guò)使用顏色編碼表使消息著色，秘密數(shù)據(jù)位嵌入到消息(或覆蓋文本)中。趙文強(qiáng)等[3]提出一種基于改進(jìn)的LZW可逆數(shù)據(jù)隱藏方案，通過(guò)增加用于隱藏秘密的符號(hào)數(shù)量，提高隱藏速度和提取速度，從而達(dá)到更好的隱藏效果。這些加密算法的提出為數(shù)據(jù)的安全性提供了保障，但提高信息安全性忽略了加密算法對(duì)數(shù)據(jù)壓縮率的影響。通過(guò)對(duì)比幾種加密算法，分析不同加密算法對(duì)以LZW壓縮算法作為壓縮方式的GIF文件壓縮率的影響。

1 知識(shí)背景

1.1 Arnold算法

Arnold變換。該變換的本質(zhì)操作是拉伸和折疊，通過(guò)這兩種操作可以改變圖像內(nèi)各像素點(diǎn)的空間位置[4]，破壞像素點(diǎn)之間原來(lái)的關(guān)聯(lián)，降低像素點(diǎn)之間的關(guān)聯(lián)性?？捎糜谝曨l圖像加密中對(duì)視頻圖像進(jìn)行位置置亂操作以達(dá)到對(duì)視頻圖像加密的效果。算法公式為：

(1)

式中，xn和yn分別為二維坐標(biāo)系中某一像素點(diǎn)所在行和列的坐標(biāo)；xn+1和yn+1分別為該像素點(diǎn)經(jīng)過(guò)Arnold矩陣變換后所置換到新位置的行和列的坐標(biāo)；mod為取余運(yùn)算；N代表數(shù)據(jù)變換的維數(shù)，當(dāng)Arnold加密算法用在圖像處理領(lǐng)域時(shí)，N代表被處理圖片的行和列的個(gè)數(shù)，Arnold加密算法只能用來(lái)處理行和列相等的圖片；a、b取不同的值可得到不同的Arnold變換矩陣。a、b的值可以作為Arnold加密算法的秘鑰，使用不同的a、b值生成多個(gè)Arnold變換矩陣處理視頻的不同幀圖像，可以提高視頻信息的安全性。

1.2 Logistic算法

由于Logistic混沌系統(tǒng)具有出色的混沌特性，其被廣泛應(yīng)用在多媒體加密領(lǐng)域[5]，該算法來(lái)源于蟲口模型，其算法公式為：

xn+1=μxn

(2)

式中，xn為當(dāng)前這一代蟲子的數(shù)量；xn+1為下一代的蟲子的數(shù)量。第n代蟲子的數(shù)量是第一代蟲子數(shù)量的μn-1倍，顯然該增長(zhǎng)不符合自然規(guī)律。經(jīng)過(guò)研究后提出一種更合理的Logistic算法，算法公式為：

xn+1=μxn(1-xn)

(3)

當(dāng)μ的取值在(3.569 945 672…，4)之間時(shí)，此式對(duì)初值敏感、不具有周期性、有奇異吸引子，而這些特性正是混沌系統(tǒng)所特有的[6]。

1.3 約瑟夫置亂

約瑟夫置亂加密的原理是使用約瑟夫環(huán)將數(shù)據(jù)進(jìn)行重新排列。約瑟夫環(huán)是一個(gè)數(shù)學(xué)應(yīng)用問題，過(guò)程為N個(gè)人圍著一個(gè)圓桌，對(duì)這N個(gè)人用1，2，3，…，N進(jìn)行標(biāo)記，設(shè)定從第a個(gè)人開始從1數(shù)數(shù)，數(shù)b個(gè)數(shù)并將此人移出，他的下一個(gè)人從1開始標(biāo)記，并從第a個(gè)人開始從1開始數(shù)數(shù)，數(shù)到b個(gè)數(shù)的人移出，依次按照該移出規(guī)則，直到將圓桌上的最后一個(gè)人移出后則游戲結(jié)束[7]。利用該移出規(guī)則按照移出的順序?qū)Υ薔個(gè)人進(jìn)行重新排序就是約瑟夫置亂算法。

1.4 GIF文件和LZW壓縮編碼

圖1 LZW壓縮編碼過(guò)程圖Fig.1 LZW compression coding process diagram

GIF是“圖像交換格式”，可以通過(guò)將多幅彩色圖像連續(xù)播放形成動(dòng)畫，其具有時(shí)間短、體積小、內(nèi)容簡(jiǎn)單、成像相對(duì)清晰等特點(diǎn)。GIF是一種動(dòng)態(tài)圖像媒體。GIF文件被廣泛應(yīng)用于日常交流中，可以增添交流中的趣味性，方便日常溝通。

GIF動(dòng)圖具備幀間相關(guān)性大的特點(diǎn)，多采用LZW壓縮編碼。LZW壓縮編碼又叫“串表壓縮算法”，它通過(guò)建立一個(gè)字符串表，用較短的代碼來(lái)表示較長(zhǎng)的字符串來(lái)實(shí)現(xiàn)壓縮。它是對(duì)數(shù)據(jù)流壓縮編碼的同時(shí)進(jìn)行編譯表的擴(kuò)充編寫，即編譯表不是在壓縮編碼前就建立完成的，而是根據(jù)原始文件動(dòng)態(tài)建立。LZW的編碼過(guò)程見圖1。

LZW壓縮編碼算法中的核心內(nèi)容是編譯表的動(dòng)態(tài)建立過(guò)程，在編碼前首先建立預(yù)定義編譯表，如用數(shù)字“1”表示字符“A”，用數(shù)字“2”表示字符“B”，用數(shù)字“3”表示字符“C”……則預(yù)定義的編譯表中建立了26個(gè)相互映射的規(guī)則。在編碼過(guò)程中根據(jù)輸入的數(shù)據(jù)流及編譯表中已存在的編譯規(guī)則對(duì)編譯表進(jìn)行擴(kuò)展，即為編譯表的動(dòng)態(tài)建立。如對(duì)字符串“TOBEORNOTTOBE ORTOBEORNOT”。若對(duì)該字符串使用預(yù)定義的編譯表進(jìn)行編碼，則需要使用24個(gè)編碼單元，即每一個(gè)字符使用一個(gè)編碼單元進(jìn)行編碼，而使用LZW壓縮編碼算法對(duì)該字符串進(jìn)行編碼，僅需要16個(gè)編碼單元即可完成編碼，在存儲(chǔ)和傳輸?shù)倪^(guò)程占用的資源相對(duì)較少。對(duì)字符串“TOBEORNOTTOBEORTOBEORNOT”編碼的過(guò)程建立的編譯表見表1。通過(guò)該例說(shuō)明，LZW壓縮編碼算法對(duì)相關(guān)性較高的數(shù)據(jù)壓縮效果更好，適合被應(yīng)用于GIF文件壓縮。

表1 動(dòng)態(tài)建立的編譯表Table 1 Dynamically created and compiled tables

2 加密算法對(duì)壓縮率的影響

為測(cè)試使用不同加密方案對(duì)GIF文件壓縮率的影響，使用不同的加密方案對(duì)同一個(gè)GIF文件進(jìn)行加密操作，并測(cè)試加密后密文幀間圖像的相關(guān)性。明文GIF文件分離的彩色圖像分辨率為500×500，GIF分離的彩色圖像見圖2。

圖2 GIF文件幀圖像提取Fig.2 GIF file frame image extraction

使用Logistic算法產(chǎn)生混沌序列與明文數(shù)據(jù)異或加密；使用Arnold算法對(duì)圖像像素位置置亂加密，每幀圖片的加密秘鑰不同；使用約瑟夫算法對(duì)圖像使用位置置亂的方式加密。3種加密方式的加密流程見圖3。使用不同加密算法對(duì)由GIF文件分解生成的一組圖片加密后相鄰幀間相關(guān)系數(shù)的測(cè)試見圖4。

圖3 不同加密算法加密流程Fig.3 Encryption flow chart of different encryption algorithms

由圖4可見，使用Logistic算法加密后的GIF文件相關(guān)系數(shù)較原文件降低，使用Arnold算法加密后的GIF文件相關(guān)系數(shù)較原文件提高，而使用約瑟夫算法對(duì)圖像使用位置置亂的方式加密，相關(guān)系數(shù)不變。

為進(jìn)一步研究使用不同加密算法對(duì)壓縮率的影響，對(duì)加密后的圖像使用LZW壓縮編碼算法編碼重組GIF文件，并計(jì)算文件大小。使用不同加密算法加密后圖像重組GIF文件的大小見表2。

圖4 不同加密算法加密后相鄰幀間相關(guān)系數(shù)Fig.4 Correlation coefficient between adjacent frames after encryption by different encryption algorithms

表2 不同加密算法加密圖像重組GIF文件大小Table 2 Image recombination GIF file sizes encrypted by different encryption algorithms

由圖4及表2可見，使用Logistic加密算法得到的相鄰幀間相關(guān)系數(shù)較原文件低，重組的GIF文件占用內(nèi)存較原文件大；使用Arnold加密算法得到的相鄰幀間相關(guān)系性提高，重組后的GIF文件占用內(nèi)存較原文件??；使用約瑟夫加密算法得到的相鄰幀間相關(guān)系數(shù)和重組GIF文件的大小不變。

3 結(jié) 論

通過(guò)分析及實(shí)驗(yàn)證明，不同加密算法對(duì)GIF文件的壓縮率有不同的影響。在使用加密算法對(duì)文件加密提高文件安全性的同時(shí)，無(wú)論采用何種文件壓縮算法，都需要考慮文件在傳輸和存儲(chǔ)過(guò)程中的資源占用問題，有利于促進(jìn)萬(wàn)物互聯(lián)時(shí)代的發(fā)展。