隨著多媒體信息在移動(dòng)、手持設(shè)備上應(yīng)用的日益廣泛，人們開始研究低復(fù)雜度、對硬件要求較小的多媒體加密技術(shù)。如今很多音視頻文件格式中（如MPEG4、JPEG、MP3等）都用到了Huffman編碼，基于Huffman編碼的低復(fù)雜度的多媒體加密技術(shù)逐漸進(jìn)入人們的研究視野。

一、MHT加密方法

許多音視頻格式如JPEG、MP3、MPEG的熵編碼階段都是根據(jù)已預(yù)先確定的Huffman碼表進(jìn)行編碼，進(jìn)行數(shù)據(jù)流的轉(zhuǎn)換，這個(gè)過程中可以加入一些加密措施。最早MHT加密方案就是在Huffman碼表中選擇一些合適的表對數(shù)據(jù)流進(jìn)行編碼，再對其選擇的方式和編碼的順序進(jìn)行保密，從而達(dá)到加密的目的。由于普通的經(jīng)訓(xùn)練得到的Huffman碼表數(shù)量有限，進(jìn)行加密的安全性很低，MHT算法就是為了增加Huffman碼表的數(shù)量而又不改變其碼樹的結(jié)構(gòu)，從而增大加密空間來使加密的安全性得到提高。其基本思路是，首先經(jīng)訓(xùn)練得到多媒體數(shù)據(jù)對應(yīng)的基本Huffman碼表，再按一定的方式由基本碼表變換得到變換碼表，在其中選取一部分碼表用來對數(shù)據(jù)流加密，選擇方法是通過使用一個(gè)已產(chǎn)生的密鑰來進(jìn)行。MHT的加密過程如下：

a)先得到基本Huffman碼表，再對其進(jìn)行變換后共得到2k個(gè)碼表，依次標(biāo)記為0一2K-1。

變換方法如圖l所示。若基本Huffrnan碼樹有t個(gè)葉子，就有t-l個(gè)內(nèi)部節(jié)點(diǎn)和對應(yīng)的01標(biāo)記對，先隨機(jī)產(chǎn)生一個(gè)t-l比特的隨機(jī)序列，每一位與碼樹的內(nèi)部節(jié)點(diǎn)相對應(yīng)，序列位上為O則交換對應(yīng)節(jié)點(diǎn)的01標(biāo)記，為l則不交換。

b)生成一個(gè)偽隨機(jī)向量P=(p1，p2…．，Pn)作為密鑰，pi為在0-2&-1范圍內(nèi)的k比特整數(shù)。

c)對原始數(shù)據(jù)的第i段數(shù)據(jù)使用第Pi個(gè)Huff-man碼表進(jìn)行編碼，Pi的值為p(i-l(madn))+l。

這種方法只需要經(jīng)訓(xùn)練得到少量的幾個(gè)基本Huffman表后，再由基本表變換得到大量的Huffman表，相比于由訓(xùn)練得到大量的Huffman表來說方法更簡單。若原Huffinan樹有t-l個(gè)內(nèi)節(jié)點(diǎn)，我們就有t-l個(gè)選擇來決定是否變換每個(gè)內(nèi)節(jié)點(diǎn)對應(yīng)的標(biāo)記對，故可產(chǎn)生2t-1個(gè)不同的Huffman樹，并且變化得到的Huffman樹與原Huffman樹結(jié)構(gòu)一樣，對數(shù)據(jù)流的編碼效率沒有任何影響。MHT方案與直接進(jìn)行Huffinan編碼相比，除了需要再給表加上索引外，基本沒增加太多額外的計(jì)算量，同時(shí)還增加了一定的安全性，但卻需要耗費(fèi)一些額外的內(nèi)存空間來對表進(jìn)行存儲(chǔ)。

二、MHT的安全性分析

對MHT的安全性分析我們均以JPEG算法中的加密DC（直流分量）系數(shù)時(shí)其所對應(yīng)的Huffman編碼樹為例。

唯密文攻擊：在沒有任何明文信息的情況下攻擊者只能通過尋找不同密文塊之間的統(tǒng)計(jì)特性來分析密文，而已經(jīng)證明通過MHT加密后的密文為偽隨機(jī)序列，接近理想的隨機(jī)狀態(tài)，無法使用其統(tǒng)計(jì)特性來進(jìn)行攻擊誓。若使用窮舉攻擊的方法，我們經(jīng)訓(xùn)練能得到4個(gè)基本碼表如圖2所示。若對應(yīng)的Huffman樹有t個(gè)碼值，則變換后共得到4 2t-1個(gè)Huffman樹，選取其中的m個(gè)碼樹，根據(jù)矢量P的值得到總的密鑰空間為：

總的密鑰空間大?。?a >

因其對應(yīng)的Huffman表有12個(gè)碼值，則碼樹有II個(gè)內(nèi)部節(jié)點(diǎn)，我們令m=8，P=128，則可得密鑰空間大?。?/p>

顯然是安全的。

已知明文攻擊：這種攻擊模型中攻擊者需要找出我們所使用的Huffman碼表以及編碼順序才能破譯密文。假如每個(gè)明文符號有至少兩種可能的編碼長度，則N個(gè)符號的密文的可能同步方式大于2~，即使每個(gè)Huffman碼表只有10個(gè)碼值，至少也需要數(shù)百個(gè)密文符號被同步出來，從而才能重構(gòu)出Huffman碼表及編碼順序。由此可見，該算法可有效抵抗已知明文攻擊。若攻擊者得到一串經(jīng)Huffman變換后的密文B=b lb2.6 r~，，對應(yīng)明文為S=s IS2.SN，為了將B分為n塊Si中對應(yīng)的各編碼塊，需要考慮CN:1I種情況，復(fù)雜度為O（ON-1），若能知道N塊的各編碼長度L，則復(fù)雜度可降至O(Lml)。這攻擊中存在的危險(xiǎn)通常是由于編碼時(shí)對Huffman表的選擇不當(dāng)造成的，由于MHT算法中的Huffman表的選擇是隨機(jī)的，其中一種可能就是所選擇的m棵HuFfman樹都來自于同一棵原始樹，各符號又有著一樣的編碼長度。由表l可知所有的符號最多有三種不同的編碼長度，則復(fù)雜度又可降至小于0(313)，而若給定的明文中并未包含所有的這13種符號的話復(fù)雜度會(huì)更低。

如下這種情況也很容易被攻擊者破解：由圖2知，大于5的符號均有三種不同的編碼長度，且c樹、d樹對應(yīng)的編碼長度相同，若給定兩個(gè)大于5的不同密文，當(dāng)它們由同一棵碼樹編碼所得時(shí)，較小符號的編碼為Eu，可得較大符號的編碼為Eux（其中E、X為01字符串，u為O或l，u則為u的非運(yùn)算）。那么若知道任一個(gè)大于符號5的編碼，就能很容易得到小符號的編碼，再利用該編碼可判斷出所屬的基本樹的四種可能：a樹、b樹、c或d樹。當(dāng)為第三種情況時(shí)，我們可以根據(jù)第一個(gè)符號編碼的第一個(gè)比特判斷其屬于c樹還是d樹，從而實(shí)現(xiàn)對第一個(gè)符號的同步。當(dāng)N=200時(shí)，這N個(gè)符號中不存在1的可能性很小，可以忽略不計(jì)。根據(jù)以上條件，我們可以認(rèn)為當(dāng)這N個(gè)符號中存在兩個(gè)不同且都大于5的符號時(shí)，就能實(shí)現(xiàn)對第一個(gè)符號的同步口這種情況發(fā)生的概率為：

其中，x代表明文符號，P{｝代表x的概率。各符號出現(xiàn)的概率由基本Huffman編碼表推導(dǎo)而得a當(dāng)N-200時(shí)，可計(jì)算出Psyn>0.9999，同時(shí)可以獲得這200個(gè)符號的編碼信息，構(gòu)造出8個(gè)Huffman碼表的一部分。后面的信息可使用同樣的方式進(jìn)行分析。若密鑰長度為128，我們能成功同步128次的可能性大于0.987．同時(shí)獲得200*128=25600個(gè)符號及其編碼信息。只要某個(gè)符號出現(xiàn)在已知明文中，就可以恢復(fù)其對應(yīng)的Huffman表的編碼。由于任意一個(gè)小于10的符號不出現(xiàn)在已知明文中的概率小于0.2%，因此我們能以很大的概率恢復(fù)出8個(gè)Huffinan表絕大部分的信息，因此只要能獲得200個(gè)已知明文密文對，就能以大于98.7%的概率破解該密碼。

選擇明文攻擊：MHT在這種情況下的安全性最弱。若攻擊者能夠在密文中插入一個(gè)符號標(biāo)記并能獲得相應(yīng)的輸出密文的話，就完全不存在同步的問題，這對于受保護(hù)者是非常危險(xiǎn)的。并且，如果不限制輸入明文的長度，我們通過每次輸入一個(gè)符號得出使用的第一個(gè)Huffman碼表，再每次輸入兩位獲得第二個(gè)碼表，以此類推，若密鑰P的長度為128．每個(gè)Huffman碼表有12個(gè)編碼符號，只需要輸入128*12次就能破解密鑰P和各Huffman碼表。

通過以上對MHT安全性的分析，NfHT算法存在存儲(chǔ)空間消耗大、不能有效抵抗已知明文和選擇明文攻擊的缺陷，分別提出了對MHT算法的改進(jìn)方案，但后經(jīng)研究發(fā)現(xiàn)這兩種改進(jìn)方案也有著無法抵抗同步攻擊的缺陷，并且會(huì)在一定程度上影n向編碼長度，針對MHT算法的缺陷我們也提出一種改進(jìn)的Huffman表加密方案。

三、改進(jìn)的MHT算法加密

基本MHT算法是利用變換Huffman樹來增大密鑰空間從而起到保密性，但這種方法需要大量的存儲(chǔ)空間，在某些空問受限的設(shè)備上實(shí)現(xiàn)可能比較困難，并且如果對表選擇不當(dāng)會(huì)有很大的安全漏洞。我們可利用一個(gè)偽隨機(jī)序列對基本Huffman樹先進(jìn)行隨機(jī)變化然后直接編碼，不再進(jìn)行Huffman樹的存儲(chǔ)和選擇，過程如下：

a)經(jīng)訓(xùn)練得到基本的Huffman碼表。

b)利用一輸入密鑰生成一個(gè)偽隨機(jī)序列P=(Pl，Pl，…，pn)（使用常用的對稱加密算法即可），將該序列分隔為如下的格式；

均為每四位隔開，其中Chi為Num的前兩比特，目的屜用來選擇使用哪個(gè)基本Huffinan表進(jìn)行擾動(dòng)；Num本身表示擾動(dòng)節(jié)點(diǎn)個(gè)數(shù)；indexv則表示Num個(gè)需要擾亂加密的節(jié)點(diǎn)中每個(gè)所對應(yīng)的序號，如圖3所示。

c)擾動(dòng)的方法就是將對應(yīng)內(nèi)部節(jié)點(diǎn)上的01互換，其與待加密節(jié)點(diǎn)的對應(yīng)關(guān)系及擾動(dòng)方式如圖4所示。

d)原始數(shù)據(jù)中的第i個(gè)節(jié)點(diǎn)使用擾動(dòng)后的Huffman樹進(jìn)行編碼。

計(jì)算代價(jià)分析：這種方法相比MHT方法來講主要多出了對Huffman樹加密擾動(dòng)的代價(jià)，但鑒于對Huffinan樹的加密只涉及查找和比特互換操作，開銷較小，故計(jì)算代價(jià)增加不大。而由于其不用存儲(chǔ)MHT方法中的大量變換Huffman表，又減小了存儲(chǔ)空間的開銷。

安全性分析：攻擊者在沒有密鑰的情況下無法得知所對應(yīng)的各Huffman樹，能起到保護(hù)作用；MHT方法是先對Huffman變換好，得到固定的樹后進(jìn)行存儲(chǔ)，然后從中選撣合適的進(jìn)行加密，而該方法是直接對Huffman樹進(jìn)行隨機(jī)擾動(dòng)，隨著序列P的變化每次擾動(dòng)產(chǎn)生的樹不定，且各種擾動(dòng)的概率沒有明顯的統(tǒng)計(jì)偏向，故能有效抵抗同步攻擊；同時(shí)，由于編碼使用的是擾動(dòng)后的變換樹，即使攻擊者得到了原始的四個(gè)Huffman樹，仍無法通過一些已知明密文對得到二者真正的對應(yīng)關(guān)系來猜測出密鑰，從而使選擇明文攻擊成為不可能。

admin

收藏 海報(bào)分享