鄧海濤 鄧家先 鄧小梅

(海南大學信息科學技術學院，?？?570228)

(2012年12月6日收到;2013年1月8日收到修改稿)

1 引言

對各類電子信息進行加密，以保證在其處理、存儲、傳送和交換過程的安全性，是保證信息安全的有效措施.同時，為了減少存儲空間、降低傳輸帶寬，就需要對原始數(shù)據(jù)進行高效的壓縮.Shennon指出[1]，冗余度越小，相關性越小，不確定度越大，破譯難度越大，安全性就越高.傳統(tǒng)的先壓縮后加密的方法靈活性低，計算量大，實時性差.一種解決方法就是將壓縮與加密同步實現(xiàn).相對空域加密，變換域加密具有更強的魯棒性.基于離散小波變換(discrete wavelet transform，DWT)平臺的比特平面編碼，如內嵌零樹小波編碼(EZW)[2]和JPEG2000標準[3]已被證實能夠獲得好的圖像壓縮效果，且DWT變換是對圖像的全局變換，不會出現(xiàn)離散余弦變換(discrete cosine transform，DCT)的方塊效應.當前加密領域的研究主要是對空域數(shù)據(jù)的單純加密或基于簡單的非自適應的熵編碼進行加密[4-8].因其所使用的熵編碼器模型簡單，算法復雜度較低，在不進行明文或密文置換條件下，很容易受到攻擊[6].文獻[9]提出采用分組密碼系統(tǒng)在非線性有限域小波變換子帶上加密，但沒有研究算法的壓縮特性.文獻[10]提出一種基于Logistic映射的分組加密系統(tǒng)，將Logistic映射產生隨機二進制序列分成兩部分，一部分用于對明文的置亂，另一部分再與置亂明文進行簡單的異或運算產生密文，但在加密過程中沒有進行密鑰流與明文的相關，使得該算法在明文攻擊時顯得很脆弱.文獻[11]提出了一種基于多級樹集合分割算法(set partitioning in hierarchical trees，SPIHT)的感知加密，通過置換同一父系數(shù)的四個子系數(shù)的位置進行加密，但沒有考慮子帶間相關性，致使壓縮效率不高.文獻[12]研究了在小波變換與SPIHT編碼之間進行加密，因加密發(fā)生在量化和壓縮之前，在有損壓縮中魯棒性極差且影響壓縮效率.本文提出了一種新的簡單有效的基于EZW的圖像壓縮和樹形加密同步算法.該算法充分利用EZW編碼的漸進式傳輸特性和樹形結構，利用Logistic映射生成的密鑰對比特平面編碼過程中產生的上下文和系數(shù)進行修正，再采用高壓縮率的MQ算術編碼進行熵編碼，并將密文反饋給Logistic映射實現(xiàn)密鑰流與明文相關，因加密發(fā)生在比特平面編碼與熵編碼之間，無需進行數(shù)據(jù)置換且不破壞小波子帶系數(shù)之間的相關性，故算法對壓縮性能無影響，并能夠在實現(xiàn)圖像數(shù)據(jù)壓縮的同時，也實現(xiàn)算術加密.實驗結果表明，算法具有良好的壓縮效率和安全性.

2 EZW編碼簡述

Shapiro提出的內嵌零樹小波編碼算法(EZW)[2]利用子帶系數(shù)之間的相似性，取得了高效壓縮效率，即將小波變換后各級HLK，LHK，HHK子帶系數(shù)構成一棵樹，如圖1所示.編碼每次都從最低分辨率系數(shù)開始掃描，如果一棵樹的根及其子孫的小波系數(shù)的絕對值都小于某個給定的閾值(threshold，T)(這棵樹稱為零樹)，可以用一個預定義的符號代表整棵樹，從而提高壓縮比.

圖1 零樹結構

本文算法為每棵樹分配一組密鑰，在比特平面掃描過程中，利用密鑰對每個系數(shù)產生的上下文(context，CX)和判決 (decision，D)進行修正，再送往算術編碼器進行進一步壓縮.這種編碼方式既實現(xiàn)了分辨率壓縮，又達到樹形加密的目的.

3 MQ編碼器及加密可行性分析

算術編碼的最主要優(yōu)點是輸出的碼長能逼近信源的熵，因此廣泛應用于各種壓縮算法，如JPEG，JPEG2000，JBIG和H.264等.MQ算術編碼是一種基于上下文的自適應二進制算術編碼(context based adaptive binary arithmetic coding，CABAC)，是對無乘法器的Q編碼算法的改進，增加了條件交換和概率估計狀態(tài)機中的貝葉斯學習過程，采用Q編碼的位填充策略.與比特平面編碼相結合，編碼從最高有效位(most signi ficant bit，MSB)平面開始到最低有效位(least signi ficant bit，LSB)平面結束，按一定的順序掃描每個位平面，生成編碼數(shù)據(jù)對(CX，D)，再經MQ編碼輸出壓縮的碼流，如圖2所示.

圖2 MQ編碼器輸入輸出模型

MQ編碼器采用一種對原始數(shù)據(jù)快速自適應概率估計模型.輸入數(shù)據(jù)流中的信源符號被分成大概率符號(more probable symbol，MPS)和小概率符號 (less probable symbol，LPS)，把 LPS 的概率記作Qe，CX用于估計D出現(xiàn)的概率.通過查索引表得到索引I(CX)和MPS，若D=MPS，表明概率估計正確，進行CODEMPS編碼，如(1)式所示，否則表明概率估計錯誤，進行CODELPS編碼，如(2)式所示.并通過及時的重整化(renormalization)操作，編碼間隔A始終保持在區(qū)間[0.75，1.5]之間，MQ編碼簡化模型如圖3所示.

圖3 MQ編碼器算法流程圖

因為不同上下文CX對應判決D的初始分布不完全相同，而且后續(xù)輸入判決D的條件概率分布也不完全相同.對于給定的序列，如果上下文CX不同，對應的概率子空間也不相同，編碼輸出的碼字也不相同.如果改變給定序列中的任何一個上下文CX或者判決D，就會導致概率子空間的不同，并會對后續(xù)判決的條件概率分布產生影響.因此，使用密鑰對上下文CX或者判決D進行修正便可以實現(xiàn)壓縮和加密同步進行.

若 D=MPS，則

若 D=LPS，則

4 Logistic映射與密鑰的生成

4.1 偽隨機序列的產生

混沌現(xiàn)象是非線性動力系統(tǒng)中一種確定性的類隨機過程，該過程具有對初始值敏感、遍歷等基本特性，相對工作在有限離散集上的傳統(tǒng)密碼系統(tǒng)，混沌系統(tǒng)工作在無限的連續(xù)實數(shù)集上，而這些都是一個好的密碼系統(tǒng)所期盼的[1]，因此被廣泛應用于加密技術[13-16].本文使用Logistic映射產生混沌軌道[10,17]，如(3)式所示.其中μ為分岔參數(shù)，當μ＞3.57時，Logistic映射處于混沌狀態(tài).

軌道上的每個點采用二進制表示為

其中bi(x)可通過下式得出

上式中Θt(x)是一個門限函數(shù)，其定義如下

通過式(3)—(6)式便可得到具有獨立均勻分布的偽隨機序列其中n是二值序列的長度，τn(x)是Logistic映射第n次迭代時的值.

4.2 密鑰的生成

在本文算法中，x1,x2,···,xK,xK+1是以雙精度浮點型格式表示的Logistic映射的秘密初始值(K為小波分解級數(shù))，這些值被用來為圖1所示的樹形結構每一層節(jié)點生成一個32位二進制密鑰Key.將xi(i∈[1,K+1])迭代32次并得到32個數(shù)據(jù)xi1,xi2,···,xi32.利用4.1節(jié)的方法產生二進制序列

為了保證加密的安全性及加密和解碼雙方同步，本文在加密過程中采用了密文反饋的形式與密鑰流相關.具體實現(xiàn)的方法是對MQ編碼器每生成一字節(jié)的碼流，便用該字節(jié)碼流對當前密鑰重新進行迭代，以生成新的密鑰，如下式所示：

其中Cnum為當前字節(jié)密文，R為要迭代次數(shù).迭代完成后得到R個數(shù)據(jù)xi1,xi2,···,xiD，從中抽取32個數(shù)據(jù)生成 32 位二進制序列

5 圖像壓縮和樹形加密的實現(xiàn)方法

本文提出的基于EZW的壓縮和樹形加密同步算法原理如圖4所示.原始圖像經DWT變換后將原圖數(shù)據(jù)的相關冗余映射成為小波系數(shù)的統(tǒng)計冗余，再進行EZW編碼.在比特平面編碼過程中生成原始編碼數(shù)據(jù)對(CX，D)，用密鑰Key對CX和D分別進行修正，產生修正數(shù)據(jù)對(CX1，D1)，并送往MQ編碼器進行熵編碼，最后輸出壓縮的碼流，從而實現(xiàn)圖像壓縮和按樹形結構加密.

圖4 基于EZW圖像壓縮和樹形加密原理框圖

為使MQ編碼器獲得良好的編碼效率，將比特平面編碼過程中按所使用的是相鄰系數(shù)或相鄰集合的重要性對產生的判決進行了分類以形成上下文.由于比特平面編碼的判決有兩種(即集合判決和系數(shù)判決)，與之相應的將上下文也分為集合上下文和系數(shù)上下文兩種.

集合上下文的計算，本文采用簡單的同分辨率相鄰集合重要性產生，如圖5所示，A表示當前集合重要性，D0，D1，D2，D3表示對角相鄰集合重要性，H0，H1表示水平方向相鄰集合重要性，V0，V1表示垂直方向相鄰集合重要性，它們的取值為{0,1}(其中0代表集合不重要，1代表集合重要).8個周邊集合共形成256種上下文，經合并形成4種集合上下文.集合上下文CXs的計算公式為

其中“|”表示或運算.顯然CXs取值為{0,1,2,3}.

圖5 集合A的相鄰集合

系數(shù)上下文的計算采用最佳截斷嵌入碼塊編碼(embedded block coding with optimized truncation，EBCOT)中的方法[18-21]進一步細化為零編碼上下文、幅值上下文、符號編碼上下文，限于篇幅不再贅述.

基于判決修正的算術加密原理如下：

利用密鑰對位平面產生的二進制判決進行某種運算，使得修正后的判決與原始判決不同，只有當系統(tǒng)編碼和解碼使用相同的密鑰流時才能解碼正確，否則解碼錯誤，從而實現(xiàn)了判決加密.

設 Key 表示加密密鑰流，D=(d1,d2,···,dN)表示編碼產生的原始二進制判決矢量，長度為N，定義一種運算

其中 D1=(d11,d12,···,d1N) 為修正后的二進制判決矢量，長度也為N.

設Key1表示解密密鑰流，表示解碼后的判決矢量，當Key1=Key時，則=D，即當解密使用相同密鑰流時，將正確重建原始判決序列，于是下式成立：

其中 f-1為(9)式對應的逆運算，所以(9)式定義的運算對密鑰流應是可逆的.

基于上下文修正的加密方法如下：

設MQ編碼器的上下文范圍為(m,m+1,···,m+Lm)，設 Key 為加密密鑰流，CX 為原始上下文，取值范圍為 (m,m+1,···,m+L)，CX1為修正后的上下文，取值范圍為 (m,m+1,···,m+L′)，上下文修正可以表示為

其中g(·)表示定義的某種變換，n表示該類上下文出現(xiàn)的順序，L與L′分別表示CX和CX1的種類，且有L＜Lm,L′＜Lm.(11)式需要滿足如下要求：

1)對應給定CX和Key，對于不同的n(即在編碼的不同時刻)，(11)式運算的修正上下文不能總是固定值，即CX1是CX和Key的非線性運算，否則不能實現(xiàn)算術加密.

2)在加密和解密過程中，若比特平面編碼和解碼生成的上下文CX相同，且使用相同的變換和相同密鑰流對CX進行修正，則送往MQ編碼器的修正上下文CX1相同，從而得到正確的解碼.即在加密和解密過程使用相同的運算可保證正確解密，故(11)式可以是不可逆運算.

3)因為MQ編碼使用的各類上下文范圍一定，如果超出MQ編碼使用的某類上下文范圍，則進入其他類別的上下文范圍.而不同類別的上下文所對應的初始概率分布不同，條件概率的跳轉規(guī)律也不相同，進行聯(lián)合壓縮加密時，可能會導致重建圖像質量下降.所以CX1不能超過算術編碼所對應類型的范圍，否則可能導致壓縮的效率下降.

在本文中，判決修正采用簡單的異或運算，對密鑰流Key進行循環(huán)移位得到密鑰流Key1，即首先利用Key的最低位與原始判決進行異或運算，再將密鑰循環(huán)移位一次得到Key1，以供下一次判決修正使用.

上下文修正算法是對密鑰流Key進行循環(huán)移位，取移位后的最低若干位二進制數(shù)據(jù)dk與CX(范圍為 (m,m+1,···,m+L))按下式運算：

其中 mod(·)表示模運算.CX1范圍為 (m,m+1,···,m+Lm).該算法能夠滿足上文所提的上下文修正的三條要求.

結合EZW的比特平面編碼，對整個小波域系數(shù)按樹形結構掃描順序進行加密，能夠實現(xiàn)圖像壓縮和樹形加密同步進行.

6 實驗結果與分析

實驗中采用 (9，7)不可逆浮點 DWT變換，分解級數(shù)為K=3，共需4個Logistic映射初值x1,x2,x3,x4，分別被用來為圖1所示的樹形結構每一層節(jié)點生成一個32位二進制密鑰Key，用其對在比特平面編碼過程中生成的數(shù)據(jù)對(CX，D)分別進行修正，以產生修正數(shù)據(jù)對(CX1，D1)，并送往MQ編碼器進行熵編碼，最后輸出壓縮的碼流，從而實現(xiàn)圖像壓縮和按樹形結構加密同步進行.隨機選擇的4個初始值如下：

6.1 重構圖像的視覺質量

采用標準 8位灰度級圖像 (Lena，Airplane，Barbara，Boat，Baboon)進行測試，在 (12)式中取L=Lm，表1中顯示當圖像壓縮8倍，輸出碼率分別為 0.5 bpp，0.75 bpp，1.00 bpp，1.25 bpp，1.50 bpp時的測試結果.圖6顯示了在碼率為0.5 bpp時重構圖像.結果表明，在相同碼率下，本文算法與原始EZW算法重構圖像質量基本相同，即具有相同的壓縮效果.

6.2 密鑰空間

一個好的加密算法應該對密鑰敏感，密鑰空間應該足夠大來抵抗窮舉攻擊.本文提出的算法密鑰空間大小估計如下：

在K級DWT分解過程中共得到3×K+1個小波子帶.小波子帶的寬度或高度為M/2l(M為原始圖像的寬或高，l為所在的級)，正如在4.2節(jié)所描述的，為圖1中第一棵樹的每一層節(jié)點分配32 bit的密鑰作為初始值，共32×(K+1)bit.MQ編碼每輸出1Byte壓縮碼流，便對密鑰重新迭代一遍，即密鑰是與密文相關的，對一幅大小為M×N的圖像，其編碼字節(jié)數(shù)約為2「log2(M×N)?，所以算法總的密鑰空間是 32×(K+1)×2l「log2(M×N)?bit.當 K=3，圖像大小為512×512時，密鑰空間將達225bit.因此，算法擁有足夠長的密鑰空間.

表1 原始算法與本文算法重構圖像質量PSNR(單位dB)比較

圖6 視覺質量比較 (a)原圖;(b)只壓縮;(c)上下文修正;(d)判決修正;(e)上下文、判決修正;(f)解密錯誤

6.3 抗線性攻擊與差分攻擊分析

6.3.1 密鑰敏感性測試

對密鑰作一微小改變以測試密鑰敏感性，即將Logistic映射初始值小數(shù)點最后1位加1或減 1，再進行壓縮和加密.測試中僅將x1=0.764350394698857改為 x1=0.764350394698858，其他初始值不變.然后對密文進行逐位比較，并計算其bit變化百分比.如表2和表3所示.結果表明，在不同碼率下，位變化百分比都在50%左右，這表明密文對密鑰是敏感的.

6.3.2 明文敏感性測試

由(7)式可知，參數(shù)R通過密文反饋與明文相關，不同的明文使Logistic映射在加密過程中迭代不同次數(shù)，從而產生不同的密鑰流.為了測試明文敏感性，隨機選取兩幅不同的圖像(限于篇幅本次測試只給出Lena圖像和Barbara圖像上下文和判決同時修正的密鑰流對比)，進行同步壓縮加密，產生相應的密鑰流，如表4所示.可以看出，從第二組開始密鑰就不相同，迭代次數(shù)R也不相同，所以算法對明文敏感的.

表2 Lena圖像密鑰敏感性測試(bit變化百分比)

表3 Barbara圖像密鑰敏感性測試(bit變化百分比)

以上測試表明，密文對密鑰和明文都很敏感，從而能夠很好的抵抗差分攻擊和線性攻擊.

6.4 加密與解密速度

表5中列出了Lena圖像在不同碼率下的編碼和解碼時間(表中“加密時間”表示加密時間占總時間的百分比).從表中可以看出，隨著碼率的增大，總的編解碼時間也隨之增加.加密時間占整個算法時間的百分比均小于50%，即加密時間不會超過壓縮時間，這種通過犧牲部分運算來達到良好的壓縮加密效果是非常值得的.

6.5 與其他壓縮和加密算法比較

表6中列出了本文算法與文獻[12]中SPIHT+SHA-1同步加密算法及JPEG+AES先壓縮后加密算法的實驗比較結果.實驗結果表明，當碼率較低時，本文算法重構圖像質量要好于SPIHT+SHA-1算法和JPEG+AES算法，這主要是因為SPIHT+SHA-1算法先對小波系數(shù)加密再量化壓縮致使各分辨率子帶系數(shù)相關性被破壞導致壓縮效率降低引起;而JPEG+AES算法中主要是DCT變換的塊效應引起的.本文算法加密時間占算法總時間百分比較高，因為本文加密算法是對整個壓縮碼流進行了加密，并且密鑰流與明文相關.

表4 Lena圖像和Barbara圖像部分密鑰流

表5 Lena圖像加密和解密速度

表6 本文算法與其他算法重構圖像質量PSNR的比較

7 結論

通過以上分析和仿真表明，本文提出的壓縮和樹形加密同步算法密鑰流與明文相關，因加密發(fā)生在比特平面編碼與熵編碼之間，故算法能夠在實現(xiàn)圖像數(shù)據(jù)壓縮的同時，也實現(xiàn)算術加密.實驗結果表明，加密算法對壓縮效率幾乎沒有影響，且安全性非常好，有很大的密鑰空間，對差分攻擊和線性攻擊具有良好的免疫性具有良好的應用前景.

[1]Shannon C E 1949 Bell System Technical Journal 28 656

[2]Shapiro J M 1993 IEEE Trans.Signal Processing 41 3445

[3]Christopoulos C，Skodras A，Ebrahimi T 2000 IEEE Trans.Consumer Electronics 46 1103

[4]Katti R S，Srinivasan S K，Vosoughi A 2011 IEEE Trans.Information Forensics and Security 6 19

[5]Duan L L，Liao X F，Xiang T 2010 Acta Phys.Sin.59 6744(in Chinese)[段黎力，廖曉峰，向濤2010物理學報59 6744]

[6]Kim H，Wen J T，Villasenor J D 2007 IEEE Trans.Signal Processing 55 2263

[7]Wen J T，Kim H，Villasenor J D 2006 IEEE Signal Processing Lett.13 69

[8]Bose R，Pathak S 2006 IEEE Trans.Circuits Syst.I 53 848

[9]Chan K S，F(xiàn)ekri F 2004 IEEE Trans.Signal Processing 52 2795

[10]Xiang T，Liao X F 2006 Physics Letters A 349 109

[11]Lian S，Sun J，Wang Z 2004 IEEE Int.Conf.Multimedia Expo 3 2195

[12]Yang H Q，Liao X F，Wong K W，Zhang W，Wei P C 2012 Acta Phys.Sin.61 040505(in Chinese)[楊華千，廖曉峰，Wong K W，張偉，魏鵬程2012物理學報61 040505]

[13]Zhou W J，Yu M，Yu S M，Jiang G Y，Ge D F 2012 Acta Phys.Sin.61 080701(in Chinese)[周武杰，郁梅，禹思敏，蔣剛毅，葛丁飛2012物理學報61 080701]

[14]Liu Q，F(xiàn)ang J Q，Zhao G，Li Y 2012 Acta Phys.Sin.61 130508(in Chinese)[劉強，方錦清，趙耿，李永2012物理學報61 130508]

[15]He T T，Luo X S，Liao Z X，Wei Z C 2012 Acta Phys.Sin.61 110506(in Chinese)[何婷婷，羅曉曙，廖志賢，韋正叢2012物理學報61 110506]

[16]Sun K H，He S B，Yin L Z，Duo L K 2012 Acta Phys.Sin.61 130507(in Chinese)[孫克輝，賀少波，尹林子，阿地力·多力坤2012物理學報61 130507]

[17]Yang J Y，Liao X F，Xiao D 2008 Journal on Communications 29 86(in Chinese)[楊吉云，廖曉峰，肖迪2008通信學報29 86]

[18]ISO/IEC JTC 1/SC 29/WG1 FCD 14495 public draft，1997-06.http：//www.jpeg.org/public/jpeglinks.htm.

[19]Taubman D 2002 IEEE Trans.Image Processing 9 1151

[20]Taubman D，Ordentlich E，Weinberger M，Seroussi G 2002 Signal Processing：Image Communication 17 49

[21]Deng J X，Wu C K，Chen J 2004 Acta Optica Sinica 24 299(in Chinese)[鄧家先，吳成柯，陳軍2004光學學報24 299]