（计算机应用技术专业论文）有限精度下一种混沌密码算法安全性分析及其应用.pdf

摘要 摘要 混沌系统具有良好的随机性、轨道不可预测性、对初始条件和控制参数敏感 等一系列的特性，这些特性和密码学的很多要求吻合。混沌理论和密码学相结合， 产生一门新的交叉学科：混沌密码学。但是受有限计算精度的影响，在计算机上 实现的数字化混沌系统，其动力学特征出现了严重的退化。 本文首先介绍了混沌系统和密码学之间的紧密联系，然后综合分析了近年来 提出的混沌加密算法及其相关的安全性分析，总结了设计混沌密码的一般思路。 接下来重点分析有限计算精度对混沌密码系统安全性的影响以及增强混沌密码 系统安全性的一些可行措施，在此基础上对l o g i s t i c 混沌映射在有限精度下的动 态特征退化问题做了初步的研究。 本文对y e n g u o 提出的一种混沌加密算法进行了详细的安全性分析，发现这 种混沌加密算法在选择明文攻击下是不安全的，并给出了可能的改进措施。提出 了一种基于改进型l o g i s t i c 混沌映射的伪随机数发生器，理论和试验分析表明生 成的伪随机序列具有良好的密码学特征，以此为基础设计并实现了一种新型的混 沌流密码算法，试验结果表明该算法具有较高的安全性。 关键字：混沌、密码学、密码分析、有限精度、l o g i s t i c 映射 - 蕾- a b s t r a c t o n ec h a o t i c c i p h e r s s e c u r i t ya n a l y s i s u n d e rf i n i t e p r e c i s i o na n di t sa p p l i c a t i o n l i uj i a n x i a ( c o m p u t e r a p p l i c a t i o n ) d i r e c t e db yg a o q i n g s h i s o m ei n n e rp r o p e r t i e so fc h a o s 。s u c ha sr a n d o m n e s s ， u n p r e d i c t a b l e o r b i t sa n di n i t i a lv a r i a b l e ss e n s i t i v i t y , a c c o r dd e e p l yw i t hr e q u i r e m e n t so f c r y p t o g r a p h y b e t w e e nc h a o sa n dc r y p t o g r a p han e wc r o s s - d i s c i p l i n a r yf i e l d c a l l e dc h a o t i c - c r y p t o g r a p hg e n e r a t e s b u tb e c a u s eo ff i n i t ep r e c i s i o n ，w h e n d i g i t a lc h a o s r e a l i z e si nc o m p u t e r , i t s d y n a m i cp r o p e r t i e sd e s c e n d sb a d l y w ef i r s ti n t r o d u c et h en a t u r a ir e l a u o nb e t w e e nc h a o sa n dc r y p t o g r a p h y , a n dt h e ng i v eac o m p r e h e n s i v es u r v e ya b o u tm a n yc h a o t i cc i p h e r s d e s i g n s c h e m ea n ds e c u r i t ya n a l y s i s o u re m p h a s i si st h ei n f l u e n c eo ff i n i t ep r e c i s i o n t oc h a o t i cc i p h e r sa n dr e m e d i e st oe n h a n c e s e c u r i t yo fc h a o t i cc i p h e r s b a s e d o nt h es u r v e yw eg i v ea ni n i t i a l i n v e s t i g a t i o n a b o u tl o g i s t i cm a p sd y n a m i c p r o p e r t i e sd e g r a d a t i o nu n d e r f i n i t ep r e c i s i o n t h i st h e s i sa n a l y z e so n ec h a o t i cc i p h e rp r o p o s e db yy e n g u oj nd e t a i l s a n df i n d si ti si n s e c u r et oc h o s e np l a i nt e x ta t t a c k a l s o s o m er e m e d i e sa r e g i v e n t oi m p r o v ei t ss e c u n t y b a s e do nt h em o d i f i e dl o g i s t i cm a pw e p r o p o s e a p s e u d o r a n d o m n u m b e rg e n e r a t o r ( p r n g ) t h e o r e t i c a ia n de x p e d m e n t a l r e s u l t ss h o wt h i sp r n gh a s g o o dc r y p t o g r a p h i cp r o p e r t i e s 。u s i n gt h i sp r n g w e d e s i g na n di m p l e m e n tar o v e ic h a o t i cs t r e a mc i p h e r , w h i c hs h o w sg o o d s e c u r i t yu n d e re x p e r i m e n t a lt e s t s k e y w o r d e ：c h a o s c r y p t o g r a p h 。c r y p t a n a l y s i s ，f i n i t ep r e c i s i o n l o g i s t i cm a p 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并 表示了谢意。 作者签名：a 关于论文使用授权的说明 日期： 咄z ，2 ， 中国科学院计算技术研究所有权处理、保留送交论文的复印件， 允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采 用影印、缩印或其它复制手段保存该论文。 储虢专惮及导师躲乏叶吼少峨7 沙 弓i 言 研究背景和课题意义 引言 混沌是指在确定性非线性系统中存在的不需要附加任何随机因素即可出现 类似随机性的行为，混沌理论作为自然科学的一个分支，随着现代科学技术的进 步，尤其是在计算机技术的出现和普遍应用基础上开始快速的发展起来。混沌系 统的最大的特点就是对初始条件和控制参数的极端敏感性，初始条件或者控制参 数有非常细微的变化都会导致最终结果的巨大差异，这样，由混沌映射产生的混 沌轨道随着时间的流逝变得越来越“不可预测”。混沌理论最广为人知的一个科 学假设就是“蝴蝶效应”。除了对初始条件的敏感性之外，混沌系统还具有的基 本特性包括遍历性、混和性、不确定性等。 混沌系统的基本特性和密码学中的混淆( c o n f u s i o n ) 和扩散( d i f f u s i o n ) 概念都 可以联系起来，在s h a n o n 的经典论：l r c o m m u n i c a t i o nt h e o r yo f s e c r e c ys y s t e m s ” s h a n o n , 1 9 4 9 中就曾经提到好的保密系统中所需要的好的混和变换( m i x i n g t r a n s f o r m a t i o n ) 可以使用基本的“r o l l e d - o u t a n df o l d e d o v e r ”操作得到，而在混沌 系统中，许多经典的映射，例如l o g i s t i c 映射、b a k e r 映射、s m a l e 马蹄映射等 引发混沌的原因就是“拉伸并折叠( g 吨c h a n d - f o l d ) ”，显然s h a n o n 所说的好的混 和变换可以看作是限制在有限空间内的混沌映射( 当然这不是严格意义上的) 。从 另一方面看，好的密码系统对明文加密带来的密文混沌状态，非常类似于复杂动 力系统产生的混沌现象，从算法的角度看，好的密码系统也可以看成是一个混沌 或者拟混沌系统。下面的这张图给出了混沌和密码学一个形象的比较： 图1 1 混沌系统和密码算法的对比 由于混沌系统和密码学之自j 存在着如此紧密的联系，采用混沌系统去设计新 的密码算法的想法就很自然了。自从1 9 8 9 年第一篇采用混沌系统构造加密算法 的论文 m a t t h e w s ，1 9 8 9 发表以来，大量的混沌密码算法以及相关的分析成果被提 出。关于混沌密码学的研究有助于丰富传统密码学的内容，为好的密码系统的设 计提供更多的设计思路和手段，可以丰富离散时间和离散空间混沌系统的理论知 识。 当混沌系统在计算机、d s p 、单片机等数字设备上实现时，由于受到有限计 算精度的影响，导致混沌系统的动力学特征出现了比较严重的退化，典型的问题 包括短周期问题、退化的轨道分布和相关特性。研究混沌系统在有限计算精度下 的动态特征退化问题，采取一些措施改善其动力学特征，对增强混沌密码系统的 安全性和推广应用都具有很重要的意义。 本文的研究思路和主要工作 大部分混沌密码系统在设计的时候，对数字化混沌系统出现的动力学特征退 化问题缺乏足够的重视，导致相当一部分混沌加密算法从严格密码学的意义上来 说是不安全的。由于现有的关于数字化混沌系统动力学特征退化的理论研究还很 不完善，缺乏完备的理论体系，从理论上对混沌密码系统的安全性进行分析存在 着相当大的难度。在本文中，我们主要使用试验的方法研究数字化混沌系统的动 力学特征退化问题，并尝试从三个方面展开工作：数字化混沌系统动力学特征退 化的试验分析、数字化混沌密码系统的安全性分析、设计混沌密码系统的新思路。 第一个方面的研究是后面两个研究的基础，而第二个方面的研究又是第三个方面 的另外一个基础。 总的来说，本文主要的工作可以总结为下面四点： 1 。我们对混淹密码学这个研究方向做一个较为详细的回顾。按照采取的混 沌映射的不同对各种混沌加密算法进行分类，讨论了相关的安全性分析， 并总结了设计混沌加密算法的两种一般思路。 2 我们通过试验的手段对l o g i s t i c 映射在有限精度下动态特征行为做了初 步的分析。发现在定点运算和单精度浮点运算下，产生的混沌轨道会以 相当大的概率进入短周期循环或者收敛到一个固定点，在双精度浮点运 算下能够较好的模拟混沌行为。 3 我们对y e n g u o 提出的一种混沌加密算法进行详细的安全性分析，发现 算法存在两个严重的缺陷，我们设计了一种选择明文攻击方法成功的破 解了这个算法，提出了一种密文反馈的方法加强y e n - g u o 混沌加密算法 的安全性。 4 我们提出了一种基于改进型l o g i s t i c 映射的伪随机数发生器，从理论上 引言 证明该随机数发生器产生的二进制序列具有良好的密码学性能。以此为 基础设计了一种新型的混沌序列密码算法，试验结果表明这个加密算法 可以获得较高的安全性。 本文的组织 本文的正文部分是这么组织的： 第一章，概述混沌密码学的研究状况。 第二章，重点介绍数字化混沌系统在有限精度下的动态特征退化问题，采用 试验的手段分析l o g i s t i c 映射的动态特征退化问题。 第三章，对y e n - g u o 提出的一种基于l o g i s t i c 映射的混沌加密算法的安全性 分析，针对算法的弱点提出了改进意见。 第四章，提出一种基于改进型l o g i s t i c 映射的伪随机数发生器，以此为基础 设计了一种新型的混沌流密码算法。 第五章，对所做工作的总结并对将来的研究方向进行展望。 第一章福沌加密算法概述 第一章混沌加密算法概述 混沌密码学兴起于1 9 9 0 年前后。1 9 8 9 年r m a t t h e w s 提出了第一个混沌加 密算法，采用l o g i s t i c 混沌映射进行加密算法设计，此后，混沌密码学分别在物 理学、电子工程和密码学等多个领域同时发展起来，越来越多的混沌加密方案被 提出，混沌加密开始应用在保密通信、图像，视频加密和数字水印等领域。 在本章的第一部分，我们按照采取的混沌映射的不同，对从1 9 8 9 年以来在 各种文献中公开发表的混沌加密算法做了一个比较详细的综述，重点讨论相关的 安全性问题。在第一部分的基础上，总结设计混沌加密算法的两种一般思路。 1 1 混沌加密算法的分类综述 按照混沌加密算法采取的混沌映射的不同，可以将混沌加密算法分成以下 几类：基于l o g i s t i c 映射的混沌加密算法、基于逐段混沌映射的混沌加密算法、 基于二维混沌映射的混沌加密算法以及基于其他混沌映射的混沌加密算法。这样 分类的原因是因为相同的混沌映射在有限精度下的动态退化特征相近，基于同种 混沌映射构造的加密算法在有限精度下表现的安全性相似。 1 1 1 基于l o g i s t i c 映射 l o g i s t i c 映射是一个简单的混沌系统，也被称为虫1 2 1 方程。2 0 世纪5 0 年代， 有好几位生态学家就利用过这个简单的差分方程来描述种群的变化： x n + l = 僻n ( 1 - x n )p ( o 4 ) 式中x n 表示当年的种群数，x n + l 便是下年的种群数，“为增长参数。l o g i s t i c 映 射已经从理论上证明具有典型的混沌动态特征，当“选择在【3 5 6 9 9 9 4 5 6 ，4 】之 间时，l o g i s t i c 映射工作于混沌态【黄润生，2 0 0 0 。l o g i s t i c 映射只包括乘法和减法 运算，在计算机上很容易实现。l o g i s t i c 映射用在混沌加密系统中，通常把初始 条件) ( 0 作为密钥，因为初始条件即使有非常小的差别，迭代后产生的混沌序列 都会差别很大。控制参数“也可以用来作为隐藏参数或者是密钥。但是同时采用 和“作密钥可能不是足够安全的 k o c a r e v , 2 0 0 1 。l o g i s t i c 映射既可以用来设 计分组加密算法，也可以用来设计流加密算法。 1 9 8 9 年m a t t h e w s 提出了一个采用混沌映射的加密算法 m a t t h e w s , 1 9 8 9 ，用 密码学的思想分析l o g i s t i c 方程，使用产生的序列最后两个小数作为随机序列。 比较典型的是m s b a p t i s m 在1 9 9 8 年提出了一种方案 b a p t i s t a , 1 9 9 8 ，假定传输 的信息是由字母组成的文本，每个字母单元和一个e 区间相关联，对某个字符 第一章混沌加密算法概述 的加密是l o g i s t i e 映射的迭代次数，这个迭代次数满足混沌轨道从某个初始条件 与或分离后到达与这个字符相关联的e 区间。w a i k i tw o n g 等人在分析b a p t i s m 的加密方案基础上，提出了一种改进方案w k w o n g ，2 0 0 1 1 ，把文本信息的 a s c 2 码映射到l o g i s t i c 相空间介于0 2 和0 8 之间的不同区域上，对每个文本块 加密时，先产生一个介于0 和预定义的最大随机数r 。之间的随机数。然后对 l o g i s t i c 映射迭代r 次，继续迭代直到混沌轨道进入设定区域整个迭代次数作为 密文。后来，针对b a p t i s m 加密方案的速度问题，w a i - k i tw o n g 又提出了一种采 用动态更新的小的查找表的方法改进加密速度t w - k w o n g ，2 0 0 2 】。a p a l a e i o s 等提出采用循环混沌的方法加强b a p t i s m 加密方案的安全性 p a l a e i o s ，2 0 0 2 】。 那么，以上的混沌加密方案的安全性如何呢? d w h e e l e r 在 w h e e l e r ，1 9 8 9 中指出m a t t h e w s 的加密算法在计算机上实现时由于离散映射会产生不可预测的 短周期轨道，不能抵抗己知明文攻击。u u p l e ok o e a r e v 等在 j a k i r a o s k i ，2 0 0 1 】中 对m s b a p t i s t a 提出的混沌加密算法进行了分析，发现该算法不能抵抗已知明文 攻击，通过统计测试表明，只使用大概4 0 0 0 对的明文，密文对就能破解超过9 0 的密钥，同时还指出加密速度和传统的加密算法相比落后两个数量级。w h i 妇 w o n g 在 w - i c w o n g ，2 0 0 1 文中分析指出， b a p t i s t a , 1 9 9 8 中的加密算法有两个主 要的缺点：1 ) 获得的密文集中于迭代中较小的数，密文的分布不是均匀的，这 个性质从密码学的角度考虑是不合适；2 ) 对于一个单独的文本信息快需要产生 一系列的随机数，加密的时间变长，初期产生的随机数可能会重复。g 由v s a l 蛤z 等在【g a l v a r e z ，2 0 0 3 1 也对b a p t i s t a 的加密算法进行了分析，证明该算法使用了 重复密钥，采用三种攻击方法：一次性密码本攻击、根据熵攻击、削弱密文的密 钥恢复攻击。 1 1 2 基于逐段线性混沌映射 逐段线性映射是一个很简单的混沌映射，也很容易在计算机上实现，具有混 沌映射的很多特征，例如随机不变分布和很好的相关函数，很适合作混沌加密和 伪随机编码。许多学者用它构造加密算法和伪随机数发生器。1 9 9 1 年t h a b u t s u 等在e u r o c r y p t 9 1 会议上提出了基于迭代分段混沌映射的一种密钥加密算法 n a b u t s u ，1 9 9 1 1 ，通过迭代混沌系统，使用密钥k 把6 4 位的明文加密成从与明 文对应的2 7 5 个密文中随机抽取的1 4 7 位的密文。加密的过程包括使用7 5 个随 机位的7 5 次迭代。采用的混沌映射如下： 第一章混沌加密算法概述 a 7 5 ：p f 绷， ，i = 0 a j + l 2 1 ( 口一1 ) 口+ l ，：l t = a o 其中，p 表示明文，t 表示密文。解密的过程如下： a o = t i 口a 。，= 0 12 池1 ) “口一1 ) ，：l p = a ，5 e l ib i h a m 在 a i h a m , 1 9 9 1 1 中发现，【h a b u t s u ，1 9 9 1 1 的加密算法存在两个弱点： 1 ) 密文的大小远远大于明文的大小；2 ) 对随机位r i 的每个固定选择，明文和密 文之间存在着一种线性关系，使用固定选择的随机位得到的所有密文出现在一个 很小的范围里。给出了两种攻击方法：选择密文攻击和已知明文攻击 复旦大学的周红等提出了采用分段混沌映射设计前馈型流密码，并且采用扰 动的方法提高加密系统的强度。他的设计从结构上可以分为两种：一种是基于均 匀驱动信号下非线性多次迭代，一种是混沌迭代序列的分区阎非线性处理采用 的混沌映射为； f ( x ，p ) = x p ，x e 【o ，p ) ( x p ) 畦一p ) ，x e p ， ko t p 丢 f 姐一毛p ) ，x e 互1 ，1 】 在文献【周红，1 9 9 7 中使用n 级m 序列c ( t ) 生成输入驱动信号，该信号通过k 次混沌迭代之后输出密钥流；文献周红，1 9 9 8 针对传统混沌逆系统加密方法的 缺陷，提出了基于【周红，1 9 9 7 q ，的映射式的改进方案。文献【周红，1 9 9 8 1 的加 密方案实际上是一种密文反馈式的流密码方案，可以把它看作是文献【周红，1 9 9 7 1 的一种变形。 1 9 9 9 年桑涛等人在周红的研究基础上提出【桑涛，1 9 9 9 ，由予分段线性混沌 映射的逐段线性性，可能存在。潜在”的攻击方案建议采用一种逐段非线性混 沌映射替代。 李树钧在 s h u j u nl i ，2 0 0 3 a 和f 李树钧，2 0 0 3 中对周红提出的两种加密算法 分别进行了分析，发现这两种混沌加密方案都是不安全的。在 s h u j u nl i ，2 0 0 3 a 中，李树钧认为，周的方案采用的分段线性混沌映射( p i c e w i s e l i n e a r c h a o t i c m a p ， p w l c m ) 在有限精度下存在的动态特征退化，破坏了p w l c m 映射迭代产生的 混沌序列密钥流的均匀分布特性，导致许多弱密钥的产生和信息的泄漏，可以采 用一种多分辨率的攻击方法破解。通过采用统计学的方法，李树钧定性的证明了 p w l c m 的在有限精度下的动态特征退化问题。在【李树钧，2 0 0 3 q ，李树钧采 第一章混沌加密算法概述 用相同的方法分析周在【周红，1 9 9 9 中提出的加密方案，得出了类似的结论，提 出了一些可能的改进安全性的措施：提高系统的数字化有限精度：掩盖数字化混 沌系统的扰动结构：避免使用弱密钥；使用更复杂的混沌映射。 e g a r c i a 等在 g a r c i 如2 0 0 2 1 中提出了一种对称加密算法把任意长的比特流 加密成一个实数序列，基于迭代逐段线性映射集。加密过程如下：1 ) 假定初始 信息m 为二进制代码，根据下面的规则把它转化成一系列四种不同的符号6 n 。 仃h = 0 0 _ g l o l 斗窖2 l o 9 3 1 i j q 4 2 ) 选择密钥作为一系列n 索引的逐段线性映射和从0 到n 1 的整数中随机选取 的有限序列( 鼬) 。这些映射由式子：x ”i = i - i x 。一t n 给定。其中， h 。= p lx i lf s l s 2 s 3 s 4 x 。e 厶 x 1 2 x 。el x ne 1 4 n = 晶= 风一1 ，= 1 - i 信息分成长为t 的序列砌 m 2 c r 0 ，盯l ，q i q ，q + ，盯2 l l 盯2 ，- 1 f 一。i 一 第j 个序列通过向后迭代由第j 个密钥指向的映射t 次进行加密。这个过程对 每个序列重复进行直到整个文本都完成为止。解密的过程很直观。只要把第j 个 密文通过向前迭代由 k j 中第j 个密钥指向的映射t 次，初始条件就是x j 。 q a l v a r c z 等在【g a l v a r e z2 0 0 3 1 对 g a r c i2 0 0 2 中的加密算法进行了分析， 指出存在下面的弱点：1 ) 没有指明采用的多大的精度，并且在很多情况下( 3 ) 序列的最后一个或者两个符号会由于有限精度产生的错误不能还原。2 ) 密钥的 一部分是已知的。如果一个或多个线性映射的参数被获知，对应的密钥单元常常 能够正确解密。3 ) 没有指明如何选择合适的密钥。g a l v a r e z 用四种方法破解了 【g a r c t a ，2 0 0 2 中的加密算法：选择密文攻击、选择明文攻击、已知明文攻击、 唯密文攻击。 1 1 3 基于二维混沌映射 基于二维混沌映射的加密方案主要用来对大的数据进行加密，例如对图像的 加密。澳大利亚的ep i c h l c r 和j s c h a r i n g e r 在1 9 9 4 年在 p i c h l e r1 9 9 4 1 q b 首先 j j e l l 厶 靠 2 3 4 p p p 第一章混沌加密算法概述 提出了采用离散二维混沌映射进行图像加密。1 9 9 8 年j f d d r i c h 【f r i d r i c h1 9 9 8 】 在他们的基础上提出基于离散b a k e rm a p 的二维对称加密方案，这个方案具有可 变的密钥长度和块大小，简单快速，很容易在计算机上实现，加密文件和原始文 件大小相同。k i y o s h it a n a k a 等先后提出了两种基于截断b a k e rm a p 的加密算法 i g y o s h it a n a k a ，1 9 9 9 】【k i y o s h it a n a k a , 2 0 0 2 。由于二维混沌映射驱动的伪随机装 置与替换算法组合使用，使得对上述加密算法的分析变得相当困难，目前尚未看 到相关的分析文章出现。 1 1 4 基于其他混沌映射 在i s c a s 2 0 0 0 ，j u i - c h e n g y e n 等提出了一种新的基于密钥的混沌加密算法用 于图像加密，称为c k b a 图像加密算法【j u i - c h e n gy e n ，2 0 0 0 ，假定明文图像的 大小m x n ，选择两个字节k e y l 、k e y 2 ( 8 位) 和一个一维混沌映射的初始条件x 0 作为加密系统的密钥，迭代混沌映射产生混沌序列p w k o( 假定m n i s ) ，通 过1 6 位的二进制表达式i ) = 司b ( 1 6 i + 0 ) b ( 1 6 i + 1 ) b ( 1 6 i + 1 5 ) 产生个伪随机序列 妒u j m ，然后开始加密过程。对于明文像素点f ( x 。y 即x m l ，o y n - 1 ) ， 对应的密文像素点f ( x ，y ) 由下面的规则 决定： i f ( x ，y ) x o rk e y l ，( x ，y ) = 3 、l f ( x , y ) x n o r 蚴，矿似力= 2 。7 l f ( x ，y ) x o r 埏皿，6 ( x ，) ，) = l l f ( x ，y ) x t l i o 四k e y 2 ，b o ，j ，) = 0闻 其中，6 。y ) 2 2 x 6 ( ，) + 6 ( ，+ 1 ) ，2 x + y 解密过程和加密过程类似。 李树钧在 s h u j u nl i ，2 0 0 2 a 中对c k b a 加密算法分析的结果表明c k b a 算 法时不安全的，不能够抵抗已知明文和选择明文攻击。他的分析方法如下：对于 c k b a 算法在有限精度下实现。当有限精度l = 1 6 ，每个混沌轨道的周期长度远小 于2 1 6 ，和许多明文图像的大小相比，这个周期长度是不够安全的，例如，对一 个2 5 6 x 2 5 6 的图像，混沌轨道的总长度是2 1 3 ，对大多数的初始条件，混沌轨 道的周期长度还小于2 1 3 ，所以，从一个大小为2 5 6 x 2 5 6 的已知的加密图像可 以得到更大的加密图像，也就是说，不用获得加密的密钥只从一个2 5 6 x 2 5 6 的 加密图像就可以解密得到所有的明文图像。 e a l v a r e z 等在【e a l v a r e z ，1 9 9 9 中提出了一种混沌加密算法。作者假定传 送的信息a 是一个二进制文件，由一系列的0 和1 组成。发送端t 和接收端r 采用同一个d 维的混沌动态规则：x n + i - - f ( x n , x n 1 ，x n - d + 1 ) 。通过迭代上式产生 实数序列。加密的过程如下：首先，发送端t 选择一个临界点u l ，根据规则x n 。 u l 一0 产生0 和1 的序列c 1 ，然后t 查找与a 开始的b l 字节大 小的段相同的一个序列s t i ，块的大小b 1 是与t 有关的一个固定参数。与这段明 第一章混沌加街算 圭概述 文对应的密文由种子向量x n + l = ( x n ，x n 1 ，x n l d + 1 ) 和临界值u l ，参数 b l 。实数数组( u l ，b l ，x n l ) 通过迭代b 1 次规则f 在接受端解密。当最开始的 b l 字节发送完之后，发送端选择个新的临界值u 2 ，采用类似的规则对接下来 的b 2 个字节产生新的叭序列c 2 。依次类推，直到a 全部发送完毕。c j o c e j a k i m o s k i 等在 a k i m o s k i ，2 0 0 1 】对这个加密算法进行分析，指出该算法的安全 性依赖于末授权的人不知道采用的动态映射规则，这和通常都假定密码分析者知 道加密算法的细节相矛盾。在已知加密算法的细节基础上，这个算法可以很容易 的采用唯密文攻击破解。假定算法采用t e n t 映射，j a k i m o s k i ，2 0 0 1 中还提出了 一种可行的已知明文攻击，通过实验证明只需要很少的密文，明文对在较短的时 间内就能够破解该加密算法。ga l v a r e z 等在【g a l v a r e z ，2 0 0 0 对f e a l v a r e z ， 1 9 9 9 的算法也进行了分析，分别采用选择密文攻击、选择明文攻击、已知密文 攻击、已知明文攻击四种方法破解了该加密算法，也证实这个算法是不安全的， 同时，【g a l v a r e z ，2 0 0 0 文还指出【e a l v a r e z ，1 9 9 9 】中加密算法的几个缺点： 没有确定采用的计算精度，在【e a l v a r e z ，1 9 9 9 中用6 位数字得精度，可以在 1 0 6 内用穷举得方法破解；相关的精确性也没有考虑，如果发送端和接收端采用 不同得精度，即使采用相同的混沌映射规则产生的轨道也会发生很大的变化：没 有指出如何选择合适的密钥等等。李树钧在 s h u j u nl i ，2 0 0 3 a 文中，分析e a l v a r e z ，1 9 9 9 e p 加密算法的结构特点，指出可以把原混沌分组密码改进成混沌 流密码，可以抵抗 g a l v a r e z ，2 0 0 0 文中的四种攻击方法，并且给出了详细的 性能分析。 1 2 设计混沌加密算法的一般思路 基本上，设计混沌密码系统有两种通用的设计思想：1 ) 使用混沌映射构造 伪随机数发生器用产生的伪随机序列对明文流进行加密，加密的方式通常是异 或运算，这种思路对应于传统密码学中的流密码。2 ) 将明文分成固定大小的块， 通过多次迭代反向迭代混沌映射构造替换，置换矩阵对明文块进行加密，这种思 路对应于传统密码学的分组密码。绝大多数混沌加密系统加密和解密时都使用同 样的密钥，属于私钥机密算法，仅有最近提出的少数几个混沌系统属于公钥密码 算法。 1 2 1 混沌流式密码 混沌序列从理论上来说具备下列性质： 1 ) 混沌序列是遍历的，即沿着混沌轨迹对某一函数在时间上的平均等于其 集平均 第一章混沌加密算法概述 2 ) 由于混沌系统在迭代过程中的信息损失，使得混沌序列的信息量渐进趋 于零，因此对混沌序列进行长期预测是不可能的。 以上性质说明作为密码序列，混沌信号不仅具有良好的统计性能而且具有理 论的保密性。 在混沌流式密码中，核心部分在于混沌伪随机数发生器的设计。通常采用三 种方法来设计：1 ) 将混沌系统迭代产生的十进制值，然后抽取其中的某些位构 造随机序列；或者将十进制值转化成二进制，抽取其中某些位构造随机序列。2 ) 把混沌系统的值域划分成k 个区间( k 2 ) ，每个区间对应一个特定的值，根据 迭代结果进入的区间获得对应的值来构造随机序列。有的混沌随机数发生器采取 某个值作为阀限值，通过比较迭代结果和阀限值来构造随机序列，可以看作是这 种方法的一个特例。因为实际上相当于用阀限值把混沌系统的值域划分成两个区 间。3 ) 采用两个或多个混沌系统迭代，对迭代的结果进行一些操作来构造随即 序列，这些操作可以是大小比较，也可以是异或运算。 大部分的混沌流式密码采用单个混沌映射，包括l o g i s t i c 映射及其改进型、 逐段混沌线性映射、逐段混沌非线性映射、二维h e n o n 映射、c h e b y s h e v 映射等 等。对于某些混沌系统，采用单个映射产生的拟混沌轨道和密文之间存在很强的 相关性，这样就使得攻击者利用一些从混沌轨道抽取信息的理论工具来降低攻击 的复杂度，因此。作为加强安全性的通用手段，一些混沌流密码采用了多个混沌 系统。 1 2 2 混沌分组密码 典型的混沌分组密码大多应用在图像加密方面，采用正向迭代一个或者多个 混沌系统，用迭代结果直接构造置换矩阵置乱明文图像的象素，然后利用某些替 换算法压平明文的直方图，或者用迭代结果去控制象素的伪随机置换或替换。 基于逆向迭代的混沌分组密码算法，基本的方法是根据一个混沌映射的逆向 映射进行迭代，明文作为逆向映射的输入，迭代的结果作为密文。解密的时候通 过正向迭代该混沌映射获得。 在混沌分组密码中还有一种方法就是使用混沌系统生成分组密码s 盒。有两 种不同的构造混沌s 盒的方法：动态的混沌s 盒和固定的s 盒。构造动态s 盒 目前已知的方法有三种：1 ) 基于胞元自动机的s 盒：2 ) 基于神经网络的s 盒； 3 ) 基于动态查找表的s 盒。生成固定s 盒的方法主要是由l k o c a r e v 等人提出 的，他们的方法分为两种：1 ) 直接定义一个原混沌映射的离散化一一映射的版 本2 ) 迭代一个混沌映射生成2 n 个顺序置乱的整数1 2 ，2 n ，然后利用它们构造 一个n x n 的s 盒。 第一章混沌加密算法概述 1 3 本章小结 由于混沌系统的动力学特征可以用来实现密码系统要求的密码学特征，混沌 系统可能成为设计新的数字化密码的源泉。在本章中，我们对混沌密码系统的研 究做了一个比较全面的回顾，按照采取的混沌映射的不同对大多数公开发表的混 沌加密算法以及相关的安全性分析进行了分类讨论，在此基础上总结了构造混沌 加密算法的两种基本思路。 第一二章混沌系统在有限精度下的动态特征退化 第二章混沌系统在有限精度下的动态特征退化 由于计算机的有限计算精度在计算机上模拟的数字化混沌系统和理论的实 值混沌系统存在着较大的差异。数字化混沌系统在有限精度下存在严重的动态特 征退化，典型的问题包括短周期性问题、退化的轨道分布和相关特性。 本章首先阐述了混沌系统在有限精度下动力学特征退化产生的原因以及相 关的理论研究成果，然后讨论了一些改善其动力学特征退化的措施，最后，通过 试验的方法研究l o g i s t i c 映射在有限计算精度的动力学特征退化问题。 2 1 动力学特征退化的理论研究 在经典混沌理论中，所有的混沌系统都是定义在连续实数域上的，它们的动 力学特征往往只在具有正的l e b c s g u e 测度的连续相空间中才有意义。在计算机 上通过迭代混沌映射构造加密算法，由于受到计算机有限精度的影响。连续混沌 系统的动力学特征很难保持，导致许多加密算法都是不够安全的。严格的讲，在 计算机上不能出现混沌，因为计算机处理的是有限数字集，初始条件通常都是精 确已知的，计算出来的混沌轨道最终都会循环，成为周期性的，但是从另外一个 方面看，计算机能够在一个较长的时间段里模拟混沌行为 李树钧，2 0 0 4 。 一般来说，计算机上模拟的混沌轨道经过有限次迭代之后都将进入循环状 态，因此，一条拟混沌轨道可以分成两个部分，循环状态之前的轨道和进入循环 状态的轨道，它们分别被称为暂态分支和循环分支。那么，如何估计一条拟混沌 轨道的暂态分支的长度和循环周期的最大值9 均值昵? 这些参数是否足够大以 使得对连续混沌系统的动力学特性的模拟有意义呢? 大量的研究试图对这个问 题给出一个可行的答案，由于缺乏关于数字化混沌系统的遍历性理论，对相关参 数的严格估计( 尤其是平均长度) 非常之难，基于统计的实验方法被广泛采用以 探索这些问题的可能答案。在f r a n n o u r a n n o u ，1 9 7 4 1 和y e l e 、r ) ，【l e v y ，1 9 8 2 】 的早期工作的推动下，关于拟混沌轨道度量方面的一个重要发现标度率( s c a l i n g l a w ) 被勾勒出来并在不同的的混沌系统中反复确认，它实际上也暗示了拟混沌轨 道的分形特征。假设计算精度为l ，令c = 2 - c ，标度率解释了如下的事实： 拟混沌轨道的暂态长度和循环周期的最大值和平均值全部服从指数规律 o ( e d ) ，这里d 是一个由混沌系统方程唯一确定的正的指标量。一般来说， e d ( 2 l 。 有限循环的数量满足量级o ( i ne “) = 0 ( l ) 。 不同的循环周期的出现频率随着循环周期的增加而按指数衰减，这意味 着存在大量的具有短循环周期的拟混沌轨道 第一二章混沌系统在有限精度下的动态特征退化 需要注意的是，上面的结论对某些特殊的混沌映射，如t e n t 映射和b c m o u l i 移位映射是不成立的，这两种映射在有限精度下迭代产生的拟混沌轨道的暂态长 度不会大于有限精度l ，并且最终总会收敛到周期为l 的循环上去。 对于数字化混沌系统产生动态特征退化的的原因，到目前为止，还缺乏比较 完备的系统阐述和结论。定性的讲，当采用定点运算时，由于有限精度表示的值 都是二进制的有理小数形式，不能够正确的描述混沌轨道，迭代过程会产生量化 和舍入误差，最终导致拟混沌轨道偏离真实的轨道，如果有限计算精度为l 。所 有拟混沌轨道的周期不会超过2 0 ，而且遥常都会远小于2 l s h u j u nl i ，2 0 0 3 b 。 有一些学者尝试针对某一类混沌映射在有限精度下的动态特征退化进行研究，取 得了一些比较有用的结论 w a g n e r ，1 9 9 3 i s h u j u nl i ，2 0 0 h 。 2 2 一些可能的改进措施 正如本文第一节提到的，现在密码学安全的概念在混沌理论中还没有对应的 部分，从理论上证明混沌加密算法的安全性存在着相当大的难度。因为这个原因， 所有的针对数字化混沌系统的动态特征退化问题的解决方案都主要是在工程领 域讨论并使用的。几种可能的补救措施主要包括：使用更高的计算精度、采用多 个混沌系统替代单一的混沌系统、对数字化混沌系统进行随机扰动。 采用更高的计算精度能够提高拟混沌轨道周期的平均长度，使密钥熵交大。 这似乎是一种最简单最方便的增强数字化混沌密码安全性的方法。在文献 w h e e l e r ，1 9 8 9 中作者建议使用更高的有限精度改善短周期给m a t t h e w s 混沌流密 码带来的安全性问题。但是，采用更高的计算精度不能真正有效得增加每条拟混 沌轨道的长度，仍然存在着大量的拟混沌轨道，它们的长度较所有拟混沌轨道的 平均值短得多。文献 w a g n e r ，1 9 9 3 对l o g i s t i c 在不同的机型和不同的精度下( 单 精度、双精度) 迭代结果的统计分析也表明，提高计算精度对l o g i s t i c 的动态特征 退化的改善并不显著。对于逐段线性混沌映射，提高计算精度不能有效得改善弱 密钥的不均匀分布，在原来精度下的弱密钥一点都得不到加强 s h u j u nl i ， 2 0 0 3 a 李树钧，2 0 0 3 。 对于很多采用单一混沌系统的密码算法，有限的计算精度导致混沌轨道并不 能实现真正的复杂的混沌现象，密文和混沌轨道之间存在很强的相关性，这样， 使用一些从混沌轨道中提取信息的理论工具 s h u j u nl i 2 0 0 1 a ，攻击者就可能 从密文中得到一些关于初始变量或者控制参数的有用信息以降低攻击复杂度。因 此，采用多个混沌系统替代单一的混沌系统，就可能增强混沌密码系统的安全性， 因为多个混沌轨道的叠加能更有效的掩盖密钥信息，降低密文和混沌轨道之间的 相关性，使得上述的密码分析变得更难。尤其是当这些混沌系统具有不同的初始 条件和不同的迭代方程的情况下。这样的一个想法已经在一些数字化混沌密码中 第二章混沌系统n ：青l 限精度下的动态特缸退化 得到应用【p h i l i p ，2 0 0 1 s h u j u nl i ，2 0 0 1b 】 s h u j u nl i 2 0 0 2 ，部分的理论和试 验分析暗示两个混沌系统可能已经足够提供可接受的安全性 s h u j u nl i ，2 0 0 1 b 1 。 量化噪声的随机扰动模型在理论界已经被广泛采用已研究数字化混沌系统 的动力学特征，工程中使用的扰动策略可以看作是随机扰动模型的一个应用。扰 动策略的基本思想是运行一个在相应的离散空间上满足均匀分布的简单伪随即 数发生器，如卜序列，产生一个伪随机的小扰动信号，以异或的方式或者其他扰 动函数叠加到原有的混沌轨道上去，这种叠加每隔k 1 次混沌迭代执行一次。 按照扰动对象的