（计算机科学与技术专业论文）混沌密码研究与实现.pdf

国防科学技术大学研究生院学位论文 摘要 随着信息化的不断发展和迅速普及，信息安全问题日益突出，已经成为国民经济正常 运行和国家安全的一个重要问题。密码是信息安全的核心，混沌密码是密码学的一个新的 研究方向。本文首先介绍了密码理论、混沌发展历史和混沌理论，对混沌理论和相关的传 统理论之间的关系进行了初步归纳分析，在理论分析了混沌数字化过程中的问题的基础 上，分析了l o g i s t i c 映射在混沌密码应用中由于其分布不均匀而导致的平衡性问题，指 出这不符合s h a n n o n 提出的指导密码设计的两个基本原则之一的扩散原则，并且用数据试 验的方法对其进行了分析和描述，提出了一些改进措施并进行了性能仿真。在此基础上， 设计并实现了混沌密码系统，并且进行了安全性分析和实验。本文的主要成果包括以下几 个方面： 首先，结合密码学理论、伪随机序列理论、非线性理论、线性复杂度理论、复杂系统 理论和随机性理论，归纳阐述了混沌密码学与它们的关系。 其次，对混沌密码系统在计算机上有限精度实现情况下的性能退化问题进行分析，并 提出相应对策以减少有限精度效应提高其安全性和可用性。结合l o g i s t i c 映射，进行大 量的数据测试和分析，提出了改进措施并进行了性能分析。 再次，基于已有的理论分析和数据分析，根据提出的改进措施，设计了多混沌密码系 统并进行了实现，进行了安全性分析和加解密实验。 关键词：混沌密码，不变分布，数字混沌，有限精度，扩散，扰乱 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t a l o n g 、析mt h ec o n t i n u o u sd e v e l o p m e n ta n dt h er a p i d l yg r o w i n gp o p u l a r i t yo f i n f o r m a t i o nt e c h n o l o g y , t h ep r o b l e mo fi n f o r m a t i o ns e c u r i t yi sb e c o m i n gi n c r e a s i n g l y p r o m i n e n t , i th a sb e e nb e c o m ea ni m p o r t a n ti s s u eo ft h en o r m a lo p e r a t i o n so ft h e n a t i o n a le c o n o m ya n dn a t i o n a ls e c u r i t y c r y p t o g r a mi st h ec o r eo fi n f o r m a t i o n s e c u r i t y , c h a o s - b a s e de n c r y p t i o ni san e wr e s e a r c hd i r e c t i o no fc r y p t o g r a m i nt h i s d i s s e r t a t i o n , a tf i r s t ，s o m ec r y p t o g r a me l e m e n t s ，t h ec h a o st h e o r ya n dt h eh i s t o r yo f t h e d e v e l o p m e n to ft h ec h a o sw e r ei n t r o d u c e d , t h er 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 d t h er e l a t e dt r a d i t i o n a lt h e o r yw a sp r e l i m i n a r ys u m m a r i z e da n da n a l y s i s e d o nt h eb a s e o fa n a l y s i s i n gt h ep r o b l e m si nt h ep r o c e s so fp r o d u c i n gd i g i t a lc h a o si nt h e o r e t i c a l l y , t h ed i s s e r t a t i o na n a l y z e st h a tt h ep r o b l e mo fq u a l i t yo fb a l a n c er e s u l tb yt h eu n e v e n d i s t r i b u t i o no fl o g i s t i cm 印u s e di nt h ec h a o s - b a s e de n c r y p t i o n t h e n , t h ed i p l o m a t h e s i sp o i n t e do u tt h a tt h i sw a sn o tc o n s i s t e n tw i t ht h ep r i n c i p l eo fd i f f u s i o nw h i c hi s o n eo ft h et w ob a s i cp r i n c i p l e so fc o a c h i n gp a s s w o r dd e s i g np r o v i d e db ys h a n n o n , b e s i d e s ，t h ed i s s e r t a t i o na n a l y z e da n dd e s c r i b e dt h ep r o b l e mb yu s i n go ft h em e t h o do f d a t ae x p e r i m e n t a t i o n , t h e n , b r o u g h tf o r w a r dan u m b e ro fm e a s u r e sf o ri m p r o v i n gt h e p e r f o r m a n c ea n dl a yo u ti t sc a p a b i l i t yb yu s i n go fc o m p u t e rs i m u l a t i o n , o nt h i s f o u n d a t i o n , c h a o sc r y p t o g r a p h yw a sd e s i g n e da n dc a r r i e do u t , t h ed i s s e r t a t i o na l s o d e s c r i b e ds a f e t ya n a l y s i sa n de x p e r i m e n t s n l em a i na c h i e v e m e n t sc o n t a i n e di nt h i sd i s s e r t a t i o na r ea sf o l l o w s ： f i r s t l y , c o m b i n i n gc r y p t o g r a p h yt h e o r y , t h et h e o r yo fp s e u d o r a n d o ms e q u e n c e ， t h en o n l i n e a rt h e o r y , l i n e a rc o m p l e x i t yt h e o r y , c o m p l e xs y s t e mt h e o r ya n ds t o c h a s t i c t h e o r y ，t h i sd i s s e r t a t i o ns u m m e da n dd e s c r i b e dc h a o t i cc r y p t o g r a p h ya n dt h e i r r e l a t i o n s s e c o n d l y , t h ep e r f o r m a n c ed e g r a d a t i o ni s s u e so ft h el i m i t e da c c u r a c yt h a tc h a o s c i p h e r sw a sa c h i e v e m e n to nc o m p u t e rs y s t e m sw e r ea n a l y s i e d t h e ns o m ep r o p o s e a p p r o p r i a t em e a s u r e sw e r eb r o u g h tf o r w a r dt or e d u c et h ee f f e c t so fl i m i t e da c c u r a c y a n di m p r o v et h e i rs a f e t ya n da v a i l a b i l i t y c o m b i n e dl o g i s t i cm a p ，b a s e do nal o to f d a t at e s t i n g sa n da n a l y s i s ，p r o p o s em e a s u r e st oi m p r o v et h ep e r f o r m a n c ew e r e b r o u g h tf o r w a r da n da n a l y s i e d 似l y ，b a s e do nt h ee x i s t i n gt h e o r e t i c a la n a l y s i sa n dd a t aa n a l y s i s ，a c c o r d i n gt o t h em e a s u r e sf o ri m p r o v i n gt h ed e s i g no ft h es y s t e m ，m u l t i c h a o t i cc i p h e r sw a s d e s i g n e da n da c h i e v e d ，t h e n ，as e c u r i t ya n a l y s i sa n dt h ee x p e r i m e n t so fe n c r y p t i o n a n dd e c r y p t i o nw e r ea c c o m p l i s h e d k e yw o r d s ：c h a o s ，l n v a r i a n tp r o b a b i l i t yd i s t r i b u t i o n ，d i g i t a lc h a o s ， l i m i t e dp r e c i s i o n ，d i f f u s i o n ，c o n f u s i o n 第页 国防科学技术大学研究生院学位论文 图目录 图1 1 混沌密码及相关领域图圈2 图4 1 “= 4 ，x o = o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时的散点连线图2 5 图4 2i _ t - - 4 ，x o = o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时的散点分布图2 5 图4 3p = 3 5 6 9 9 4 5 6 0 0 0 0 0 0 1 ，x - o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时的散点分布图2 7 图4 4 = 3 6 6 9 9 4 5 6 0 0 0 0 0 0 1 ，x = o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时的散点分布图2 8 图4 5 “= 3 7 6 9 9 4 5 6 0 0 0 0 0 0 1 ，x - o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时的散点分布图2 8 图4 6p = 3 8 6 9 9 4 5 6 0 0 0 0 0 0 1 ，x - - o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时的散点分布图。2 8 图4 7 斗= 3 9 6 9 9 4 5 6 0 0 0 0 0 0 1 ，x = o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时的散点分布图2 9 图4 8p = 4 ，x o = o 9 7 7 3 1 7 7 7 7 7 7 0 0 0 时在阈值范围内的散点分布图3 0 图4 9l , t = 3 9 7 7 3 1 7 7 7 7 7 7 1 3 3 、样本数为l x l 0 5 时的不变分布图3 2 图4 1 0p = 3 9 7 7 3 1 7 7 7 7 7 7 1 3 3 、样本数为l x l 0 5 时的不变分布图3 2 图4 1 1 改进后在粒度0 0 0 1 时的不变分布图一3 3 图4 1 2 改进后在粒度0 0 0 1 时的不变分布图的局部放大图一3 3 图5 1 混沌序列加密方法3 7 图5 2 混沌序列解密方法3 7 图5 3 多混沌密码设计。3 9 图5 4p = 3 9 7 7 3 1 7 7 7 7 7 7 1 3 3 ，x o = o 2 2 2 2 2 2 2 2 2 2 2 5 5 5 原序列自相关特性分析一4 3 图5 5p = 4 ，x o = o 9 7 7 3 1 7 7 7 7 7 7 1 3 3 原序列自相关特性分析。4 3 图5 6 图5 4 和图5 5 产生的原序列互相关特性分析j 。4 4 图5 7p = 3 9 7 7 31 7 7 7 7 7 7 1 3 3 ，x o = o 2 2 2 2 2 2 2 2 2 2 2 5 5 5 改进后序列自相关特性分析4 4 图5 8i t = 4 ，x o - - o 9 7 7 3 1 7 7 7 7 7 7 1 3 3 改进后序列自相关特性分析4 4 图5 9 图5 7 和5 8 产生的混沌序列的互相关特性分析4 5 图5 1 0 明文4 6 图5 1 1 按表5 4 设置的混沌初始参数加密后的密文4 6 图5 1 2 按表5 3 设置的混沌初始参数加密后的密文4 7 图5 1 3 微小参数改变后解密原密文后的结果。4 7 第i i i 页 国防科学技术大学研究生院学位论文 表目录 表4 11 t = 4 不同初始值的散点区间分布2 6 表4 2i t = 3 6 6 9 9 4 5 6 7 2 7 6 5 2 5 不同初始值的散点区间分布2 6 表4 31 t = 3 9 7 7 3 1 7 7 7 7 7 7 1 3 3 不同初始值的散点区间分布2 6 表4 4 l a = 3 8 0 0 0 0 0 0 0 0 0 0 0 0 0 不同初始值的散点区间分布2 7 表5 1 混沌加密与传统密码算法的相似点与不同点【3 】3 6 表5 2o 1 平衡性分析4 1 表5 3 相关系数的量化意义。4 3 表5 4 混沌加密初始参数设置。4 5 表5 5 微小改变的混沌加密初始参数设置4 7 第i v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目丝叠生驻立丛l 一一 学位论文作者签名： 挡：缉 j j 日期：矿。7 年，夕月) 多口 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子之档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 国防科学技术大学研究生院学位论文 第1 章绪论 本章首先介绍了课题的研究背景和课题意义，然后介绍了课题的研究现状与内容、课 题的主要工作和本文的主要成果，最后介绍了本文的结构。 1 1 研究背景与课题意义 随着信息化的不断发展和迅速普及，信息安全问题日益突出，已经成为国民经济正常 运行和国家安全的一个重要问题。而密码是信息安全的核心，因此设计具有自主知识产权 的新型高性能的密码系统是亟待解决的重要问题u 】。在国家的“十一五刀国家密码发展基 金密码理论研究课题选题指南中，在新技术在密码研究中的应用项中包括了混沌密码在密 码中的应用的选题，其中复杂度理论在密码设计中的应用项中包括了复杂度理论和密码特 性分析研究；密码系统形式化描述和可证明安全模型研究；具有良好密码学性质的非线性 函数研究；良好密码学性质的置换群研究等的选题。 s h a n n o n 早在其经典文章【2 】中就已将类似于混沌理论具有的如混合、初值参数敏感性 等基本特性应用到密码学中，并提出了密码学中用于指导密码设计的两个基本原则：扩散 ( d i f f u s i o n ) 和扰乱( c o n f u s i o n ) 。扩散是将明文冗余度分散到密文中使之分散开来，以便隐藏 明文的统计结构，实现方式是使得明文的每一位影响密文中多位的值。扰乱则是用于掩盖 密钥和密文之间的关系，使密钥和密文之间的统计关系变得尽可能复杂，导致密码攻击者 无法从密文推理得到密钥l l 一。 混沌是确定性系统中的一种伪随机的运动。混沌系统都具有如下基本特性：有界性、 遍历性、内随机性、分维性、标度性、普适性、统计特征。混沌系统所具有的一些基本特 性恰好能够满足保密通信及密码学的基本要求：混沌动力学方程的确定性保证了通信双方 在收发过程或加解密过程中的可靠性：混沌轨道的遍历性( 混沌运动在其混沌吸引域内是各 态历经的，即在有限时间内混沌轨道经过混沌区内每一个状态点) 及内随机性( 它是由系统 对初值的敏感性( 即不可预测性) 造成的) 正好满足s h a n n o n 提出的密码系统设计的第一个基 本原则一一扩散原则；混沌吸引子的拓扑传递性与混合性，正好满足s h a n n o n 提出的密码 系统设计的第二个基本原则一一扰乱原则【l j 。 自1 9 8 9 年r m a t h e w s ，d w h e e l e r ，l m p c c o r a 和c a r r o l l 等人首次把混沌理论使用到序 列密码及保密通信理论以来，数字混沌密码系统和基于混沌同步的保密通信系统的研究已 引起了相关学者的高度关注【3 l ，这些年的研究取得了许多可喜的进展。但目前还没有建立 一套完善的混沌密码学理论，也没有完善的混沌密码学安全性评估体系，因此我们的研究 从理论和实践入手，以期能为完善混沌密码学理论体系提出一些初步的参考并设计一种相 对安全性较好的混沌密码系统。 第1 页 国防科学技术大学研究生院学位论文 1 2 课题研究历史与现状 随着人们对混沌系统的了解，越来越多的研究人员开始尝试基于混沌系统设计加密算 法。1 9 8 9 年到1 9 9 3 年间是对数字混沌加密系统研究的最初阶段，数字混沌密码在这个时 期有过短暂的繁荣，这段时间里出现了大量的有关数字混沌加密的论文【5 ，6 。然而在随后 几年中由于人们对混沌系统数字化后的退化进行的分析暴露了数字混沌加密系统的很多 安全缺陷【6 ，8 ，9 ，1 0 1 1 ，2 1 ，所以在1 9 9 3 年到1 9 9 6 年间在数字混沌加密领域的进展不明显。1 9 9 7 年后，人们开始尝试通过对数字混沌加密系统进行改进来弥补己知的和未知的安全缺陷， 以便得到更加健壮的加密算法。这个时期有大量的研究结果发表 1 3 - 2 1 l ，虽然一些新提出的 数字混沌密码还是很快被破解了，但是仍有很多直到目前尚未被攻破。同时出现了一些设 计混沌密码的通用方法，这些方法往往对系统的安全性做了相当细致的分析，从而具有较 高的实用价值和安全性，如使用由混沌系统生成的( 固定的或者动态更新的) s 盒的分组密 码等等【4 】。 混沌密码学是一个多学科交叉的领域，其与混沌理论、通信理论、现代密码学的研究 领域相关性如下图所示： 图1 1 混沌密码及相关领域图瞄l 目前混沌密码学大致可以分为两个大的研究方向：( 1 ) 以混沌同步技术为核心的混沌保 密通信系统，主要基于模拟混沌电路系统；( 2 ) 利用混沌系统构造新的流密码和分组密码， 第2 页 国防科学技术大学研究生院学位论文 主要基于计算机有限精度下实现的数字化混沌系统嘲。 实际上，其他很多领域也开展了利用混沌系统应用的研究工作，不少研究结果可资混 沌密码学借鉴。比较重要的研究包括1 4 捌： l 、混沌通信( 混沌调制、混沌键控、混沌扩频、混沌掩盖) 2 、混沌伪随机序列( 与混沌扩频有密切关系) 3 、混沌信号检测( 与混沌密码分析相关) 4 、混沌数字水印( 大部分思路与数字混沌密码类似) 但是，目前还没有建立一套完善的混沌密码学理论，也没有完善的混沌密码学安全性 评估体系。 1 3 课题研究的主要工作 我们从理论和实践入手，结合混沌理论、密码学理论进行研究，探索数字混沌产生过 程，对数字混沌产生过程中出现的问题进行深入分析，以期能为完善混沌密码学理论体系 提出一些初步的参考，提出改进措施设计一种相对安全性较好的混沌密码系统并进行应用 实验研究。具体的研究内容： 1 、混沌理论和密码学理论的结合：基于混沌系统特性，结合密码学中的密码设计模 式理论和密码分析理论，对混沌密码学的理论基础进行阐述，对混沌密码系统在 计算机上有限精度实现情况下的性能退化问题进行分析，并提出相应对策以减少 有限精度效应提高其安全性和可用性。 2 、混沌密码系统的产生和设计：基于混沌密码理论，根据对混沌密码系统在计算机 上有限精度实现情况下退化及对策的分析和混沌密码系统的安全性分析，选择合 适的混沌系统，设计出一种安全性较好的混沌密码系统。 3 、混沌密码系统的实现和分析：根据设计出的混沌密码系统，进行编码实现，结合 实验分析其安全性，为增强敏感数据的安全性提供一定的参考和借鉴。 1 4 本文的主要成果 1 、结合密码学理论、伪随机序列、非线性、线性复杂度、复杂性和随机性，归纳阐 述了混沌密码学与它们的关系。 2 、对混沌密码系统在计算机上有限精度实现情况下的性能退化问题进行分析，并提 出相应对策以减少有限精度效应提高其安全性和可用性。结合l o g i s t i c 映射，进 行大量的数据测试和分析，提出了改进措施并进行了性能分析。 3 、基于已有的理论分析和数据分析，根据提出的改进措施，设计了多混沌密码系统 并进行了实现，进行了安全性分析和加解密实验。 第3 页 国防科学技术大学研究生院学位论文 1 5 本文结构 全文共分6 章，每一章的内容总结如下： 第1 章为绪论，介绍了课题研究的背景与课题意义、课题研究现状及课题的研究内容、 课题研究的主要工作和本文的主要成果。 第2 章我们首先概述了密码学的一些基本知识，并介绍了密码系统理论安全性和实际 安全性的相关知识。认真探索了混沌的发展历史，列举了目前提出的混沌定义，并结合混 沌的特征对混沌定义中的各部分之间的关系和各定义之间的联系进行了较为全面的综合。 对目前己有混沌的定性和定量研究方法描述进行了综述，指出了由于混沌目前没有统一严 格的数学定义，这些方法都只是是从不同的侧面反映了混沌系统的复杂性，不具有通用性， 在实际应用中，应综合采用多种方法研究混沌特性。 第3 章首先对混沌密码相关的理论：非线性与线性、混沌与非线性、线性复杂度、复 杂性、随机性的关系进行了归纳和分析，初步描述了混沌与复杂性和随机性的关系。随后 总结了数字混沌系统的实现途径，描述了数字混沌系统在实现过程的中的问题，并就如何 构造好的混沌密码系统归纳了一些方法。 第4 章在第3 章理论分析的基础上对混沌加密中广泛采用的l o g i s t i c 映射进行了详 细的数据分析，深入分析了其在混沌加密应用中直接运用的潜在危险，并以详细的数据和 m a t l a b 图形模拟说明了l o g i s t i c 映射在区间分布的不均匀，提出了改进措施并进行了性 能仿真，对仿真中发现的问题进行了更深入的分析并提出了进一步的解决办法。最后从不 变分布的角度对改进前后的性能进行了理论分析和模拟。 第5 章在前面理论分析是数据实验的基础上，归纳总结了混沌加密的原理、方法和步 骤，并且基于l o g i s t i c 混沌映射设计实现了多混沌加密系统，并且进行了安全性分析和 加解密实验。 第6 章进行了全文总结并提出了以后的研究方向。 第4 页 国防科学技术大学研究生院学位论文 第2 章混沌密码学相关基础理论 本章首先概述了密码学的一些基本知识和密码系统安全性的相关知识。然后 探索了混沌的发展历史，列举了目前提出的混沌定义，并结合混沌的特征对混沌 定义中的各部分之间的关系和各定义之间的联系进行了较为全面的综合。最后对 目前己有混沌的定性和定量研究方法描述进行了综述。 2 1 1 概述 2 1 密码理论 密码学( c r y p t o l o g y ) 是研究信息系统安全保密的科学，它分为密码编码学 ( c r y p t o g r a p h y ) 和密码分析学( c r y p t a n a l y t i c s ) 。密码编码学主要研究对信息进 行编码，实现对信息的隐蔽。密码分析学主要研究加密消息的破译或消息的伪造。 消息被称为明文( p l a i n t e x t ) 。用某种方法伪装消息以隐藏它的内容的过程 称为加密( e n c r t p t i o n ) ，被加密的消息称为密文( c i p h e r t e x t ) ，而把密文转变为 明文的过程称为解密( d e c r y p t i o n ) 。密码算法( c r y p t o g r a p h ya l g o r i t h m ) 是用于 加密和解密的数学函数。密码员对明文进行加密操作时所采用的一组规则称作加 密算法( e n c r y p t i o na l g o r i t h m ) 。所传送消息的预定对象称为接收者 ( r e c e i v e r ) 。接收者对密文解密所采用的一组规则称为解密算法( d e c r y p t i o n a l g o r i t h m ) 。加密和解密算法的操作通常都是在一组密钥的控制下进行的，分别 称为加密密钥( e n c r y p t i o nk e y ) 和解密密钥( d e c r y p t i o nk e y ) 瞄】。 基于密钥的算法，按照密钥的特点分为对称密码算法( s y m m e t r i cc i p h e r ) 和非对称密钥算法( a s y m m e t r i cc i p h e r ) 。对称密码算法又称传统密码算法 ( c o n v e n t i o n a lc i p h e r ) ，就是加密密钥和解密密钥相同，或实质上等同，即从 一个易于推出另一个，又称为秘密密钥算法或单密钥算法。非对称密钥算法的加 密密钥和解密密钥不相同，从一个很难推出另一个，又称公开密钥算法 ( p u b l i c k e yc i p h e r ) 。公开密钥算法用一个密钥进行加密，而用另一个进行 解密。其中的加密密钥可以公开，又称公开密钥( p u b l i ck e y ) ，简称公钥。解密 密钥必须保密，又称私人密钥( p r i v a t ek e y ) ，简称私钥。 按照明文的处理方法可分为分组密码( b l o c kc i p h e r ) 和流密码( s t r e a m c i p h e r ) 。分组密码是将明文分成固定长度的组，用同密钥和算法对每一块加 密，输出也是固定长度的密文。流密码又称序列密码，每次加密一位或一字节的 明文。 第5 页 国防科学技术大学研究生院学位论文 对称密钥密码可以用分组加密方式，每次对一块数据加密，如 d e s ，i d e a ，r c 6 ，r i j n d a e l 等。也可以用流密码每次对一位或一字节加密。 公开密钥密码大部分是分组密码，只有概率密码体制属于流密码。常用于数 字签名，身份认证。如r s a ，e c c ，e i g a m a l 等。 2 1 2 密码系统的安全性 一个完整的密码体制可由一个五元组似k 玩d m ) 来描述。m 是所有可能 的明文组成的有限集，称为明文空间；c 是所有可能的密文组成的有限集，称为 密文空间；k 代表密钥空间，是由所有可能的密钥组成的有限集；对任意的加密 密钥k eek 和相应的解密密钥k d ek ，都存在一个加密法则如和相应的解密法 则d 船，并且有d 材溉伽) ) = 聊 2 4 1 。 一个好的密码体制至少应该满足下述两个条件t 2 4 1 ： 1 、在已知明文m 和加密密钥勋时，计算c - - e u ( m ) 容易，在已知密文c 和 解密密钥嬲时，计算m = ( c ) 容易。 2 、在不知解密密钥耐时，不可能由密文c 推知明文朋。 虽然如果密码分析者或潜在敌人不知道其分析的密码系统破译密码很难，但 是我们不应该把密码系统的安全性建立在密码分析者或潜在敌人不知道我们所 使用的密码系统这个前提之下，而是通常假定密码分析者或潜在敌人知道其分析 的密码系统，这个假设称作k e r c k h o f f 假设1 2 5 】。因此，在设计密码系统时，我 们的目的是在k e r c k h o f f 假设下达到安全性。 根据密码分析者对明、密文掌握的程度，攻击可分为下述四种【2 5 j ： 1 、唯密文攻击：密码分析者仅知道一些密文。 2 、己知明文攻击：密码分析者知道一些明文和相应的密文。 3 、选择明文攻击：密码分析者可以选择一些明文，并得到相应的密文。 4 、选择密文攻击：密码分析者可以选择一些密文，并得到相应的明文。 上述每种攻击的目的都是获得密码系统所使用的密钥。这四种攻击类型的攻 击强度按上述次序依次递增。即如果一个密码系统能够抵抗选择密文攻击，那么 它当然能够抵抗其余三种攻击。 实际中看上去完美的密码系统往往是非常脆弱的。即使很强的密码系统，哪 怕是一点点的改变就会使它变得非常脆弱。更重要的是密码的安全性不应该依赖 于算法的细节，而应依赖于密钥。假设密码分析者已经获得了密码算法的所有细 节；或者他们能够得到发起唯密文攻击的足够多的密文；或者他们能得到所需要 的尽可能多的数据发起明文攻击；甚至他们能进行选择明文攻击或者甚至他们能 够进行选择密文攻击。在这些情况下，如果密码体制仍然是安全的，那么它就达 到所需要的安全性要求了【2 3 1 。 第6 页 国防科学技术大学研究生院学位论文 密码系统的安全性一般分为实际安全性和无条件安全性( 又称理论安全性) 。 实际安全性是根据破译密码系统所需的计算量来评价其安全性。实际安全性又分 为计算安全性和可证明安全性。如果破译一个系统在原理上是可能的，但用所有 已知的算法和现有的计算工具不可能完成所要求的计算量，就称其为计算上安全 的。如果能够证明破译某个密码系统的困难性等价于解决某个数学难题，就称其 为可证明安全的。这两种安全性虽然都是从计算量来考虑的，但不尽相同。计算 安全要算出或估计出破译它的计算量下限，而可证明安全则要从理论上证明破译 它的计算量不低于解已知数学难题的计算量。一般说一个密码系统是“实际上安 全的是指利用已有的方法破译该密码系统所需要的能力超过分析者或潜在敌人 的破译能力( 如时间、资金等资源承受能力) ，或者破译该密码系统的难度等价于 解决数学上的某个已知难题。当然，这只是从计算量角度提供了密码系统安全性 的一些参考，并不能说明该密码系统就是绝对安全的。理论安全性与分析者或潜 在敌人的计算能力无关。一个密码系统被认为是“理论上安全的 是指具有无限 计算资源( 如时间、设备和资金等) 分析者或潜在敌人也无法破译该系统【z 5 。 2 2 1 概述 2 2 混沌理论 混沌的研究渊源可以追溯到1 9 世纪，1 8 9 2 年法国学者庞加莱( p o i n c a r e ) 在 研究三体问题时就发现，系统在某类鞍型不动点附近具有不寻常的运动，无法求 出精确解。他在1 9 0 3 年出版的科学与方法一书中明确指出，三体问题，在 一定范围内，其解是随机的。这实际上是一种保守系统的混沌。庞加莱是世界上 第一位预见到混沌现象的人删。 1 9 6 3 年，美国气象学家洛伦兹( l o r e n z ) 在研究大气对流模型过程中通过长 期反复的数值实验和计算机模拟，在耗散系统中首先发现了混沌运动。他在1 9 6 3 年它发表了著名论文确定性非周期流，在这篇论文中中研究了由气象预报抽 象出的伯纳德对流问题，采用数值积分方法计算如下三维自治系统( 后人称之为 洛伦兹系统) - 1 习 ro + - 澎ti l 叫j 的初值问题时发现，当系统参数取口= 1 0 ，= 8 3 ，厂= 2 8 时，系统自任意初 始状态出发的相轨道呈蝴蝶形态，既不重复也无规律。这是典型的非确定性运动， 第7 页 国防科学技术大学研究生院学位论文 而该系统却是一个典型的确定性动力系统。洛伦兹第一次在确定性动力系统中发 现了非确定性现象，成为混沌研究的里程碑闭。随后他又陆续发表了三篇论文， 这组论文成为研究耗散系统混沌现象的经典文献，为以后的混沌研究开辟了道 路。 1 9 6 4 年法国天文学家赫农( h e n o n ) 提出如下映射，后人称之为h e n o n 映射【2 6 】： 厂： 芝：6 屹一口砰 该映射代表了一个2 自由度的不可积h a m i l t o n 系统，然而当b - - o 3 时，随着口 的改变，系统运动轨道在相空间中的分布显得越来越随机。这实际上是一种最简 单的奇异吸引子。赫农以此解释了几个世纪遗留下来的太阳系的稳定性问题。 2 0 世纪7 0 年代混沌学研究在多个学科领域同时展开，形成了一股研究热潮。 1 9 7 1 年，法国的d r u e l l e 和荷兰的f t a k e n e s 联名发表了著名论文论湍流的 本质【2 引，在文中他们正式提出“奇异吸引子刀概念以解释湍流的发生机制， 这一概念以后被广泛应用于耗散系统的混沌研究中。生物学家，特别是种群生态 学家，对建立混沌学有着特殊贡献，他们在研究种群演化中建立的l o g i s t i c 方 程的数学模型，是研究混沌中十分理想而重要模型。1 9 7 3 年，法国数学家 b m a n d e l b r o t 正式提出了分形与分形几何的概念，他的工作为探索混沌种种不 规则的、回转曲折的奇异吸引子提供了重要的工具。1 9 7 5 年，正在美国马里兰 大学攻读博士学位的华人李天岩和他的导师j y o r k e 联名发表了一篇震动学术 界的论文周期3 蕴含着混沌眇】，这是一个关于混沌的数学定理，定理描述 了混沌的数学特征，揭示了从有序到无序的演化过程，为以后一系列的研究开辟 了方向，“混沌 一词正式成为科学词汇。1 9 7 7 年，第一届国际混沌会议在意大 利召开，标志着混沌科学地诞生。 2 0 世纪8 0 年代以来混沌研究出现了更大的热潮，科学美国人、科学、 新科学家、自然等杂志纷纷介绍混沌理论，专业学术刊物包括我国的物 理学报、物理学进展等也大量刊登混沌学研究的论文【2 7 1 。我国以中国科学 院理论物理所郝柏林院士、大气所曾庆存院士、复旦大学谷超豪院士、北京大学 廖山涛院士等为代表的学者也在混沌研究领域做了大量的工作，取得了一大批研 究成果【3 0 1 。 由于混沌运动是自然界中的一种普遍运动形式，混沌研究同时推动了其他学 科的发展，而其他学科的发展又反过来促进了对混沌的更进一步的深入研究。现 在，混沌与其他学科相互交错渗透，混沌在数学、物理学、生物学、化学、电子 学、信息科学、气象学、天文学、地质学、经济学，甚至音乐、美术等领域都得 到了广泛的应用【2 6 j 。 第8 页 国防科学技术大学研究生院学位论文 2 2 2 混沌的定义 由于混沌系统的奇异性和复杂性至今尚未被人们彻底揭示，不同领域的学者 从不同角度给出了定义，因此混沌至今还没有一个统一的定义。以下给出的是几 种影响较广的定义。 l 、l i y o k e ( 李天岩一约克) 的混沌定义娜1 】 l i - y o k e 定义是影响较广的混沌的数学定义之一。它是从区间映射的角度出 发进行定义的。以下首先叙述l i - y o k e 定理。 定理1l i - y o k e 定理设俐是 a ，6 上的连续自映射，若刷有3 周期点， 则对任何正整数m 俐有刀周期点。 下面介绍l i - y o k e 的混沌定义。 定义1 口，b 上的连续自映射厂称为是混沌的，若其满足： ( 1 ) 厂的周期点的周期无上界。 ( 2 )存在不可数子集s c a ，b ，s 中无周期点，且满足 a 对任意x ，) ，有舰时矿“( x ) 一” ) i - o ； b 对任意x ，j ，s ，x 乃：伺有。l i m 。s u p 1 f ”( 功一f ”o ) l o ； c 对任意x e s 和f 的任意周期点y ，有l i m s u d ”( x ) 一”) i 0 。 根据l i y o k e 定理和l i y o k e 的混沌定义可知：对 a ，b 上的连续自映射万 如果存在一个周期为3 的周期点，就一定存在周期为任何正整数的周期点，则一 定会出现混沌现象。 l i - y o k e 的混沌定义刻画了混沌运动的以下三个重要特征： a 存在可数的无穷多个稳定的周期轨道； b 存在不可数的无穷多个稳定的非周期轨道； c 至少存在一个不稳定的非周期轨道。 2 、d e v a n e y 的混沌定义瞄 3 d e v a n e y 的混沌定义是另一种影响较广的混沌的数学定义，它是从拓扑的角 度出发进行定义的。 定义2 度量空间v 上的映射 y _ y 称为是混沌的，若其满足： a 对初值的敏感依赖性，存在艿 0 ，对任意的占 0 和任意的x n 在x 的s 邻域，内存在y 和自然数刀，使得d ( f “( 石) ，f “o ) ) 万； b 拓扑传递性，对矿上的任意开集x l 存在k o ，f ( x ) n 】，( 如一映 射具有稠轨道，则它显然是拓扑传递的) ： 第9 页 国防科学技术大学研究生院学位论文 c 厂的周期点集在y 中稠密。 对这样的万如果用计算机计算其轨道，则任意微小的初始误差就将导致多 次迭代后的计算结果与实际结果产生足够大的差异，从而导致计算失败。因此对 初值的敏感依赖性也称为不可预测性。拓扑传递性意味着：任一点的邻域在f 的多次作用下将遍及度量空间n 这说明厂不可能分解为两个在厂下互不影响的 子系统。周期点集在矿中稠密意味着混沌系统存在着规律性的成分，决非混乱 一片，形似混乱而实则有序。 3 、m e l n i k o v 的混沌定义1 3 1 1 在二维系统中，最具开创性的研究是s m a l e 马蹄理论。马蹄映射f 定义于 平面区域d 上，只功c d ，其中d 由一单位正方形s 和两边各一个半圆构成。 映射规则是不断把s 纵向压缩( 压缩比小于1 2 ) ，同时横向拉伸( 拉伸比大于2 ) ， 再弯曲成马蹄形后放回d 中。h e n o n 映射就是马蹄映射的一个实例。已经证明， 马蹄映射的不变集是两个c a n t o r 集之交，映射在这个不变集上呈混沌态。因此， 如果在系统吸引子中发现马蹄，就意味着系统具有混沌。 由h o l m e s 转引的m e l n i k o v 方法是对混沌的另一种严格描述，可表述为：如 果存在稳定流形和不稳定流形且这两种流形横截相交，则必存在混沌。m e l n i k o v 给出了判定稳定流形和不稳定流形横截相交的方法，但这种方法只适合于近可积 h a m i l t o n 系统。 2 2 3 混沌的特征 混沌运动是确定性非线性动力系统所特有的复杂运动状态，它是一种不稳定 的有限定常( 这里所谓的定常运动，指的是运动状态在某种意义上( 以相空间的有 限域为整体来看) 不随时间变化) 运动，局限于有限区域但轨道永不重复，即为全 局稳定和局部不稳定的运动。稳定性是指系统受到微小的扰动后系统保持原来状 态的属性和能力，一个系统的存在是以结构与性能相对稳定为前提。但是，一个 系统要进化到一个新的演化状态又不能绝对稳定，而应在整体稳定的前提下允许 局部不稳定，这种局部不稳定是进化的基础。在混沌运动中这一点表现的十分明 显。所谓的局部不稳定是指系统运动的某些方面( 如某些维度、熵) 的行为强烈地