DO10.13374斤.is00153x.2010.05.024 第32卷第5期 北京科技大学学报 Vo132 No 5 2010年5月 Journal ofUniversity of Science and Technobgy Bejjing May 2010 对一种基于排序变换的混沌图像置乱算法的商榷 刘婷”闵乐泉) 1)北京科技大学信息工程学院.北京1000832)北京科技大学应用科学学院.北京100083 摘要针对“基于排序变换的混沌图像置乱算法”一文提出的密码系统进行了安全性分析.在有限数字精度下，密钥空间 小不足以抵抗唯密文攻击.在选择明文攻击或选择密文攻击下，置换地址码可以重现.在此基础上，结合【gsi混沌映射 的反向迭代，提出了一个密钥恢复算法.理论和实验结果均表明，该密钥恢复算法是实际可行的.有限数字精度的限制和线 性变换的弱点，是导致该密码系统不够安全的两个主要原因.最后讨论了五种可能采取的改进措施及其效果. 关键词密码系统：安全性分析；混沌密码：密码分析 分类号TP309TNg181 D iscussion of a chaotic i age scrambling a lgor ithm based on sort transfomm ation LU Ting).MN Lequan 2) 1)Schoolof hpmaton Eng neerng University of Sc ience and Techrokgy Beijing Beijng 100083 Chna 2)SchoolofApplied Science Universit of$ence ad Technobgy Beijng Beijng 100083 China ABSTRACT The security of a cryptosystem Proposed n the article ofChaotic in age scnambling agorithm based on sort transfom ation was analyzed The whole key space of the iage scrambling cryptosystem is too small to prevent the cpherextony atack when reali zng in fin ite comn putng precision The add ress coles of transposition can reappear by chosen-plantext atuck or chosencphertext at tads A key recovery agoritm was presented by reverse iterating te Logistic chaotic map The heoretical and experin ental results verify hat the key recovery agoritlm is feasb le and efficient Two priary reasons pr the unsafe prob km ae he restriction of fnite camputing precision and he weakness of linear transfom atpn Five possble iproved methods and heir effectswere alo discussed KEY WORDS cryppsysem seaurity aaysis chaotic cryppgraphy cryptanalsis 近年来，网络通信技术的快速发展增加了对图 基于Lgsq映射的排序变换，文献[3]设计了 像加密方法的需求.一般来说，传统的对称和非对 一个图像置乱算法.本文对该算法作了安全性分 称加密算法，如DES3 DES AES和RSA算法不适 析，提出了改进意见. 于直接应用于图像加密.另一方面，由于混沌系统 1基于排序变换的混沌图像置乱算法简介 特性与密码学特性之间的紧密联系，使得基于混沌 的图像密码算法的研究备受关注7 文献[3]的图像行置乱算法可以描述如下.假 置乱技术是图像加密方法之一，常见的图像置 设明文图像的像素数目为M仪N(M和均为正整 乱方法有Amod咬换1-，基于混沌排序的置乱变 数人，选择Logisti9映射(1)的初始条件平1)作为该 换等.但是已有密码分析研究证明，Amo变换 密码系统的密钥. 具有周期性4和可逆性，其置乱算法不能抵抗己 Y叶1)=1-2(. (1) 知明文攻击4和选择明文攻击.到目前为止，对 式中，Y)∈（一11）是Lgs9映射的状态变量， 基于混沌排序的置乱算法的密码分析研究报道的 n=l2…. 较少 迭代该混沌映射，图像行置乱过程叙述如下： 收稿日期：2009-05-31 基金项目：国家自然科学基金资助项目(NQ60674059,N0607B120) 作者简介：刘婷(1984-)，女，博士研究生：闵乐泉(195)，男，教授，博士生导师，Email minlequa@sn8cm
第 32卷 第 5期 2010年 5月 北 京 科 技 大 学 学 报 JournalofUniversityofScienceandTechnologyBeijing Vol.32 No.5 May2010 对一种基于排序变换的混沌图像置乱算法的商榷 刘 婷 1) 闵乐泉 1, 2) 1) 北京科技大学信息工程学院, 北京 100083 2) 北京科技大学应用科学学院, 北京 100083 摘 要 针对“基于排序变换的混沌图像置乱算法”一文提出的密码系统进行了安全性分析 .在有限数字精度下, 密钥空间 小不足以抵抗唯密文攻击.在选择明文攻击或选择密文攻击下, 置换地址码可以重现.在此基础上, 结合 Logistic混沌映射 的反向迭代, 提出了一个密钥恢复算法.理论和实验结果均表明, 该密钥恢复算法是实际可行的.有限数字精度的限制和线 性变换的弱点, 是导致该密码系统不够安全的两个主要原因.最后讨论了五种可能采取的改进措施及其效果. 关键词 密码系统;安全性分析;混沌密码;密码分析 分类号 TP309;TN918.1 Discussionofachaoticimagescramblingalgorithmbasedonsorttransformation LIUTing1) , MINLe-quan1, 2) 1) SchoolofInformationEngineering, UniversityofScienceandTechnologyBeijing, Beijing100083, China 2) SchoolofAppliedScience, UniversityofScienceandTechnologyBeijing, Beijing100083, China ABSTRACT ThesecurityofacryptosystemproposedinthearticleofChaoticimagescramblingalgorithmbasedonsorttransformation wasanalyzed.Thewholekeyspaceoftheimagescramblingcryptosystemistoosmalltopreventtheciphertext-onlyattackwhenrealizinginfinitecomputingprecision.Theaddresscodesoftranspositioncanreappearbychosen-plaintextattackorchosen-ciphertextattack.AkeyrecoveryalgorithmwaspresentedbyreverseiteratingtheLogisticchaoticmap.Thetheoreticalandexperimentalresults verifythatthekeyrecoveryalgorithmisfeasibleandefficient.Twoprimaryreasonsfortheunsafeproblemaretherestrictionoffinite computingprecisionandtheweaknessoflineartransformation.Fivepossibleimprovedmethodsandtheireffectswerealsodiscussed. KEYWORDS cryptosystem;securityanalysis;chaoticcryptography;cryptanalysis 收稿日期:2009--05--31 基金项目:国家自然科学基金资助项目 ( No.60674059, No.60773120) 作者简介:刘 婷 ( 1984— ), 女, 博士研究生;闵乐泉 ( 1951— ), 男, 教授, 博士生导师, E-mail:minlequan@sina.com 近年来, 网络通信技术的快速发展增加了对图 像加密方法的需求.一般来说, 传统的对称和非对 称加密算法, 如 DES、3DES、AES和 RSA算法不适 于直接应用于图像加密.另一方面, 由于混沌系统 特性与密码学特性之间的紧密联系, 使得基于混沌 的图像密码算法的研究备受关注 [ 1--7] . 置乱技术是图像加密方法之一, 常见的图像置 乱方法有 Arnold变换 [ 1--2] 、基于混沌排序的置乱变 换 [ 3] 等.但是已有密码分析研究证明, Arnold变换 具有周期性 [ 4] 和可逆性 [ 5] , 其置乱算法不能抵抗已 知明文攻击 [ 6] 和选择明文攻击 [ 7] .到目前为止, 对 基于混沌排序的置乱算法的密码分析研究报道的 较少. 基于 Logistic映射的排序变换, 文献[ 3]设计了 一个图像置乱算法.本文对该算法作了安全性分 析, 提出了改进意见 . 1 基于排序变换的混沌图像置乱算法简介 文献 [ 3]的图像行置乱算法可以描述如下 .假 设明文图像的像素数目为 M×N(M和 N均为正整 数 ), 选择 Logistic映射 ( 1)的初始条件 x( 1)作为该 密码系统的密钥. x(n+1) =1 -2x 2 ( n) . ( 1) 式中, x(n)∈ ( -1, 1)是 Logistic映射的状态变量, n=1, 2, …. 迭代该混沌映射, 图像行置乱过程叙述如下: DOI :10 .13374 /j .issn1001 -053x .2010 .05 .024
。674 北京科技大学学报 第32卷 SeP1以《1)为初始条件迭代Logisti映射， 更难，但不应该把密码系统的安全性建立在敌手不 产生混沌流{￥}： 知道所使用的密码系统这个前提之下.因此，在设 SeP2对混沌流{)}，按升序排序，得到 计一个密码系统时，应该在Kerckho假设下达到 有序序列{(}： 安全9 SeP3确定每一个混沌值在有序序列 常用的密码分析攻击有四类从难到易列举 {()}中的位置编号，记录为羊功，即得到置 如下. 换地址码{年}=： (1)唯密文攻击：密码分析者有一个或者多个 SeP4按照置换地址码{【)，对图像第1 密文 行的像素进行置换，将第1行的第列（在[↓y) (2)己知明文攻击：密码分析者有一些明文以 像素分别置换到第1行的第t列： 及相应的密文. SeP5把YW的值赋给Y1,对第2行至 (3)选择明文攻击：密码分析者有机会使用密 第M行重复Step1~SeP4直到第M行的像素全 码机，因此可以选择一些明文，并产生密文 部置换完毕， (4)选择密文攻击：密码分析者有机会使用密 使用相同的密钥只需将Sp4改为“按照置 码机，因此可以选择一些密文，并产生明文 上述每一种攻击，目的都是确定密码系统所使 换地址码{中)}对图像的第1行像素进行逆置 用的密钥.后面两种攻击看似不合理，但是密码系 换，即分别将第1行的第【j列像素置换到第1行 统的密钥一旦投入使用（该密钥不为密码分析者所 的第列”，其他步骤相同，即可实现图像行置乱算 知，被嵌入到设备中，密码分析者就可能操纵.这 法的正确解密. 种设备在日常生活中很常见如电子钱包卡(elec 如文献[3]的描述，图像列置乱算法只需对上 tron ic purse ca,GSM电话中的SM卡，销售点 述图像行置乱加解密算法作简单修改，在此不再重 终端机(post of sale tem inalmachin9和网络应用会 复叙述.图像行置乱算法，还可以进一步改进成为 议的令牌加密(web application session pken encryp 行列复合置乱算法.对于像素数目为仪的明文 ton19 图像，行列复合置乱算法的全过程，如上述Sp 1~Step5和承接在Step5之后的Stp6~Step10 3唯密文攻击 的描述 文献[3]使用Lgisti9映射作为图像置乱算法 Sep6把Y)的值赋给Y1: 的混沌系统以初始条件作为密钥.原文认为该算 Step7以Y1)为初始条件迭代Logisti9映射， 法的密钥空间为（一11）之间的全体实数.考虑如 产生混沌流{Y》,对混沌流{Y}￥按升序 下事实：图像置乱算法使用的混沌系统都是在有限 排序，得到有序序列{(}： 精度下实现的.如果实现精度为Lbjt则密钥共有 SeP8确定每一个混沌值Yj在有序序列 2+1个，即密钥熵为+1全部21个密钥并不是 {4j}中的位置编号，记录为羊或即得到置换 都可用，例如0.50这些坏点是不能在置乱算法 地址码{羊j: 中使用的. SeP9按照置换地址码{【j)￥，对图像第1 准确的穷举攻击复杂度可以如下估计.用行置 列的像素进行置换，将第1列的第行([1M) 乱算法加密一幅像素数目为M仪的明文图像，生 像素分别置换到第1列的第t)行： 成所有的置换地址码需要MN次混沌迭代。M次长 SeP10把￥M)的值赋给平1)，对第2列到 度为的序列的排升序操作和N次置换.以交换 第N列重复SeP7~SePg直到第N列的像素全 排序法的起泡排序为例，长度为的序列排序平均 部置换完毕， 需要比较YN1)2次，交换YN-1)/2次，而 2 K erckhof假设和攻击类型 一次交换需要移动3次，即移动3YN-1)2次.假 设一次混沌迭代与比较、移动操作的耗时相等，则 对密码算法进行分析时，通常假设密码分析者 总的攻击复杂度为2MN+4MVYN-1)2=2M. 知道密码设计的系统和工作原理，即秘密全寓于密 对于相当大的尺寸M==1024(这是一幅较大的 钥中.这个假设称作Kerkho锻设.当然，如果密 数字图像的典型尺寸，攻击复杂度为2M=2. 码分析者不知道所使用的密码系统那么破译密码 同理，加密同样大小的明文图像列置乱算法的攻
北 京 科 技 大 学 学 报 第 32卷 Step1 以 x( 1)为初始条件迭代 Logistic映射, 产生混沌流 {x( i)} N i=1; Step2 对混沌流 {x( i)} N i=1按升序排序, 得到 有序序列{x′( i)} N i=1; Step3 确定每一个混沌值 x( i)在有序序列 {x′( i)} N i=1中的位置编号, 记录为 t( i), 即得到置 换地址码{t( i) } N i=1 ; Step4 按照置换地址码 {t( i) } N i=1对图像第 1 行的像素进行置换, 将第 1行的第 i列 ( i∈ [ 1, N] ) 像素分别置换到第 1行的第 t( i)列 ; Step5 把 x( N)的值赋给 x( 1 ), 对第 2行至 第 M行重复 Step1 ～ Step4, 直到第 M行的像素全 部置换完毕 . 使用相同的密钥, 只需将 Step4改为 “按照置 换地址码{t( i) } N i=1对图像的第 1行像素进行逆置 换, 即分别将第 1行的第 t( i)列像素置换到第 1行 的第 i列 ”, 其他步骤相同, 即可实现图像行置乱算 法的正确解密. 如文献 [ 3]的描述, 图像列置乱算法只需对上 述图像行置乱加解密算法作简单修改, 在此不再重 复叙述 .图像行置乱算法, 还可以进一步改进成为 行列复合置乱算法.对于像素数目为 M×N的明文 图像, 行列复合置乱算法的全过程, 如上述 Step 1 ～ Step5和承接在 Step5 之后的 Step6 ～ Step10 的描述 . Step6 把 x(N)的值赋给 x( 1) ; Step7 以 x( 1)为初始条件迭代 Logistic映射, 产生混沌流 {x( j)} M j=1, 对混沌流 {x( j) } M j=1按升序 排序, 得到有序序列 {x′( j)} M j=1 ; Step8 确定每一个混沌值 x( j)在有序序列 {x′( j) } M j=1中的位置编号, 记录为 t(j), 即得到置换 地址码 {t(j) } M j=1 ; Step9 按照置换地址码 {t( j) } M j=1对图像第 1 列的像素进行置换, 将第 1列的第 j行 ( j∈ [ 1, M] ) 像素分别置换到第 1列的第 t( j)行; Step10 把 x( M)的值赋给 x( 1), 对第 2列到 第 N列重复 Step7 ～ Step9, 直到第 N列的像素全 部置换完毕 . 2 Kerckhoff假设和攻击类型 对密码算法进行分析时, 通常假设密码分析者 知道密码设计的系统和工作原理, 即秘密全寓于密 钥中.这个假设称作 Kerckhoff假设 .当然, 如果密 码分析者不知道所使用的密码系统, 那么破译密码 更难, 但不应该把密码系统的安全性建立在敌手不 知道所使用的密码系统这个前提之下 .因此, 在设 计一个密码系统时, 应该在 Kerckhoff假设下达到 安全 [ 8] . 常用的密码分析攻击有四类, 从难到易列举 如下 . ( 1) 唯密文攻击:密码分析者有一个或者多个 密文 . ( 2) 已知明文攻击 :密码分析者有一些明文以 及相应的密文 . ( 3) 选择明文攻击 :密码分析者有机会使用密 码机, 因此可以选择一些明文, 并产生密文. ( 4) 选择密文攻击 :密码分析者有机会使用密 码机, 因此可以选择一些密文, 并产生明文. 上述每一种攻击, 目的都是确定密码系统所使 用的密钥 .后面两种攻击看似不合理, 但是密码系 统的密钥一旦投入使用 (该密钥不为密码分析者所 知 ), 被嵌入到设备中, 密码分析者就可能操纵 .这 种设备在日常生活中很常见, 如电子钱包卡 ( electronicpursecard), GSM电话中的 SIM卡, 销售点 终端机 ( post-of-saleterminalmachine)和网络应用会 议的令牌加密 ( webapplicationsessiontokenencryption) [ 9] . 3 唯密文攻击 文献 [ 3] 使用 Logistic映射作为图像置乱算法 的混沌系统, 以初始条件作为密钥 .原文认为该算 法的密钥空间为 ( -1, 1)之间的全体实数 .考虑如 下事实:图像置乱算法使用的混沌系统都是在有限 精度下实现的 .如果实现精度为 Lbit, 则密钥共有 2 L+1个, 即密钥熵为 L+1.全部 2 L+1个密钥并不是 都可用, 例如 ±0.5, 0这些坏点是不能在置乱算法 中使用的 . 准确的穷举攻击复杂度可以如下估计 .用行置 乱算法加密一幅像素数目为 M×N的明文图像, 生 成所有的置换地址码需要 MN次混沌迭代, M次长 度为 N的序列的排升序操作和 MN次置换 .以交换 排序法的起泡排序为例, 长度为 N的序列排序平均 需要比较 N( N-1) /2次, 交换 N(N-1) /2次, 而 一次交换需要移动 3次, 即移动 3N( N-1) /2次 .假 设一次混沌迭代与比较 、移动操作的耗时相等, 则 总的攻击复杂度为 2MN+4MN( N-1) /2 =2MN 2. 对于相当大的尺寸 M=N=1 024(这是一幅较大的 数字图像的典型尺寸 ), 攻击复杂度为 2MN 2 =2 31. 同理, 加密同样大小的明文图像, 列置乱算法的攻 · 674·
第5期 刘婷等：对一种基于排序变换的混沌图像置乱算法的商榷 675 击复杂度为2P二2”；行列复合置乱算法的攻击 选择明文攻击和选择密文攻击， 复杂度为2M3+2MN=22.由于数字计算机和分 对行列复合置乱算法的选择明文攻击，两幅像 布式运算的快速发展，一个安全的密码需要O 素数目为M仪的明文图像就可以破译.选取一幅 (22)量级（阶号Q·)用来度量复杂性）的安全复 明文图像，使得像素灰度值满足P= 杂度.因此文献[3]的混沌图像置乱算法（无论 11… 1 是行列置乱算法还是行列复合置乱算法)的安全 2 2 2 ,通过加密操作，请求的密 性不够高。 MM... M 4选择明文密文攻击 文图像G.分别检测G的第1列中每个像素灰度 4.1重现置换地址码 值（主12，M所在的行数，记录为(）即得 假设该算法的密钥不为攻击者所知，对行置乱 到了第1列的列置换地址码{(j生.依次检测 算法的选择明文攻击方案如下：选取幅明文图像 G的第=23；V列中每个像素灰度值≠ P(=12…,),分别满足第1行第列的像素灰 12M在该列所处的行数，即可以得到所有N 度值为非零，其他像素灰度值均为零.请求明文图 列的列置换地址码{(j》。{(}出。； 像P的密文图像C分别检测G中非零像素所在 {(}士.然后选取明文图像B,使得像素灰度值 的位置（该像素一定位于第1行），把该像素所在的 12 N 列数记为t).这样，就成功恢复了图像第1行像 1 N 素的置换地址码{t)}士·如果想继续恢复图像第 满足B= 通过加密操作，请求 行（庄[2M的置换地址码，重新选择幅明文 12 N 图像(=I2:),满足第行第列的像素灰 B的密文图像S.按照N列的列置换地址码 度值非零其他像素灰度值均为零即可. 《j},{j},{(,对G进行 对行置乱算法的选择密文攻击，稍不同于上文 列置换解密操作，即分别对对应的每列像素进行 的选择明文攻击.选取N幅密文图像C(=12 逆置换.把得到的图像记为C,则G就是明文图 ,),满足第1行第列的像素灰度值为非零，其 他像素灰度值均为零，通过解密操作，请求密文图 像B经过行置换地址码加密之后的图像.检测C 像C对应的明文图像P分别检测P中非零像素 的第1行中每个像素灰度值(=12，N)所在 的列数，分别记录为，即得到了第1行的行置 所处的列数（一定都位于第1行），记录为￥.则 非零像素在图像置乱前后所在的列数，用整数对序 换地址码{())三.依次检测G的第（≠23 列{（可头》1表示.对序列{（可，）}按照 …,M行中每个像素灰度值=12；在该 行所处的列数，即得到了所有M行的行置换地址 的升序排序，把排序后的序列记录为{(，J ￥j)}.则{j}即为图像第1行的置换地址 码{9}，{()}e,,{()}1.这样， 码.如果想继续恢复第行（庄[2M)的置换地址 图像的行置换地址码和列置换地址码均被成功 码，重新选择N幅密文图像C(=12:),满 恢复 足第行第列的像素灰度值非零，其他像素灰度 对行列复合置乱算法的选择密文攻击，亦可以 值均为零即可. 通过两幅像素数目为M仪的密文图像破译.选取 选择明文密文攻击方法，同样可以用来攻击 一幅密文图像G,使得像素灰度值满足G= N 文献[3]的列置乱算法.在选择明文攻击中，选取 1 2 M幅明文图像P(=12M),分别满足第1列 2 4 通过解密操作，请求该密文图 第行的像素灰度值为非零，其他像素灰度值均为 零的条件：在选择密文攻击中，选取M幅密文图像 1 2 C(=L2…,M),分别满足第1列第行的像素 像对应的明文图像R.检测R的第1行中每个像 灰度值为非零，其他像素灰度值均为零的条件，均 素灰度值（≠12，y所在的列数，分别记录为 可成功重构第1列的置换地址码.重构其他列的置 (j:则第1行像素在图像加密前后所在的列数 换地址码的方法与之类似由于篇幅的限制，具体 用整数对序列{($（功，）}=1表示.对序列 细节不再详述.下面对行列复合置乱算法分别进行 {((,}三按照（的升序排序，把排序后的
第 5期 刘 婷等:对一种基于排序变换的混沌图像置乱算法的商榷 击复杂度为 2M 2 N=2 31;行列复合置乱算法的攻击 复杂度为 2MN 2 +2M 2 N=2 32.由于数字计算机和分 布式运算的快速发展, 一个安全的密码需要 O ( 2 128 )量级 (阶号 O(· )用来度量复杂性 )的安全复 杂度 [ 10] .因此文献[ 3]的混沌图像置乱算法 (无论 是行 /列置乱算法还是行列复合置乱算法 )的安全 性不够高. 4 选择明文 /密文攻击 4.1 重现置换地址码 假设该算法的密钥不为攻击者所知, 对行置乱 算法的选择明文攻击方案如下 :选取 N幅明文图像 Pi( i=1, 2, …, N), 分别满足第 1行第 i列的像素灰 度值为非零, 其他像素灰度值均为零.请求明文图 像 Pi的密文图像 Ci, 分别检测 Ci中非零像素所在 的位置 (该像素一定位于第 1行 ), 把该像素所在的 列数记为 t( i).这样, 就成功恢复了图像第 1 行像 素的置换地址码 {t( i)} N i=1.如果想继续恢复图像第 j行 (j∈ [ 2, M] )的置换地址码, 重新选择 N幅明文 图像 Pi′(i=1, 2, …, N), 满足第 j行第 i列的像素灰 度值非零, 其他像素灰度值均为零即可 . 对行置乱算法的选择密文攻击, 稍不同于上文 的选择明文攻击.选取 N幅密文图像 Ci( i=1, 2, …, N), 满足第 1行第 i列的像素灰度值为非零, 其 他像素灰度值均为零 .通过解密操作, 请求密文图 像 Ci对应的明文图像 Pi.分别检测 Pi中非零像素 所处的列数 (一定都位于第 1行 ), 记录为 s( i).则 非零像素在图像置乱前后所在的列数, 用整数对序 列 {(s(i), i)} N i=1表示.对序列 {( s( i), i) } N i=1按照 s(i)的升序排序, 把排序后的序列记录为 {(j, t( j) ) } N j=1.则 {t( j) } N j=1即为图像第 1行的置换地址 码 .如果想继续恢复第 j行 ( j∈ [ 2, M] )的置换地址 码, 重新选择 N幅密文图像 Ci′( i=1, 2, …, N), 满 足第 j行第 i列的像素灰度值非零, 其他像素灰度 值均为零即可. 选择明文 /密文攻击方法, 同样可以用来攻击 文献[ 3]的列置乱算法 .在选择明文攻击中, 选取 M幅明文图像 Pi( i=1, 2, …, M), 分别满足第 1列 第 i行的像素灰度值为非零, 其他像素灰度值均为 零的条件;在选择密文攻击中, 选取 M幅密文图像 Ci( i=1, 2, …, M), 分别满足第 1 列第 i行的像素 灰度值为非零, 其他像素灰度值均为零的条件, 均 可成功重构第 1列的置换地址码.重构其他列的置 换地址码的方法与之类似, 由于篇幅的限制, 具体 细节不再详述.下面对行列复合置乱算法分别进行 选择明文攻击和选择密文攻击. 对行列复合置乱算法的选择明文攻击, 两幅像 素数目为 M×N的明文图像就可以破译 .选取一幅 明文 图 像 P1, 使 得 像 素 灰 度 值 满 足 P1 = 1 1 … 1 2 2 … 2 M M … M .通过加密操作, 请求 P1 的密 文图像 C1.分别检测 C1 的第 1列中每个像素灰度 值 j(j=1, 2, …, M)所在的行数, 记录为 t1 ( j), 即得 到了第 1列的列置换地址码 {t1 ( j) } M j=1.依次检测 C1 的第 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 .然后选取明文图像 P2, 使得像素灰度值 满足 P2 = 1 2 … N 1 2 … N 1 2 … N .通过加密操作, 请求 P2 的密文图像 C2.按照 N列 的列置 换地址 码 {t1 ( j) } M j=1, {t2 ( j) } M j=1, …, {tN( j) } M j=1, 对 C2 进行 列置换解密操作, 即分别对对应的每列像素进行 逆置换 .把得到的图像记为 C′2, 则 C2′就是明文图 像 P2 经过行置换地址码加密之后的图像 .检测 C′2 的第 1行中每个像素灰度值 i( i=1, 2, …, N)所在 的列数, 分别记录为 t( i), 即得到了第 1行的行置 换地址码 {t1 ( i) } N i=1 .依次检测 C′2 的第 j( j=2, 3, …, M)行中每个像素灰度值 i( i=1, 2, …, N)在该 行所处的列数, 即得到了所有 M行的行置换地址 码 {t1 ( i) } N i=1, {t2 ( i) } N i=1, …, {tM ( i) } N i=1 .这样, 图像的行置换地址码和列置换地址码均被成功 恢复. 对行列复合置乱算法的选择密文攻击, 亦可以 通过两幅像素数目为 M×N的密文图像破译.选取 一幅密文图像 C1, 使得像素灰 度值满足 C1 = 1 2 … N 1 2 … N 1 2 … N .通过解密操作, 请求该密文图 像对应的明文图像 P1.检测 P1 的第 1行中每个像 素灰度值 i( i=1, 2, …, N)所在的列数, 分别记录为 s1 ( i) ;则第 1行像素在图像加密前后所在的列数, 用整 数 对序 列 {( s1 ( i), i) } N i=1 表 示.对 序 列 {(s1 (i), i) } N i=1按照 s1 (i)的升序排序, 把排序后的 · 675·
。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·
第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·