（计算机应用技术专业论文）几种混沌块加密算法的研究.pdf

大连理丁大学硕十学位论文 摘要 在资讯科技非常发达的今天，信息成为了我们每个人最关键的东西，而我们在关 注信息本身价值的同时，同时更关注信息的安全性，一直以来，许多学者都在不停的 研究信息加密技术，无论使用什么方法，速度和安全性都是非常重要的。 混沌动力系统对初值的高度敏感使得其天生的具有良好的加密特性，这些良好的 特性都是得混沌动力系统在加密领域有着潜在的应用前景。然而，混沌动力系统是作 用在浮点数域上的，在数字环境下能实现的是数字混沌系统，我们没有办法在我们的 实际研究中直接使用不加改动的混沌动力系统。本文主要研究混沌块加密算法，尤其 是在算法设计上可能会出现的缺陷，以及设计了一种快速的非对称的快速块加密算法 和一种基于置换的对称块加密算法，通过编程实现以及系统仿真，验证了算法的优秀 安全性能，具体为： ( 1 ) 对一种典型的块加密算法进行密码分析，并发现一种存在于很多块加密算 法中的算法缺陷，该缺陷的存在使得对应的密码系统无法承受基于选择密文的攻击， 这会大大降低密码系统的安全性，本文提出了一种缺陷的修复方法，不仅能保留原算 法的特性和性能，而且能较大限度的增加安全性。 ( 2 ) 基于c h e b y s h e v 多项式和l o g i s t i c s 映射设计的混沌块加密公钥算法。利用 c h e b y s h e v 多项式具有的半群性特性，将其从连续的实数域拓展到有限域里头，并采用 了将公钥算法和对称加密算法结合的方法，实现了高速的，安全的非对称的混沌块加 密算法。 ( 3 ) 基于多次置换的混沌块加密算法。本算法根据密钥动态构建了两个s 盒， 一个s 盒对加密过程中的数据进行置换，一个s 盒对加密后的密文进行位置上的置 换，消除明文块和密文块的位置顺序，增加了密码分析的难度，从而提高了密码系统 的安全性。 关键词：混沌：块加密；安全性分析；公钥加密 大连理t 大学硕士学位论文 r e s e a r c ho ns o m ebl o c kc h a o t i c c r y p t o g r a p h i ca l g o r i t h m s a b s t r a c t w i t hm ef a s td e v e l o p m e n to fi n f o r m a t i o n f e c h n o l o g y i n f o r m a t i o nb e c o m e sm o s t i m p o r t a n tt h i n go fo u rl i v e s w ew o u l df o c u st h ev a l u eo ft h ei n f o r m a t i o n m e a n w h i l ew ec a r e s e c u r i t yo fo u ri m p o r t a n ti n f o r m a t i o ni no r d e rt oa v o i db e i n gs t o l e nb yt h eh a c k e r s m a n y s c h o l a r sa r ed o i n gt h e i rr e s e a r c ho nt h ec r y p t o g r a p h y ，n om a t t e rw h i c hm e t h o d st h e yu s e ，t h e s p e e da n dt h es e c u r i t ya r et h ef i r s tb e i n gc o n s i d e r e d i n s t a b i l i t yt ot h ei n i t i a lv a l u em a k et h ed y n a m i cc h a o t i cs y s t e mc a nb eu s e di n c r y p t o g r a p h y n l eg o o dp r o p e r t i e so ft h ed y n a m i cc h a o t i cs y s t e mh a v ep o t e n t i a lo nt h ef i e l d o fc r y p t o g r a p h ya p p l i c a t i o n b u tt h er e a lc h a o t i cs y s t e mi sb a s e do nf l o a t i n g p o i n td o m a i n , w eo n l yc a ni m p l e m e n tt h ed i g i t a lc h a o t i cs y s t e mw i t ht h e h e l po fc o m p u t e rt e c h n o l o g y c h a o t i cs y s t e mc a n n o tb ed i r e c t l yu s e dl i k et h et h e o r i e st h a tw ec a l lo b t a i na l le x c e l l e n t p r o p e r t i e sl i k ei n f i n i t yc y c l ee t c t h i sp a p e rm a i n l yc o n c e r n st h es e c u r i t yo fc h a o t i cb l o c k c r y p t o g r a p h i ca l g o r i t h m sa n dp r o p o s e dt w on o v e lc r y p t o s y s t e m t h e nt h es i m u l a t i o na n d a n a l y s i sh a sv e r i f i e dt h ea l g o r i t h m se x c e l l e n ts e c u r i t yp e r f o r m a n c e s p e c i f i c a l l ya sf o l l o w s ： ( 1 ) u s ec r y p t a n a l y s i sm e t h o dt oa t t a c kan o v e lt y p i c a lc h a o t i cb l o c ke n c r y p t i o n a l g o r i t h m t h e nif o u n daf l a wt h a tt h i sa l g o r i t h mc a n n o tr e s i s tt h ec h o s e n c i p h e r t e x ta t t a c k i t w i l lg r e a t l yr e d u c et h es e c u r i t yo ft h ea l g o r i t h m a n dt h i sf l a we x i s t s i nl o t so fb l o c k e n c r y p t i o na l g o r i t h m ip r o p o s eam e t h o dt or e m e d yt h ef l a wt h a tn o to n l yr e t a i nt h ef e a t u r e s o fo r i g i n a la l g o r i t h m ，b u ta l s oi n c r e a s et h es e c u r i t yo f t h ea l g o r i t h m ( 2 ) an e wn o n - s y m m e t r i cc h a o t i cb l o c ke n c r y p t i o na l g o r i t h m 础sa l g o r i t h mm i x e sw i t h e h e b y s h e vp o l y n o m i a l sa n dl o g i s t i cm a p b a s e do nt h es e m i - g r o u pp r o p e r t yo ft h ec h e b y s h e v p o l y n o m i a l s ，ip r o p o s eap u b l i ck e ya l g o r i t h m ，a n du s et r a d i t i o n a lc h a o t i cb l o c ke n c r y p t i o n m e t h o dt oe n h a n c et h ee n c r y p t i o ns p e e d i no r d e rt oa v o i dl o s i n ga c c u r a c y ie x t e n dt h e c h e b y s h e vp o l y n o m i a l sf r o mf l o a t i n g p o i n tt of i n i t ef i e l d ( 3 ) an o v e lc h a o t i cb l o c ke n c r y p t i o nu s i n gd u a ls - b o x t h i sa l g o r i t h mc o n s t r u c t st w os b o xd y n a m i c a l o n eu s e sf o rs u b s t i t u t i n gt h ep l a i n t e x t ，a n dt h eo t h e ru s e sf o rc o n f u s i n gt h e s e q u e n c eo ft h ep l a i n t e x t t h et w os - b o xe n h a n c et h es e c u r i t yo ft h ec h a o t i cb l o c ke n c r y p t i o n k e yw o r d s ：c h a o s ；b l o c ke n c w p t i q n ；s e c u r i t ya n a l y s i s ；p u b l i ck e y i i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方 外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已 申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的 贡献均已在论文中做了明确的说明并表示了谢意。 学位论文题目： 缝i 壁主空型幽这丝显弦 作者签名： 4 溶起型多l 日期：每年2 月上 日 基于混沌理论的动态序列加密算法研究 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题 作者签名： 导师签名： 大连理工大学硕士学位论文 引言 混沌，是指看来遵从确定规律的事物也会呈现超乎想象的繁复多样，只要有些微 小的条件差异，就会导致令人瞪目结舌的不同结果。混沌研究的进展，是非线性科学 最重要的成就之一。它正在消除对于同一的自然界的决定论和概率论两大对立描述体 系之间的鸿沟，使复杂系统的理论开始建立在“有限性 这个更符合客观实际的基础 之上【1 - 5 1 。 混沌理论的诞生来源于古往今来许多学者对微分方程组的研究。微分方程组的历 史悠久，可以追溯到大科学家牛顿，牛顿使用微分方程组来描述物体运动。到1 9 世纪 末，许多学者认识到很多非线性微分方程根本没有显式解，即便是牛顿万有引力的三 体运动也有非常复杂的性态，学者庞加莱( j u l e sh e n r ip o i n c a r d ) 将工作重心从寻找显 式解转移到讨论解的几何性质上，他通过一些具体的例子阐述了自己的思想，这些思 想成为了当今混沌动力系统学科的开端，他意识到一个确定性系统可以出现随机混沌 状态。在微分方程理论的研究过程中，2 0 世纪上半叶涌现出了大量关于非线性振子的 研究工作，所谓非线性振子是模拟一组弹力的方程组，其中恢复力非线性地依赖于离 开平衡点的位置，李雅普诺夫( l y a p u n o v ) 等人研究了平衡点的稳定性，范德波尔 ( v a nd e rp 0 1 ) 发现了某些自激系统存在周期轨道，此外c a r t w r i g h t ，l i t t l e w o o d ， l e v i n s o n 等人研究得到微分方程的解不外乎平衡态，周期运动和拟周期解三种。2 0 世 纪6 0 年代，斯梅尔( s t e p h e ns m a l e ) 利用庞加莱首创的思想来审视微分方程，提出了 “斯梅尔马蹄”将c a r t w r i g h t ，l i t t l e w o o d ，l e v i n s o n 等人的研究结果统一到一个具有一 般性的理论框架里，而这个就是后来所谓的混沌现象。1 9 7 5 年，中国学者李天岩和美 国数学家j y o r k 首次提出了“混沌 这一概念，用来刻画比不动点，周期运动，拟周 期运动更加复杂的非周期性态。使用计算机来寻求数值解大大影响了非线性微分方程 的研究，1 9 6 3 年e l o r e n z 用一台计算机研究模拟大气湍流运动的非线性方程，发现初 始条件的细微变化可以在相对短的时间里导致非常不同的结果，这一性质被称为对初 始条件的敏感性，就是后来著名的“蝴蝶效应 。混沌理论是继相对论问世以来，2 0 世纪物理学的第三次大革命，其覆盖面广及自然科学与社会科学的几乎各个领域【2 】。 s h a n n o n 的信息论对密码学的发展具有深远的意义，他提出一个理想的密码系统， 密文的所有的统计特征都是独立于所用的密钥，舍弃对理想系统的追求，他引进了混 淆和扩散这两个术语来刻画任何密码系统的两个基本构件，目的在于挫败密码分析。 扩散就是指明文的统计特征消散在密文中，可以让每个明文数字尽可能的影响多个密 文数字获得，等价说每个密文数字被许多明文数字影响：另一方面，混淆就是尽可能 几种混沌块加密算法的研究 的使密文和加密密钥间的统计关系变得更加复杂，以阻止攻击者发现密钥，但是简单 的线性代换是增加不了混淆的。考虑一下“蝴蝶效应 的本质，对初始条件的敏感 性，是一种很好的增强密码系统混淆性的途径，而且同时还可以实现密码系统的扩散 性。最近一段时间，使用混沌系统进行分组和序列密码设计的想法陆续有一些新的研 究报道，这些研究显示混沌可以很自然地在传统密码学的框架下得到运用，就象传统 密码学中一些其他的常用基本算法一样p j 。 一个安全的密码系统实质上就是通过使用确定性的密码系统能产生的伪随机的混 乱状态，从算法的角度看，任何好的密码系统也可以看成是一个混沌或者拟混沌系 统。安全的密码系统对明文加密获得的密文混乱状态非常类似于由复杂动力系统产生 的混沌现象。实际上，一般来说混沌系统是在浮点数域中展现其各种各样的特性，当 混沌系统在计算机上以有限精度实现时，经常使用模运算来描述混沌方程的离散形 式，然而模运算也是传统密码学中最常用的操作。 混沌密码学是非线性计算机科学中的重要组成部分，是计算机学科和理论物理学 科中的交叉领域，混沌理论在密码学领域中得以应用，为密码学的研究和发展开辟了 一条新的途径【5 d6 1 。本文主要研究的是数字化混沌密码以及其应用，重点在密码系统分 析和密码系统设计，提出了现有的混沌密码系统存在的一些缺陷，以及如何修正和避 免这些问题，然后设计了一些密码系统的设计方案，将序列密码和分组密码完美结合 起来，并通过仿真分析验证了算法的优秀安全性能。 本文的组织如下： 第一章简要介绍了混沌理论、符号动力学和混沌密码学的基础知识。 第二章介绍了本文所用到的数字化混沌加密的基本原理和密码分析原理。 第三章对一个现有的密码系统进行破解和分析，并提出改进方案。 第四章介绍了一种基于c h e b y s h e v 多项式的非对称密码系统。 第五章介绍了一种基于混沌的置换加密系统。 最后给出了全文的结论。 大连理工大学硕士学位论文 1 绪论 1 1 混沌理论概述 1 1 1 混沌的定义 到如今，学术界对“混沌仍然缺乏统一和普遍接受的一般定义，这主要源于混 沌现象的复杂性，人们目前对混沌本身种种特性还没有完全掌握。论文在此选择两个 常见的“混沌”的定义作为说明。 第一种定义t 若一个非线性系统的行为对初始条件的微小变化具有高度敏感的依 赖性，则称为混沌运动。该定义描述了混沌运动局部的极度不稳定性，常常被形容为 “蝴蝶效应 。这种高度的不稳定性是指在相空间中初始值极其接近的两条轨道，随 着时间的推进，轨道间的距离以指数形式迅速分离，这种行为显示了混沌系统局部的 不稳定性；但整个混沌系统本身并不会随着轨道间的指数分离特性而变得发散或不稳 定，混沌运动总是在个有限的空间里反复折迭、伸缩逐渐分布于整个相空间上。当两 条轨道间的距离大到可以与混沌运动的空间相比拟时，轨道在相空间中呈现出近似随 机的特性，这是一种确定性系统本身表现出的内在的随机性5 1 。 第二种定义是基于l i y o r k s 定理的严格定义。 l i y o r k s 定理为：设f ( x ) 是【口，b 】上的连续自映射，若厂( x ) 有3 周期点，则对任何 正整数刀，f ( x ) 有刀周期点。 混沌的定义如下：闭区间i 上的连续自映射f ( x ) ( 下文中简记为f ) ，若满足下列 条件，则一定出现混沌现象： ( 1 ) f 周期点的周期无上界； ( 2 )闭区间i 上存在不可数子集满足： 对任意x ，y s ，当z y 时，则有 ! i m s u p l f ”( x ) - f ”( 少) l 0 ( 1 1 ) 对任意x ，y s ，有 ! i m i n f l f “( x ) - f ”( j ，) i = 0 ( 1 2 ) 对任意x ，y s ，其中y 是的任一周期点，则有 l i m s u p l 厂”( 石) - f ”( y ) i 0 ( 1 3 ) 几种混沌块加密算法的研究 这就是著名的论文“周期三意味着混沌 ，即对于上述所定义的系统，若存在3 周期点，则任何周期点都可能拥有，该系统可能出现混沌现象。上述的定理及定义说 明了混沌运动不同于一般周期运动的重要特点，式( 1 1 ) ，( 1 2 ) 和( 1 3 ) 说明，混 沌运动的轨道之间总是时而无限接近，时而彼此分离，表现出非周期的混乱性；混沌 动力系统的相空间中充满着可数无穷多的周期轨道和不可数无穷多的非周期轨道；在 相空间中总存在着不稳定的周期轨道；随着系统的演化，不稳定周期轨道旁的临近轨 道总是与该轨道分离。混沌运动充斥在相空间上的有限区域，在相空间中形成了混沌 吸引子，由于其不同于其他常见的吸引子，因而也称为奇异吸引子【1 7 抛1 。 1 1 2 混沌的性质 混沌是复杂的非线性系统，主要具有以下几方面特性【1 7 2 2 j ： ( 1 ) 遍历性。在混沌吸引域中，混沌轨道会经过每一个状态点。 ( 2 ) 对初始条件的敏感依赖性。“蝴蝶效应非常形象地反映了混沌系统对于 初始条件的极度敏感性。初始条件包括混沌系统的迭代初值和控制参数，在混沌允许 的范围内微小地改变控制参数或对迭代初值进行细微地改动，经过若干次演化之后都 会导致混沌系统，其运行轨迹与原始轨迹相差甚远，对其未来的状态造成巨大的影 响。 ( 3 ) 长期不可预测性。由于混沌系统所具有的轨道的不稳定性和对初始条件的 敏感性等特征，因此不可能长期预测将来某一时刻的动力学特性。 ( 4 ) 有界性。混沌的运动轨迹始终局限于一个确定的区域，叫作混沌吸引域， 无论其局部运动如何不稳定，其轨迹都不会脱离混沌吸引域，这也反映出混沌系统的 整体稳定性。 ( 5 )内随机性。稳定性是指系统受到微小的扰动后，仍保持原来状态的属性和 能力。混沌系统具有整体稳定性，虽然可以用确定的方程表示，但其运动状态确有某 些随机性，而这些随机性源自系统自身。混沌的内随机性实际上就是它的不可预测 性，混沌系统运动的某些方面如某些维度、熵的行为强烈地依赖于初始条件。 ( 6 ) 轨道不稳定性及分岔。长时间动力运动的类型在某个参数或某组参数发生 变化时也发生变化。这个参数值或这组参数值称为分岔点，在分岔点处参数的微小变 化会产生不同定性性质的动力学特性，所以系统在分岔点处是结构不稳定的。 ( 7 ) 分形结构。耗散系统的有效体积在演化过程中将不断收缩至有限分维内， 耗散是一种整体稳定性因素，而轨道又是不稳定的，这就使它在相空问的形状发生拉 伸、扭曲和折叠，形成精细的无穷嵌套的自相似结构。混沌状态表现为无限层次的自 一4 一 大连理工大学硕士学位论文 相似结构。 ( 8 ) 普适性。所谓普适性，。是指在趋向混沌态时所表现出来的某些共同特征， 它不依具体的系统方程或参数而变。普适性是混沌系统内在规律性的一种体现。 1 1 3 混沌的研究方法 混沌是一种复杂的非线性系统，我们可以使用一些用来分析非线性系统特性的方 法来进行研究，例如对吸引子1 7 ，1 羽、分岔图【1 7 2 2 1 、l y a p u n o v 指数1 7 1 、功率谱分析【1 7 1 等 进行定量分析。 ( 1 ) 吸引子 在统计物理中，相空间运动过程中始终保持相体积不变是保守系统的特性，然而 耗散系统却不具有这个特性。一般来说，其相体积要逐渐收缩，有的收缩到一点，有 的收缩到一个闭曲线上，有的收缩到二维或二维以上的环面上。我们称这些除掉暂态 后相空间所趋向的有限空间为吸引子。 混沌运动的重要特点突出表现在相空间中的轨线在捕捉区所形成的吸引子不同于 通常规则运动的吸引子。 混沌运动的奇怪吸引子有以下几个主要特点： 从整体说，系统是稳定的：吸引子外的一切运动最后都要收缩进入到吸引子 中。但是就局部说，吸引子内的运动又是不稳定的：相邻运动轨道要相互排斥而按指 数形式分离。所以奇怪吸引子是这种整体稳定性和局部不稳定性一对矛盾的结合体。 单纯的轨道分离( 扩张) 或收缩是不可能使运动复杂化而形成混沌的，混沌运 动的吸引子是由轨线经大量分离和折叠才形成的。 混沌态的吸引子不一定填满某一有限区域，而往往是具有一些空隙或空洞。混 沌运动的奇怪吸引子具有无穷层次的自相似结构。 奇怪吸引子的维数常常是非整数。 奇怪吸引子具有遍历性，即在时间足够长的情况下，吸引子中轨道可遍及吸引 子中各处。 ( 2 ) 分岔图 分岔图是表示动力学系统随某一参数变化而变化的二维图形，即计算对应于每一 参数的不动点x 的值( 离散系统) 或振荡的最大值x ( 连续系统) 。为得到稳定不动 点x 值，在用计算机进行迭代运算时，必须去掉与初始值有关的暂态，以参数为横 坐标，不动点或振荡的最大值x 为纵坐标作图，这个图即为分岔图。 随着的逐渐变化，依次出现2 玎周期分岔，当取某些值时，z 取值出现了有一 几种混沌块加密算法的研究 定疏密度的随机，即出现了混沌。在混沌区左右通常会出现倍周期现象，如果把x 和 参数的尺度放大，便看出混沌区内的细节，可以发现在混沌区内也还存在许多不是 混沌的周期窗口，这就是混沌的自相似结构，这也是混沌的典型特征之一。 ( 3 ) 李雅普诺夫( l y a p u n o v ) 指数 李雅普诺夫指数可以定量地表示离散映像中相邻点相互分离的快慢或奇怪吸引子 中轨道分离的快慢，即轨道对初始条件的敏感依赖性。 在一维离散系统 以+ 。= f ( 以) ( 1 4 ) 中，初始两点是互相分离还是靠拢由下式决定： l d f d x l 1 ，映象使两点分开； l d f d x i 1 ，映象使两点靠拢。 为了表示从整体看两相邻初始状态分离的情况，必须对时间( 或迭代次数) 取平 均。为此，设平均每次迭代所引起的指数分离( 或微分系统中每单位时间内所引起的 指数分离) 中的指数为a ，则原来相距为8 的两点经过刀次迭代后相距变为 c e 以峋= f ”( x o + 占) 一f ”( ) ( 1 5 ) 取极限_ 0 ，刀一，由上式得到与初始点x 0 无关的表达式： 兄= 舰吉喜i n 吼五 6 ， 式中五称为李雅普诺夫指数。 当a 0 时，相邻点要分开，这对应于混沌运动。对于微分动力系统来说， 上述两种情况分别对应轨道收缩( 稳定) 和轨道分离( 不稳定) 。 ( 4 ) 功率谱分析 混沌动力学关心的主要是运动轨道的回归行为。纯随机性的运动包含一切可能的 频率成分，而一切非随机的运动都具有一定的特征时间尺度或频率结构。功率谱中的 宽带，被作为可能存在混沌的简单指示，我们可以方便地应用傅立叶分析对其进行研 究。 对于任何非周期运动的时间函数x ( f ) ，设 大连理工大学硕士学位论文 fj x ( f ) 眵 o o ( 1 7 ) 巴 则x ( ，) = if ( a o e 埘d c o ( 1 8 ) 1 巴 f ( o ) = 亡ix ( t ) e 1 甜d t ( 1 9 ) z 兀二 也就是说非周期运动的频谱是连续谱，但是对于噪声或混沌信号由于可能会随时间，而 无限连续下去，不满足式( 1 7 ) ；而且由于混沌信号同时包含随机信号和有序信号， 频谱并不能完全描述其性质，因此我们利用功率谱密度描述动力学系统的性质。 功率谱密度函数定义为 1巴 s ( c o ) = 亡ic ( r ) e - - l “o g d r ( 1 1 0 ) z 兀二 式中，c ( 力为x ( 力的自相关函数。 对于周期系统，功率谱只在基频及其倍频处有6 函数形式的尖峰：对于准周期系 统，功率谱在几个不可约的基频和由它们叠加的频率处有万函数形式的尖峰：对于混 沌系统，功率谱上会出现宽带的噪声背景。 混沌的研究与判定的方法还有很多种，比如关联维数、测度熵、庞加莱截面等， 这些方法同样可以有效地分析出混沌系统的某些典型特征。 1 1 4 混沌的应用 混沌理论在信息相关学科的应用可以分为混沌综合和混沌分析，前者利用人工产生 的混沌从混沌动力学系统中获得可能的功能，如人工神经网络的联想记忆等，后者由 复杂的人工和自然系统中获得混沌信号并寻找隐藏的确定性规则，如时间序列数据的 非线性确定性预测等。 混沌的可能应用如下【2 3 】： ( 1 ) 混沌加密：比如利用混沌序列的非周期性和伪随机的特性，将混沌序列作为 密钥流和原始明文序列进行逐位异或得到加密密文。 ( 2 ) 神经网络：将混沌与神经网络相融合，使神经网络由最初的混沌状态逐渐退 化到一般的神经网络，利用中间过程的混沌状态的动力学特征使神经网络逃离局部极 小点，从而保证全局最优，可用于联想记忆、机器人的路径规则等。 几种混沌块加密算法的研究 ( 3 )图像数据压缩：把复杂的图像数据用一组能产生混沌吸引子的简单动力学方 程替代，这样只需记忆存储这一组动力学方程组的参数，其数据量比原始数据量大大 减小从而实现图像压缩。 ( 4 ) 高速检索：利用混沌的遍历性进行检索，即在改变初值的同时，将要检索的 数据和刚进入混沌状态的值相比较，检索出接近于待检索数据的状态，这种方法比随 机检索或遗传算法具有更高的检索速度。 ( 5 ) 非线性时间序列预测：任何一个时间序列都可以看作一个由非线性机制确定 的输入输出系统。如果不规则的运动现象是一种混沌现象，则通过利用混沌现象的决 策论非线性技术就能高精度的进行短期预测。 ( 6 ) 模式识别：利用混沌轨迹对初始条件的敏感性，有可能使系统识别出只有微 小区别的不同模式。 ( 7 ) 故障诊断：根据由时间序列在构成的吸引子的集合特征和采样时间序列数据 相比较，可以进行故障诊断。 ( 8 ) 混沌保密通信：利用混沌信号的编码和解码技术实现混沌信号的保密通信。 此研究已经进入了美国国防部的计划并正在加紧研制中。 ( 9 ) 优化：利用混沌运动的随机性、遍历性和规律性寻找最优点，可用于系统辨 识、最优参数设计等多方面。 当然混沌理论还可以应用在其他方面。例如，在语言加工信息的研究方面、对人 脑功能以及处理信息的机理方面等。 1 2 密码学概述 1 2 1 密码编码学 密码编码学是密码学的重要的组成部分【让3 1 ，有以下三个特征：转换明文为密文的 运算类型、所用的密钥数和处理明文的方法。所有的加密算法都需要基于两个原理， 代换和置换，代换是将明文中的每一个元素映射成另外一个元素，置换是将明文中的 元素重新排列。 根据算法所用的密钥数的不同，可以区分对称加密和非对称加密。如果发送方和 接收方使用相同的密钥，这种密码就为对称密码、单密钥密码或传统密码。如果发送 方和接收方使用不同的密码，这种密码就叫非对称密码、双钥或公钥密码。 对称密码方案有五个部分组成，明文、加密算法、密钥、密文和解密算法。原始 可理解的消息或数据被称为明文。用某种方法伪装消息以隐藏它的内容被称为加密， 加了密的消息称为密文，而把密文转变为明文的过程称为解密。 大连理工大学硕士学位论文 公钥算法依赖于一个加密密钥和一个与之相关的不同的解密密钥，由六部分组 成，明文、加密算法、公钥、私钥、密文和解密算法。与对称密码不相同的是加密密 钥和解密密钥是不同的，而且有一个密钥需要保密，这种加密方法与以前四千多年来 的密码学方法有着根本的不同，也是近代密码学研究的一个重大成就。 明文用m ( 消息) 或p ( 明文) 表示，它可能是比特流( 文本书件、位图、数字 化的语音流或数字化的视频图像) 。密文用c 表示，它也是二进制数据，有时和m 一 样大，有时稍大( 通过压缩和加密的结合，c 有可能比p 小些。然而单单加密通常达 不到这一点) 。 对于对称加密来说，密钥用k 来表示，加密函数e 作用于m 得到密文c ，用数学 表示为： c = e ( m ，k ) ( 1 1 1 ) 相反地，解密函数d 作用于c 产生m m = d ( c ，k ) ( 1 1 2 ) 对于非对称加密来说，密钥用p u b k 和p r i k 来表示，加密函数e 作用于m 得到 密文c ，用数学表示为： c = e ( m ，p u b k ) ( 1 1 3 ) 相反地，解密函数d 作用于c 产生m m = d ( c ，p r i k ) ( 1 1 4 ) 根据处理明文的方式的不同，可以分为分组密码和流密码。分组密码每次处理输 入的一组元素，相应的输出一组元素；流密码则是连续的处理输入元素，每次输出一 个元素。 1 2 2 密码分析学 密码编码学的主要目的是保持明文( 或密钥，或明文和密钥) 的秘密以防止偷听 者知晓。密码分析学是在不知道密钥的情况下，恢复出明文的科学。成功的密码分析 能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结 果( 密钥通过非密码分析方式的丢失叫做泄露) 对密码进行分析的尝试称为攻击。 常用的密码分析攻击有四类： ( 1 ) 唯密文攻击。密码分析者有一些消息的密文，这些消息都用同一加密算法 加密。密码分析者的任务是恢复尽可能多的明文，或者最好是能推算出加密消息的密 几种混沌块加密算法的研究 钥来，以便可采用相同的密钥解出其他被加密的消息。 己知：c 1 = ( 毋) ，c 2 = 乓( b ) ，g = 反( c ) 。 推导出：墨，最，只；k 或者找出一个算法从e + 。= 以( 只+ 。) 推出只+ 。 ( 2 )已知明文攻击。密码分析者不仅可得到一些消息的密文，而且也知道这些 消息的明文。分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此 算法可以对用同一密钥加密的任何新的消息进行解密。 已知：互，g = 乓( p 1 ) ，昱，c 2 = 敏( 昱) ，e = & ( e ) 。 推导出：密钥k ，或从从e + 。= ( + 。) 推出只+ 。的算法。 ( 3 ) 选择明文攻击。分析者不仅可得到一些消息的密文和相应的明文，而且他 们也可选择被加密的明文。这比己知明文攻击更有效。因为密码分析者能选择特定的 明文块去加密，那些块可能产生更多关于密钥的信息，分析者的任务是推出用来加密 消息的密钥或导出一个算法，此算法可以对用同一密钥加密的任何新的消息进行解 密。 已知：置，c l = 敏( 置) ，e ，c 2 = 坟( 昱) ，# ，c j = ( 只) 。 其中丑，昱，p 是由密码分析者选择的。 推导出：密钥k ，或从g + 。= 瓯( + 。) 推出只+ 。的算法。 ( 4 ) 选择密文攻击。密码分析者能选择不同的被加密的密文，并可得到对应的 解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推 出密钥。 已知：c l ，暑= d 髟( c 1 ) ，g ，= d k ( c ：) ，c ，只= d k ( c j ) 。 推导出：k 。 这种攻击主要用于公开密钥体制。选择密文攻击有时也可有效地用于对称算法 ( 有时选择明文攻击和选择密文攻击一起称作选择文本攻击) 。 1 2 3 混沌和密码学的关系 现如今，随着密码学的研究的深入，已经成功的提出了许多不但安全性较高，而 且效率也比较高的加密算法，但是这些算法也有自己的局限性和不足。为了推动科学 的发展和进步，研究者们不断在寻找和研究更安全更高效的算法，而混沌作为一种非 线性现象，有许多值得在密码学上应用的性质，或许能够为密码学的发展提供新的思 路和途径，为保密通信提供更好的手段 2 4 - 2 5 】。同时，目前的研究也发现，传统的密码 方法中存在着与混沌的联系2 6 】；与此同时，混沌现象也具有密码的某些特征，因此， 大连理工大学硕士学位论文 研究混沌保密通信，不仅对构造新的更安全的加密方法和加密体系有帮助，同时，对 进一步深入地理解现有的密码与密码体制也有帮助，这无论是在理论上还是在实际应 用中，都十分有益。 一个密码系统其实也是一个映射，只是它是定义在有限域上的映射【1 9 1 。密码系统 是一个确定性的系统，它所使用的变换由密钥控制；加密变换c = e ( p ，的求取不困 难，但在不知道k 的情况下，解密变换p = d ( c ，的的求取却极为困难。要做到这一 点，密码系统须对密钥极端敏感；密文需要对明文敏感地依赖，这使得在知道部分密 文( 和明文) 的条件下，猜测全部明文( 或密钥) 极其困难。要保证这一点，明文须 得到充分的混合。这些对密码系统的要求和混沌的特性有着十分密切的联系。 根据被破译的难易程度，不同的密码算法具有不同的安全等级。如果破译算法的 代价大于加密数据的价值，那么可能是安全的；如果破译算法的时间比加密数据的保 密时间更长的，那么可能是安全的；如果用单密钥加密的数据量比破译算法的数据量 少得多，那么可能是安全的。 评价密码体制的安全性有不同的途径，下面是几个有用的准则【2 3 】： 无条件安全性：无论密码攻击者掌握了多少计算资源，都无法攻破的密码体系， 是无条件安全的。s h a n n o n 从理论上证明了，仅当可能的密钥数至少与可能的消息数目 一样多的时候，无条件安全才是可能的。实际上，只有一次一密的乱码本才是不可攻 破的。除此之外，任何一个密码系统使用唯密文攻击在理论上都是可破的，只需用穷 举法进行蛮力攻击即可。 计算安全性：密码攻击者使用了可以使用的所有计算资源，仍然无法攻破的密码 体制，是计算上安全的。这是密码学更为关系的性质，如果一个密码体制的最好结果 需要n 次操作，而n 是一个非常大的数字，我们可以定义该密码体制是计算机上安全 的，问题是没有一个已知的实际密码体制在这个定义下可以被证明是安全的。实际 中，研究人员通常使用几种特定的攻击类型来研究计算安全性，对于对称密码体制， 一般可以用密码系统的熵来衡量系统的理论安全性，它由密钥空间的大小计算出来： h ( k ) = i o g ( k ) ，密码系统的熵越大，破译它就越困难。 可证明安全性：将密码系统的安全性归结为某个经过深入研究的数学难题，则这 种密码体制是可证明安全的。这和证明一个问题是n p 完全有些类似，例如，r s a 公 开密钥体制的安全性是基于分解大整数的难度，e 1 g a m a l 公开密钥密码体制是基于计 算有限域上的离散对数的难度等等。如果对应的理论被解决，这种可证明安全性的不 存在了，以这种理论为基础的密码系统会马上崩溃。然而，在这个理论问题没有被解 决之前，要破解这种密码系统的代价非常大，而失去了破解的价值，因此相对来说是 非常安全的。 1 3 本章小结 混沌作为一种非线性现象，有许多值得利用的性质，而且混沌和密码学之间具有 天然的联系和结构上的某种相似性，启示人们把混沌应用在密码学领域，能够为密码 学的发展提供新的思路，为保密通信提供更好的手段。本章主要介绍了论文所用到的 混沌理论和密码学的基础概念。首先介绍了混沌理论的发展简史，混沌的定义、性质 和一些研究方法。随后介绍了密码学以及密码分析学的基本原理，同时也简要的介绍 了混沌密码学和密码学的天然关系，揭示了两者之间有紧密的联系，并且仍有很大的 发展空间。 大连理工大学硕十学位论文 2本文应用的数字混沌加密原理 2 1数字化混沌密码学研究现状 混沌是现实社会中普遍存在的现象，对混沌理论的研究已成为各个学科的前沿课 题和学术热点【3 。3 0 1 ，包括如何减少或消除混沌所产生的有害因素，如何控制现有的动力 学系统使其达到混沌状态，以及如何在各个学科应用混沌等。自e l o r e n z 于1 9 6 3 年首 次发现混沌以来，混沌理论的发展非常迅速，然而相关的研究很大一部分是关于混沌 的定义、特征、特性等的分析和判定，这些研究对其在各领域中的应用帮助不大。随 着1 9 9 0 年美国科学家p e c o r a 和c a r r o l l 提出了混沌同步理论【l6 1 ，混沌理论成为了一种 颇有潜力的保密通信的载体【l7 忽】。同步是自然界中的一种基本现象，指的是两个或两 个以上的振动系统相位间的协调一致现象。混沌同步是指两个混沌系统，在特定的初 始条件下，通过某种驱动或耦合，以实现混沌轨道的同步化【3 。 早期，混沌应用在信息安全领域主要是基于混沌的保密通讯。通过使用混沌同步 的理论，使得混沌信号成为信道中信号传输的载体。后期随着对混沌理论研究的逐渐 深入，有学者开始把混沌和密码学联系了起来，指出在混沌理论和密码学之间存在着 紧密的联系1 3 2 3 1 。许多混沌系统的基本特性，如遍历性( e r g o d i c i t y ) 、混合性 ( m i x i n g ) 、确定性( e x a c t n e s s ) 和对初始条件的敏感性( s e n s i t i v i t y ) ，都可以和密 码学中的混乱( c o n f u s i o n ) 和扩散( d i f f u s i o n ) 等概念联系起来，昭示着人们把混沌 应用于密码学领域。然而混沌毕竟不等于密码学，它们之间还有很多不同，比如传统 密码学已经建立了一套分析系统安全性和性能的理论，密钥空间的设计方法和实现技 术亦比较成熟从而能保证系统的安全性，而目前混沌加密系统还缺少这样一个评估算 法安全性和性能的标准。表2 1 给出了混沌理论同密码学的相似之处和不同之处1 3 ，2 引。 表2 1 混沌理论与密码学的关系 t a b 2 1 r e l a t i o n s h i pb e t w e e nc h a o st h e o r ya n dc r y p t o g r a p h y 几种混沌块加密算法的研究 通过类比研究混沌理论和密码学，可以彼此借鉴各自的研究成果，促进学科的发 展。抽象的说，混沌和密码学变换都服从确定性的算法或方程，在若干次迭代之后， 其结果都会表现出某种伪随机的特征。并且，混沌和密码变换均要求对初始条件的敏 感性，初始条件的微小变化会带来结果的显著不同。但是，混沌系统定义在无限的连 续实数集上，而密码系统定义在有限的离散集上，所以并不是所有的混沌系统都适合 用来设计密码系统。如何选取适当的混沌系统，以及如何利用混沌系统设计出有效的 加密算法是混沌加密的焦点问题。近年来，应用混沌构建加密系统的研究已取得了很 多可喜的进展【3 圳1 。 随着人们对混沌理论了解的深入，研究人员开始尝试研究基于混沌系统设计数字 加密算法。从上世纪八十年代开始，出现了相关的研究文章，同时，对混沌系统用在 数字加密领域的安全性也在不断地论证中。在加密与破译的推动下，数字混沌加密系 统越来越成熟，安全性越来越高【l 。 1 9 8 9 年到1 9 9 3 年间是数字混沌加密系统研究的最初阶段，这段时间里出现了大量 的有关数字混沌加密的论文。随后几年，人们对混沌系统数字化后的退化进行的分 析，暴露了数字混沌加密系统的很多安全缺陷，所以在1 9 9 3 年到1 9 9 7 年间在数字混 沌加密领域的进展不明显。1 9 9 7 年后，人们开始尝试通过对数字混沌加密系统进行改 进来弥补已知的和未知的安全缺陷，以便得到更加健壮的加密算法。进入2 1 世纪之 后，更加细致深入的研究已经使数字混沌加密领域越来越接近实用化。过去人们提出 的基于混沌的数字加密方法大体上可以分为三类： ( 1 ) 利用混沌系统产生的伪随机密钥流序列对明文进行加密运算得到密文 6 1 。 ( 2 ) 利用明文作为混沌系统的控制参数或者初始值，经过混沌系统的迭代或者 反迭代得到密文1 2 引。 ( 3 ) 。利用混沌系统来构造公开密钥密码。该项研究还处于初期阶段，混沌公钥 加密的方案实用性还较差，但是对这类密码系统的研究是一件很有意义的事情，对促 进传统公开加密算法的改进大有益处。 第一类方法对应于序列加密，第二类一般对应于分组加密。除了以上三种以外， 还出现了一些新的设计方法，比如使