。676° 北京科技大学学报 第32卷 序列记录为{(k(内》。则{(}即为图 ,正{L2…,N,若)<tj,则X<芩若 像第1行的行置换地址码.依次检测的第了= 羊>rj,则>X 2,M)行中每个像素灰度值≠12：y在该 证明由假设条件可知，X在序列{，中的 行所处的列数，用同样的方法得到所有M行的行 位置编号为t,在序列{)正中的位置编号为 置换地址码{(k),{(k), j.由于{是按升序排列的，对于H共，j,i {(y·然后选取密文图像G使得像素灰度 任{12，N,当￥<时，第个位置对 11…1 应的值一定小于第【个位置对应的值，则 22 2 值满足G= 通过解密操作，请 当>t时，第〔个位置对应的值一定大于 第j个位置对应的值，则证毕. MM... M 根据置换地址码【)和【V一1)的取值，利用 求该密文图像对应的明文图像.按照前面得到的 定理1能够得知与名的大小关系.至此，可以 M行行置换地址码{()。{y}。,{杰 对密钥展开攻击.Lgsti映射(1)的不动点为0.5 (y),分别对明文图像B对应的每行像素进行 在定义区间（一11）上，当X<时，∈k1= 行置换，把所有M行像素置换完毕之后得到的图 (-↓05片当1>时，-∈1=(05 像记为CS:检测C的第1列中每个像素灰度值j1,.对Lgt9映射进行反向迭代：若￥-1∈无1= (主12；M所在的行数，分别记录为(：则 图像G的第1列像素在列置乱加密前后所处的行 -15ek:=-1-U 数，用整数对序列{((，}1表示.对序列 {(()}按照(j的升序排序，把排序后的 序列记录为{(k().则{（即为图 42=- 1-0.51-05 像第1列的列置换地址码.依次检测的第= N2N2 依次反向迭代下 23:列中每个像素灰度值‘卡12；M在 去，直到求出爷所属的区间集【显然，密钥￥必 该列所处的行数，即可以得到所有列的列置换地 然属于↓而且1相对于区间（一11）缩小了.但 址码{(.{》，《(》.这样， 是实验表明，这种方法并不是很有效.原因有二： 利用选择密文攻击，行列复合置乱算法的行置换地 其一，如果实现精度为Lbt在I中穷举密钥搜索 址码和列置换地址码也被成功恢复， 的平均复杂度为23一2，相比密钥空间（一1 4.2密钥恢复算法 1),密钥熵仅仅降低了3~4bt其二，随着反向迭 攻击者利用41节提出的选择明文密文攻击 代次数的增加，组成区间集的区间个数随着的 方案，分别重构了图像行列置乱算法和行列复合 减小成指数倍增长.当=1时，I的区间个数最多 置乱算法的置换地址码.挖掘置换地址码隐藏的信 能达到2,2个区间将占用很大的存储空间. 息，可以进一步恢复密钥. 因此，需要改进算法，进一步缩小密钥搜索区间来 为方便起见，用X表示Y,X表示(. 降低攻击复杂度. 定理1假设混沌序列{)，排升序得到 解决方法就是同时考虑时间延迟为1~3的相 {为其置换地址码为{年}对于H共，j 空间.Logistic9映射的相空间图如图1所示. 1.0 a 190-05 005 1.0-0.50 -1.0-0.500.5 0 图1 Lcgist映射的相空间图.（时间延迟为上（时间延迟为2(9时间延迟为3 Fg1 Phase space ppts of the Logisticma理（号the dely ti恤es上(he dely tme is:2(9 the delay tme is3北 京 科 技 大 学 学 报 第 32卷 序列记录为 {( k, t1 (k) )} N k=1, 则 {t1 ( k)} N k=1即为图 像第 1行的行置换地址码.依次检测 P1 的第 j(j= 2, …, M)行中每个像素灰度值 i( i=1, 2, …, N)在该 行所处的列数, 用同样的方法得到所有 M行的行 置 换 地 址 码 {t1 ( k) } N k=1, {t2 ( k) } N k=1, …, {tM ( k) } N k=1 .然后选取密文图像 C2, 使得像素灰度 值满足 C2 = 1 1 … 1 2 2 … 2    M M … M .通过解密操作, 请 求该密文图像对应的明文图像 P2.按照前面得到的 M行行置换地址码 {t1 ( k)} N k=1, {t2 ( k)} N k=1, …, {tM ( k) } N k=1, 分别对明文图像 P2 对应的每行像素进行 行置换, 把所有 M行像素置换完毕之后得到的图 像记为 C2′.检测 C′2 的第 1列中每个像素灰度值 j ( j=1, 2, …, M)所在的行数, 分别记录为 s1 (j);则 图像 C′2 的第 1列像素在列置乱加密前后所处的行 数, 用整数对序列 {( s1 ( j), j) } M j=1表示 .对序列 {( s1 ( j), j)} M j=1按照 s1 ( j)的升序排序, 把排序后的 序列记录为 {( k, t1 ( k) ) } M k=1 .则 {t1 ( k) } M k=1即为图 像第 1列的列置换地址码.依次检测 C′2 的第 i( i= 2, 3, …, N)列中每个像素灰度值 j( j=1, 2, …, M)在 该列所处的行数, 即可以得到所有 N列的列置换地 址码{t1 ( j) } M j=1, {t2 ( j)} M j=1, …, {tN( j)} M j=1 .这样, 利用选择密文攻击, 行列复合置乱算法的行置换地 址码和列置换地址码也被成功恢复. 4.2 密钥恢复算法 攻击者利用 4.1节提出的选择明文 /密文攻击 方案, 分别重构了图像行 /列置乱算法和行列复合 置乱算法的置换地址码.挖掘置换地址码隐藏的信 息, 可以进一步恢复密钥 . 为方便起见, 用 xi表示 x(i), x′i表示 x′(i). 定理 1 假设混沌序列 {xi} N i=1 排升序得到 {x′i} N i=1, 其置换地址码为 {t( i)} N i=1.对于 i≠j, i, j∈ {1, 2, …, N}, 若 t( i) <t( j), 则 xi <xj;若 t(i) >t(j), 则 xi>xj. 证明 由假设条件可知, xi在序列{xi′} N i=1中的 位置编号为 t( i), xj在序列{xi′} N i=1中的位置编号为 t( j) .由于 {x′i} N i=1是按升序排列的, 对于 i≠j, i, j∈ {1, 2, …, N}, 当 t(i) <t( j)时, 第 t( i)个位置对 应的值一定小于第 t( j)个位置对应的值, 则 xi<xj. 当 t(i) >t(j)时, 第 t(i)个位置对应的值一定大于 第 t(j)个位置对应的值, 则 xi>xj.证毕. 根据置换地址码 t( N)和 t( N-1)的取值, 利用 定理 1能够得知 xN 与 xN-1的大小关系 .至此, 可以 对密钥展开攻击.Logistic映射 ( 1)的不动点为 0.5, 在定义区间 ( -1, 1)上, 当 xN-1 <xN 时, xN-1∈ IN-1 = ( -1, 0.5) ;当 xN-1 >xN 时, xN-1∈ IN-1 =( 0.5, 1).对 Logistic映射进行反向迭代:若 xN-1 ∈ IN-1 = ( -1, 0.5), xN-2 ∈ IN-2 = -1, - 1 -0.5 2 ∪ 1 -0.5 2 , 1 ;若 xN-1 ∈ IN-1 =( 0.5, 1), xN-2 ∈ IN-2 = - 1 -0.5 2 , 1 -0.5 2 .依次反向迭代下 去, 直到求出 x1 所属的区间集 I1.显然, 密钥 x1 必 然属于 I1, 而且 I1 相对于区间 ( -1, 1)缩小了 .但 是实验表明, 这种方法并不是很有效.原因有二: 其一, 如果实现精度为 Lbit, 在 I1 中穷举密钥搜索 的平均复杂度为 2 L-3 ～ 2 L-2 , 相比密钥空间 ( -1, 1), 密钥熵仅仅降低了 3 ～ 4 bit;其二, 随着反向迭 代次数的增加, 组成区间集 Ii的区间个数随着 i的 减小成指数倍增长 .当 i=1时, I1 的区间个数最多 能达到 2 N-1 , 2 N-1个区间将占用很大的存储空间. 因此, 需要改进算法, 进一步缩小密钥搜索区间来 降低攻击复杂度. 解决方法就是同时考虑时间延迟为 1 ～ 3的相 空间 .Logistic映射的相空间图如图 1所示 . 图 1 Logistic映射的相空间图.( a) 时间延迟为 1;( b) 时间延迟为 2;( c) 时间延迟为 3 Fig.1 PhasespaceplotsoftheLogisticmap:( a) thedelaytimeis1;( b) thedelaytimeis2;( c) thedelaytimeis3 · 676·