一種基于復(fù)合混沌系統(tǒng)的數(shù)字圖像加密算法

 收稿日期：2008-01-08；

修回日期：2008-03-27

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（60703035）； 重慶市自然科學(xué)基金資助項(xiàng)目（2006BB2227）



作者簡介：鄧紹江（1971-），男，重慶人，副教授，博士，主要研究方向?yàn)樾畔踩⒒煦缋碚?sj_deng@cqu.edu.cn)；

張岱固（1981-），男，碩士，主要研究方向?yàn)樾畔踩?/p>

濮忠良(1983-)，男，碩士，主要研究方向?yàn)樾畔踩?

(重慶大學(xué) 計算機(jī)學(xué)院 重慶 400044)

摘要：

利用已有復(fù)合離散混沌動力系統(tǒng)在不變分布和迭代軌跡的若干性質(zhì)，以Logsitic映射產(chǎn)生的離散混沌序列的偽隨機(jī)性作為基礎(chǔ)，選擇迭代函數(shù)產(chǎn)生新的離散混沌序列值，設(shè)計了圖像加密算法。最后討論了算法的安全性，經(jīng)實(shí)驗(yàn)證明此算法使得加密圖像具有很高的保密效果。

關(guān)鍵詞：混沌; 復(fù)合混沌系統(tǒng); 圖像加密

中圖分類號：TP309

文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)10-3097-03

Digital image encryption algorithm based on composite discrete chaotic system

DENG Shao-jiang ZHANG Dai-gu PU Zhong-liang

(College of Computer Science Chongqing University Chongqing 400044 China)

Abstract:

This paper utilized some characteristics on invariant distribution density and iteration track of a composite discrete chaotic dynamical system which had been presented. Used the R sequence based on the pseudo-randomness of Logistic-map to select iteration function in composite discrete chaotic dynamical system to get a new chaotic sequence. According to the above prosented a digital image encryption algorithm. In the end discussed the security of this algorithm. The result of this experiment shows that the encrypted image has high security.

Key words：chaotic; composite chaotic system; image encryption

數(shù)字圖像具有信息直觀、生動形象的特征，是信息的良好載體，現(xiàn)已漸漸成為人們表示信息的重要手段之一。數(shù)字圖像能夠在互聯(lián)網(wǎng)廣泛傳播，方便人們的信息交流。與此同時，隨著互聯(lián)網(wǎng)安全性問題的凸顯，解密技術(shù)以及軟/硬件技術(shù)的高速發(fā)展嚴(yán)重威脅著信息的安全性[1，2]，這就需要可靠安全的數(shù)字圖像加密技術(shù)。混沌是確定系統(tǒng)中出現(xiàn)的一種類隨機(jī)現(xiàn)象，它具有良好的偽隨機(jī)性、統(tǒng)計學(xué)和拓?fù)鋵W(xué)特性，對初始條件極其敏感，且其迭代軌跡在一定程度上不可預(yù)測，但只要系統(tǒng)參數(shù)及其初始條件相同，就能重構(gòu)混沌。由于混沌系統(tǒng)具有以上特性，混沌加密方法研究已成為現(xiàn)代密碼學(xué)的一個重要前沿[3~6]。其中，李紅達(dá)、馮登國提出由兩個非線性離散混沌系統(tǒng)構(gòu)成復(fù)合混沌系統(tǒng)[7~9]，其迭代過程不僅具有對初始條件的敏感性，而且具有依照復(fù)合序列選擇迭代函數(shù)的靈活性，因此迭代過程還具有一定的隨機(jī)性。復(fù)合離散混沌系統(tǒng)產(chǎn)生的離散混沌序列具有獨(dú)立同分布的特性，能很好地抵抗統(tǒng)計分析，是構(gòu)造密碼體系的理想工具。

本文利用復(fù)合混沌序列良好的密碼學(xué)特性，設(shè)計加/解密算法。同時用Arnold置亂，使得加密效果得到了明顯的提高。

1復(fù)合離散混沌系統(tǒng)

定義1設(shè)xi=fq(xi-1)(q=0，1)，是兩個離散混沌動力系統(tǒng)，對任意序列R=(r1，r2，…)∈{0，1}∞，稱

xi=fri(xi-1)； i=1，2，3，…(1)

為這兩個迭代系統(tǒng)在序列R下的復(fù)合離散混沌動力系統(tǒng)（簡稱復(fù)合迭代系統(tǒng)），記為(f0 f1，R)。其中，R稱為復(fù)合序列。對q=0或q=1，xi=fq(xi-1)(i=1，2，3，…)，稱為它的子系統(tǒng)。

一般地，復(fù)合迭代系統(tǒng)保持了所有子迭代系統(tǒng)的混沌特性，比其單個子混沌系統(tǒng)的行為要復(fù)雜得多，因此，其在加密領(lǐng)域的應(yīng)用更加理想。

定理1設(shè)N(q)表示復(fù)合混沌序列R(ri)前N個元素中q的個數(shù)，若limN→∞N(q)/N=α(q)，則復(fù)合迭代系統(tǒng)式(1)的不變分布密度函數(shù)為

ρ(x)=α(0)ρ0(x)+α(1)ρ1(x)(2)

其中: ρ0(x)、 ρ1(x)分別是子系統(tǒng)的不變分布密度函數(shù)。

定義2設(shè)xi=fq(xi-1)，ρ=ρq(x)(q=(0，1))是兩個離散混沌動力系統(tǒng)和對應(yīng)的不變分布，若存在正實(shí)數(shù)0<α<1，使得αρ0(x)+(1-α)ρ1(x)≡1，則稱它們分布互補(bǔ)；若還有f0(x)+f1(x)=1，則稱它們嚴(yán)格互補(bǔ)。

由定義及復(fù)合迭代系統(tǒng)的不變分布式(2)可以看出，分布互補(bǔ)的離散混沌動力系統(tǒng)組一定存在復(fù)合序列R，使得在R下的復(fù)合迭代系統(tǒng)均勻分布。若構(gòu)成它的子系統(tǒng)都是均勻的不變分布，則在任意的復(fù)合序列R下，復(fù)合系統(tǒng)具有均勻的不變分布。

李紅達(dá)等人[9]構(gòu)造復(fù)合離散混沌動力系統(tǒng)如下，在[0，1]定義函數(shù):

f0(x)=1-1-2x 0≤x＜1/2

2x-1 1/2≤x≤1

f1(x)=1-2x 0≤x＜1/2

1-2x-1 1/2≤x≤1(3)

定理2a)f -1q(E)={x:fq∈E}是Lebesgue意義下的保測變換；

b)xi=fq(xi-1)（i=1，2，3，…）是混沌迭代系統(tǒng)，且不變分布函數(shù)均為ρ(x)=1，從而對任意的復(fù)合序列R，(f0 f1 R)具有均勻的不變分布；

c)它們嚴(yán)格互補(bǔ)。

定義算子Tj:[0，1]→{0，1}為Tj(x)=|2jx| mod 2，用于將離散混沌動力系統(tǒng)得到的迭代序列{xi}轉(zhuǎn)換為二進(jìn)制序列{sji}。

定理3設(shè)R={ri}是任意二進(jìn)制序列，{xi}是復(fù)合系統(tǒng)(f0 f1 R)的迭代軌跡，則對任意的j>0，sji=Tj(xi)的各位獨(dú)立同分布，即(a1，a2，a3，…，an)∈{0，1}∞，有P(sji=ai i=1，2，3，…，n)=2-n。

2Arnold映射

本文用Arnold映射實(shí)現(xiàn)圖像置亂，Arnold映射通常也被稱為貓映射[10]，最早由Arnold和Avez提出。其變換方程為



xn+1yn+1=1112 xnyn mod 1(4)

其變換的系數(shù)矩陣C=1112，其行列式等于1，因此貓映射是一個二維保面積、可逆映射，沒有吸引子。貓映射包括拉伸和折疊兩個過程，乘以矩陣C，使x、y變大，相當(dāng)于拉伸；取模使x、y又折回單位矩陣內(nèi)，相當(dāng)于折疊。并且貓映射還是一個混沌映射，也是一個一一映射，單位矩陣內(nèi)的每一點(diǎn)通過變換將惟一地變換到矩陣內(nèi)的另一點(diǎn)。

由于圖像的像素值是以整數(shù)表示的，為了將混沌貓映射應(yīng)用于圖像加密，可以將其進(jìn)行推廣。

首先，令圖像像素點(diǎn)坐標(biāo)x，y∈{0，1，2，…，N-1}，為圖像的寬度，這樣就把相空間推廣到{0，1，2，…，N-1}×{0，1，2，…，N-1}。這樣，式(4)就可以改寫為

xn+1yn+1=1112n x0y0 mod N(5)

其次，更進(jìn)一步地，可以將系數(shù)矩陣推廣到一般情況，即得到如式(6)所示的廣義貓映射。

xn+1yn+1=abcdn x0y0 mod N(6)

令A(yù)=abcd為變換陣，a、b、c、d為正整數(shù)。為了確保映射式(6)仍然為保面積的一對一映射，矩陣A必須滿足：|A|=ad-bc=1。廣義貓映射的逆映射為

x0y0=d-b-can xn+1yn+1 mod N(7)

由于整個過程都是取的整數(shù)進(jìn)行變換，不會引入誤差。加密時根據(jù)條件取定a、b、c、d的值進(jìn)行變換，解密時采用逆變換迭代相應(yīng)次數(shù)即可恢復(fù)。

3算法描述

3.1加密過程

a)以x0為初始值（同時也作為算法解密的密鑰），通過Logistic映射迭代產(chǎn)生混沌序列值。取迭代10 000次甚至更多次的迭代值，將浮點(diǎn)型混沌序列值離散化，轉(zhuǎn)換為{0，1}序列K1={k11，k12，…，k1n}（n=kp。k為位深度，如灰度圖像位深度為8；p為原圖像中像素點(diǎn)個數(shù)）。

b)以x0為初始值，K1序列作為復(fù)合混沌序列式（3）的R序列，迭代產(chǎn)生混沌序列值。通過算子Tj:[0，1]→{0，1}（文中為了方便MATLAB模擬加/解密實(shí)驗(yàn)，取j=1），將浮點(diǎn)型混沌序列值離散化，轉(zhuǎn)換為{0，1}序列K2={k21，k22，…，k2n}。

c)將加密圖像像素值按行排列，降至一維序列，再將像素值轉(zhuǎn)換為二進(jìn)制{0，1}序列，其中的每一位mi完成下列操作：c′i=mik1ik2i。

d)將異或后的{0，1}序列按原斷點(diǎn)還原成加密后的像素值，再將一維序列轉(zhuǎn)換為原圖大小的二維序列，獲得異或后的像素矩陣C′。

e)選定符合條件ad-bc=1的a、b、c、d值及迭代次數(shù)t，用Arnold映射對像素矩陣C′進(jìn)行置亂，得到最后的加密矩陣C即為加密圖像。

3.2解密過程

a)根據(jù)a、b、c、d、t的值，用Arnold映射的逆映射對像素矩陣加密矩陣C進(jìn)行置亂得到矩陣C′。

b)同加密過程的步驟a)b)，以x0為初始值得到離散混沌序列K1、K2。

c)同加密過程的步驟c)d)，對置亂后的矩陣降維、轉(zhuǎn)換成二進(jìn)制位，再進(jìn)行兩次異或運(yùn)算，按原斷點(diǎn)還原成解密后的像素值，再將一維序列轉(zhuǎn)換為原圖大小的二維序列，獲得解密后的圖像矩陣。

4實(shí)驗(yàn)結(jié)果

取密鑰初值x0=0.811 2，Logistic映射中取λ=3.810 4，a=7，b=31，c=2，d=9，t=20，利用加密算法對圖像進(jìn)行加密，無論是二值圖像、灰度圖像還是RGB圖像，其加密結(jié)果均能得到類似于噪聲的均勻圖像，且完全不能從加密圖像中識別原圖像的幾乎任何信息。解密過程則剛好是加密的逆過程，在得到正確密鑰的前提下，對已加密圖像執(zhí)行解密算法，便能得到解密圖像。在解密過程中，若初始值（密鑰）發(fā)生極其細(xì)微的變化，如x0=0.811 200 01，解密后的圖像都將恢復(fù)不到原圖像，且與原圖像差異巨大，基本依然是類似于噪聲的均勻圖像，完全不能獲得原圖像的任何信息。

圖3是256×256的灰度圖像Lena的實(shí)驗(yàn)數(shù)據(jù)。

5實(shí)驗(yàn)結(jié)論及分析

從加密后圖像的直方圖(圖5)可以看出，加密后圖像直方圖與原圖像直方圖(圖4)有很大的不同，且各像素值上像素點(diǎn)數(shù)目近似均勻。變換后的直方圖呈近似均勻分布，很好地掩蓋了變換前的分布規(guī)律。

另外通過對加密圖像和原始圖像中各隨機(jī)選擇了1 000對像素對，測試其水平方向、垂直方向和對角方向的像素相關(guān)系數(shù)(表1)，以及以垂直方向?yàn)槔ㄟ^圖6和7相關(guān)性的對比，可見原圖像中相鄰像素的相關(guān)性很大，而加密后圖像相鄰兩個像素的相關(guān)性明顯降低，從而很好地破壞了統(tǒng)計攻擊。

表1原圖和加密圖像相鄰像素對之間的相關(guān)關(guān)系

相關(guān)系數(shù)原圖像加密圖像

水平方向0.945 80.081 9

垂直方向0.975 90.023 3

對角方向0.904 80.011 3

通過反復(fù)測試與分析，本文運(yùn)用Logistic映射與復(fù)合混沌映射配合產(chǎn)生的離散混沌序列，對原圖像進(jìn)行異或加密，具有混沌序列有利于加密的眾多基本屬性。例如對初始值敏感性高（細(xì)微變化產(chǎn)生完全不同的效果），使得此算法中用窮舉法攻擊幾乎不可實(shí)現(xiàn)，難于破解；在K1作為R序列控制下，復(fù)合離散混沌動力系統(tǒng)式(3)產(chǎn)生的K2序列，提高了對初值的依賴，且此復(fù)合混沌系統(tǒng)具有良好的加密特性，如具有獨(dú)立同分布的特性，使得攻擊者即使通過分析密文C的統(tǒng)計特性也無法得到明文；算法中的異或運(yùn)算在計算機(jī)中易于實(shí)現(xiàn)，圖像加密速度快；對異或后的圖像再進(jìn)行置亂，使得加密過程中復(fù)雜度提高，在算法復(fù)雜度上明顯比只利用一次混沌離散序列異或加密要具有更高的安全性，但必然需要以犧牲一定的加密時間為代價。因此加密時間與安全性的沖突在此算法中依然存在，

亦即此算法有待進(jìn)一步改進(jìn)的地方所在。但從數(shù)字圖像加密安全性的角度分析，在加密時間上做出的一定犧牲，獲得了更高的安全性，仍然是很值得的。

參考文獻(xiàn):

[1]PARKER A T SHORT K M. Reconstructing the keystream from a chaotic encryption scheme[J]. IEEE Trans on Circuits and Systems Ⅰ: Fundamental Theory and Applications 2001，48(5):624-630.

[2]YANG T，YANG L B，YANG C M.Breaking chaotic secure communication using a spectrogram[J].Phys Lett A，1998，247(5):105-111.

[3]MAO Yao-bin，CHEN Guang-rong LIAN Shi-guo. A novel fast image encryption scheme based on 3D chaotic baker maps[J]. Bifurcation and Chaos 2004，14(3):613-624.

[4]LEE P H PEI S C CHEN Yin-yun. Generating chaotic stream ciphers using chaotic systems[J]. Chinese Journal of Physics 2003，41(6):559-581.

[5]BELKHOUCHE F QIDWAI U. Binary image encoding using 1D chaotic maps[C]//Proc of IEEE Region 5 2003 Annual Technical Conference. 2003:39-43.

[6]JAKIMOSKI G KOCAREY L. Chaos and cryptography: block encryption ciphers based on chaotic maps[J]. IEEE Trans on Circuits and System Ⅰ: Fundamental Theory and Applications 2001，48(2):163-169.

[7]李紅達(dá)，馮登國.復(fù)合離散混沌動力系統(tǒng)的序列密碼算法[J].電子學(xué)報，2003，31(8):1209-1212.

[8]李紅達(dá)，馮登國.復(fù)合離散混沌動力系統(tǒng)與hash函數(shù)[J].計算機(jī)學(xué)報，2003，26(4):460-464.

[9]李紅達(dá)，馮登國.基于復(fù)合離散混沌動力系統(tǒng)的序列密碼算法[J].軟件學(xué)報，2003，14(5):991-998.

[10]ARNOLD E A AVEZ A. Ergodic problems of classical mechanics[M]. New Jersey: AddisonWesley 1968.