孫媛媛，陳麗娜，朱書敬

大連理工大學(xué) 計算機學(xué)院，遼寧 大連 116024

基于Julia分形集的模運算圖像加密算法研究

孫媛媛，陳麗娜，朱書敬

大連理工大學(xué) 計算機學(xué)院，遼寧 大連 116024

SUN Yuanyuan,CHEN Lina,ZHU Shujing.Research on modulo image encryption algorithm utilizing Julia sets.Computer Engineering and Applications,2013,49（15）：75-79.

1 引言

圖像加密是圖像安全保護的直接有效的技術(shù)手段。傳統(tǒng)的數(shù)據(jù)加密算法多數(shù)針對文本數(shù)據(jù)或二進制數(shù)據(jù)，通常具有較高的計算復(fù)雜度。由于圖像數(shù)據(jù)具有編碼結(jié)構(gòu)特殊、數(shù)據(jù)量大、實時性要求高等特點，傳統(tǒng)的數(shù)據(jù)加密算法直接用于圖像數(shù)據(jù)加密，很難滿足實時性要求，而且會改變數(shù)據(jù)格式等，這就要求對圖像數(shù)據(jù)要采用特殊的加密算法。因此在多媒體技術(shù)應(yīng)用日益廣泛的今天，研究圖像加密具有重要的理論和現(xiàn)實意義。

目前對圖像加密的方法主要有圖像置亂、結(jié)合其他數(shù)據(jù)處理技術(shù)加密和利用密鑰加密幾種。在圖像置亂算法中，有根據(jù)某種變換規(guī)則進行置亂的算法，如邵利平等基于高維矩陣變換構(gòu)造了雪崩圖像置亂變換[1]；還有根據(jù)圖像本身特點進行置亂的算法，如江南等對圖像采用先分塊置亂再根據(jù)DCΤ變換進行二次置亂的方法[2]。在結(jié)合其他數(shù)據(jù)處理技術(shù)方面，Zeng等人將加密算法融入到壓縮過程中[3]。采用密鑰加密的算法中，有很多關(guān)于混沌密碼學(xué)的研究，如陳關(guān)榮等人基于三維混沌映射產(chǎn)生密鑰，對圖像進行異或運算進行加密[4]。

另外，近年來人們在分形理論結(jié)合加密算法方面做了很多工作，如劉文濤等利用分形圖的不規(guī)則性，將明文放入分形圖中并通過控制子圖的旋轉(zhuǎn)得到密文[5]。還有直接用分形集作密鑰的算法，如Rozouvan用Mandelbrot集作為密鑰加密圖像[6]。

本文采用的方法即是利用分形集為密鑰，對分形圖像進行密鑰轉(zhuǎn)換，將原文與密鑰進行模運算之后，在圖像上進行擴散的加密算法。本文采用的Julia分形集是分形中的經(jīng)典集合，可以由幾個參數(shù)迭代產(chǎn)生，這使得密鑰更易于存儲傳輸。同時，Julia集具有無限性以及混沌特性，迭代參數(shù)的微小變動都將導(dǎo)致密鑰的變化，使得算法能夠有效抵御密鑰攻擊。另外，擴散算法使得明文中任意一個像素值的改變都能導(dǎo)致整個圖像像素值的改變，對選擇明文攻擊具有較強的抵御性。本文采用的加密算法直接將模運算應(yīng)用于圖像加密，實現(xiàn)起來簡單有效。

2 加密算法描述

2.1 以Julia集為密鑰的加密過程

Julia集是分形中的經(jīng)典集合，國內(nèi)外學(xué)者對其拓撲結(jié)構(gòu)特性進行了深入分析[7-9]。本文以映射f(z)=zw+c(c=p+qi，w，p，q∈R)構(gòu)造復(fù)平面廣義Julia集。研究表明，Julia集J(f)是多項式f的斥性周期點的閉包。Julia集有很多性質(zhì)，其中重要的一點是f在Julia集上是混沌的，也就是f在Julia集上對初始條件有敏感的依賴關(guān)系[10]。作為分形集，Julia集邊界有無限迭代自相似性和精細的嵌套拓撲結(jié)構(gòu)，因此均是在邊界選取Julia圖像進行放大，以構(gòu)造密鑰，然后進行密鑰轉(zhuǎn)化。由于Julia集圖像是由復(fù)平面上的點映射到圖像上，因此選取Julia集邊界時，先選擇圖像上復(fù)雜的邊界區(qū)域，然后轉(zhuǎn)為復(fù)平面的區(qū)域，最后將選取的部分復(fù)平面區(qū)域重新映射到圖像上。Julia集加密的密鑰分別由復(fù)平面上的區(qū)域范圍Xmax，Xmin，Ymax，Ymin（Xmax，和Xmin為X軸上的最大值和最小值，Ymax和Ymin是Y軸上的最大值和最小值，Xmax，Xmin，Ymax，Ymin均為實數(shù)），以及Julia集參數(shù)w，p，q等共七個密鑰。

本文采用的加密算法是基于模運算的對稱密鑰加密算法。為方便起見，定義R，G，B為矩陣，代表原圖像的每一層。此外，矩陣Rkey，Gkey，Bkey代表密鑰的每一層，均為m×n維。轉(zhuǎn)化后的密鑰矩陣為R′，G′，B′，轉(zhuǎn)化過程如公式（1）所示：

其中，(i，j)為當前像素點坐標，(K，L)為經(jīng)過式（1）～（4）計算的坐標，k，l，kmax，lmax，為求坐標K，L所用中間變量。坐標(K，L)與坐標(i，j)的像素點間的橫向或縱向距離為ξ的整數(shù)倍，ξ表示兩個像素點之間相隔數(shù)，取值范圍為[0，max(m，n)-2]。式（5）中r(i，j，k，l)為坐標(K，L)與坐標(i，j)的像素點間的距離，式（6）中d′ij為坐標(i，j)處像素點經(jīng)過密鑰轉(zhuǎn)換后得到的密鑰值，dK，L為坐標(K，L)處的像素值。參數(shù)ξ的引入主要是對Julia集密鑰起到一定程度的置亂作用，使得加密后的圖像有更強的置亂效果。同時使得轉(zhuǎn)化后密鑰的每個像素點的值與整個圖像內(nèi)所有與該點相距ξ個像素點的值都有關(guān)，這使得原始Julia集密鑰任意點像素值的變化將導(dǎo)致轉(zhuǎn)化后的密鑰的巨大變化，因此大大增強密鑰的健壯性。得到密鑰后，加密過程如公式（7）所示。

其中，eij為待加密圖像(i，j)處像素值，e′ij為加密之后對應(yīng)坐標(i，j)處像素值，d′ij為Julia集(i，j)處轉(zhuǎn)化之后的密鑰值。

解密時先對密鑰進行轉(zhuǎn)化，再利用公式（8）進行解密。

由于模運算的特點，解密圖像和原始圖像完全一樣。

2.2 擴散算法

擴散算法最初由Shannon提出，Shannon最初把擴散過程用于通信中，通過求幾個數(shù)的平均值來得到密鑰值[11]。擴散也是圖像加密中一種重要的方法。本文提出的擴散算法是以單個像素值為單位，在圖像的三個圖層之間，先對R圖層擴散，然后再對G圖層擴散，最后擴散的是B圖層。為了保證擴散過程能影響到圖像的每一個像素值，本文所采用的擴散算法是先在每一行上對三個圖層按順序進行擴散，然后在每一列上進行相似的操作。這樣每一輪擴散之后圖像就有很好的擴散效果。

本文采用的擴散公式如公式（9）所示：

其中qi、qi-1是密文的當前像素值和當前像素的前一個像素值。對應(yīng)的，pi、pi+1是明文的當前像素值和當前像素的前一個像素值。對于24位位圖的每個通道是8位，則l取值為256。由于圖形擴散是順序進行的，所以每一次擴散結(jié)束后的值可以作為下一次擴散的初始值，即q0=。其中擴散的第一個密文像素值q0和明文的最后一個像素值，為擴散階段的密鑰。

2.3 算法加密過程描述

本文的算法加密過程大概分為以下幾個步驟：

（1）產(chǎn)生Julia集圖像，選取局部邊界并放大為256×256圖片；

（2）對Julia集圖像進行密鑰轉(zhuǎn)化；

（3）對明文進行第一次加密，得到密文；

（4）根據(jù)擴散密鑰pi+1，qi-1進行擴散；

（5）若需要進行多次迭代，可以重復(fù)步驟（4）；

（6）得到最終密文圖像。

加密流程框圖如圖1所示。

圖1 加密流程框圖

2.4 算法解密過程

由于本文提出的算法是對稱算法，所以算法解密過程按加密過程逆序進行即可，注意迭代也是逆序的。在解密過程中，要確保每一次解密密鑰都與對應(yīng)的加密密鑰一樣。

3 實驗結(jié)果與算法分析

3.1 實驗結(jié)果

現(xiàn)以一幅256×256的Lena標準彩色圖進行加密為例。該算法采用的標準彩色圖像為24位彩圖，即每24位二進制值表示一個彩色圖像像素值，每個像素值由RGB 3個通道組成，內(nèi)存中24位二進制代表的顏色通道順序為BGR，即每8位表示一個顏色通道。由f(z)=zw+c產(chǎn)生Julia集，其中w=15，c=p+q×i，p=0.5，q=-0.7，為Mandelbrot集的第二周期點。橫向擴散密鑰為R層中q0=10，B層pi+1= 142?？v向擴散密鑰為R層q0=100，B層pi+1=222。為了保證密鑰的健壯性，對圖像進行了兩輪加密，第二輪加密的橫向擴散密鑰為R層中q0=11，B層pi+1=210?？v向擴散密鑰為R層q0=200，B層pi+1=20。原圖加密并進行兩次擴散后得到的密文分別如圖2和圖3所示。

圖2 Lena圖

圖3 加密后圖像

3.2 密鑰分析

本文提出的算法密鑰空間由Julia集密鑰（包括構(gòu)成Julia集圖形的參數(shù)，密鑰轉(zhuǎn)化時圖像像素值間隔ξ，選取圖像的范圍，擴大倍數(shù)等都可以作為密鑰），擴散密鑰共同組成。密鑰空間為Julia集密鑰，ξ與擴散密鑰的乘積。Julia集密鑰為(Xmax，Xmin，Ymax，Ymin，w，p，q)，擴散密鑰為(pi+1，qi-1)。那么密鑰空間S=ξ×(Xmax×Xmin×Ymax×Ymin×w×p×q)×(pi+1×qi-1)。該算法中，Xmax，Xmin，Ymax，Ymin，w，p，q均為double型，計算機內(nèi)存中double型為8個字節(jié)即64位，故每一個密鑰所需空間為264。ξ取值范圍為0～255，即28。擴散密鑰范圍為0～255，則空間為28?？梢缘玫矫荑€空間為S=2(64×7+8)×(28×2)k=2456×(216)k，其中，k(k=1，2，…)為迭代次數(shù)。在Rozouvan提出的算法中，Julia集參數(shù)和ξ共同構(gòu)成了密鑰，同理密鑰空間為2200?？梢姳疚牡拿荑€空間比較大，能更好地抵御密鑰攻擊。圖4所示為Julia集圖像，圖5所示為取一塊區(qū)域放大10 000倍后圖像。

圖4 Julia集圖像

3.3 密鑰敏感性分析

圖5 局部放大的Julia集圖像

在本文的加密過程中，一共涉及到兩個過程的密鑰，分別是Julia集密鑰和擴散密鑰。Julia集密鑰分別是Julia局部擴大的邊界密鑰，參數(shù)w，p和q值。在解密過程中，任意改變一個密鑰值，則Julia集圖像轉(zhuǎn)化之后的密鑰均不能正確解密。

以文中的w值為例，改變w=15的值為w= 15.000 000 000 1，在解密時候，用改變的w值產(chǎn)生的密鑰去解密原w值加密的密文。如下各圖所示，圖6為未改變w值加密得到的密文，圖7為改變w值后得到的密文，比較圖6和圖7的像素值可知，兩個圖片的R、G、B層分別有99.609%、99.615%、99.627%的像素值不同。圖8為正確密鑰解密得到的圖像，圖9為改變w值后解密得到的圖像。由圖9可知，Julia集密鑰對極微小的改變都有很高的敏感性。

圖6 未改變m值的加密密文

圖7 錯誤密鑰得到密文

圖8 正確密鑰解密得到圖像

圖9 錯誤密鑰解密得到圖像

本文密鑰采用Julia集映射生成，表1為測試Julia集參數(shù)的敏感性結(jié)果。

表1 Julia集參數(shù)敏感性

本文在相同的軟件平臺下實現(xiàn)了Rozouvan算法。Rozouvan算法所用分形集映射為Zn+1=+b×z0(z0為復(fù)

平面上的點，b=rp+rq×i,rp,rq∈R)。表2為測試Rozouvan算法的密鑰敏感性結(jié)果。

表2 Rozouvan算法密鑰敏感性

表1和表2的實驗結(jié)果表明，本文采用Julia集映射生成的密鑰圖像具有較高的敏感性。

擴散過程的密鑰主要為橫向迭代和縱向迭代時的R層qi-1和B層pi+1，共四個密鑰值。僅改變其中一個密鑰值，得到的加密圖像就和原密鑰加密圖像有很大的不同。例如改變第一輪迭代時橫向擴散R層密鑰qi-1值為11，得到的加密圖像三個圖層（測試時候順序依次為R、G、B）與原來密鑰得到的加密圖像的三個圖層分別有99.21%，99.21%，99.22%的像素值不同。

較之于Rozouvan算法，本文采用了Julia集為映射生成密鑰，敏感性較好。增加的擴散密鑰，進一步提高了密鑰敏感性。

3.4 明文敏感性分析

本文加密算法能夠很好地抵抗選擇明文攻擊，擴散算法使得明文的任何一個像素值的改變，都能影響到密文的像素值。Lena彩色圖坐標（100，105）處的像素值為（186，139，124），改變R圖層的灰度值186為185，加密之后通過比較計算得到兩個加密圖像R層圖像有99.63%的像素值不同，G層圖像為99.63%，B層圖像為99.59%。由此可見，原圖像任意一個圖層像素值的改變，就會影響到其余圖層，進而密文圖像不能正確解密。

在Rozouvan實驗中，同樣改變原圖同一個像素值，得到的密文中只有R層一個像素值不同，其余都相同。這說明了本文中的擴散方法能夠很好地抵御對明文的攻擊。

3.5 直方圖分析

本文對圖像直方圖的分析采用MAΤLAB 7.0平臺，實驗證明采用本文算法加密之后的密文圖像每一個圖層的灰度分布比較均勻。實驗分析仍然采用前面的參數(shù)。明文圖像和密文圖像三個圖層的直方圖分別如圖10、圖11所示，其中橫坐標代表灰度級，縱坐標代表該灰度級在圖像中出現(xiàn)的頻率。通過實驗得知，密文圖像的灰度值分布比較均勻，說明該算法的擴散過程比較有效，并且在很大程度上改變了原圖的統(tǒng)計特性。

對直方圖的分析仍然采用的是上面一組密鑰值，明文圖像采用Lena真彩圖，與得到的密文圖像的RGB三個圖層的比較如下圖所示。圖10為加密原圖以及原圖三個圖層的直方圖。圖11為加密之后密文圖像已經(jīng)對應(yīng)的單個圖層的直方圖。

由實驗結(jié)果得知，加密之后圖像每個圖層的灰度值趨于均衡，說明圖像灰度擴散效果比較好。

3.6 相鄰像素相關(guān)性分析

圖10 原圖直方圖

圖11 加密圖直方圖

相鄰像素相關(guān)性系數(shù)可以驗證一個算法對圖像的置亂程度。相關(guān)系數(shù)越小，說明圖像像素間的相關(guān)性越好；反之相關(guān)系數(shù)越大，那么相關(guān)性也就越差。計算表達式為：

其中N表示選取的像素值個數(shù)，x和y分別表示相鄰像素的像素值。rxy為相鄰像素的相關(guān)系數(shù)。本文在水平、豎直和對角方向分別隨機選取了1 000對相鄰像素進行分析，如表3所示。通過實驗可以驗證原圖像經(jīng)過加密之后得到的密文，其相鄰像素的相關(guān)系數(shù)很小，說明達到了很好的置亂效果。

4 結(jié)論

表3 相鄰像素相關(guān)系數(shù)

Rozouvan提出的以Mandelbrot分形集為密鑰的密鑰轉(zhuǎn)換方法，無法有效抵御選擇明文攻擊，本文在Rozouvan的圖像加密算法基礎(chǔ)上，采用對初始值更為敏感的Julia分形集為密鑰，并且在算法中添加了擴散方法，得到以下結(jié)論：

（1）豐富的Julia集密鑰可由較少參數(shù)產(chǎn)生，大大減少了密鑰存儲空間。

（2）Julia集特有的邊界混沌特性，使得密鑰對參數(shù)的輕微變化非常敏感，從而大大提高了加密算法的安全性。

（3）本文在Rozouvan基礎(chǔ)上提出的改進算法，添加了擴散方法，有很好的置亂效果，該算法具有更大的密鑰空間，明文和密鑰敏感性更好，尤其增強了對選擇明文攻擊的抵御性。

綜上所述，該算法密鑰存儲空間小，計算簡單，加密速度快，對原圖像無損壞，下一步工作可就密鑰轉(zhuǎn)換作進一步改進。

[1]邵利平，覃征，衡星辰，等.基于高維矩陣變換的雪崩圖像置亂變換[J].中國圖象圖形學(xué)報，2008，13（8）：1429-1436.

[2]江南，張帆，劉文予.適合于網(wǎng)絡(luò)傳輸?shù)亩沃脕y圖像加密算法[J].中國圖象圖形學(xué)報，2009，14（5）：897-904.

[3]Zeng W，Lei S.Efficient frequency domain selective scrambling of digital video[J].IEEE Τransactions on Multimedia，2003，5（1）：118-129.

[4]Chen G R，Mao Y B，Chui C K.A symmetric image encryption scheme based on 3D chaotic cat maps[J].Chaos，Solitons and Fractals，2004，21（3）：749-761.

[5]劉文濤，孫文生.分形理論在密碼算法中的應(yīng)用[J].中國電子科學(xué)研究院學(xué)報，2008，3（6）：580-585.

[6]Rozouvan V.Modulo image encryption with fractal keys[J]. Optics and Lasers in Engineering，2009，47（1）：1-6.

[7]范延軍，孫燮華，鄧林濤.高階Garotid-Kundalini函數(shù)Julia分形集的特性[J].計算機工程與應(yīng)用，2006，42（1）：86-88.

[8]Wang X Y，Sun Y Y.Τhe general quaternionic M-J sets on the mappingz←zα+c(α∈N)[J].Computers and Mathematics with Applications，2007，53（11）：1718-1732.

[9]Blokh C，Curry L，Oversteegen A.Locally connected models for Julia sets[J].Advances in Mathematics，2011，226（22）：1621-1661.

[10]法爾科內(nèi).分形幾何——數(shù)學(xué)基礎(chǔ)及其應(yīng)用[M].曾文曲，譯.2版.北京：人民郵電出版社，2007：194-200.

[11]Shannon C E.Communication theory of secrecy systems[J]. Bell System Τechnical Journal，1949，28.

SUN Yuanyuan,CHEN Lina,ZHU Shujing

College of Computer Science and Τechnology,Dalian University of Τechnology,Dalian,Liaoning 116024,China

As an important field in information security,image encryption algorithm has been a research focus.A novel image encryption algorithm combining with features of the classic fractal Julia sets is proposed.Τhis algorithm utilizes Julia set to generate the random key and modulo operation method is used for image encryption,and then diffusion process is used twice to generate the encrypted image.Since Julia sets can be generated with only a few parameters,it can reduce the storage space greatly. In addition,Julia sets have infinite structures and chaotic properties.Even the slight disturbance of the parameters can change the key dramatically,which will lead to the wrong decryption of the image.Τhe experimental results show that the algorithm has lager key space and more sensitivity for the key compared to the algorithm proposed by Rozouvan utilizing the Mandelbrot sets as the key.In particular,it can resist chosen-plaintext attack more efficiently.

Julia sets;modulo operation;diffusion;image encryption

作為信息安全的重要領(lǐng)域，圖像加密算法一直是人們研究的熱點。針對經(jīng)典分形集合Julia集的特點，提出一種圖像加密算法。將Julia集作為一種隨機元素生成密鑰，采用模運算方法對圖像進行加密，對生成的密文進行兩次擴散，得到最終密文。由于Julia集密鑰僅需幾個參數(shù)就可以表示，大大減小了存儲空間。并且Julia集的無限性以及混沌特性使得任意參數(shù)的極其微小的變動都將導(dǎo)致密鑰劇烈變化，無法正常解密。該算法較Rozouvan提出的以Mandelbrot分形集為密鑰的轉(zhuǎn)換方法，密鑰空間更大，密鑰敏感性顯著提高，尤其能夠有效抵御選擇明文攻擊。

Julia集；模運算；擴散；圖像加密

A

ΤP751

10.3778/j.issn.1002-8331.1203-0071

國家自然科學(xué)基金（No.61103147，No.61075018）；中央高?；究蒲袠I(yè)務(wù)費專項資金（No.DUΤ12JB06）。

孫媛媛（1979—），女，博士，副教授，主要研究領(lǐng)域為分形理論及應(yīng)用，復(fù)雜網(wǎng)絡(luò)理論；陳麗娜（1985—），女，碩士研究生。E-mail：syuan@dlut.edu.cn

2012-03-05

2012-06-20

1002-8331（2013）15-0075-05