三維Arnold映射的周期及在圖像加密中的應(yīng)用

李用江，張睿哲，葛建華，孫志林

?

三維Arnold映射的周期及在圖像加密中的應(yīng)用

李用江1，張睿哲2，葛建華3，孫志林4

(1. 廣東海洋大學(xué)信息學(xué)院 廣東湛江 524088; 2. 平頂山學(xué)院計算機(jī)科學(xué)與技術(shù)學(xué)院 河南平頂山 467002; 3. 西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)國家重點(diǎn)實驗室 西安 710071; 4. 河南宇通信息技術(shù)有限公司 鄭州 450003)

具有混沌特性的Arnold映射在圖像置亂、保密通信等方面都取得了很好的效果，但Arnold變換矩陣具有周期性，因此確定變換矩陣的周期是置亂變換的重要基礎(chǔ)。為了研究三維Arnold變換矩陣的周期性，引入了孿生Fibonacci數(shù)列對概念，并闡述了4條相關(guān)性質(zhì)定理。證明了三維Arnold變換矩陣的模周期是孿生Fibonacci數(shù)列對的模周期的一半，從而找到了確定變換矩陣模周期的新方法。最后提出了一種新的基于三維Arnold映射的多輪雙置亂加密算法，對比二維Arnold映射置亂加密算法，仿真結(jié)果表明該算法優(yōu)勢比較明顯，具有一定的先進(jìn)性。

Arnold變換; 圖像置亂; 信息隱藏; 多輪置亂; 孿生Fibonacci數(shù)列對

信息置亂變換既可作為信息加密的一種方法，又可作為進(jìn)一步隱藏的預(yù)處理過程，越來越多地受到眾多學(xué)者的關(guān)注。具有混沌特性的Arnold變換[1-3]用于圖像置亂能取得很好的效果[4]，因而受到學(xué)術(shù)界的重視，而Arnold變換與Fibonacci數(shù)列有關(guān)[2]。顯然確定變換矩陣的周期是其用于圖像置亂變換的重要基礎(chǔ)[5]，近十年來世界范圍內(nèi)的學(xué)者從不同的數(shù)學(xué)角度尋找計算周期的算法[3, 5-11]，但鮮有這方面的理論分析結(jié)果。文獻(xiàn)[2]研究了矩陣變換(模運(yùn)算)具有周期的充要條件；文獻(xiàn)[11]發(fā)現(xiàn)了二維Arnold變換的周期性與Fibonacci模數(shù)列周期性的內(nèi)在聯(lián)系，開辟了通過求模數(shù)列的周期來確定矩陣變換周期的新方法。基于該思路，本文研究三維Arnold變換的模周期性與孿生Fibonacci數(shù)列對[12-13]的模周期的關(guān)系。

1 基礎(chǔ)知識

下面介紹有關(guān)孿生Fibonacci數(shù)列對及其性質(zhì)定理[12-13]，以及相關(guān)的矩陣知識。

引理4[2]對給定的階數(shù)字圖像，有變換，其中是變換的矩陣，向量的每一分量的值。矩陣變換對所有向量都具有周期的充分必要條件是與互素。

定義 3[14]實數(shù)上的維矩陣構(gòu)成的集合記為，上的可逆元的全體記為，當(dāng)=Z時簡記為。

2 三維Arnold映射的模周期與孿生Fibonacci數(shù)列對的模周期的關(guān)系

2.1 FF_矩陣的周期性定理

記變換矩陣FF_為：

根據(jù)引理1及性質(zhì)有下式成立：

(6)

由引理2、引理3和定理1可以得到如下定理：

所以只要確定了模為素數(shù)冪的矩陣的階，即可求出模為合數(shù)的階。

2.2 三維Arnold變換的周期性與FF_矩陣的周期性的關(guān)系

定義4[2]對于給定的自然數(shù)，下列變換稱為三維Arnold變換：

引理5 如果變換

(10)

由引理5和引理6立即得到：

從上述定理得出：三維Arnold映射的模周期是孿生Fibonacci數(shù)列的模周期的一半。例如，，由引理2得，由定理1得到，由定理5得到三維Arnold變換的周期為112，這個結(jié)論與文獻(xiàn)[2]的結(jié)果是一致的。

3 三維Arnold映射在圖像加密中的應(yīng)用及周期驗證

3.1 一個簡單圖像位置置亂加密算法及周期驗證

通過分析，可知三維Arnold變換模64的周期為112，但用直觀的圖示方法驗證其正確性卻較困難，因此，設(shè)計了一種新的圖像置亂加密算法，用該算法檢驗三維Arnold映射的周期的正確性。

1) 圖像位置置亂加密算法

②使用三維Arnold變換對圖像像素的位置進(jìn)行多次映射變換；由于三維Arnold變換在進(jìn)行圖像置亂中對于(0, 0, 0)位置上的像素不起任何作用，因此，可把(0, 0, 0)位置上的像素和一個固定位置的像素在每輪迭代過程后進(jìn)行交換。這樣，前一輪(0, 0, 0)位置的像素就可以在下一輪迭代中被置亂。其中也可以被看作密鑰進(jìn)行控制；

2) 仿真實驗

下面給出一個基于Arnold映射的圖像仿真變換實例。如圖1a所示，圖像像素為512′512，變換成64′64′64的三維立體圖。使用三維Arnold映射變換對原始圖像作多次變換得到的圖像變換狀態(tài)(image transform state，ITS)，可以看出原始圖像經(jīng)過112次變換后恢復(fù)到原來狀態(tài)，從而驗證了上述相關(guān)定理的正確性。僅就位置置亂而言，效果比二維Arnold映射置亂效果好。本仿真實驗在Matlab 2010軟件環(huán)境下進(jìn)行。

a.原圖512′512???b.變換1次圖???c. 變換10次圖

d. 變換100次圖???e. 變換111次圖???f. 變換112次圖

圖1 原圖像進(jìn)行次Arnold變換的效果圖

3.2 基于圖像位置置亂的加密算法

3.2.1 圖像位置置亂加密算法

1) 圖像置亂加密算法

2) 仿真實驗

如圖2a所示，原始圖像像素為440′440。根據(jù)算法可以求出，，三維Arnold的周期為14。使用三維Arnold映射變換對原始圖像作多次變換得到的圖像變換狀態(tài)如圖2所示，效果比二維Arnold映射置亂效果好。

a. 原圖440×440???b. 變換1次圖

c. 變換7次圖???d. 變換14次圖

圖2 原圖像進(jìn)行次Arnold變換的效果圖

3.2.2 圖像位置置亂解密算法

基于圖像位置置亂的解密算法如下：

2) 將二維圖像變換為一維數(shù)組，去冗余信息，將一維數(shù)組變換成的三維立體圖像；

3) 使用三維Arnold變換對圖像像素進(jìn)行次逆變換；

4) 將三維立體圖像變?yōu)橐痪S數(shù)組，去冗余信息，將一維數(shù)組變換成二維圖像。

3.2.3 圖像位置置亂算法的冗余度

在算法中增加了冗余信息，冗余度的大小也是衡量這個算法好壞的一個標(biāo)準(zhǔn)。如當(dāng)原始圖像像素分別440′440，300′300，512′512時，它們的冗余度分別為0.91%，1.34%，0。圖3給出了圖像像素在200～2 000之間的冗余度的值，從圖上可以看出信息冗余度一般不超過9%，這說明該算法是可用的。

圖3 圖像像素在200～2 000之間的冗余度的值

3.3 基于三維Arnold映射的多輪雙置亂加密算法

與文獻(xiàn)[16]相似，為了防止僅作空間置亂有輪廓顯現(xiàn)，再引入色彩空間的置亂，然后進(jìn)行多輪置亂變換。具體步驟是：1) 首先使用三維Arnold變換對圖像像素坐標(biāo)進(jìn)行置亂；2) 再使用文獻(xiàn)[16]構(gòu)造的維廣義Arnold變換對圖像像素灰度值進(jìn)行APS變換；3) 為了加強(qiáng)安全，重復(fù)步驟1)和步驟2)進(jìn)行多輪乘積型置亂變換，達(dá)到高維矩陣置亂的效果。

a.第1輪置亂變換效果圖????b. 第1輪置亂變換直方圖

c. 第18輪置亂變換效果圖????d. 第18輪置亂變換直方圖

e. 解密效果圖 ????f. 解密直方圖

4 結(jié) 論

通過研究孿生Fibonacci數(shù)列對的模數(shù)列的性質(zhì)和定理，研究了FF_變換的模周期性，從而獲得了三維Arnold變換矩陣的周期性規(guī)律，為其在圖像置亂編碼的應(yīng)用提供必要的數(shù)學(xué)理論基礎(chǔ)。這種研究方法也對變換矩陣的階的理論分析開辟了新的途徑，也為探討任意維Arnold變換矩陣的周期性問題提供了新的方法。下一步的相關(guān)工作有4個方面。

1) 秘密圖像置亂的效果越好，將其隱藏在公開圖像中其安全性越高，針對具有混沌特性的三維Arnold變換用于圖像置亂，其置亂程度的進(jìn)一步研究可以參考文獻(xiàn)[2, 17]。

2) 關(guān)于三維Arnold映射的周期性與文獻(xiàn)[12-13]中孿生Fibonacci數(shù)列對的周期性相同。

3) 使用三維Arnold變換對圖像像素坐標(biāo)進(jìn)行置亂，因其周期性，在安全性(保密性)方面達(dá)不到要求，通常情況下一定要和別的加密算法配合使用，如本文中的多輪雙置亂加密算法。本文圖像加密算法的性能分析，將另文論述。

4) 將繼續(xù)研究基于三維Arnold映射的多輪雙置亂彩色圖像加密算法。

[1] ARNOLD V I, AVEZ A. Ergodic problems of classical mechanics[M]// Mathematical Physics Monograph Series NewYork: W A Benjamin, INC, 1968.

[2] QI D X, ZOU J CH, HAN X Y. A new class of scrambling transformation and its application in the image information covering[J]. Science in China(Series E), 2000, 43(3): 304-412.

[3] DYSON F J. FALK H. Period of a discrete cat map-ping[J]. The American Mathematical Monthly, 1992, 99(7): 603-614.

[4] YANG Ya-li, CAI Na, NI Guo-qiang. Digital image scrambling technology based on the symmetry of Arnold transform[J]. Journal of Beijing Institute of Technology, 2006, 15(2): 216-220.

[5] 楊禮珍, 陳克非. 變換矩陣(mod)的階及兩種推廣Arnold變換矩陣[J]. 中國科學(xué), E輯, 2004, 34(2): 151-161.

YANG Li-zhen, CHEN Ke-fei. Rank of transformation matrix(mod I) and two generalized Arnold transformation matrices[J]. Science in China(Series E), 2004, 34(2): 151- 161.

[6] QI D X, WANG D SH, YANG D L. Matrix transformation of digital image and its periodicity[J]. Progress in Natural Science, 2001, 11(7): 542-549.

[7] 鄒建成, 鐵小勻. 數(shù)字圖像的二維Arnold變換及其周期性[J]. 北方工業(yè)大學(xué)學(xué)報, 2000, 12(1): 1014-1032.

ZOU Jian-cheng, TIE Xiao-yun. Arnold transformation of digital image with two dimensions and its periodicity[J]. Journal of North China University of Technology, 2000, 12(1): 1014-1032.

[8] 李兵, 徐家偉. Arnold變換的周期及其應(yīng)用[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2004, 43(S2): 139-142.

LI Bing, XU Jia-wei. On the periods of Arnold transformations and some applications[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni(Natural Science), 2004, 43(S2): 139-142.

[9] 黎羅羅. Arnold型置亂變換周期分析[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2005, 44(2): 1-4.

LI Luo-luo. On periods of Arnold _type transformations[J]. Acta Scientiarum Naturalium Universitatis Sunyatseni (Natural Science), 2005, 44(2): 1-4.

[10] 李用江, 李昌利, 葛建華, 等.維Arnold變換矩陣模r的周期性研究[J]. 數(shù)學(xué)的實踐與認(rèn)識, 2010, 40(16): 53-59.

LI Yong-jiang, LI Chang-li, GE Jian-hua, et al. Study on the periodicity of-Arnold-type transformation matrix Modr[J]. Mathematics in Practice and Theory, 2010, 40(16): 53-59.

[11] 李用江, 張辰光, 李昌利, 等. 貓映射的周期性與Fibonacci模數(shù)列的周期性的內(nèi)在聯(lián)系[J]. 計算機(jī)應(yīng)用, 2010, 30(4): 38-43.

LI Yong-jiang, ZHANG Chen-guang, LI Chang-li, et al. Inherent relationship between the periodicity of cat map and that of series generated from Fibonacci series[J]. Journal of Computer Applications, 2010, 30(4): 38-43.

[12] LI Yong-jiang, GE Jian-hua, SUN Zhi-lin, et al. Periods of a new sequence modulo[J]. Communications in Computer and Information Science, 2011(158): 187-193.

[13] LI Yong-jiang, GE Jian-hua, SUN Zhi-lin. Periods of twin Fibonacci sequence modulor[J]. Advanced Science Letters, 2012, 7(3): 340-344.

[14] GARRETT P. 密碼學(xué)導(dǎo)論[M]. 吳世忠, 宋曉龍, 郭濤,譯. 北京: 機(jī)械工業(yè)出版社. 2003.

GARRETT P. An Introduction to cryptology[M]. Translated by WU Shi-zhong SONG Xiao-long, GUO Tao. Beijing: China Machine Press, 2003.

[15] YANG Ya-li, CAI Na, NI Guo-qiang. Digital image scrambling technology based on the symmetry of Arnold transform[J]. Journal of Beijing Institute of Technology, 2006, 15(2): 216-220.

[16] 李用江, 葛建華, 李昌利, 等. 一種新的維廣義Arnold矩陣構(gòu)造方法及其在圖像置亂中的應(yīng)用[J]. 北京科技大學(xué)學(xué)報, 2010, 32(12): 1631-1637.

LI Yong-jiang, GE Jian-hua, LI Chang-li, et al. A new construction method for-Dimensional generalized Arnold matrix and its application in image scrambling[J]. Journal of University of Science and Technology Beijing, 2010, 32(12): 1631-1637.

[17] 吳旻升, 王介生, 劉慎權(quán). 圖像的排列變換[J]. 計算機(jī)學(xué)報, 1998, 21(6): 514-519.

WU Min-sheng, WANG Jie-sheng, LIU Shen-quan. Permutation transform of images[J]. Journal of Computers, 1998, 21(6): 514-519.

編 輯 張 俊

Periods of the 3-Arnold Transformation and Its Application in Image Encryption

LI Yong-jiang1, ZHANG Rui-zhe2, GE Jian-hua3, and SUN Zhi-lin4

(1. College of Information, Guangdong Ocean University Zhanjiang Guangdong 524088; 2. College of Computer Science and Technology, Pingdingshan University Pingdingshan Henan 467002; 3. State Key Laboratory of Integrated Service Networks, Xidian University Xi’an 710071; 4. Henan Yu-tong Information Technology Co., Ltd. Zhengzhou 450003)

The Arnold mapping with chaotic has achieved good results in the image scrambling and secure communication, however, the Arnold transformation matrix is periodic so that finding the cycle of the transformation matrix is the important basis of scrambling transformation. In order to study the periodicity of the 3-Arnold transform matrix, the new concept of the twin Fibonacci sequence is introduced and four related periodicity theorems are given. And then we prove that the molding cycle of 3-Arnold transform matrix is half of the molding cycle of the twin Fibonacci sequence. Accordingly, a new method to determine the molding cycle of the transformation matrix is formed. At last, a new several-rounds double-scrambling encryption algorithm based on the 3-Arnold mapping is proposed. Simulation results show the proposed algorithm outperforms the 2-Arnold mapping algorithm.

Arnold transformation; image scrambling; information hiding; several rounds of scrambling; twin Fibonacci sequence

TP393; O156

A

10.3969/j.issn.1001-0548.2015.02.022

2011-01-11;

2014-12-08

國家自然科學(xué)基金(41340049)；國家863項目(B50306290182)；國家發(fā)展改革委衛(wèi)星應(yīng)用高技術(shù)產(chǎn)業(yè)化專項([2009]214)；河南省科技計劃重點(diǎn)項目(102102210420)

李用江(1967-)，男，副教授，博士，主要從事信息安全方面的研究.