中国科学院计算技术研究所硕士学位论文有限精度下一种混沌密码算法安全性分析及其应用姓名：刘建夏申请学位级别：硕士专业：计算机应用技术指导教师：高庆狮20040701摘要摘要混沌系统具有良好的随机性、轨道不可预测性、对初始条件和控制参数敏感等一系列的特性，这些特性和密码学的很多要求吻合混沌理论和密码学相结合，产生一门新的交叉学科：混沌密码学但是受有限计算精度的影响，在计算机上实现的数字化混沌系统，其动力学特征出现了严重的退化本文首先介绍了混沌系统和密码学之间的紧密联系，然后综合分析了近年来提出的混沌加密算法及其相关的安全性分析，总结了设计混沌密码的一般思路接下来重点分析有限计算精度对混沌密码系统安全性的影响以及增强混沌密码系统安全性的一些可行措施，在此基础上对Logistic混沌映射在有限精度下的动态特征退化问题做了初步的研究本文对Yen．Guo提出的一种混沌加密算法进行了详细的安全性分析，发现这种混沌加密算法在选择明文攻击下是不安全的，并给出了可能的改进措施提出了一种基于改进型Logistic混沌映射的伪随机数发生器，理论和试验分析表明生成的伪随机序列具有良好的密码学特征，以此为基础设计并实现了一种新型的混沌流密码算法，试验结果表明该算法具有较高的安全性。
关键字：混沌、密码学、密码分析、有限精度、Logistic映射-蕾-AbstractOneChaoticCiphers’SecurityAnalysisUnderFinitePrecisionandItsApplicationLiuJianxia(ComputerApplication)DirectedbyGaoQingShiSomeinnerpropertiesofchaossuchasrandomness，unpredictableorbitsandinitialvariablessensitivityaccorddeeplywithrequirementsofcryptography．Betweenchaosandcryptographanewcross-disciplinaryfieldcalledchaotic-cryptographgenerates．Butbecauseoffiniteprecision，whendigitalchaosrealizesincomputeritsdynamicpropertiesdescendsbadly．WefirstintroducethenaturaIrelaUonbetweenchaosandcryptographyandthengiveacomprehensivesurveyaboutmanychaoticciphers’designschemeandsecurityanalysis．OuremphasisiStheinfluenceoffiniteprecisiontochaoticciphersandremediestoenhancesecurityofchaoticciphers．Basedonthesurveywegiveaninitialinvestigationaboutlogisticmap’Sdynamicpropertiesdegradationunderfiniteprecision．ThisthesisanalyzesonechaoticcipherproposedbyYen—GUOjndetailsandfindsitiSinsecuretochosenplaintextattack．Also．someremediesaregiventoimproveitssecunty．BasedonthemodifiedLogisticmapweproposeapseudo．randomnumbergenerator(PRNG)．TheoreticaIandexpedmentalresultsshowthisPRNGhasgoodcryptographicproperties。
UsingthisPRNGwedesignandimplementaRoveIchaoticstreamcipherwhichshowsgoodsecurityunderexperimentaltests．Keyworde：Chaos．CryptographCryptanalysis，FinitePrecision．LogisticMap声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果就我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示了谢意作者签名：a关于论文使用授权的说明日期：咄Z，2，中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存该论文储虢专惮及导师躲乏叶吼少峨7‘沙弓I言研究背景和课题意义引言混沌是指在确定性非线性系统中存在的不需要附加任何随机因素即可出现类似随机性的行为，混沌理论作为自然科学的一个分支，随着现代科学技术的进步，尤其是在计算机技术的出现和普遍应用基础上开始快速的发展起来。
混沌系统的最大的特点就是对初始条件和控制参数的极端敏感性，初始条件或者控制参数有非常细微的变化都会导致最终结果的巨大差异，这样，由混沌映射产生的混沌轨道随着时间的流逝变得越来越“不可预测”混沌理论最广为人知的一个科学假设就是“蝴蝶效应”除了对初始条件的敏感性之外，混沌系统还具有的基本特性包括遍历性、混和性、不确定性等混沌系统的基本特性和密码学中的混淆(confusion)和扩散(diffusion)概念都可以联系起来，在Shanon的经典论：Lr‘CommunicationTheoryofSecrecySystems”『Shanon1949]中就曾经提到好的保密系统中所需要的好的混和变换(mixingtransation)可以使用基本的“rolled-outandfolded．over”操作得到，而在混沌系统中，许多经典的映射，例如Logistic映射、Baker映射、Smale马蹄映射等引发混沌的原因就是“拉伸并折叠(g吨ch．and-fold)”，显然Shanon所说的好的混和变换可以看作是限制在有限空间内的混沌映射(当然这不是严格意义上的)从另一方面看，好的密码系统对明文加密带来的密文混沌状态，非常类似于复杂动力系统产生的混沌现象，从算法的角度看，好的密码系统也可以看成是一个混沌或者拟混沌系统。
下面的这张图给出了混沌和密码学一个形象的比较：图1．1混沌系统和密码算法的对比由于混沌系统和密码学之『自J存在着如此紧密的联系，采用混沌系统去设计新的密码算法的想法就很自然了自从1989年第一篇采用混沌系统构造加密算法的论文[Matthews，1989]发表以来，大量的混沌密码算法以及相关的分析成果被提出关于混沌密码学的研究有助于丰富传统密码学的内容，为好的密码系统的设计提供更多的设计思路和手段，可以丰富离散时间和离散空间混沌系统的理论知识当混沌系统在计算机、DSP、单片机等数字设备上实现时，由于受到有限计算精度的影响，导致混沌系统的动力学特征出现了比较严重的退化，典型的问题包括短周期问题、退化的轨道分布和相关特性研究混沌系统在有限计算精度下的动态特征退化问题，采取一些措施改善其动力学特征，对增强混沌密码系统的安全性和推广应用都具有很重要的意义本文的研究思路和主要工作大部分混沌密码系统在设计的时候，对数字化混沌系统出现的动力学特征退化问题缺乏足够的重视，导致相当一部分混沌加密算法从严格密码学的意义上来说是不安全的由于现有的关于数字化混沌系统动力学特征退化的理论研究还很不完善，缺乏完备的理论体系，从理论上对混沌密码系统的安全性进行分析存在着相当大的难度。
在本文中，我们主要使用试验的方法研究数字化混沌系统的动力学特征退化问题，并尝试从三个方面展开工作：数字化混沌系统动力学特征退化的试验分析、数字化混沌密码系统的安全性分析、设计混沌密码系统的新思路第一个方面的研究是后面两个研究的基础，而第二个方面的研究又是第三个方面的另外一个基础总的来说，本文主要的工作可以总结为下面四点：1我们对混淹密码学这个研究方向做一个较为详细的回顾按照采取的混沌映射的不同对各种混沌加密算法进行分类，讨论了相关的安全性分析，并总结了设计混沌加密算法的两种一般思路2．我们通过试验的手段对Logistic映射在有限精度下动态特征行为做了初步的分析发现在定点运算和单精度浮点运算下，产生的混沌轨道会以相当大的概率进入短周期循环或者收敛到一个固定点，在双精度浮点运算下能够较好的模拟混沌行为3．我们对Yen．Guo提出的一种混沌加密算法进行详细的安全性分析，发现算法存在两个严重的缺陷，我们设计了一种选择明文攻击方法成功的破解了这个算法，提出了一种密文反馈的方法加强Yen-Guo混沌加密算法的安全性4．我们提出了一种基于改进型Logistic映射的伪随机数发生器，从理论上引言证明该随机数发生器产生的二进制序列具有良好的密码学性能。
以此为基础设计了一种新型的混沌序列密码算法，试验结果表明这个加密算法可以获得较高的安全性本文的组织本文的正文部分是这么组织的：第一章，概述混沌密码学的研究状况第二章，重点介绍数字化混沌系统在有限精度下的动态特征退化问题，采用试验的手段分析Logistic映射的动态特征退化问题第三章，对Yen-Guo提出的一种基于Logistic映射的混沌加密算法的安全性分析，针对算法的弱点提出了改进意见第四章，提出一种基于改进型Logistic映射的伪随机数发生器，以此为基础设计了一种新型的混沌流密码算法第五章，对所做工作的总结并对将来的研究方向进行展望第一章福沌加密算法概述第一章混沌加密算法概述混沌密码学兴起于1990年前后1989年R．Matthews提出了第一个混沌加密算法，采用Logistic混沌映射进行加密算法设计，此后，混沌密码学分别在物理学、电子工程和密码学等多个领域同时发展起来，越来越多的混沌加密方案被提出，混沌加密开始应用在保密通信、图像，视频加密和数字水印等领域在本章的第一部分，我们按照采取的混沌映射的不同，对从1989年以来在各种文献中公开发表的混沌加密算法做了一个比较详细的综述，重点讨论相关的安全性问题。
在第一部分的基础上，总结设计混沌加密算法的两种一般思路§1．1混沌加密算法的分类综述按照混沌加密算法采取的混沌映射的不同，可以将混沌加密算法分成以下几类：基于Logistic映射的混沌加密算法、基于逐段混沌映射的混沌加密算法、基于二维混沌映射的混沌加密算法以及基于其他混沌映射的混沌加密算法这样分类的原因是因为相同的混沌映射在有限精度下的动态退化特征相近，基于同种混沌映射构造的加密算法在有限精度下表现的安全性相似§1．1．1基于Logistic映射Logistic映射是一个简单的混沌系统，也被称为虫121方程20世纪50年代，有好几位生态学家就利用过这个简单的差分方程来描述种群的变化：Xn+l=僻n(1-Xn)p∈(O’4)式中Xn表示当年的种群数，Xn+l便是下年的种群数，“为增长参数Logistic映射已经从理论上证明具有典型的混沌动态特征，当“选择在【3．56999456⋯，4】之间时，Logistic映射工作于混沌态【黄润生，2000]Logistic映射只包括乘法和减法运算，在计算机上很容易实现Logistic映射用在混沌加密系统中，通常把初始条件)(0作为密钥，因为初始条件即使有非常小的差别，迭代后产生的混沌序列都会差别很大。
控制参数“也可以用来作为隐藏参数或者是密钥但是同时采用‰和“作密钥可能不是足够安全的[Kocarev2001]Logistic映射既可以用来设计分组加密算法，也可以用来设计流加密算法1989。