第12期 文昌辞等：基于三维仿射变换的数字图像置乱算法 ·1479· 均可能变换了位置，而猫映射变换和二维非等长置 乱变换没有改变(0,0)处像素的位置，这可能成为 包含置乱操作在内的整个算法的安全漏洞.基于排 序的置乱算法时间复杂度较高，而且为了存储对应 (4) 的像素位置，可能还需要额外的存储空间，所以空间 式中：ae和l为非零整数且gcd(a,M)=gcd(e,N)= 复杂度也较高 gcd(l,L)=1,c、g、h、r、s和t为任意实数，n、b,d为 任意正整数；gcd()为求最大公因子；g=M/gcd(M, 1置乱变换 N),p=N/gcd(M,N). 基于有限整数域上的二维非等长置乱变换)、 1.2一一映射证明 仿射变换和整数提升变换山，提出一种新的置乱变 引理团二维非等长置乱一一映射定理.对于 换，记为三维类仿射变换 二维非等长置乱变换，如果对于所有不同为0的整 定义1二维非等长仿射变换.设x∈O,M- 数1和2，若以下两式不同时成立，则二维非等长置 1],y∈O,N-1],若(x,y)映射为(x,y)满足 乱变换为一一映射 IldM-1,bNI/lad -bcl <M, -0+月 ,其中a、b、c、d、e和 (ad-be)I (I dM -L2bN) (5) Il CM -baNI/lad bel <N, a b ∫为非负整数且d≠0，则称为二维非等长仿射 (ad-bc）I(L,dM-lbN). (6) 变换.特别地当e和f为0时，称为二维非等长置乱 定理1三维类仿射变换的一一映射定理.如 变换 果把式(1)~(4)用于图像的置乱变换，其中(x,y, )和(x,y',z)分别代表置乱前、置乱后的像素坐标 定义2三维类仿射变换.设x、y和z为整数 且xeD,M-1],y∈0，N-1],z∈0，L-1],定 和像素值，那么该置乱变换是一一映射 证明： 义(x,y,z)映射为(x,y',z)的如下运算 (1)对于式(1)，任取两个不同位置的像素(x1, 000- y1)和(x2y2),只有两种情况：①x1≠x2②x1=2 但是y1≠y2 ①当x1≠x2时，因为gcd(a,M)=1,所以 ax +by +cz+0. Lr+0.5」 (ax1+Lr+0.5 modM≠(Lr+0.5」+ax2)modM, Ldx +ey+f+0.5 t+0.5 因此(x,y）≠(x,y),即像素的坐标位置是一一 Lgx+hy+z+0.5」 映射 为三维类仿射变换，其中a、b、cd、efg、h、l、r、s和 ②当x1=x2但y1≠y2时，=(ey,modV+Lcx2+ t为实数，M、N和L为正整数，L」表示取整. 0.5+Ls+0.5 J)mod N,y2=(ey2mod N +Lcx2 1.1置乱参数设置 0.5」+Ls+0.5)modN.因为gcd(e,N)=1,所以 要将三维类仿射变换用于图像的置乱加密，必 y≠y,即像素坐标位置是一一映射. 须使其为一一映射.对参数进行适当设置，可分别 ③在(x,y)→(x',y）计算可逆的情况下，因为 得到以下四个式子： gcd(l,L）=1,所以z=(z'-Lt+0.5」-Lgx+hy+ 0.5」)×l-modL,-1为l在剩余类域Z,中的模L 乘法逆元，即像素值的计算也可逆 综合①、②和③，可得出式(1)是一一映射.同 00分 理可证，式(2)也是一一映射. (2)对于式(3)，改变坐标位置的变换矩阵为以 下二维非等长置乱变换： : 对应于此时的二维非等长置乱变换，上文中的 式(5)和式(6)可变换为第 12 期 文昌辞等: 基于三维仿射变换的数字图像置乱算法 均可能变换了位置，而猫映射变换和二维非等长置 乱变换没有改变( 0，0) 处像素的位置，这可能成为 包含置乱操作在内的整个算法的安全漏洞． 基于排 序的置乱算法时间复杂度较高，而且为了存储对应 的像素位置，可能还需要额外的存储空间，所以空间 复杂度也较高． 1 置乱变换 基于有限整数域上的二维非等长置乱变换［7］、 仿射变换和整数提升变换［11］，提出一种新的置乱变 换，记为三维类仿射变换． 定义 1 二维非等长仿射变换． 设 x∈［0，M － 1］，y∈［0，N － 1］，若( x，y) 映 射 为( x'，y') 满 足 x' ( ) y' = a b ( ) c d ( ) x y + e ( )f mod M ( ) N ，其中 a、b、c、d、e 和 f 为非负整数且 a b c d ≠0，则称为二维非等长仿射 变换． 特别地当 e 和 f 为 0 时，称为二维非等长置乱 变换． 定义 2 三维类仿射变换． 设 x、y 和 z 为整数 且 x∈［0，M － 1］，y∈［0，N － 1］，z∈ ［0，L － 1］，定 义( x，y，z) 映射为( x'，y'，z') 的如下运算 x' y'        z' = a b c d e f        g h l x y        z + r s        t mod M N        L  = ?ax + by + cz + 0. 5」 ?dx + ey + fz + 0. 5」 ?gx + hy + lz + 0. 5        」 + ?r + 0. 5」 ?s + 0. 5」 ?t + 0. 5        」 mod M N        L  为三维类仿射变换，其中 a、b、c、d、e、f、g、h、l、r、s 和 t 为实数，M、N 和 L 为正整数，?」表示取整． 1. 1 置乱参数设置 要将三维类仿射变换用于图像的置乱加密，必 须使其为一一映射． 对参数进行适当设置，可分别 得到以下四个式子: x' y'        z' = a 0 0 c e 0        g h l x y        z + r s        t mod M N        L  ， ( 1) x' y'        z' = a c 0 0 e 0        g h l x y        z + r s        t mod M N        L  ， ( 2) x' y'        z' = 1 + dnq nq 0 d 1 0        g h l x y        z + r s        t mod M N        L  ， ( 3) x' y'        z' = 1 b 0 np 1 + bnp 0        g h l x y        z + r s        t mod M N        L  ． ( 4) 式中: a、e 和 l 为非零整数且 gcd( a，M) = gcd( e，N) = gcd( l，L) = 1，c、g、h、r、s 和 t 为任意实数，n、b，d 为 任意正整数; gcd( ) 为求最大公因子; q = M/gcd( M， N) ，p = N/gcd( M，N) ． 1. 2 一一映射证明 引理［7］ 二维非等长置乱一一映射定理． 对于 二维非等长置乱变换，如果对于所有不同为 0 的整 数 l1 和 l2，若以下两式不同时成立，则二维非等长置 乱变换为一一映射． | l1 dM － l2 bN| / | ad － bc| ＜ M， ( ad － bc) | ( l1 dM － l2 bN) ; ( 5) | l1 cM － l2 aN| / | ad － bc| ＜ N， ( ad － bc) | ( l1 dM － l2 bN) ． ( 6) 定理 1 三维类仿射变换的一一映射定理． 如 果把式( 1) ～ ( 4) 用于图像的置乱变换，其中( x，y， z) 和( x'，y'，z') 分别代表置乱前、置乱后的像素坐标 和像素值，那么该置乱变换是一一映射． 证明: ( 1) 对于式( 1) ，任取两个不同位置的像素( x1， y1，z1 ) 和( x2，y2，z2 ) ，只有两种情况: ①x1≠x2 ; ②x1 = x2 但是 y1≠y2 ． ①当 x1 ≠ x2 时，因 为 gcd ( a，M) = 1，所 以 ( ax1 + ?r + 0. 5」) modM≠( ?r + 0. 5」+ ax2 ) mod M， 因此( x' 1，y' 1 ) ≠( x' 2，y' 2 ) ，即像素的坐标位置是一一 映射． ②当 x1 = x2 但 y1≠y2 时，y' 1 = ( ey1mod N + ?cx2 + 0. 5」+ ? s + 0. 5」) mod N，y' 2 = ( ey2mod N + ? cx2 + 0. 5」+ ?s + 0. 5」) mod N． 因为 gcd ( e，N) = 1，所以 y' 1≠y' 2，即像素坐标位置是一一映射． ③在( x，y) →( x'，y') 计算可逆的情况下，因为 gcd( l，L) = 1，所以 z = ( z' － ? t + 0. 5」－ ? gx + hy + 0. 5」) × l － 1 mod L，l － 1 为 l 在剩余类域 ZL 中的模 L 乘法逆元，即像素值的计算也可逆． 综合①、②和③，可得出式( 1) 是一一映射． 同 理可证，式( 2) 也是一一映射． ( 2) 对于式( 3) ，改变坐标位置的变换矩阵为以 下二维非等长置乱变换: x' ( ) y' = 1 + dnq nq d ( ) 1 ( ) x y + ( )r s mod M ( ) N ． 对应于此时的二维非等长置乱变换，上文中的 式( 5) 和式( 6) 可变换为 ·1479·