arnold变换的周期性与安全性分析.pdf

算机安全 2008.5学术.技术1 引言对图像进行加密是保证图像安全问题的有效手段，但图像数据量大，很多常用的高强度的加密方法并不适合图像的加密置乱技术是一种针对图像进行加密的技术，是信息隐藏与数字水印中常用的预处理技术，它可以有效提高隐藏信息的安全性和鲁棒性置乱技术除了对图像进行加密之外，对于 DCT 域的嵌入算法也经常用置乱技术对载体图像做置乱处理，其目的在于将图像白噪声化，这使得图像的能量能够均匀分布如果把图像视为信道，那么置乱将增大这个信道的带宽，这对于数据的嵌入来说就意味着为嵌入提供了更多的空间目前人们使用较多的置乱技术主要有：Arnold 变换[1,2]、幻方、Hilbert 曲线、Conway 游戏、Tangram 算法、IFS 模型、Gray 码变换、广义 Gray 码变换等[3]，其中使用最广的为 Arnold 变换作为一种加密技术，其安全性是至关重要的本文分析了 Arnold 变换及其推广的周期性，探讨了其周期性所带来的安全隐患，提出了一种克服其周期性的实现方法，可提高 Arnold 变换的安全性，可供图像加密者参考2 Arnold 变换及其推广Arnold 变换是 V.J.Arnold 在研究环面上的自同态时提出的，俗称猫脸变换，其原意为 cat mapping，Arnold 猫映射可以表示为：(1)其中 ,mod 1 表示取小数部分。

猫映射为混沌映射，它具有非常典型的产生混沌运动的几个特性：拉伸（乘以矩阵 C 使 x, y 都变大）和折叠( 取模使 x 和 y 又折回单位矩阵内 )，除此之外它还有可逆性和周期性，由于猫映射的混沌运动的特性，使它比较适合于二维数字图像的置乱处理考虑到数字图像的需要 ,基于位置的图像置乱的 Arnold 变换可改写为：(2) 其中 ,x,y ∈ (0,1,2,⋯, N-1), 表示某一像素点的坐标 , 而 N 是图像矩阵的阶数用 (2) 式进行置乱时，随着迭代次数的增加，图像逐渐趋于混乱，置乱次数不同时其置乱效果也不一样，但只有置乱次数一个密钥参数，安全性较低，为提高安全性，对 (2) 式进一步推广[4]为最一般的二维可逆保面积方程：(3)其 中，， 且 特 征 值Arnold 变换的周期性与安全性分析基金项目 : 湖南省软科学课题（2007ZK3049）; 湖南省科技计划项目 (06FJ3171)谢建全 ,,1 , 21 , 22谢 勍黄大足( 1 . 中南大学信息科学与工程学院，湖南 长沙 4 1 0 0 8 3 ; 2 . 湖南财经高等专科学校，湖南 长沙 4 1 0 2 0 5 )2008.5 计算机安学术.技术，推广的 (3) 式仍然具有混沌映射的特性[5]。

因此矩阵 C 的取值可作为密钥使用，从而可增大密钥空间，进而提高抵抗穷举攻击的能力用矩阵 C 作为密钥时的密钥空间与 N 的大小有关，表 1 为 N 取不同值时 C 矩阵相应的密钥空间，可见用变换矩阵的取值作为密钥时其密钥空间远大于用变换次数作为密钥时的密钥空间表 1 用变换矩阵参数作密钥时的有效密钥空间3 Arnold 变换的周期性与安全性分析采用 (2) 式进行置乱处理时，随着迭代次数的增加，虽然图像逐渐趋于混乱，但经过一定的次数后，又将回到原图，这就是 Arnold 变换的周期性因此很多算法利用置乱变换的周期来恢复图像信息，同时攻击者也可利用其周期性来进行穷举攻击图像 Arnold 变换的周期性与 N 的取值有关，F. J. Dyson 和 H.Falk 给出了对于任意 N>2, Arnold 变换的周期 的结论[6]文献 [7] 更是得出它的周期等于以 N 的两两互素的因数为模的变换的周期之最小公倍数表 2 是 Arnold 变换在不同 N 下的周期表 2 图像大小与 Arnold 变换周期从表 1 中可以看出 Arnold 变换的周期并不长，攻击者只要继续进行为数不多的有限次置乱处理，就可恢复到置乱前的图像，即密钥空间比较小，因此 Arnold 变换的周期性使得其安全性较低。

对给定的 N 阶数字图像 P 变换：(4)其中为整数， 文献 [8] 证明了 (4) 式有周期性的充分必要条件是|C| 与 N 互素，此处 |C| 是矩阵 C 的行列式由此可知，采用 (3) 式或更高维的方法进行置乱处理时，也同样存在周期性，只是周期的长度有差异，其周期长度与变换矩阵有关，并且其周期长度与 Arnold 变换差不多，因此推广的 Arnold 变换也同样存在安全性低的问题并且同样可证明， 用两组 ( 或多组 ) 不同的参数， 用 (3) 式进行置乱时，置乱后的图像仍然可通过用周期性的方法恢复出原始图像4 消除周期性安全隐患的实现方法由于是 Arnold 变换及其推广均有周期性，显然单纯通过变换次数或变换矩阵的参数作为密钥来进行置乱时，由表 1 和表 2 可知，其周期均比较小，无法解决其周期性所带来的安全问题如果将图像分成多个子块，不同的子块采用不同的参数进行置乱的话，由于其周期的不同，整个图像的置乱就不再呈现原来的周期现象了如果将图像分为两次置乱，第一次先对整个图像置乱，在此基础上对图像进行分块得到若干个子块，再对不同子块用不同参数进行第二次置乱，最终置乱后的图像就无法用其周期性来恢复出原始图像，从而消除周期性带来的安全问题。

从表 1 和表 2 可知，置乱的周期既与图像大小有关，还与所选用的置乱矩阵的参数有关，因此可设计如下算法实现图像的安全置乱： 设需要置乱的图像为 ，置乱步骤如下：(1) 根据约束条件选取合适的参数，得到满足 (3) 式所要求的矩阵 C； (2) 用矩阵 C 和 (3) 式对图像 P 进行 k1次置乱，得到P'；(3) 将置乱后的图像 P' 分成大小相同的 m 个子块，设这些子块分别子块的数量及每个子块的大小通过密钥 k2 控制，但在分块时需注意保证每个子块为方块，设子块大小分别为；(4) 根据约束条件选取合适的参数，得 到满足 (3) 式所要求的矩阵 C'，并由 k3产生子密钥；(5)用矩阵C'和(3)式对图像子块分别进行次置乱，得到 ；(6) 将组合起来，得到最终置乱后的图像其中第 (1) 步的作用之一是防止某些图像不同区域相差太大时，分块置乱后可能出现的明显的块痕迹；作用之二是破解者即使猜中了分块参数和分块后的置乱参数，也最多得到图像 P' 的一部分，仍然是密文，无法得到任何明文（原始图像块） ，从而提高其安全性置乱后的图像的恢复比较简单，基本就是置乱处理的逆过程，在置乱的恢复中需要参数，,k2,k3, 其恢复算法如下：8算机安全 2008.5学术.技术(1) 根据置乱时的分块方法和参数 k2，将的分成 m个子块；(2) 用矩阵公式 19 的逆矩阵和 (3) 式对各子块分别进行次置乱得到；(3) 将进行组合，得到图像 P'；(4) 用矩阵 C 的逆矩阵 C-1 和 (3) 式对 P' 进行 k1 次置乱，即得到原始图像 P。

5 仿真实验用如图 1 所示的 256×256 lena 图像进行置乱试验，选取置乱参数分别为 71,65,83,76,1, 分别为 21,10,23,11， 第 (3) 步子块的划分采 用将图像简单划分成 4 个 128×128 的子块的方法，子密钥分别为 5,7,12,3，置乱后的图像如图 2 所示图 1 原始图像 P 图 2 置乱后图像 Q经计算用矩阵 C 和矩阵 C' 通过 (3) 式对图像进行置乱的周期分别为 192 和 16，为检测本算法的安全性，进行周期性恢复试验，分别选用矩阵 C 和矩阵 C'，用（3）式对置乱后的图像 Q 继续进行 16、192、3072（16×192） 、4000、10000、20000 次置乱，整个过程中均未出现某次置乱后的图像与原图相同的现象，可见本算法不再出现单一 Arnold 变换所发生的周期现象，可防止 Arnold 变换的周期性所带来的安全问题6 结论置乱技术是一种常用的图像加密技术，本文分析了广泛使用的 Arnold 变换及其推广的周期性，提出了克服其周期性所带来的安全问题，试验表明，用本算法置乱后的图像不再具有 Arnold 变换周期性现象，可有效防止通过变换周期性来进行的攻击。

如果要进一步提高其安全性，只要再做一次分块和分块置乱即可，如果要在色度空间置乱，也只要在上述方法中将二维置乱改为三维置乱参考文献:[1]Arnold V I,Avez A. Ergodic Problems of Classical Mechanics, Mathematical Physics Monograph Series. New York: Benjamin W A,INC.1968.[2] 张华熊 , 仇佩亮 . 置乱技术在数字水印中的应用 . 电路与系统学报 ,2001,6(3):32~36.[3] 孔涛，张 . Arnold 反变换的一种新算法 . 软件学报 , 2004, 15(10):1558~1564.[4] Feng Guorui,Jiang Lingge,He Chen,et al. A Novel Algorithm for Embedding and Detecting Digital Watermarks. Acoustics,Speech and Signal Processing 2003 Proceedings,ICASSP'03,2003,3: 549~552.[5] 马在光 , 邱水生 . 基于广义猫映射的一种图像加密系统[J]. 通信学报 , 2003,24(2):51~57.[6] 丁 伟 , 闫 伟 齐 , 齐 东 旭 . 基 于 Arnold 变 换 的 数 字 图像置乱技术 [J]. 计算机辅助设计与图形学学报 , 2001, 13(4):338~341.[7] 黎罗罗 . Arnold 型置乱变换周期分析 . 中山大学学报 ( 自然科学版 ),2005,44(2):1~4.[8] 齐东旭 , 邹建成 , 韩效宥 . 一类新的置乱变换及其在图像信息隐藏中的应用 . 中国科学 (E 辑 ),2000,30(5): 440 ~ 447).作者简介：谢建全（1964-） ，男，教授，博士生，研究方向为信息安全技术 ; 谢 （1966-） ，女，副教授，硕士，研究方向为数字水印；黄大足（1968-） ，男，副教授，博士生，研究方向为数字水印。

收稿日期：2007-10-234 月 26 日，国家计算机病毒应急处理中心、北京江民奥运网络安全应急保卫中心联合发布了“网页安全专家”软件，免费供所有互联网用户下载使用，为确保奥运期间网络安全增添了一件安全新利器网页安全专家”是江民反病毒中心在系统自动搜集的庞大恶意网页特征库的基础上研发而成，使用该软件，用户可以检测到自己的电脑是否感染了恶意网址，如检测发现恶意网页，用户可以按照提示自动上报给国家计算机病毒应急中心进行处理网页安全专家下载地址：http://www.antivirus-。