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

葉瑞松，莊樂(lè)儀

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

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

葉瑞松，莊樂(lè)儀

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

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

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

0 引言

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

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

1 相關(guān)知識(shí)

1.1 迭路

符號(hào)動(dòng)力學(xué)指出，如果動(dòng)力系統(tǒng)的某軌道一定通過(guò)一列不同的區(qū)間，將每個(gè)區(qū)間用一個(gè)符號(hào)對(duì)應(yīng)表示，那么就得到這條軌道的迭路[8].

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

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

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

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

1.2 Baker映射

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

1.2.1 二進(jìn)制Baker映射

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

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

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

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

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

2 編碼過(guò)程

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

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

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

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

步驟3重復(fù)步驟2，直到k=M-1.得到有限符號(hào)串s0s1s2…sM-1.令k=0.

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

步驟5重復(fù)步驟4，直到k=M.得到有限符號(hào)串s-M…s-2s-1.

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

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

3 仿真實(shí)驗(yàn)

3.1 二進(jìn)制編碼置亂

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

圖1 二進(jìn)制Baker映射迭路編碼的置亂結(jié)果

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

表1 置亂算法周期

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

3.2 三進(jìn)制編碼置亂

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

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

圖3 三進(jìn)制Baker映射迭路編碼的置亂結(jié)果

3.3 灰度值擴(kuò)散

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

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

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

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

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

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

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

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

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

圖4 LENA圖三次加密、解密圖像及對(duì)應(yīng)直方圖

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

圖5 NPCR和UACI變化圖

4 結(jié)語(yǔ)

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

[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ù)字圖像置亂技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2001，13（4）：338-344.

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

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

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

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

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

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

[9] 熊昌鎮(zhèn)，鄒建成.K進(jìn)制面包師變換及其在數(shù)字圖像加密中的應(yīng)用[J].北方工業(yè)大學(xué)學(xué)報(bào)，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].中山大學(xué)學(xué)報(bào)（自然科學(xué)版）,2005（44）:126-129.

[12] 葉瑞松，郗坤洪.一種基于混沌序列控制的3D cat映射加密算法[J].汕頭大學(xué)學(xué)報(bào)（自然科學(xué)版），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ù)值計(jì)算，分形混沌及其計(jì)算機(jī)應(yīng)用.E-mail：rsye@stu.edu.cn