三维Arnold映射的周期及在图像加密中的应用

李用江，张睿哲，葛建华，孙志林

三维Arnold映射的周期及在图像加密中的应用

李用江1，张睿哲2，葛建华3，孙志林4

(1. 广东海洋大学信息学院 广东湛江 524088; 2. 平顶山学院计算机科学与技术学院 河南平顶山 467002; 3. 西安电子科技大学综合业务网国家重点实验室 西安 710071; 4. 河南宇通信息技术有限公司 郑州 450003)

具有混沌特性的Arnold映射在图像置乱、保密通信等方面都取得了很好的效果，但Arnold变换矩阵具有周期性，因此确定变换矩阵的周期是置乱变换的重要基础。为了研究三维Arnold变换矩阵的周期性，引入了孪生Fibonacci数列对概念，并阐述了4条相关性质定理。证明了三维Arnold变换矩阵的模周期是孪生Fibonacci数列对的模周期的一半，从而找到了确定变换矩阵模周期的新方法。最后提出了一种新的基于三维Arnold映射的多轮双置乱加密算法，对比二维Arnold映射置乱加密算法，仿真结果表明该算法优势比较明显，具有一定的先进性。

Arnold变换; 图像置乱; 信息隐藏; 多轮置乱; 孪生Fibonacci数列对

信息置乱变换既可作为信息加密的一种方法，又可作为进一步隐藏的预处理过程，越来越多地受到众多学者的关注。具有混沌特性的Arnold变换[1-3]用于图像置乱能取得很好的效果[4]，因而受到学术界的重视，而Arnold变换与Fibonacci数列有关[2]。显然确定变换矩阵的周期是其用于图像置乱变换的重要基础[5]，近十年来世界范围内的学者从不同的数学角度寻找计算周期的算法[3, 5-11]，但鲜有这方面的理论分析结果。文献[2]研究了矩阵变换(模运算)具有周期的充要条件；文献[11]发现了二维Arnold变换的周期性与Fibonacci模数列周期性的内在联系，开辟了通过求模数列的周期来确定矩阵变换周期的新方法。基于该思路，本文研究三维Arnold变换的模周期性与孪生Fibonacci数列对[12-13]的模周期的关系。

1 基础知识

下面介绍有关孪生Fibonacci数列对及其性质定理[12-13]，以及相关的矩阵知识。

引理4[2]对给定的阶数字图像，有变换，其中是变换的矩阵，向量的每一分量的值。矩阵变换对所有向量都具有周期的充分必要条件是与互素。

定义 3[14]实数上的维矩阵构成的集合记为，上的可逆元的全体记为，当=Z时简记为。

2 三维Arnold映射的模周期与孪生Fibonacci数列对的模周期的关系

2.1 FF_矩阵的周期性定理

记变换矩阵FF_为：

根据引理1及性质有下式成立：

(6)

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

所以只要确定了模为素数幂的矩阵的阶，即可求出模为合数的阶。

2.2 三维Arnold变换的周期性与FF_矩阵的周期性的关系

定义4[2]对于给定的自然数，下列变换称为三维Arnold变换：

引理5 如果变换

(10)

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

从上述定理得出：三维Arnold映射的模周期是孪生Fibonacci数列的模周期的一半。例如，，由引理2得，由定理1得到，由定理5得到三维Arnold变换的周期为112，这个结论与文献[2]的结果是一致的。

3 三维Arnold映射在图像加密中的应用及周期验证

3.1 一个简单图像位置置乱加密算法及周期验证

通过分析，可知三维Arnold变换模64的周期为112，但用直观的图示方法验证其正确性却较困难，因此，设计了一种新的图像置乱加密算法，用该算法检验三维Arnold映射的周期的正确性。

1) 图像位置置乱加密算法

②使用三维Arnold变换对图像像素的位置进行多次映射变换；由于三维Arnold变换在进行图像置乱中对于(0, 0, 0)位置上的像素不起任何作用，因此，可把(0, 0, 0)位置上的像素和一个固定位置的像素在每轮迭代过程后进行交换。这样，前一轮(0, 0, 0)位置的像素就可以在下一轮迭代中被置乱。其中也可以被看作密钥进行控制；

2) 仿真实验

下面给出一个基于Arnold映射的图像仿真变换实例。如图1a所示，图像像素为512´512，变换成64´64´64的三维立体图。使用三维Arnold映射变换对原始图像作多次变换得到的图像变换状态(image transform state，ITS)，可以看出原始图像经过112次变换后恢复到原来状态，从而验证了上述相关定理的正确性。仅就位置置乱而言，效果比二维Arnold映射置乱效果好。本仿真实验在Matlab 2010软件环境下进行。

a.原图512´512   b.变换1次图   c. 变换10次图

d. 变换100次图   e. 变换111次图   f. 变换112次图

图1 原图像进行次Arnold变换的效果图

3.2 基于图像位置置乱的加密算法

3.2.1 图像位置置乱加密算法

1) 图像置乱加密算法

2) 仿真实验

如图2a所示，原始图像像素为440´440。根据算法可以求出，，三维Arnold的周期为14。使用三维Arnold映射变换对原始图像作多次变换得到的图像变换状态如图2所示，效果比二维Arnold映射置乱效果好。

a. 原图440×440   b. 变换1次图

c. 变换7次图   d. 变换14次图

图2 原图像进行次Arnold变换的效果图

3.2.2 图像位置置乱解密算法

基于图像位置置乱的解密算法如下：

2) 将二维图像变换为一维数组，去冗余信息，将一维数组变换成的三维立体图像；

3) 使用三维Arnold变换对图像像素进行次逆变换；

4) 将三维立体图像变为一维数组，去冗余信息，将一维数组变换成二维图像。

3.2.3 图像位置置乱算法的冗余度

在算法中增加了冗余信息，冗余度的大小也是衡量这个算法好坏的一个标准。如当原始图像像素分别440´440，300´300，512´512时，它们的冗余度分别为0.91%，1.34%，0。图3给出了图像像素在200～2 000之间的冗余度的值，从图上可以看出信息冗余度一般不超过9%，这说明该算法是可用的。

图3 图像像素在200～2 000之间的冗余度的值

3.3 基于三维Arnold映射的多轮双置乱加密算法

与文献[16]相似，为了防止仅作空间置乱有轮廓显现，再引入色彩空间的置乱，然后进行多轮置乱变换。具体步骤是：1) 首先使用三维Arnold变换对图像像素坐标进行置乱；2) 再使用文献[16]构造的维广义Arnold变换对图像像素灰度值进行APS变换；3) 为了加强安全，重复步骤1)和步骤2)进行多轮乘积型置乱变换，达到高维矩阵置乱的效果。

a.第1轮置乱变换效果图    b. 第1轮置乱变换直方图

c. 第18轮置乱变换效果图    d. 第18轮置乱变换直方图

e. 解密效果图     f. 解密直方图

4 结 论

通过研究孪生Fibonacci数列对的模数列的性质和定理，研究了FF_变换的模周期性，从而获得了三维Arnold变换矩阵的周期性规律，为其在图像置乱编码的应用提供必要的数学理论基础。这种研究方法也对变换矩阵的阶的理论分析开辟了新的途径，也为探讨任意维Arnold变换矩阵的周期性问题提供了新的方法。下一步的相关工作有4个方面。

1) 秘密图像置乱的效果越好，将其隐藏在公开图像中其安全性越高，针对具有混沌特性的三维Arnold变换用于图像置乱，其置乱程度的进一步研究可以参考文献[2, 17]。

2) 关于三维Arnold映射的周期性与文献[12-13]中孪生Fibonacci数列对的周期性相同。

3) 使用三维Arnold变换对图像像素坐标进行置乱，因其周期性，在安全性(保密性)方面达不到要求，通常情况下一定要和别的加密算法配合使用，如本文中的多轮双置乱加密算法。本文图像加密算法的性能分析，将另文论述。

4) 将继续研究基于三维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]. 中国科学, 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] 邹建成, 铁小匀. 数字图像的二维Arnold变换及其周期性[J]. 北方工业大学学报, 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变换的周期及其应用[J]. 中山大学学报(自然科学版), 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]. 中山大学学报(自然科学版), 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]. 数学的实践与认识, 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模数列的周期性的内在联系[J]. 计算机应用, 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. 密码学导论[M]. 吴世忠, 宋晓龙, 郭涛,译. 北京: 机械工业出版社. 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矩阵构造方法及其在图像置乱中的应用[J]. 北京科技大学学报, 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] 吴旻升, 王介生, 刘慎权. 图像的排列变换[J]. 计算机学报, 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

国家自然科学基金(41340049)；国家863项目(B50306290182)；国家发展改革委卫星应用高技术产业化专项([2009]214)；河南省科技计划重点项目(102102210420)

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