葉瑞松，莊樂儀

(汕頭大學數(shù)學系,廣東汕頭515063)

基于Baker映射迭路的圖像加密算法

葉瑞松，莊樂儀

(汕頭大學數(shù)學系,廣東汕頭515063)

提出一種基于Baker映射迭路的數(shù)字圖像空間域的編碼新方法，利用Baker映射迭路所得的有限符號串對圖像像素位置編碼，從而對數(shù)字圖像進行置亂，并計算置亂周期和置亂度.在此基礎上，利用Logistic映射的混沌性質對置亂圖像作了進一步的加密.

Baker映射；迭路；置亂；加密

0 引言

數(shù)字圖像置亂在信息隱藏的前處理或者后處理當中是一種常見的處理方法，許多學者提出了有效的置亂方法，如Chen等人[1]用3D混沌映射做圖像加密的置亂處理，丁瑋等人[2]利用Arnold變換置亂圖像，王筍等人[3]則利用FASS曲線掃描的方法置亂.Baker映射是一種混沌映射[4]，因此也被廣泛應用到圖像的置亂加密.茅耀斌等人[4]提出了將離散的二維Baker映射用于圖像置亂，并推廣到三維的情形用于圖像加密[5].趙學峰[6]則結合帳篷映射的折疊方式提出了一種新的離散型Baker變換圖像置亂.

本文以符號動力學為工具，提出了將構造的Baker映射迭路應用于圖像像素位置的編碼，并對圖像進行置亂的方法.與鄒建成等人[7]的置亂方法做比較，結果顯示本文的方法效果明顯較佳.在此基礎上，利用Logistic映射的混沌性質對置亂圖像做進一步的加密，擴散圖像的灰度值以抵抗統(tǒng)計分析的攻擊.

1 相關知識

1.1 迭路

符號動力學指出，如果動力系統(tǒng)的某軌道一定通過一列不同的區(qū)間，將每個區(qū)間用一個符號對應表示，那么就得到這條軌道的迭路[8].

定義設映射F是從集合X到其自身的函數(shù)，Λ為X的子集，如果：

i）若x∈Λ，則F（x）∈Λ；

ii）對于任一點b∈Λ，都存在一點a∈Λ，使得F（a）=b.則稱子集Λ為F的不變集，即F（Λ）=Λ.

設函數(shù)F的不變集Λ=H0∪H1∪…∪HN，滿足int（Hi）∩int（Hj）=?，對任意的i≠j成立，其中，i，j=0，1…，N，N∈Z+.由定義，任一點x∈Λ必對所有的j∈Z滿足Fj（x）∈Ht， 其中t=0，1，…，N.由此可得任一點x∈Λ對應的符號串如下:即對于所有的j∈Z，F(xiàn)sj（x）∈Hsj，故x∈F-j（Hsj），且稱無限雙邊符號串s=…s-2s-1·s0s1s2…為點x的迭路.定義迭標映射h:Λ→Σ為s=h（x）.

1.2 Baker映射

Baker映射是一個綜合壓縮、拉伸、翻轉和折疊的映射，具有混沌的性質，受到數(shù)學家、物理學家和其他從事非線性研究的科研工作者廣泛關注[7].下面構造的兩個Baker映射將用于產(chǎn)生有限的符號串作為圖像空間位置的編碼.

1.2.1 二進制Baker映射

首先考慮如式（2）、（3）所示的二進制Baker映射及其逆映射.

顯然，區(qū)域Λ=［0，1］×［0，1］為式（2）、（3）的不變集.將該區(qū)域劃分為兩個互不相交的區(qū)域H0：，從而得到任一點x∈Λ相應的迭標映射:

其中sj由式（1）決定，j∈Z，式（1）中取N=1.式（2）在y軸上像帳篷映射一樣分段擴張，在x軸上壓縮；而式（3）剛好相反，在x軸上分段擴張，在y軸上壓縮，故與文獻［8］中介紹的幾何馬蹄映射F是相似的，不同之處在于映射F的不變集ΛF是Cantor集,而式（2）、（3）的不變集Λ=［0，1］×［0，1］.Robinson[8]指出，迭標映射hF:ΛF→Σ2是一一對應的.故任一區(qū)域，都有唯一的有限符號串s-n…s-1·s0…sn-1與之對應，即對應的二進制編碼（s0…sn-1，s-n…s-1）唯一，其中，sj=0，1（j=-n，…0，1，…，n-1）.這就保證用此方法對圖像像素點編碼是一一對應的.1.2.2三進制Baker映射

可將二進制Baker映射推廣到三進制，甚至是K進制的情況，并利用其迭路產(chǎn)生的有限符號串作為圖像像素點的K進制編碼.若對區(qū)域Λ=［0，1］×［0，1］從上至下劃分為3等分，即和H2：，仍然將壓縮、拉伸、翻轉和折疊應用于這3個子區(qū)域，則可得到三進制Baker映射式（5）及其逆映射式（6）:

不變集仍為區(qū)域［0，1］×［0，1］，式（1）中取N=2.同樣用式（5）、（6）的迭路對圖像像素點編碼也是一一對應的.Baker映射還可有其他形式，只是式（2）和式（5）的迭路較為復雜，置亂效果較好.如何構造簡單的K進制Baker映射的具體形式見文獻［9-10］.

2 編碼過程

由于二維數(shù)字圖像的像素總數(shù)總是有限的，取有限符號串即可為各像素位置編碼,而編碼的長度是由圖像的大小所決定的.采用K進制Baker映射的迭路進行編碼時,可得到KM×KM個不相交的區(qū)域int（Vs-M…s-1·s0…sM-1），其中M∈Z+，sj=0，1，…，K-1.圖像大小的選取也應該是KM×KM，以保證編碼是一對一的.

下面以2M×2M圖像為例（M∈Z+），敘述采用二進制Baker映射的迭路編碼的步驟.其中Ht的選取（t=0，1）如前面第1節(jié)所述.

步驟1令迭代次數(shù)k=0.對于每一像素位置（i，j），讀取行、列數(shù)均為n=2M的圖像，取相應迭代初始點若點（x0，y0)令s0=t，其中t=0，1.

步驟2令k=k+1，將點（xk-1，yk-1）代入式（2）得到點（xk，yk）.若點（xk，yk）∈Ht，則令sk=t，其中t=0，1.

步驟3重復步驟2，直到k=M-1.得到有限符號串s0s1s2…sM-1.令k=0.

步驟4令k=k+1，將點（x-（k-1），y-（k-1））代入式（3）得到點（x-k，y-k）.如果點（x-k，y-k）∈Ht，則令s-k=t，其中t=0，1.

步驟5重復步驟4，直到k=M.得到有限符號串s-M…s-2s-1.

由上述步驟可得到所有像素位置的二進制編碼（s0s1…sM-1，s-M…s-1），將其轉換為十進制，即為（i，j）上像素的新位置.因為Vs-M…s-1·s0…sM-1，而用于迭代的初始點滿足（x0，y0）∈int（），其中i，j=1，2，…，n，所以編碼是唯一的.這就保證了圖像置亂的可逆性.

三進制Baker映射（或K進制Baker映射）進行編碼的步驟與上面類似，為保證編碼的唯一性，選取的迭代初始點應該在in t（）中，否則若選在邊界上可能會出現(xiàn)迭路不唯一的情況[8].

3 仿真實驗

3.1 二進制編碼置亂

選用256×256的灰度LENA圖像，見圖1（a），作為實驗對象，將其像素矩陣記為I（大小為28×28）.記置亂后的圖像矩陣為I′.用第2節(jié)中編碼方法為I中各像素位置（i，j）編碼，并將編碼轉化為十進制數(shù)對（Rij，Cij），令I′（Rij，Cij）＝I（i，j），即可得到置亂的圖像.圖1（b）～（d）為所得的置亂結果.

圖1 二進制Baker映射迭路編碼的置亂結果

由圖1可看出,置亂2次可達到較好的效果.表1為本算法（記為算法1）與鄒建成等人[7]的二進制Baker映射置亂算法（記為算法2）應用于不同大小圖像置亂的周期比較.

表1 置亂算法周期

由表1可看出，算法1對于2N×2N大小的圖像（N＝2，3，…，10）置亂周期較算法2好.下面對256×256的LENA灰度圖（圖1（a））采用盧振泰等[11]給出的置亂度求法進行數(shù)值實驗，繪制一個周期內兩種算法置亂度的變化曲線，如圖2所示.數(shù)值結果表明，算法1在一個周期內對圖1（a）的置亂度較算法2穩(wěn)定，迭代較少的次數(shù)即可達到較好的置亂效果,置亂周期也較長.

3.2 三進制編碼置亂

圖2 兩種置亂方法置亂度比較

如圖3（a）選用243×243的灰度LENA圖像（即大小為35×35）.結合式（5）、（6），以第2節(jié)中提出的方法為I中各像素位置（i，j）編碼，并將三進制編碼轉化為十進制數(shù)對（Rij，Cij），令I′（Rij，Cij）＝I（i，j），即可得到置亂的圖像I′.圖3（b）～（d）為置亂結果，置亂周期達到2 604.

圖3 三進制Baker映射迭路編碼的置亂結果

3.3 灰度值擴散

為了抵抗統(tǒng)計分析等攻擊，這里利用Logistic映射式（7）在μ?。?.569 9…，4］時產(chǎn)生的數(shù)列處于混沌狀態(tài)的特點[8，12]，生成一個偽隨機矩陣C，用于擴散置亂后圖像的灰度值，達到加密的目的.灰度值的擴散采用按位異或，加法和取模的算法[1].

由式（7）的特點，選擇參數(shù)μ、初始值x0和加密次數(shù)n作為密鑰對圖像進行加密，圖像加密的具體過程如下.

步驟1采用3.1節(jié)提出的二進制編碼置亂方法將原圖像I置亂一次得到圖像I′.

步驟2由式（7），取初始值x0∈（0，1），μ＝4，產(chǎn)生一個與原圖像等大的隨機矩陣C（記其行數(shù)為r，列數(shù)為c），令C＝floor（L·C），其中，L為該圖像的灰度級.

步驟3用式（8）、（9）擴散I′的灰度值.

其中2≤i≤r，1≤j≤c，L為圖像的灰度級，⊕表示按位異或運算.重復上述步驟k次可得到加密k次的圖像I″.式（8）、（9）的逆變換為:

解密為上述過程的逆過程.圖4（b）～（d）為對256×256大小的NA灰度圖加密解密結果，加密次數(shù)為3次，密鑰x0=0.712 345 678 901 234 5，錯誤解密的密鑰為x0′=0.712 345 678 901 234 6，可見10-16的差別就不能正確解密，密鑰空間為10-16.圖4（e）～（h）為加密前后對應的灰度值直方圖.

圖4的實驗結果顯示，加密后圖像的灰度直方圖能夠較均勻地分布，正確解密結果與原圖信息一致.隨機選取圖像中1 000對相鄰的像素，計算原圖和密圖的相關系數(shù)如表2所示.由表2可看出，該算法能夠有效地削弱圖像相鄰點之間的相關性.

表2 LENA原圖和密圖的相關系數(shù)

圖4 LENA圖三次加密、解密圖像及對應直方圖

最后我們測試了明文一個像素的改變對密文的影響，圖5為像素變化率NPCR[1]和歸一化平均變化強度UACI[1]隨加密次數(shù)增加的變化圖.總體來看,隨著加密次數(shù)增加，一個像素的改變對密文圖像的影響加大.

圖5 NPCR和UACI變化圖

4 結語

與常用的利用離散Baker映射或者其截斷變換進行置亂不同，本文利用Baker映射產(chǎn)生的迭路對圖像各像素位置進行編碼，得到編碼矩陣用于將數(shù)字圖像置亂，避免了由計算機精度問題導致多次變換后圖像像素值丟失的情況.數(shù)值實驗表明，與鄒建成等[7]的二進制Baker映射置亂方法比較，本文利用二進制Baker映射的迭路編碼的方法在穩(wěn)定性和置亂周期都有優(yōu)勢.最后利用Logistic映射混沌性質對置亂后圖像灰度值進行擴散，得到進一步加密的圖像.

[1] Chen Guangrong,Mao Yaobin,Chui Charles K.A symmetric image encryption scheme based on 3D chaotic cat maps [J].Chaos,Solitons and Fractals,2004（21）：749-761.

[2] 丁瑋,閆偉齊,齊東旭.基于Arnold變換的數(shù)字圖像置亂技術[J].計算機輔助設計與圖形學報，2001，13（4）：338-344.

[3] 王筍,徐小雙.Hilbert曲線掃描矩陣的生成算法及其MATLAB程序代碼[J].中國圖象圖形學報,2006,11（1）：119-122.

[4] 茅耀斌，戴躍偉,王執(zhí)銓.一種基于Baker映射的圖像信息隱藏方法[J].南京理工大學學報，2002，26（2）：152-156.

[5] 廉士國,茅耀斌,王執(zhí)銓.Baker映射三維擴展及其在多媒體加密中的應用[J].控制與決策,2004,19（6）：714-717.

[6] 趙學峰.基于面包師變換的數(shù)字圖像置亂[J].西北師范大學學報,2003，2（39）：26-29.

[7] 鄒建成，齊東旭,熊昌鎮(zhèn).基于面包師變換的數(shù)字圖像加密[J].北方工業(yè)大學學報，2003，15（1）：6-10，61.

[8] Clark R R.動力系統(tǒng)導論[M].北京：機械工業(yè)出版社，2007.

[9] 熊昌鎮(zhèn)，鄒建成.K進制面包師變換及其在數(shù)字圖像加密中的應用[J].北方工業(yè)大學學報，2004，16（1）:6-11.

[10] Fidrich J.Symmetric ciphersbasedon two- dimensional chaotic maps[J].International Journal of Bifurcation and Chaos，1998，8（6）：1 259-1 284.

[11] 盧振泰，黎羅羅.一種新的衡量圖像置亂程度的方法[J].中山大學學報（自然科學版）,2005（44）:126-129.

[12] 葉瑞松，郗坤洪.一種基于混沌序列控制的3D cat映射加密算法[J].汕頭大學學報（自然科學版），2007，22（2）:65-70.

Encryption Algorithm Based on the Itinerary of Baker Map

YE Rui-song，ZHUANG Le-yi
(Department of Mathematics，Shantou University，Shantou 515063，Guangdong，China)

A novel digital image encoding approach based on the itinerary of Baker map in spatial domain is proposed.It uses the finite character strings generated by the itinerary of Baker map to encode the pixels’positions so as to scramble the image.The periods and scrambling degrees of the algorithm are calculated as well.Furthermore，the chaotic characteristics of the Logistic map are applied to encrypt the scrambled image.

Baker map；itinerary；scrambling；encryption

TP 391.41

A

1001-4217（2010）01-0054-07

2009-06-09

葉瑞松（1968-），男，福建漳州人，教授.研究方向：分歧理論及其數(shù)值計算，分形混沌及其計算機應用.E-mail：rsye@stu.edu.cn