一種基于復合混沌系統的數字圖像加密算法

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

修回日期：2008-03-27

基金項目：國家自然科學基金資助項目（60703035）； 重慶市自然科學基金資助項目（2006BB2227）



作者簡介：鄧紹江（1971-），男，重慶人，副教授，博士，主要研究方向為信息安全、混沌理論(sj_deng@cqu.edu.cn)；

張岱固（1981-），男，碩士，主要研究方向為信息安全；

濮忠良(1983-)，男，碩士，主要研究方向為信息安全.

(重慶大學 計算機學院 重慶 400044)

摘要：

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

關鍵詞：混沌; 復合混沌系統; 圖像加密

中圖分類號：TP309

文獻標志碼：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

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

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

1復合離散混沌系統

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

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

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

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

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

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

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

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

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

李紅達等人[9]構造復合離散混沌動力系統如下，在[0，1]定義函數:

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，…）是混沌迭代系統，且不變分布函數均為ρ(x)=1，從而對任意的復合序列R，(f0 f1 R)具有均勻的不變分布；

c)它們嚴格互補。

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

定理3設R={ri}是任意二進制序列，{xi}是復合系統(f0 f1 R)的迭代軌跡，則對任意的j>0，sji=Tj(xi)的各位獨立同分布，即(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映射實現圖像置亂，Arnold映射通常也被稱為貓映射[10]，最早由Arnold和Avez提出。其變換方程為



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

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

由于圖像的像素值是以整數表示的，為了將混沌貓映射應用于圖像加密，可以將其進行推廣。

首先，令圖像像素點坐標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)

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

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

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

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

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

3算法描述

3.1加密過程

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

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

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

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

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

3.2解密過程

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

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

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

4實驗結果

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

圖3是256×256的灰度圖像Lena的實驗數據。

5實驗結論及分析

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

另外通過對加密圖像和原始圖像中各隨機選擇了1 000對像素對，測試其水平方向、垂直方向和對角方向的像素相關系數(表1)，以及以垂直方向為例，通過圖6和7相關性的對比，可見原圖像中相鄰像素的相關性很大，而加密后圖像相鄰兩個像素的相關性明顯降低，從而很好地破壞了統計攻擊。

表1原圖和加密圖像相鄰像素對之間的相關關系

相關系數原圖像加密圖像

水平方向0.945 80.081 9

垂直方向0.975 90.023 3

對角方向0.904 80.011 3

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

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

參考文獻:

[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]李紅達，馮登國.復合離散混沌動力系統的序列密碼算法[J].電子學報，2003，31(8):1209-1212.

[8]李紅達，馮登國.復合離散混沌動力系統與hash函數[J].計算機學報，2003，26(4):460-464.

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

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