基于LZW壓縮提出了一種安全的LZW( SecureLZW，SLZW)編碼算法，SLZW編碼算法利用動態(tài)增長的Huffman樹作為字典，有效地將LZW和動態(tài)Huffman編碼結(jié)合為一個整體，能顯著提高壓縮率。在編碼的過程，利用基于混沌的耦合映像格子(Coupled Map Lattcie，CML)產(chǎn)生隨機比特流控制Huffman樹的編碼，實現(xiàn)在壓縮過程中進(jìn)行加密，達(dá)到較好的安全性。

一、LZW編碼和動態(tài)Huffman編碼

SLZW編碼的思想是建立在LZW編碼和動態(tài)Huffman編碼的基礎(chǔ)上的，下而首先對這兩種編碼作簡單介紹。

LZW編碼的主題思想是用較短的字符串代替較長的字符串實現(xiàn)數(shù)據(jù)壓縮，具體做法為：用一定的規(guī)則選擇一些字符串放進(jìn)字符串表（字典）中，當(dāng)字典中的字符串再次出現(xiàn)時，就可以用字典中的位置索引值代替該字符串。LZW在解碼時可以構(gòu)建出同編碼方同樣的字典，因此，編碼方構(gòu)建的字典沒有必要發(fā)送給解碼方。

動態(tài)Huffman編碼在對數(shù)據(jù)進(jìn)行編碼時不必事先統(tǒng)計數(shù)據(jù)出現(xiàn)的概率信息，它采用的是根據(jù)數(shù)據(jù)輸入動態(tài)構(gòu)建Huffman樹的技術(shù)。更為重要的是，解碼方在解碼時不必事先擁有編碼方構(gòu)建出的Huffman樹，解碼方可以根據(jù)得到的壓縮碼流動態(tài)構(gòu)建出與編碼方一樣的Huffrnan樹，從而恢復(fù)出被編碼的消息。這也是它和LZW編碼結(jié)合起來后解碼方能完全恢復(fù)出編碼方字典的關(guān)鍵。

研究表明，將LZW與Huffman編碼結(jié)合能取得更好的壓縮效果，然而，這些方法均存在一個顯著缺陷，就是沒有將兩個壓縮過程無縫地合并為一個壓縮過程，它們采用的思想都是在LZW壓縮過程中計算出輸出數(shù)據(jù)的概率，然后根據(jù)這些概率再對結(jié)果數(shù)據(jù)進(jìn)行Huffman編碼。本文將動態(tài)Huffman樹結(jié)構(gòu)作為LZW的字典，無需統(tǒng)計數(shù)據(jù)概率信息，一次LZW編碼后即實現(xiàn)了總體壓縮的效果。

二、SLZW算法

1、算法原理

SLZW編碼和解碼的原理如圖1所示，它由兩部分組成：一個經(jīng)過改進(jìn)的基于動態(tài)Huffman樹的LZW編碼器（或者解碼器）和一個密鑰流產(chǎn)生器（SLZW編碼和解碼過程采用相同的密鑰流產(chǎn)生器）。編碼過程為：明文M在密鑰流譬的控制下，通過改進(jìn)的LZW編碼器，產(chǎn)生最終的密文C。解碼過程為其逆過程。

加密算法執(zhí)行過程主要包含三個步驟：首先是產(chǎn)生密鑰流，然后是基于動態(tài)Huffman樹進(jìn)行LZW編碼，最后是異或產(chǎn)生密文輸出。下面本文分別對這三個步驟進(jìn)行詳細(xì)的描述。解碼過程為其逆過程。

2、密鑰流的產(chǎn)生

密鑰流產(chǎn)生分兩步：首先，利用一個基于斜帳篷映射的二維CML混沌系統(tǒng)，CML的定義為：

其中xnj表示空間維為第j維(j=0，1)，時間維為第n維(n=0，1，...)的變量，ε∈(O，1)。f(x)選擇為斜帳篷混沌映射函數(shù)，其定義為：

其中a∈(0，1)。

然后，利用式(3)對產(chǎn)生的混沌變量進(jìn)行二值化處理，生成二進(jìn)制的密鑰流K=kok1…kn。

通過該方法產(chǎn)生的二進(jìn)制隨機序列能夠克服混沌系統(tǒng)在數(shù)字化過程中的精度退化問題，具有較好的密碼學(xué)特性。該密鑰流用來對Huffman樹的構(gòu)建過程進(jìn)行控制，以及與編碼結(jié)果進(jìn)行異或。

3、基于動態(tài)Huffman樹的LZW壓縮

在改進(jìn)的LZW壓縮算法中，我們將LZW中的字典采用動態(tài)Huffman樹進(jìn)行編碼，根據(jù)字典中各詞條出現(xiàn)的頻率分配和調(diào)整其權(quán)值，從而達(dá)到提高LZW壓縮效果的目的。

在編碼的過程中，每當(dāng)有新的符號（或者符號序列）加入到字典中或者字典中現(xiàn)有詞條的頻率改變時，就需要對這棵Huffman樹進(jìn)行更新。Huffman樹中的節(jié)點包含LZW算法中的字典信息。在沒有加入密鑰的情況下，左子樹的編碼值為0，右子樹的編碼值為1。

構(gòu)建初始字典的過程即為創(chuàng)建初始Huffman樹的過程。將信源符號集中的每個符號（即LZW字典中的每個符號）賦初始權(quán)值1，然后按照Huffman樹的構(gòu)建規(guī)則建立初始化的Huffman樹。在將每個符號加入到Huf:fman樹的葉子節(jié)點的過程中，我們依次取出密鑰流中的一位，若該位的值為1，則交換左右節(jié)點的編碼值；否則不交換左右節(jié)點的編碼值。

在利用Huffman樹構(gòu)建的字典進(jìn)行LZW編碼的過程中，每當(dāng)一個符號（或者符號序列）被編碼后，如果它在字典中已經(jīng)存在，便更新其權(quán)值（將其權(quán)值加1），然后根據(jù)新的權(quán)值調(diào)整Huffman樹的結(jié)構(gòu)；如果該符號（或者符號序列）在字典中不存在，則初始化其權(quán)值為l，然后將其加入到Huffman樹中。更新過程跟初始化Huffman樹類似，由密鑰流控制節(jié)點的編碼值。

4、最終密文的生成

雖然本文在前面的步驟中已經(jīng)通過密鑰流混淆了初始化和LZW編碼過程中產(chǎn)生的字典，為了掩蓋密文的統(tǒng)計特性，進(jìn)一步提高安全性，本文利用密鑰流對產(chǎn)生的碼字進(jìn)行異或，產(chǎn)生最后的密文輸出C= COC2...Cn...，即：

其中bn為改進(jìn)的LZW編碼器的輸出。

三、實驗結(jié)果與分析

為了驗證所提出的SLZW算法的正確性和安全性，將其應(yīng)用于GIF圖像加密中，并且采用國際上通用的USC-SIPI圖像測試庫對算法進(jìn)行了測試和驗證（圖片庫中的圖像默認(rèn)是tiff格式，本文將其轉(zhuǎn)換成gif格式后進(jìn)行實驗），實驗結(jié)果表明SLZW算法在顯著提高LZW算法壓縮效率的同時達(dá)到了較好的安全性。但是由于篇幅限制，本文在此只以一幅大小為256 x256的Lena圖像為例。

1、實驗參數(shù)和加解密效果

產(chǎn)生密鑰時需要設(shè)定一些初始參數(shù)，本實驗中各參數(shù)值選取為：a=0.67899，ε=0.11228，x00=0.167862987，xo1=o.870612 439。其中xo0和xo1為二維CML的兩個初始值，a、x00和xo1設(shè)定為算法的密鑰。

圖2(a)是原始圖像效果圖，圖2(b)為利用SLZW算法加密后的結(jié)果，圖2(c)為正常解碼后的固像。從圖2(b)可以看出加密后的圖片呈均勻噪聲分布，不能分辨出任何關(guān)于
明文圖像的有意義的信息。而圖2(c)說明在給定正確密鑰的情況下SLZW算法能夠精確恢復(fù)出明文圖像。

2、壓縮效果分析

對于基于壓縮的加密算法麗言，一個基本的要求是不能因為引入加密而給壓縮效果帶來負(fù)面的影響。對于上述的Lena圖像，SLZW算法的壓縮效果如表1所示。表1分別給
出了原始圖像數(shù)據(jù)的大小、經(jīng)過LZW和SLZW壓縮后圖像數(shù)據(jù)的大小囊通過計算得知，SLZW的壓縮率比LZW提高了10.74t%，可以明顯看出SLZW算法在壓縮效果上優(yōu)于原始的Lzw算法。

3、安全性分析

3.1 密鑰空間分析

一個好的加密算法必須具有足夠大的密鑰空間來抵抗窮舉法的攻擊爭本文中，a，x11和x12作為密鑰，這三個值均是雙精度浮點型。在計算機中，雙精度浮點數(shù)采用IEEE754標(biāo)準(zhǔn)進(jìn)行存儲，這種標(biāo)準(zhǔn)下,浮點數(shù)的尾數(shù)值占52位，故本算法的密鑰空間可以達(dá)到252x3= 2156，具有較大的密鑰空間，可以抵擋窮舉法的攻擊。

3.2統(tǒng)計分析

統(tǒng)計分析是試圖利用密文統(tǒng)計特性恢復(fù)出明文信息，為了能夠抵擋攻擊者采用統(tǒng)計手段破解編碼信息，加密后的圖像應(yīng)具有均勻的直方圖，并且密文圖像相鄰兩像素的相關(guān)性也必須盡可能得低。本實驗分別對明文和密文圖像的直方圖，及其相鄰像素的相關(guān)性進(jìn)行了測試。

圖3顯示了明文圖像和密文圖像的直方圖，通過對比，明文直方圖的分布有多處峰值，而密文的直方圖分布均勻，有效地掩蓋了密文的統(tǒng)計信息，符合安全性要求。

在相關(guān)性測試中，測試了水平、垂直和對角三個方向上兩個相鄰像素之間的相關(guān)性d對實驗圖像分別隨機取出1000對像素點進(jìn)行測試，結(jié)果見圖4和表2。從圖4(a)，4(c)、4(e)和表2的笫2列可以看出，明文圖像中相鄰像素值皇楷狀分布，其相關(guān)系數(shù)都在0.9以上，具有很高的相關(guān)性；而圖4(b)，4|(d)，4(f)和表2的第3列表明，密文圖像中相鄰像素值的分布比較均勻，其相關(guān)性在0.02左右，從而表明密文圖像中相鄰像素的相關(guān)性已經(jīng)非常小，滿足安全性要求。

3.3敏感性分析

攻擊者可能利用差分分析手段來獲取明文圖像和密文圖像之間的相關(guān)信息，這就要求加密算法具有良好的密鑰敏感性和明文敏感性。本實驗測試了SLZW算法對密鑰和明文的敏感性。

為了測試密鑰敏感性，本文分別改變a，x11和x12值中的一位得到新的密文圖像，然后求其與原密文圖像之間的像素改變比率( Number of Pixels Change Rate，NPCR)和像素值的平均標(biāo)準(zhǔn)改變強度(Unified Average Change Intensity，UACI)。測試明文敏感性時，通過改變明文中的一個像素值來得到一幅新的密文圖像，然后求共與原密文圖像之間的NPCR和UACI。其中，a、x11和x12改變一位后的新值分別為0. 663 36,0. 167 924022和0.870 956 579，明文敏感性測試中改變的像素值坐標(biāo)為(100，100)。

表3列出了密鑰和明文敏感性實驗的結(jié)果。觀察可以看出：改變密鑰或者明文的某一位，得到的NPCR均大于0.995，UACI在0.33左右，這表明算法具有良好的密鑰敏感性和明文敏感性，能夠抵抗差分攻擊。

admin

收藏 海報分享