（计算机应用技术专业论文）基于混沌映射与排序变换的图像置乱算法.pdf

重庆大学硕士学位论文 中文摘要 摘要 在信息时代的今天，随着网络技术和多媒体技术的快速发展和广泛应用，越 来越多的信息在网络上能够迅速和方便地传输，新技术给人们带来便捷的同时， 与之相伴而生的是安全隐患问题。因而，信息安全成为国际上研究的热门话题。 加密技术是保护信息最有效的手段，已经成为一项非常实用又急需快速发展的关 键技术。混沌现象是2 0 世纪人类最重要的科学发现之一，随着对混沌现象认识的 深入，如何应用混沌研究成果为人类服务已成为非线性科学发展提出的一个重要 课题。 本文简要介绍了数字图像加密技术的意义、研究现状及发展趋势；探讨了数 字图像加密的基本原理，分析了几种数字图像加密技术的原理、算法，指出了它 们各自的优点和局限性；系统介绍了混沌理论，详细讨论了由l o g i s t i c 映射所产生 的混沌序列及其性质。混沌序列具有容易生成、对初始条件敏感以及具备白噪声 的统计特性等优点，将其与数字图像加密技术相结合，可以构造出非常好的图像 信息加密系统。本文提出了基于混沌映射与排序变换的图像置乱算法，通过混沌 序列的排序来得到图像置乱的地址交换码。由于排序变换的不规则性，因此新的 混沌图像置乱算法具有较强的保密性能。通过对新算法的置乱性能进行仿真实验， 结果表明，新算法具有良好的置乱性能。 最后论文对研究工作进行了全面的总结，并对今后工作进行了展望。 关键词：数字图像，加密算法，混沌映射，排序变换，图像置乱 重庆大学硕士学位论文英文摘要 a b s t r a c t n o w a d a y s ，w i t ht h er a p i dd e v e l o p m e n ta n dw i d ea p p l i c a t i o n s o fc o m p u t e r t e c h n o l o g ya n dn e t w o r kt e c h n o l o g y , m o r ea n dm o r ei n f o r m a t i o nh a sb e e nq u i c k l ya n d c o n v e n i e n t l yt r a n s m i t t e dt h r o u g ht h en e t w o r k a tt h es a m et i m e ，i th a st h ep o t e n t i a l p r o b l e m so f t h es e c u r i t yo f i n f o r m a t i o n t h e r e f o r e ，t h es e c u r i t yo f i n f o r m a t i o ni sg e t t i n g m o r ea n dm o r ei m p o r t a n t c r y p t o g r a p h y , w h i c ha i m sa tt h es e c u r i t yo fi n f o r m a t i o n ，h a s b e c o m eo n eo ft h ei m p o r t a n tr e s e a r c hf i e l d si ni n f o r m a t i o ns c i e n c ea n dt e c h n o l o g y u p t on o w ，d a t ae n e r y p t i o nt e c h n o l o g yi st h eb e s tm e t h o dt oo b t a i ni n f o r m a t i o ns e c u r i t y u n d o u b t e d l y ；i ti sg r e a t l yp r a c t i c a la n du r g e n tt od e v e l o pk e yt e c h n o l o g y c h a o si so n e o ft h em o s ti m p o r t a n ts c i e n c ed i s c o v e r i e s a l o n gw i t ht h e f u r t h e ru n d e r s t a n d i n go f c h a o t i cp h e n o m e n o n ，h o wt oa p p l yt h ec h a o t i cr e s e a r c ha c h i e v e m e n t st os e r v ef o rt h e h u m a n i t yh a sb e c a m eo n ei m p o r t a n tt o p i ci nn o n l i n e a rs c i e n c e t h et h e s i s # y e sab r i e fi n t r o d u c t i o nt ot h es i g n i f i c a n c e ，c u r r e n tr e s e a r c hs t a t u sa n d d e v e l o p m e n tt e n d e n c yo fi m a g ee n c r y p t i o n ，h a sd i s c u s s i o na b o u tt h eb a s i ct h e o r yo f s e v e r a li m a g ee n c r y p t i o n s ，a n dp o i n t so u td i s a d v a n t a g ea n da d v a n t a g eo fs e v e r a l e n c r y p t i o na l g o r i t h m s ；c h a o t i cd y n a m i c sa r ep r e s e n t e d ，t h ea u t h o rd i s c u s s e dt h ec h a o t i c s e q u e n c e sg e n e r a t e dv i al o g i s t i cm a p c h a o t i cs e q u e n c e sh a v es e v e r a lg o o dp r o p e r t i e s i n c l u d i n gt h ee a s eo f g e n e r a t i o n , s e n s i t i v ed e p e n d e n c eo ni n i t i a lc o n d i t i o na n d n o i s el i k e c h a o t i ct h e o r ya n dd i g i t a li m a g ec n c r y p t i o na r ec o m b i n e d ，w h i c hc a nb eu s e dt od e s i g n ab e t t e rs y s t e mo fi m a g ee n e r y p t i o n t h i sp a p e rp r o p o s e sa na l g o r i t h mo fi m a g e s c r a m b l i n ga l g o r i t h mb a s e do nt h ec h a o t i cm a pa n ds o r tt r a n s f o r m a t i o n t h en e v r a l g o r i t h mo b t a i n s t h ea d d r e s sc o d e so ft h ei m a g e st r a n s p o s i t i o nb yt h es o r t t r a n s f o r m a t i o no ft h ec h a o t i cs e q u e n c e d u et ot h es t r o n gi r r e g u l a r i t yo fs o r t t r a n s f o r m a t i o n ，t h en e wc h a o t i ci m a g e ss c r a m b l i n ga l g o r i t h mp o s s e s s e sh i g hs e c u r i t y t h e p a p e ra l s oa n a l y z e st h es c r a m b l i n gp e r f o r m a n c eo f t h en e wa l g o r i t h mi na s t a t i s t i c a l w a y t h e r e s u l t si n d i c a t et h a tt h ea l g o r i t h mb e a r sn i c es c r a m b l i n gc a p a b i l i t y f i n a l l y , t h es u m m a r i z a t i o ni so b t a i n e da n dt h ef u t u r er e s e a r c hd i r e c t i o n sa r ea l s o g i v e n k e y w o r d s ：d i g i t a li m a g e ，e n c r y p t i o na l g o r i t h m ，c h a o sm a p ，s o r tt r a n s f o r m a t i o n , i m a g es c r a m b l i n g i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：蕾汤 签字日期： 学位论文版权使用授权书 年f 月2 - 2 - 日 本学位论文作者完全了解 重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重鏖太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：灰秀 一名：移 签字日期：1 年s , g z ) - 日 签字日期：，7 叼年，月力1 e t 重庆大学硕士学位论文1 绪论 1 绪论 1 1 问题的提出及研究意义 计算机、多媒体、互联网这些随着数字时代的到来而涌现出的新事物给我们 的世界带来了翻天覆地的变化。在上个世纪9 0 年代，数字时代最富传奇色彩的人 物微软公司总裁比尔盖茨，写了一本书叫做未来之路，在这本书中， 他用一句著名的话：“信息就在你的指尖( i n f o r m a t i o ni so ny o u rf i n g e rt i p s ) ”，向 人们勾画了一幅美好的景象：坐在家里，通过一台电脑、一个鼠标、一段网线， 就能找到想要的一切【1 1 。是的，i n t e m e t 技术和多媒体技术仍在飞速发展，信息化 不可逆转，以数字媒体数据为主的大量个人和公众信息以各种形式在网络上迅速 便捷地传输，尤其是存储技术的迅速发展和网络带宽限制的突破，越来越多的容 量巨大的多媒体信息得以在网络上传输。 在网络连接起来的信息世界中，距离己不再是问题，我们可以通过网络得到 各种文章、图片、音乐、动画，甚至是一部电影、一段足球比赛的实况等等，信 息随处可纠2 1 。但是，网络在给人们带来便利的同时也暴露出越来越严重的安全问 题：一方面由于计算机网络的开放性，使信息在传输和存储过程中有可能被盗用 或篡改；其次，随着计算机和网络的普及，使得人们很容易接触并搜集到网络中 这些信息，无论这种搜集是善意还是恶意、合法还是非法，信息的安全问题逐步 成为众所关心的问题。例如：多媒体作品的版权侵犯、软件或文档的非法拷贝、 电子商务中的非法盗用和篡改、网络中信息的非法截取和查看，甚至黑客攻击等 等。另外，近年来利用计算机和网络犯罪的数量也在逐年上升。据权威资料统计， 全世界几乎每2 0 秒钟就有一起黑客入侵事件发生【”。另据美国联邦调查局调查， 仅美国每年由于信息安全问题所造成的经济损失就超过1 7 0 亿美元f ，j 。由此可见， 信息安全技术不但关系到个人通信的隐私问题，关系到一个企业的商业机密乃至 企业的生存问题，而且也关系到一个国家的安全问题。因此，信息安全技术越来 越受到全社会的高度重视。毫无疑问，网络信息安全是现在乃至未来相当长时期 内的需要解决的热点问题之一。 加密技术作为安全通信的重要手段，从古至今人们都在不断地进行研究。然 而，任何加密方案都存在可能的破解方法，只是有的方案破解需要几十年甚至上 百年或更长的时间，而有的只需要一年甚至更短的时间。特别是近年来，随着计 算机硬件技术的飞速发展，性能的不断提高，密码分析理论的不断创新，过去非 常安全的加密技术，现在已变得不再那么安全，高性能的计算机有可能在很短的 时间内就能破解过去根本不能破解的加密方案。因此，需要研究新的加密技术， 重庆大学硕士学位论文i 绪论 以适应新形势下信息安全的要求。 目前，信息安全技术涉及的范围越来越广泛，从密码技术、鉴别技术、访问 控制技术、口令控制技术、防火墙技术、计算机网络病毒防治技术到计算机安全 检测技术等，但密码技术始终是核心技术。在国家关键基础设施中不可能引进或 采用别人的加密技术，我们必须要有自己自主开发的加密算法。可以说2 1 世纪的 竞争，在很大程度上将取决于信息对抗的能力的竞争。 2 0 世纪下半叶，非线性科学获得了前所未有的蓬勃发展。非线性科学是一门 研究非线性现象共性的基础科学，被誉为2 0 世纪自然科学中的“三大革命之一”。 科学界认为：非线性科学的研究不仅具有重大的科学意义，而且具有广泛的应用 前景 1 , 3 - 5 1 。事实上，这门科学几乎涉及自然科学和社会科学的各个领域，并且不断 在改变人们对现实世界的许多传统看法。非线性科学的研究涉及对确定性与随机 性、有序与无序、偶然和必然、量变和质变、整体和局部等数学范畴和哲学概念 的再认识。它将深刻影响人类的思维方法，涉及现代科学的逻辑体系及其变革这 样一些根本性问题。一般来说，非线性科学的主体包括：混沌( c h a o s ) 、分岔 ( b i f u r c a u o n ) 、分形( f r a c t a l ) 、孤立子( s o l i t o n ) 和复杂性( m p l c x i t y ) 的研究吲。其中， 混沌的研究占有极大的份量。 从数学上讲，对于确定的初始值，由动力系统就可以推知该系统长期行为甚 至追溯到其过去的性态。但是2 0 世纪6 0 年代，美国气象学家l o r e n z 在研究大气 的时候发现，当选取一定参数的时候，一个由确定的三阶常微分方程组描述的大 气对流模型，变得不可预测了，这就是有趣的“蝴蝶效应”【4 5 ，6 】。在研究的过程中， l o r e n z 观察到了这个确定性系统的规则行为，同时也发现了同一系统出现的非周 期无规则行为。通过长期反复地数值实验和理论思考，l o r e n z 揭示了该结果的真 实意义，首先发现了混沌运动。这为以后的混沌研究开辟了道路。2 0 世纪7 0 年代， 特别是1 9 7 5 年以后，是混沌科学发展史上光辉灿烂的年代。在这一时期，作为一 门新兴的科学混沌学正式诞生了。1 9 7 1 年，法国数学物理学家r u e l l e 和荷兰 学者t a k e n s 一起发表了论湍流的本质【3 】，在学术界首次提出了用混沌来描述 湍流形成机理的新观点。通过严密的数学分析，独立的发现了动力系统存在“奇 怪吸引子”，他们形容为“一簇曲线，一团斑点，有时展现为光彩夺目的星云或 烟火，有时展现为可怕和令人生厌的花丛，数不清的形式有待探讨，有待发现”【3 1 。 1 9 7 3 年，日本京都大学的y u e d a 在用计算机研究非线性振动时，发现了一种杂乱 振动形态，称为u e d a 吸引子。1 9 7 7 年夏天，物理学家j f o r d 和g c a s a t i 在意大利 组织了关于混沌研究的第一次国际性科学会议，进一步营造了混沌研究的氛围。 1 9 7 8 年，m j f e i g e n b a u m 用手摇计算机彻夜工作，发现一类周期倍化通向混沌的 道路中的普适常数。1 9 7 9 年，p j h o l m e s 作了磁场中曲片受简谐激励时的振动实 2 重庆大学硕士学位论文i 绪论 验，发现激励频率和振幅超过某个特定值之后，就出现混沌振动。1 9 8 0 年，意大 利的v f r a n c e s c h i n i 用计算机研究流体从平流过渡到湍流时，发现周期倍化现象， 验证了f e i g e n b a u m 常数。1 9 8 1 年，美国麻省理工学院的p s l i n s a y 第1 次用实验 证明了f e i g e n b a u m 常数。1 9 8 9 年，召开了美苏混沌讨论会。二十世纪九十年代以 后，国际上混沌同步及混沌控制取得了突破性进展，由此激发起来的理论与实验 应用研究的蓬勃开展，使棍沌的应用出现了契机，为人们展现了十分诱人的应用 与发展前景。1 9 9 0 年，在德国专门召开了分岔与混沌研讨会，混沌同步原理及混 沌控制方法，在1 9 9 0 年先后提出，前者是由美国海军实验室的学者p e c o r a 和c a r r o l l 提出的，他们在电子线路上首先实现了混沌同步，后者是由美国马里兰大学的物 理学家o t t 、g r e b o 垂和y o r k e 提出，也称为o g y 方法【9 1 。1 9 9 1 年4 月，在日本由 联合大学与东京大学共同召开“混沌对科学与社会的影响”的国际会议。1 9 9 1 年 1 0 月，在美国召开了首届混沌实验讨论会。这些会议的召开促进了混沌学研究世 界性热潮的到来。同年，该校的d i t t 等人利用该法首次在一个物理系统上，即磁 弹性体上实现了对周期一的稳定控制【10 1 。随后，国际上混沌控制方法及其实验的 研究迅速发展，混沌同步也获得进一步拓广，大大推进了应用研究，诸如在电子 学、保密通讯、密码学、激光、化学、生物、脑科学及神经网络系统等众多领域 中，其都有很大的应用潜力。近l o 年来，混沌科学更是与其它科学互相渗透，无 论是生物学、生理学、心理学、数学、物理学、电子学、信息科学，还是天文学、 气象学、经济学，甚至在音乐、艺术等领域，混沌都得到了广泛的应用。如今， 混沌的发现被认为是2 0 世纪物理学的三大成就之一，可以说“相对论消除了关于 绝对空间与时间的幻想；量子力学则消除了关于可控测量过程的牛顿式的梦；而 混沌则消除了拉普拉斯关于决定式可预测性的幻想”。正如混沌科学的倡导者之 一，美国海军部官员m s h l e s i n g e r 所说的那样“2 0 世纪将永远铭记的只有三件事， 那就是相对论、量子力学和混沌”，它将在整个科学中所起作用相当于微积分学 在1 8 世纪对数理科学的影响。混沌学创立，将在确定论和概率论这两大科学体系 之间架起桥梁，它将揭开物理学、数学乃至整个现代科学发展的新篇章【圳。 近半个世纪以来，混沌现象的应用研究已越来越受到人们的重视，人们对混 沌运动的规律及其在自然科学和社会科学中的表现有了比以前更广泛和更深刻的 认识。特别是如何应用混沌理论的研究成果为人类服务已经成了2 1 世纪非线性科 学发展的新课题，也是目前数学家和工程技术人员所面临的一个重要挑战。一方 面，混沌的应用将会直接促进人们对混沌本质的更深刻的认识；另一方面，混沌 应用中提出的许多新问题也将进一步促进混沌研究本身深入的发展，这为混沌理 论及其应用的研究提供了巨大的推动力。混沌( c h a o s ) 是非线性动力学系统所特有 的一种运动形式，它广泛的存在于自然界，诸如物理、化学、生物学、地质学， 重庆大学硕士学位论文1 绪论 以及技术科学、社会科学等各个科学领域。一般而言，基于其动力学性态对于初 始条件的高度敏感性，混沌现象隶属于确定性系统而难以预测：基于具有稠密轨 道的拓扑特性，隐含于复杂系统但又不可分解；以及呈现多种“混乱无序却又颇 有规则”的图像，如具有稠密的周期点。混沌系统的最大特点，在于系统的演化 对初始条件极端敏感，因此从长期意义上讲，系统的未来行为是不可预测的。然 而，尽管科学界对于混沌已经认真地研究了近半个世纪，至今尚无一个公认的非 常严格的标准数学定义。这是因为混沌系统的确非常复杂，从不同的角度理解会 有不同的内涵。数学上常用的定义包括：离散动力系统的l i y o r k e 意义下的混沌 7 1 ，高维空间中有相应的m a r o t t o 定理【引、d e v a n e y 意义下的混沌0 1 和连续动力系 统的s m a l e 马蹄意义下的混沌【1 1 1 。物理和工程上常用的混沌判据是其有界性并存 在正的l y a p u n o v 指数。一般认为，混沌具有一些主要特征：确定性、有界性、对 初值的极端敏感性、长期不可预测性、正的最大l y a p u n o v 指数、遍历性等【5 9 l o i l 】。 研究混沌的目的主要是揭示混沌的本质，刻画它的基本特性【l o ，1 2 1 4 】，了解它 的动力性态，并力求对它加以控制和利用使之为人类服务。混沌的潜在应用包括： 大脑神经活动和心脏脉搏测量分析、图像数据加密、保密通信、电力电网动态分 析和保护、工程和民用电子仪器噪声消减、电子震荡发生器设计、航天和航空发 动机动态分析和保护、流体混合、信息存储和高速检索、决策预测、系统和模式 识别、机械震动故障诊断、计算机图形处理、以及医学和生物、信号处理和通信、 控制系统和优化等越来越多的领域和方向【5 ，6 j 。 随着多媒体技术和国际互联网的飞速发展，以及存储设备容量的增长，往日 因为存储量巨大而让人望而却步的数字图像已经成为人们获取信息的主要手段， 并且由于这与人感知外部世界的基本手段相吻合，数字图像的重要性已经越来越 被国家、政府、工业界、科学家以及个人所注意和重视。今天，网络上传输的数 字图像是纷繁芜杂的，它们有可能涉及军事机密、商业秘密或者个人隐私，如何 保护图像信息的安全已经成为各界广为关注的问题。图像信息安全是集数学、密 码学、信息论、计算机复杂理论和计算机网络以及其它计算机应用技术于一体的 多学科交叉的研究课题。图像信息安全问题有着极为广泛的含义，考虑其安全算 法时，必须考虑其特殊性：数据的冗余性，对大量数据加密的可实现性，能否经 受住常见的数据有损压缩、格式变换等操作。因此，数字图像作为多媒体信息的 重要组成部份，对数字图像进行可靠的安全处理已成为当前研究的重要方向之一。 混沌理论是随着现代科学技术的迅猛发展，尤其是在计算机技术的出现和普 通应用的基础上发展起来的新兴交叉学科【“】，有着广泛的应用前景。在现代的物 质世界中，混沌现象无处不在，大至宇宙，小至基本粒子，无不受混沌理论的支 配。如气候变化会出现混沌，数学、物理学、电子学、信息科学、化学、生物学、 4 重庆大学硕士学位论文1 绪论 哲学、经济学、社会学、医学、音乐等也存在混沌现象。因此，科学家认为，在 现代的科学中普遍存混沌现象是非线性系统的一种内在类似随机过程的表现，混 沌系统产生的混沌信号具有对初始条件的敏感依赖性、类噪声、非周期性、确定 性的、类随机的过程，这种过程即非周期又不收敛，其状态完全可以重现，其结 构复杂、难以分析，因此，利用它可以构造出非常好的图像信息加密系统。另外， 采用混沌动力学模型构造的加密系统可以在图像信息受到某些信号处理后，仍然 可以较好地解密出信剧3 1 。有鉴于此，研究混沌图像加密算法具有很重要的意义。 目前有一种广泛应用于加密的混沌模型：l 0 9 i s t i c 映射。它有着形式简单、产 生混沌时间序列短等优点，但其产生的序列在整数化后随机性会受到影响，而且 密钥空间不够大。为此，本文引入基于混沌映射产生的混沌序列作为图像矩阵队 列变换的参照点的图像置乱算法，克服了其它方法的一些不足：为克服密钥空间 不够大的问题，采用l o g i s t i e 映射的两种表达式来求出两组混沌序列，用排序的方 法来对该序列进行整数化，这样的序列保持了混沌序列良好的伪随机性，用它作 为图像矩阵置乱的参照点进行图像置乱具有深入研究的价值。 1 2 国内外研究现状 近年来，相继召开了多次信息隐藏的国际学术会议，图像信息隐藏及在图像 中隐藏信息的问题成为其中重要议题之一，数字图像的安全已经成为当今计算机 应用领域的一个重要研究课题。 随着计算机技术与数字图像处理技术的发展，对信息安全问题的研究已有一 些成果，数字图像置乱变换是近年来图像加密的常用方法，对于数字化的图像， 置乱过程不仅可以在数字图像的空间域上进行，还可以在其频率域上进行。丁玮 等人把数字图像置乱方法分为以下3 类：基于a r n o l d 变换 1 5 , 1 6 1 的系列置乱方法。 例如：基于a r n o l d 变换的方法，基于改进a r n o l d 变换的方法，基于面包师变换【3 】 的数字图像置乱方法和基于f i b o n a e c i q 矩阵的置乱方法等。这些方法采用密码学 中的一种典型的古典恺撒密码方法将数字图像按照相位空间和颜色空间置乱，对 置乱图像的恢复依赖于a r n o l d 变换的周期性。用分形图形学中的方法来对空间 曲线进行填充，先后采用了h 曲线，e 曲线，幻方变换【1 7 1 ，生命游戏【2 6 1 和基于格 雷码的方法等。这些方法通过对图像上的像素点不重复，不遗漏的进行遍历从而 达到对图像上的像素重新进行排序的目的，通过改变这些排序后的像素来对图像 进行置乱。利用其它数学知识和奇特现象进行数字图像置乱的方法。这些方法 包括按位运算，按异或运算以及按照三角函数变换的方法进行数字图像的等。这 些方法的安全性由算法本身和算法的密钥来确定，针对数字图像的置乱和去乱一 般采用同一算法来进行，因此具有一定的局限性。 重庆大学硕士学位论文1 绪论 英国数学家m a t t h e w s 在8 0 年代末首次明确提出了用混沌系统来产生序列密 码的思想【4 1 1 。近年来随着非线性和混沌理论的成熟，研究工作者们纷纷探索混沌 在多媒体数据中的可能应用。陈果等提出一种基于二维s t a n d a r d 混沌映射的数字 图像加密算法【3 2 1 ，韦鹏程、张伟等提出了一种多级混沌图像加密算法【5 ”，孙鑫、 易开祥、孙优贤等提出了一种以实数值混沌序列为基础、利用图像置乱变换技术【3 7 】 等等，这些文献基本上是把混沌映射与其它各种置乱方法相结合来对图像进行加 密，各有各的优点，但偏重点不同。对于任何一种方法，主要考虑两个问题：尽 可能少的计算量；尽可能大的置乱度。两者有时往往是相矛盾的，目前还没有 一种方法是十全十美的。因此在实际应用中需要我们去寻找一种计算量更小，置 乱度更大的方法来对图像进行置乱或加密。 1 3 本文研究的目的和研究内容 1 3 1 本文研究的目的 当前，信息隐藏与伪装技术是一个非常重要而又非常活跃的研究领域。作为 一种常见的图像加密方法的置乱技术在信息隐藏与伪装技术中的应用越来越广 泛。置乱技术可以作为隐藏图像信息的预处理，对图像置乱后再隐藏可以减少对 隐藏信息攻击的可能性。已有很多文献提出了图像置乱的方法，如文献【l ”提出 的a r n o l d 变换及其扩展变换、f i b o n a c c i 变换，它们均存在取模运算，在进行图像 置乱时较费时，且逆变换不易求得。为了克服变换中存在取模运算费时以及求逆 变换困难的缺点，在广泛研究其它方法的基础上提出了一种新的基于混沌映射和 队列变换的置乱算法，该算法具有时间快、求逆方便、置乱效果均匀、抗攻击能 力强等特点，因此此方法应该是比较有应用前景的好的图像置乱方法。 1 3 2 本文研究的主要内容 混沌现象是在非线性动力系统中出现的确定性的、类似随机的过程，这种过 程既非周期又不收敛，并且对初始值有极其敏感的依赖性。从时域上看，混沌映 射得到的序列类似于随机序列，相关性较弱，具有很好的类白噪声特性，因此可 以用来产生伪随机信号或伪随机码，原理上只要增加迭代次数，伪随机码的周期 可以很长，产生长码十分简单。通过混沌系统对初始值和结构参数的敏感依赖性， 可以提供数量众多、非相关、类随机而又确定可再生的信号。由于上述特点，混 沌系统已广泛应用于各类加密系统中。混沌加密技术已成为一种新兴的加密技术。 本文在对已有的数字图像加密方法充分吸收基础之上，对混沌数字图像加密方法 做了进一步地研究，本文内容安排如下： 第1 章首先引出了所要研究的课题，阐述了研究数字图像加密的目的以及 重要意义，分析了有关数字图像加密技术的研究现状和存在问题，最后给出本文 6 重庆大学硕士学位论文1 绪论 的主要内容。 第2 章主要阐述了数字图像加密的初步知识，介绍了数字图像加密方法的 分类、特点以及各自的优缺点。 主要阐述了混沌系统含义以及常用模型，重点刻划了混沌系统的基本特 征、描述的特征量。简要描述了混沌序列的产生和性质。 详细介绍了一维l o 舀s t i e 映射的混沌特性和统计特性，在此基础上提出了 基于混沌映射与排序变换的图像置乱算法，对新算法的置乱性能进行仿真实验， 并深入分析了新算法的各项加密性能。 最后论文对研究工作进行了全面的总结，并对今后的研究方向进行了展望。 7 重庆大学硕士学位论文2 数字图像加密简介 2 数字图像加密简介 2 1 数字图像加密概述 图像作为人类认识和表达世界的基本方法，应用极为广泛，从古老的壁画、 象形文字到今天的数字化视频，图像一直伴随着人类历史的发展。人们也期望从 图像中得到直观的信息，“眼见为实”是再自然不过的事情。但是，在信息膨胀和 普及的今天，事情并不是这么简单。 置乱变换是数字图像加密中研究比较广泛的一种方法。置乱技术利用数字图 像具有数字阵列的特点，搅乱图像中像素的位置或颜色使之变成一幅杂乱无章的 图像，达到无法辨认出原图像的目的。目前已有的数字图像置乱方法有：基于 a r n o l d 变换、幻方变换、c r a y 码与广义g r a y 码变换的置乱方法【1 4 ，l5 】；基于分形 几何i f s 模型的置乱方法【1 6 】；基于h i l b c r t 曲线、f a s s 曲线以及基于t a n g r a m 算 法、c o n w a y 游戏的置乱方法【2 1 ，2 2 1 等等，其中以a r n o l d 变换的研究较多。面包师 变换【1 6 】是动力系统中一个非常经典的变换，它与b e r n o u l l i 推移是同胚的。虽然这 个变换结构简单，但它却能产生非常奇妙的混沌现象，因而倍受数学家、物理学 家和其它从事非线性研究的科研工作者的广泛关注。 2 - 2 数字图像加密方法简介 静止图像可以看作是平面区域上的二元连续函数： z = 厂y ) ，( 0 工 t ；0 y 工，)( 2 1 ) 对区域中任意的点( x ，y ) ，则f ( x ，y ) 代表图像在这一点的灰度值或r g b 颜色 分量值，与图像在这一点的亮度相对应并且图像的亮度值是有限的，因而函数 z = f ( x ，y ) 也是有界的。在图像数字化之后，z = f ( x ，y ) 则相应于一个矩阵，矩阵 的元素所在的行与列就是图像显示在计算机屏幕上诸像素点的坐标，元素的数值 就是该像素的灰度( 通常有2 5 6 等级，用整数0 至2 5 5 表示) 。矩阵的初等变换【6 】 可以将一幅图像变换成另一种图像。图像加密主要采用以下几种方法： 2 2 1 基干矩阵变换像素置换的图像加密技术 古老的藏宝图可以被随意添加一些无用的信息和标注来增加破译的难度，而 今天我们面对的是数字化的图像，能做的应该更多。图像作为直观的信息表达方 式，具有很大的迷惑性。如果我们把数字化图像做一些“扰乱”，得到一幅完全杂 乱无章、面目全非的图像，那么即使非法截获者注意到它，如果不知道如何恢复， 对它也无能为力，这就在一定程度上增加了图像的安全性。置乱技术就是这样一 项研究课题，它从一维的单表密码扩展而来，应用n - - 维图像平面、甚至三维图 重庆大学硕士学位论文 2 数字图像加密简介 像色彩空间中，扰乱图像的组成部分，破坏图像的自相关性，使得人眼无法从中 提取有价值的信息，即使计算机用“穷举法”计算各种组合，也要耗费大量的时 间，在一定程度上保护了图像信息。 数字图像的置乱技术主要用于数字图像的预处理和后处理，目前，人们考虑 较多的数字图像的置乱技术大多基于a r n o l d 变换、幻方、正交拉丁方、h i l b e r t 曲线、c o n w a y 游戏、i f s 模型、g r a y 码变换、广义g r a y 变换等方、法【”】。下面介 绍几种常用的置乱变换，并给出它们的相应推广。 基于a r n o l d 变换的图像置乱算法 a r n o l d 变换 1 4 j 5 是a r n o l d 在遍历理论研究中提出的一种变换，俗称猫脸变换， 原意为c a tm a p p i n g 。设想在平面单位正方形内绘制一个猫脸图像，通过如下变换 ( 2 2 ) 这个猫脸图像将由清晰变为模糊，这就是a r n o l d 变捌1 4 】。注意到式( 2 2 ) 定义 的a r n o l d 变换实际上是一种点的位置移动，并且这种变换是一一对应的。此外， 这个变换可以迭代地做下去。类似的变换还有面包师变换。 对于数字图像来说，可以将其看成是一个函数在离散网格点处的采样值，这 样我们就得到了一个表示图像的矩阵，矩阵中元素的值是对应点处的灰度值或 r g b 颜色分量值。对于正方形数字图像，我们有离散化的a r n o l d 变换 l 。，l ：l ：1 | | 。l r o o d n ，x ，y ( o ，1 ，n 一1 )( 2 3 ) l yjl 1j l ) ，j 其中n 为图像的高度或宽度。 对于数字化图像而言，我们所说的位置移动实际上是对应点的灰度值或者 r g b 颜色值的移动，即将原来点 ，y ) 处像素对应的灰度值或r g b 颜色值移动至 变换后的点( 石，y ) 处。如果我们对一个数字图像迭代地使用离散化的a r n o l d 变换， 即将左端输出的( 石，) ，) 作为下一次a r n o l d 变换的输入，可以重复这个过程一直作 下去当迭代到某一步时，如果出现的图像符合我们对图像的“杂乱无章”标淮的 要求，这即是一幅置乱了的图像。 a r n o l d 变换可以看作是裁剪和拼接的过程，通过这一过程将图像矩阵i 中的 点重新排列。由于图像是有限点集，这种反复变换的结果是，在开始阶段i 中像 素点的位置变化会出现相当程度的混乱，但由于动力系统固有的特性，在迭代进 行到一定步数时会恢复到原来的位置，即变换具有庞加莱恢复性，这样只要知道 加密算法，按照密文空间的任意一个状态进行迭代，都会在有限步内恢复出明文 ( 即要传输的原图像) 。这种攻击对于现代的计算机来说，它所需要的计算时间是 9 重庆大学硕士学位论文 2 数字图像加密简介 很短的，因而保密性不高。 基于幻方的图像置乱变换2 0 】 以自然数1 ，2 ，3 ，n 2 为元素的，l 阶矩阵4 a 1 1a 1 2 4 h a 2 1 口2 2 口2 h a 1a 2 一a n ” 满足 n 勺= = o = l ，2 ，3 ，h ) u = 1 ，2 ，3 ，月) ( 2 4 ) j - i 1 = 1 f + j ；q “ 其中c = 1 1 2 ( 甩2 + 1 ) 2 则称彳为标准幻方。 假定数字图像相应于栉阶数字矩阵占，对取定的，l 阶幻方彳，将b 与4 按行 列做一一对应。我们把4 中的元素1 移至为2 的位置，将元素2 移至3 的位置， 一般来说，对任何m = 1 , 2 ，3 ，栉2 1 ，它从其在a 中位置移至m + l 在4 中位置， 若r = ，1 2 则将m 移至l 在4 中所在位置，经过这样的置换之后，矩阵a 转换为矩 阵4 ，记4 = e a ，对4 来说，可以重复上述置换得矩阵a 2 = 础，如此继续下 去，经过，1 2 步，以：= a ，一般来说4 ，4 ，以：，并不满足公式( 2 4 ) ，它们不是 幻方。 对数字图像矩阵b ，注意曰与a 元素之间的对应关系，随a 转换为4 ；而把 曰中对应像素信息，如r g b 、灰度做相应的移置，产生数字图像矩阵旦，记为 e b = 8 ，一般地，e ”b = b 。 例如，我们可以考虑一个由4 x 4 像素组成的图像曰，它可以被看作一个4 阶 矩阵 在如下4 阶幻方a 得到新4 阶方阵且为l 乏 h 岛：6 3 。 6 2 ，岛，岛： 6 3 ，如，6 2 ： 钆6 4 26 i 。 1 62 5l l 97 41 4 31 3 l o8 61 2 1 5l 的置乱作用下 经过这种对图像像素的置换，打乱了像素在图像中的排列位置，从而达到加 密的目的。这种变换实质上是矩阵的初等变换，并且由于幻方矩阵是一有限维矩 阵，经过捍2 次置换，又会回到原来的位置，因而也可以用上节所述的方法加以破 译，因而其加密效果也是不好的。但若能把初等矩阵变换转化为某种非线性变换 1 0 跏助助蛳加劬如跏咖坳坳助 既巩岛以 重庆大学硕士学位论文 2 数字图像加密简介 则有可能增强置乱效果，再结合其它现代密码学一些成熟的加密算法，如d e s ， r s a 等则可以增加算法的保密性【2 ”。 基于生命游戏的数字图像置乱 生命游划2 6 】是一类特殊的图像矩阵变换。本世纪7 0 年代，人们曾疯迷于一 种被称作“生命游戏”的小游戏，这种游戏相当简单。假设有一个象棋盘一样的 方格网，每个方格中放置一个生命细胞，生命细胞只有两种状态：“生”或“死”。 英国数学家j o h n c o n w a y 和他的学生在1 9 7 0 年前后，经过大量实验，确定了生命 游戏并给出了恰当的规则。由j o h nc o n w a y 确定的游戏规则如下： 如果一个细胞周围有3 个细胞为生( 一个细胞周围共有8 个细胞) ，则该细胞 为生，即该细胞若原先为死，则转为生，若原先为生，则保持不变；如果一个细 胞周围有2 个细胞为生，则该细胞的生死状态保持不变；在其它情况下，该细胞 为死，即该细胞若原先为生，则转为死，若原先为死，则保持不变。 依此规则进行迭代变化，使细胞生生死死，会得到一些有趣的结果。该游戏 之所以被称为生命游戏，是因为其简单的游戏规则反映了自然界中这样的生存规 律：如果一个生命，其周围的同类生命太少的话，会因为得不到帮助而死亡，如 果太多，则会因为得不到足够的生命资源而死亡。 假设平面网格上，每个网格代表一个生命细胞，给网格涂黑色代表此细胞为 活，涂白色代表此细胞为死，如果平面网格无限大( 事实上，可以把有限网格上 下、左右边界相接) ，那么每个网格有8 个邻居。这8 个细胞的状态将对它们所包 围的细胞状态产生影响。对给定的初始状态，应用如下规则： 1 ) 如果被包围的网格恰好有3 个相邻网格为黑色，则无论它原始状态是什 么，都要修改为黑色。 2 ) 如果这个网格恰好有2 个相邻网格为黑色，则保持原始状态不变。 3 ) 否则无论此网格原始状态如何，都要修改为白色。 生命游戏可以如下理解：如果一个成活的细胞，它周围的成活细胞过少，它 得不到足够的支持和帮助，它将死亡；如果成活细胞周围的成活细胞过多，由于 资源不足而难以维持生命，它也将死亡。反之，如果周围成活细胞数目恰当，那 么本来不活的状态也可以被激活。 基于行列式的计算方法的置乱算法：b d c m s 行列式计算方法是：雄阶行列式的计算公式如下： 。 口h 。 口2 月 4 朋 2 ( 一1 ) 7 肚脚a b h a 2 ( 2 5 ) h hk 重庆大学硕士学位论文 2 数字图像加密简介 即：珂阶行列式的值等于所有取自不同行不同列的n 个元素的乘积： q 。口：6 a 帆代数和，这里 ，五 是l ，2 h 的一个排列，当 ，止 是偶排 列时取正号，当 ，五上是奇排列时取负号。 这种将来自不同行不同列的元素组合在一起的思想，完全可以用于图像的置 乱。因为，一幅数字图像可用一矩阵a = 【a ( i ，川。表示，其中口( f ，) 表示图像在 第i 行，列像素处的灰度值( 或r g b 分量值) 。 设原始图像a = a ( i ，_ ，) 】。，用置乱方法得到的图像设为口，则基于行列式计 算方法的置乱算法构造思想可表述如下： 第一步：按某种规则r ，在彳中选取不同行不同列的个灰度值，再按另一 规则，放入曰的第1 行( 或第l 列) ； 第二步：按规则r ，在彳中剩余的元素中，选取不同行不同列的个灰度值， 再按另一规则r 放入口的第2 行( 或第2 列) ； 第三步：按规则r ，在彳中剩余的元素中，选取不同行不同列的个灰度值， 再按另一规则：放入曰的第3 行( 或第3 列) ； 以此类推，进行步，则可得到置乱的图像。选取规则r 不同或放入规则，不 同时，可得到不同的置乱算法。将该类算法取名为：b d c m s ( b a s e do nd e t e r m i n a n t c o m p u t a t i o nm e t h o d ss c r a m b l i n g ) 算法。如果每步的选取规则r 和放入规则r 均不 同，则可以想象，这样的置乱算法是非常多的。 基于f a s s 曲线的图