第5期 刘婷等：对一种基于排序变换的混沌图像置乱算法的商榷 ·677° 图1(a中的点A图1(b中的点B、B和B 三个区间集取交集，得到一个区间集【： 及图1（中的点G、S、S、GG、C和G分别是 Stp3取交集【1=1∩【，得到X-的所 Lgst9映射时间延迟为1、2和3的不动点.用牛顿 属区间集【1. 迭代法可以得到它们的横坐标：X=0.5圣= Sp4把一1的值赋予，i【,的值赋予. -0.309016994374947=05= 如果>1重复Sep1~SeP3否则，停止. 0.80901694374947￥=-0.766044443118978 输出：X所属的区间集T. ￥，=一0623489801858733￥=一0.173648176669男 密钥恢复流程如图2所示. ￥=0.222520933956314￥，=0.5￥= 定理2假设文献[3]提出的图像（行列和行 0.900968867902419,=0.939692620785908 列复合置乱算法的实现精度为Lbt当>中2× 所以，当LOgisti映射的时间延迟为1时，若< 10)0693时，上述密钥恢复算法输出的是一个 +,∈（一↓055若，∈(0.51.当 点集. Lgst9映射的时间延迟为2时，若<X2,∈ 证明Lyapunov指数入是对两个很靠近的初 (-1-0309016994374947)U(0.5 值产生的轨道，随时间推移按指数方式分离的定量 0.809016994374947):若￥>X2￥∈ 描述.式(l所表示的Logistic混沌映射的Lyapunov (一0.3090169943749470.5)U(0.809016994374947 指数约为入=0.693 1).当LOgisticp映射的时间延迟为3时，若X< 对于任意相距为e(e为趋于0的实数)且都属 x+￥∈(-↓-0.766044443118978)U 于（一↓1）区间的两点和十ξ经过饮迭代 (-0.623489801858733-0.1736481766693)U 后相距为e®=IF(各十e)一F(各)↓其中 (0225209339563140.5儿U(0.900968867902419 F9=1-2天由于F(各+e,F(各)∈(-1 0.9396926207859085若￥>x4,X∈ 1,则F(苍十e)一F(各)<2实际上，本文提 (-0.766044443118978-0.623489801858733)U 出的密钥恢复算法是一个反向迭代过程.可以理解 (-0.173648177666930.222520933956314儿U 为：位于（一11区间上的两点F()和F(爷十 (050900968867902419儿U(093962620785908 e,经过吹Logistr映射的反向迭代之后相距为 1. :假设实现精度为Lbt当10时，这两点就 每个时间延迟的相图中，所属的区间均为开 重叠了，可以认为是同一个点. 区间，这表明不会出现X与X。X2X+3相等的情 由e心<2和≤10，得到乡(2×10)/ 况.X与不相等是因为0.5是不动点第3节 入，由此证明了密钥恢复算法在实现精度为Lb的 己经讨论过，必须从密钥空间中排除.而且它也不 计算机上，当2(2×10)入时，区间集序列 会从迭代中产生，故05这一点为开区间.假设 {【}收敛到一个点集.证毕. =X+2则￥的周期为2这与混沌的定义相违 43仿真实验 背.同理，X与X也不相等. 为了验证选择明文密文攻击方案对图像行列 具体的密钥恢复算法步骤如下. 置乱算法和行列复合置乱算法的实用性，本小节给 输入：由选择明文攻击或选择密文攻击恢复的 出一些具体的实验结果. (图像行列置乱算法和行列复合置乱算法)置换地 以I6b的实现精度和尺寸为M仪YM=N= 址码仁{1,2)，ty. 256)的图像为例作攻击实验.由42节的定理2 初始化：确定的值（≤V一2.根据比较 知，当实现精度L=16b时，乡55所以，仅重构 与：的大小：若<4，∈青=（一1 图像第1行（对图像行置乱算法和行列复合置乱算 0.5:若>+，∈=(0.51小.把的值赋 法而言或者第1列（对图像列置乱算法而言）的置 予把{的值赋予. 换地址码，对于恢复密钥绰绰有余，只要重构了足 SeP1对X的所属区间集I进行Logisti9映 够的置换地址码，密钥攻击实验对于行列置乱算 射反向迭代，得到的区间集记为L. 法和行列复合置乱算法就完全相同了.不妨以图像 SeP2由置换地址码判断X,与￥X, 行置乱算法为例，选取前80个混沌流的置换地址 X+的大小关系.然后，根据相图确定时间延迟分 码做密钥攻击实验. 别为1~3时x所属的区间集巴，，.对这 任意选取1000个（一11）区间内的值作为密第 5期 刘 婷等:对一种基于排序变换的混沌图像置乱算法的商榷 图 1(a)中的点 A, 图 1(b)中的点 B1 、 B2 和 B3 及图 1(c)中的点 C1 、C2 、C3 、C4 、C5 、C6 和 C7 分别是 Logistic映射时间延迟为 1、2和 3的不动点.用牛顿 迭代法可以 得到它们的横坐标 :xA =0.5, xB1 = -0.309 016994 374 947, xB2 = 0.5, xB3 = 0.809016994 374947, xC1 =-0.766 044 443 118 978, xC2 =-0.623489801858733, xC3 =-0.17364817766693, xC4 =0.222 520 933 956 314, xC5 =0.5, xC6 = 0.900 968 867 902 419, xC7 =0.939 692 620 785 908. 所以, 当 Logistic映射的时间延迟为 1时, 若 xi < xi+1, xi∈ ( -1, 0.5);若 xi>xi+1, xi∈ ( 0.5, 1).当 Logistic映射的时间延迟为 2时, 若 xi <xi+2, xi∈ ( - 1, - 0.309 016 994 374 947 ) ∪ ( 0.5, 0.809 016 994 374 947) ; 若 xi > xi+2, xi ∈ ( -0.309016994374947, 0.5) ∪ ( 0.809016994374947, 1) .当 Logistic映射的时间延迟为 3 时, 若 xi < xi+3, xi ∈ ( -1, -0.766 044 443 118 978 ) ∪ ( -0.623489801858 733, -0.173 648 177 666 93 ) ∪ ( 0.222 520 933 956 314, 0.5)∪ ( 0.900 968 867 902 419, 0.939 692 620 785 908 );若 xi > xi+3, xi ∈ ( -0.766044443118 978, -0.623 489 801 858 733) ∪ ( -0.173 648 177 666 93, 0.222 520 933 956 314) ∪ ( 0.5, 0.900 968 867 902 419)∪ ( 0.939 692 620 785 908, 1). 每个时间延迟的相图中, xi所属的区间均为开 区间, 这表明不会出现 xi与 xi+1, xi+2, xi+3相等的情 况 .xi与 xi+1不相等是因为 0.5是不动点, 第 3节 已经讨论过, 必须从密钥空间中排除.而且它也不 会从迭代中产生, 故 0.5 这一点为开区间.假设 xi =xi+2, 则 xi的周期为 2, 这与混沌的定义相违 背 .同理, xi与 xi+3也不相等. 具体的密钥恢复算法步骤如下. 输入:由选择明文攻击或选择密文攻击恢复的 (图像行 /列置乱算法和行列复合置乱算法 )置换地 址码 t={t( 1), t( 2), …, t( N) }. 初始化 :确定 n的值 ( n≤N-2).根据 t比较 xn与 xn+1的大小:若 xn <xn+1, xn∈ I ＊ n =( -1, 0.5) ;若 xn >xn+1, xn∈ I ＊ n =( 0.5, 1) .把 n的值赋 予 i, 把 I ＊ n 的值赋予 I ＊ i . Step1 对 xi的所属区间集 I ＊ i 进行 Logistic映 射反向迭代, 得到的区间集记为 Ii-1. Step2 由置换地址码 t判断 xi-1与 xi, xi+1, xi+2的大小关系 .然后, 根据相图确定时间延迟分 别为 1 ～ 3时 xi-1所属的区间集 I ( 1) i-1, I ( 2) i-1, I ( 3) i-1 .对这 三个区间集取交集, 得到一个区间集 Ii′-1 ; Step3 取交集 I ＊ i-1 =Ii-1∩ Ii′-1, 得到 xi-1的所 属区间集 I ＊ i-1 . Step4 把 i-1的值赋予 i, I ＊ i-1的值赋予 I ＊ i . 如果 i>1, 重复 Step1 ～ Step3;否则, 停止. 输出 :x1 所属的区间集 I ＊ 1 . 密钥恢复流程如图 2所示 . 定理 2 假设文献 [ 3]提出的图像 (行 /列和行 列复合 )置乱算法的实现精度为 Lbit, 当 n>ln( 2 × 10 L ) /0.693时, 上述密钥恢复算法输出的是一个 点集 . 证明 Lyapunov指数 λ是对两个很靠近的初 值产生的轨道, 随时间推移按指数方式分离的定量 描述 .式 ( 1)所表示的 Logistic混沌映射的 Lyapunov 指数约为 λ=0.693. 对于任意相距为 ε( ε为趋于 0的实数 )且都属 于 ( -1, 1)区间的两点 x0 和 x0 +ε, 经过 n次迭代 后相距为 εe nλ = F n ( x0 +ε) -F n ( x0 ) , 其中 F( x) =1 -2x 2 .由于 F n ( x0 +ε), F n ( x0 ) ∈ ( -1, 1), 则 F n ( x0 +ε) -F n (x0 ) <2.实际上, 本文提 出的密钥恢复算法是一个反向迭代过程 .可以理解 为:位于 ( -1, 1)区间上的两点 F n ( x0 )和 F n ( x0 + ε), 经过 n次 Logistic映射的反向迭代之后相距为 ε.假设实现精度为 Lbit, 当 ε≤10 -L时, 这两点就 重叠了, 可以认为是同一个点. 由 εe nλ <2和 ε≤10 -L , 得到 n≥ln( 2 ×10 L ) / λ.由此证明了密钥恢复算法在实现精度为 Lbit的 计算机上, 当 n≥ln( 2 ×10 L ) /λ时, 区间集序列 {I ＊ i } n i=1收敛到一个点集.证毕 . 4.3 仿真实验 为了验证选择明文 /密文攻击方案对图像行 /列 置乱算法和行列复合置乱算法的实用性, 本小节给 出一些具体的实验结果 . 以 16 bit的实现精度和尺寸为 M×N(M=N= 256)的图像为例作攻击实验 .由 4.2 节的定理 2 知, 当实现精度 L=16 bit时, n≥55.所以, 仅重构 图像第 1行 (对图像行置乱算法和行列复合置乱算 法而言 )或者第 1列 (对图像列置乱算法而言 )的置 换地址码, 对于恢复密钥绰绰有余 .只要重构了足 够的置换地址码, 密钥攻击实验对于行 /列置乱算 法和行列复合置乱算法就完全相同了.不妨以图像 行置乱算法为例, 选取前 80个混沌流的置换地址 码做密钥攻击实验 . 任意选取 1 000个 ( -1, 1)区间内的值作为密 · 677·