圖像加密算法中目前使用比較廣泛的有基于四叉樹編碼的圖像加密算法。該加密算法主要對(duì)圖像進(jìn)行四叉樹置亂加密，具有安全性較高、保持?jǐn)?shù)據(jù)編碼格式和數(shù)據(jù)壓縮率不變等優(yōu)點(diǎn)。但它沒有充分利用圖像特性，因此，其加密數(shù)據(jù)最較大，增加了計(jì)算復(fù)雜度。為此，我們?cè)谠摷用芩惴ǖ幕A(chǔ)上，從減少加密數(shù)據(jù)量和提高安全性兩方面入手，提出了一種新的圖像選擇加密算法——基于四叉樹的空城圖像選擇加密算法。

一、四叉樹置亂加密算法

1、四叉樹編碼

四叉樹編碼是最有效的圖像壓縮編碼方法之一，廣泛應(yīng)用于GIS中。其基本思想是將2n×2n像素組成的圖像構(gòu)成的二維平面按4個(gè)象限進(jìn)行遞歸分割，直到子象限的數(shù)值單調(diào)，從而得到一棵四分叉的倒向樹，該樹最高為力級(jí)。對(duì)如圖1(a)所示的圖像，可用四叉樹編碼法得到如圖1(b)所示的四叉樹。四叉樹按存儲(chǔ)方式的不同，分為線性四叉樹和非線性四叉樹2種。一個(gè)含m=2n×2n個(gè)像素的圖像，其四叉樹編碼的時(shí)間復(fù)雜度為o(4m/3)，編碼速度很快。由于四叉樹編碼具有算法簡(jiǎn)單、運(yùn)算速度快、壓縮率大等優(yōu)點(diǎn)，因此廣泛應(yīng)用于圖像編碼中。

2、置亂加密算法

我們提出了2種四叉樹置亂加密算法：（1）將同屬1個(gè)父節(jié)點(diǎn)的4個(gè)子節(jié)點(diǎn)置亂，而保持節(jié)點(diǎn)閬父子關(guān)系不變；（2）將同一高度的節(jié)點(diǎn)（包括葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)）進(jìn)行置亂。2種置亂
算法的密鑰空問分別為：

其中，H表示四叉樹的高度；KHtree表示高度為日的四叉樹置亂后獲得的置亂空間；Nh表示h高度上內(nèi)部節(jié)點(diǎn)的個(gè)數(shù)；Mh表示h高度上葉子節(jié)點(diǎn)個(gè)數(shù)；Ho表示本高度以上（不包含本高
度）的任何高度上都沒有葉子節(jié)點(diǎn)。

通過分析可以看出，第（2）種置亂方法的密鑰宅間更大、加密效果更好且圖像恢復(fù)難度更大。

二、基于四叉樹的空城圖像選擇加密算法描述

本文根據(jù)圖像選擇加密的基本思想，在第（2）種置亂方法的基礎(chǔ)上提出一種新的圖像加密算法。該算法主要過程如下：

（1）取出圖像的1個(gè)位平面，將其捌分為若干16×16的塊。

（2）將每個(gè)16×16的塊劃分為4個(gè)8×8的子塊，并對(duì)其位置置亂。如圖2所示。

（3）對(duì)每個(gè)8×8的子塊進(jìn)行四叉樹編碼。如果64個(gè)值相等，則稱其為均勻的。

1）若不均勻，則將8×8子塊內(nèi)部同一高度的節(jié)點(diǎn)進(jìn)行置亂，如圖3所示。

2）若均勻，則加密其值。

三、基于四叉樹的空城圖像選擇加密算法的實(shí)驗(yàn)結(jié)果

原始圖像為大小為160×160的圖像Lena，置亂和加密采用混沌Logistic映射，即xn+1=4×xn×(1-xn)。初始密鑰為0.34，加密了MSB和第6級(jí)位平面，實(shí)驗(yàn)結(jié)果如圖4所示。

四、基于四叉樹的空城圖像選擇加密算法分析

1、 加密數(shù)據(jù)量

通過加密算法描述可知，本文加密算法的加密過程主要包括以下3個(gè)部分：

（1）對(duì)4個(gè)8×8矩陣塊的位置置亂。

（2）對(duì)非均勻8×8矩陣塊的內(nèi)部置亂。

（3）對(duì)均勻8×8矩陣的加密。

通過仿真實(shí)驗(yàn)得到圖像MSB中均勻和非均勻8×8矩陣塊的比倒，如表1所示。

在位置置亂過程中，因?yàn)閷?duì)每個(gè)8×8矩陣都要進(jìn)行處理，所以加密數(shù)據(jù)量為原MSB的1/64≈1%。由表1可以看出，一般圖像的非均勻8×8像素都在50%以下，因此，內(nèi)部置亂過程涉及的數(shù)據(jù)量最多約為50%，加密過程的數(shù)據(jù)量最多約為50%÷64≈1%。整個(gè)文件加密過程的數(shù)據(jù)量最多約為1%+50%+1%=52%，例如Lena.bmp的加密數(shù)據(jù)量只有1%+34%+ 66%÷64≈36%。

2、安全性分析

加密算法的安全性主要依賴密鑰的安全性，而密鑰的安全性與密鑰空間大小、密文對(duì)密鑰的敏感度有很大關(guān)系。

（1）密鑰空間

內(nèi)部置亂過程在整個(gè)加密過程中占有很大比例。本文內(nèi)部置亂采用“同一高度的節(jié)點(diǎn)一進(jìn)行置亂”。由式（2）可知，8×8矩陣形成的四叉樹高度為3，可得最少的密鑰空間為24H=243，最多的密鑰空間為64！。在位置置亂過程中，16×16矩陣的密鑰空間為4！。

由上述分析可知，當(dāng)每個(gè)高度都只有一個(gè)內(nèi)部節(jié)點(diǎn)時(shí)，內(nèi)部置亂過程會(huì)出現(xiàn)密鑰空間過少的問題。雖然這種情況出現(xiàn)的概率很小，但仍對(duì)算法安全性構(gòu)成威脅。在最極端的情況下，即8×8的像素矩陣中63個(gè)點(diǎn)都同值時(shí)，密鑰空間大小雖然可達(dá)243，但實(shí)際明文空間只有64種情況。此時(shí)只要窮舉明文就能達(dá)到攻擊放果。為了進(jìn)一步提高安全性，本文提出一種對(duì)針對(duì)置亂算法的改進(jìn)算法，其步驟如下：

1）對(duì)待加密圖像文件通過密鑰生成一個(gè)8×8偽隨機(jī)矩陣A。

2）對(duì)待內(nèi)部置亂的8×8矩陣口計(jì)算：

其中，N1是值為1的點(diǎn)的個(gè)數(shù)；No是值為0的點(diǎn)的個(gè)數(shù)。若Drff大于闕值T（如T=44)，則置標(biāo)志位S=1，轉(zhuǎn)第（3）步，若小于T，則置S=0，轉(zhuǎn)第（4）步。

3）對(duì)矩陣A和矩陣B進(jìn)行異或操作得到矩陣B’，轉(zhuǎn)第（4）步。

4）對(duì)矩陣B或B’進(jìn)行內(nèi)部置亂操作。

上述改進(jìn)算法對(duì)只有少數(shù)像素值不同的8×8矩陣和一個(gè)偽隨機(jī)矩陣進(jìn)行異或操作，增加該矩陣四叉樹結(jié)構(gòu)中內(nèi)部節(jié)點(diǎn)的個(gè)數(shù)，從而提高密鑰空間和明文空問。由式（1）可知，增加一個(gè)內(nèi)部節(jié)點(diǎn)，置亂空間大約能提高29倍。因?yàn)閷?duì)每個(gè)8×8矩陣都要添加一個(gè)標(biāo)志位S來表明該矩陣是否進(jìn)行過異或運(yùn)算，所以會(huì)多占1/64×m bit，其中，m指圖像像素個(gè)數(shù)。

（2） 密文對(duì)密鑰的敏感性

雖然內(nèi)部置亂過程完成對(duì)多數(shù)數(shù)據(jù)文件加密，但由表1可以看出，大部分像素屬于均勻8×8塊，因此，對(duì)均勻8×8矩陣的加密同樣具有重要作用。本實(shí)驗(yàn)采混沌Logistic映射，因?yàn)榛煦缬成渚哂谐踔得舾行?，所以即使初值只有很小的改變，迭代多次后產(chǎn)生的偽隨機(jī)序列仍會(huì)出現(xiàn)巨大變化。因此，即使攻擊者獲得了部分明文及相應(yīng)密文，也無法恢復(fù)密鑰流。

admin

收藏 海報(bào)分享