（计算机科学与技术专业论文）基于混沌理论的非对称加密算法研究.pdf

x at h e s i si nc o m p u t e rs c i e n c ea n dt e c h n o l o g y r e s e a r c ho np u b l i c k e ye n c r y p t i o na l g o r i t hm b a s e do nc h a o st h e o r y b yy a n g y e s u p e r v i s o r p r o f e s s o r z h u z h i l i a n g n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 9 独创性声明 本人声明 所呈交的学位论文是在导师的指导下完成的 论文中取得 的研究成果除加以标注和致谢的地方外 不包含其他人己经发表或撰写过 的研究成果 也不包括本人为获得其他学位而使用过的材料 与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 二6 二 思 学位论文作者签名 翻吖 日期 学位论文版权使用授权书 t 本学位论文作者和指导教师完全了解东北大学有关保留 使用学位论 文的规定 即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘 允许论文被查阅和借阅 本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索 交流 作者和导师同意网上交流的时间为作者获得学位后 半年口一年口一年半口两年口 学位论文作者签名 才吻叶 签字日期 炒7 r j 导师签名 签字日期 东北大学硕士学位论文摘要 基于混沌理论的非对称加密算法的研究 摘要 信息技术的发展和网络应用的普及 给人类社会各个方面都带来了极大的便利并产 生了巨大的经济效益 但同时也引发了一系列的安全问题 而密码技术是保证信息安全 的关键 公开密钥算法 p u b l i c k e ya l g o r i t h m 的产生开创了密码学的新纪元 它将加密 密钥和解密密钥分离 减少了多用户通信所需的密钥量 节省了系统资源 便于密钥管 理 混沌信号具有的非周期性 类噪声的特性 使得它具有必然的隐蔽性 对初始条件 和微小扰动的高度敏感性 又使混沌信号具有长期的不可预测性 混沌信号的隐蔽性和 不可预见性使得混沌系统非常适合应用于保密通信 但相比起混沌密码在私钥系统中的 广泛研究 混沌在公钥系统中的研究还很少 本文首先研究了已有公钥加密算法 如r s a e 1 g a m a l 算法和基于混沌的公钥加密 算法 在此基础上又深入研究了c h e b y s h e v 多项式的单向性和半群性质并对现有方法进 行了改进 同时分析了如何选择初始条件等参数以获得更高的安全性 在原有理论的基 础上 提出一种改进的基于有限域c h e b y s h e v 多项式的类e 1 g a m a l 算法 该算法基于大 整数分解和求解离散对数的难解性 具有较高的安全性 在实现过程中 分别使用了普 通递归法 快速递归法 矩阵特征值法计算c h e b y s h e v 多项式 通过实验分析与对比 得出矩阵特征值法的计算时间整体上要比其他两种方法小得多 本文提出的改进算法在v i s u a lc 6 o 环境下编程实现 并与改进之前的算法进行 了比较与分析 实验结果表明 在一些参数选择的限制条件下 本文提出的算法可以有 效地抵抗唯密文攻击 从而提高整个密码算法的安全性 具有很好的应用前景 关键词 公钥算法 混沌映射 c h e b y s h e v 多项式 e 1 g a m a l 算法 大整数运算 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho np u b l i c k e ye n c r y p t i o n a l g o r i t h m b a s e do nch o a st h e o r y a bs t r a c t d e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g ya n dp o p u l a r i z a t i o no fc o m p u t e rn e t w o r k h a v eb r o u g h tg r e a tc o n v i n i e n c ea n de n o r m o u se c o n o m i cb e n e f i t st oo u rs o c i e t y h o w e v e r t h e ya l s oc a u s e das e r i e so fs e c u r i t yp r o m b l e m sa tt h es a m et i m e c r y p t o g r a p h yi st h ek e y t e c h n o l o g yw h i c hc a ng u a r a n t e ei n f o r m a t i o ns e c u r i t y a sp u b l i c k e ye n c r y p t i o no p e n san e w e r ao fc r y p t o g r a p h y i tm a k e sp u b l i c k e ys e p a r a t e df r o mp r i v a t ek e y r e d u c e st h ek e ya m o u n t n e e d e di nm u l t i u s e r sc o m m u n i c a t i o na n ds i m p l i f i e st h ek e ym a n a g e m e n tp r o c e s s c h a o t i cs y s t e m sa r ec h a r a c t e r i z e db ys 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 n sa n d s i m i l a r i t yt or a n d o mb e h a v i o r w h i c hm a k e st h e mb ee x c e l l e n tc a n d i d a t e sf o re n c y p t i o n a t p r e s e n t al o to fr e s e a c ho nc h a o t i cs y m m e t r i c k e ye n c y p t i o nh a v eb e e nd o n e b u tw i t hl e s s c o n c e r n so nc h a o t i c p u b l i c k e yc r y p t o s y s t e m s s o r e s e a r c h o fc h a o t i c p u b l i c k e y c r y p t o s y s t e m si sv e r yi m p o r t a n tt ot h ed e v e l o p m e n to f p u b l i c k e ye r y p t o s y s t e m s o nt h eb a s i so fe x p l o r i n gt h ep r i n c i p l eo ft h ee x i s t i n gp u b l i c k e ye n c r y p t i o na l g o r i t h m s u c ha sr s a e 1 g a m a la n da l g o r i t h m sb a s e do nc h a o s am o d i f i e de l g a m a l l i k ea l g o r i t h m u s i n gc h e b y s h e vp o l y n o m i a l sb a s e do nf i n i t e f i e l d si sp r o p o s e db yu s i n gas e m i g r o u p p r o p e r t y w h i c ha d o p t sat r a p d o o rm e c h a n i s m t h e o r ya n a l y s i si n d i c a t e st h a ts e c u r i t yo ft h e m o d i f i e de 1 g a m a l l i k ea l g o r i t h mi sb a s e do nb o t hi n t r a c t a b i l i t yo fi n t e g e rf a c t o r i z a t i o n p r o b l e ma n dc o n v e n t i o n a ld i s c r e t el o gp r o b l e m t h ec d n l l l l o ni t e r a t i o n f a s ti n t e r a t i o na n d m a t r i xe i g e n v a l u em e t h o da r ea d o p t e dw h e nc a l c u l a t i n gc h e b y s h e vp o l y n o m i a l i na d d i t i o n t h ep e r f o r m a n c eo ft h ea b o v et h r e em e t h o d sa r ec o m p a r e d w i t ht h ec o n c l u s i o nm a t r i x e n g e n v a l u em e t h o di sf a s t e ra n dm o r ee f f i c i e n tt h a tt h eo t h e rt w om e t h o d s t h ea l g o r i t h mp r o p o s e dw a si m p l e m e n t e du s i n gv i s u a lc 6 0 t h es i m u l a t i o nr e s u l t s o fm o d i f i e de 1 g a m a l l i k ea l g o r i t h ma n a l y s i sp r o v et h ef e a s i b i l i t yo ft h i ss c h e m e t h er e s u l t a n a l y s i si l l u s t r a t et h a tt h i se 1 g a m a l l i k ea l g o r i t h mc a nr e s i s tc i p h e r t e x to n l ya t t a c kw h e n a v o i d i n gc h o o s i n gs o m ew e a kp a r a m e t e r s t h u sw o u l de n h a n c e st h es e c u r i t yo ft h ew h o l e c r y p t o g r a p h i ca l g o r i t h m s t h e r e f o r e t h em o d i f i e de 1 g a m a l l i k ea l g o r i t h mu s i n gc h e b y s h e v p o l y n o m i a l sb a s e do nf i n i t ef i e l d sh a si t sp e r s p e c t i v ed e v e l o p m e n t s k e yw o r d s p u b l i c k e ya l g o r i t h m c h a o t i cm a p c h e b y s h e vp o l y n o m i a l e 1 g a m a l a l g o r i t h m b i g i n t e g e ro p e r a t i o n 东北大学硕士学位论文 目录 目录 独创性声明 i 摘要 i i a b s t r a c t i i i 第1 章绪论 1 1 1 非对称加密体制简介 1 1 2 混沌理论与密码学 3 1 2 1 混沌的起源与发展 4 1 2 2 混沌运动的基本特征 5 1 2 3 混沌与密码学的关系 7 1 3 混沌在公钥密码中的发展现状 8 1 4 本文所做工作与内容安排 1 0 1 5 本章小结 l l 第2 章公钥密码算法 1 3 2 1 公钥密码的基本原理 1 3 2 2d h 密码交换协议 1 3 2 3r s a 算法 15 2 3 1 算法的描述 一1 5 2 3 2r s a 算法的安全性 1 6 2 3 3r s a 参数的选择与分析 1 7 2 4e 1 g a m a l 算法 19 2 4 1 算法的描述 1 9 2 4 2e 1 g a m a l 算法的安全性 2 0 2 5 本章小结 2 0 第3 章混沌公钥密码算法的研究与改进 一2 l 3 1 混沌映射 2 1 i v 东北大学硕士学位论文 目录 3 1 1c h e b y s h e v 多项式 2 1 3 1 2 有限域c h e b y s h e v 多项式 2 2 3 1 3 环面自同构 2 4 3 1 4 环面自同构的周期 2 5 3 2 基于环面自同构的类r s a 算法 2 6 3 2 1 算法的描述 2 6 3 2 2 算法的证明 2 7 3 2 3 算法的分析 2 8 3 3 基于c h e b y s h e v 多项式的类e 1 g a m a l 公钥加密算法 2 9 3 3 1 算法的描述 2 9 3 3 2 算法的分析 3 0 3 4 基于有限域c h e b y s h e v 多项式的类e 1 g a m a l 算法 3 2 3 4 1 原算法的描述 3 2 3 4 2 原算法的分析 3 3 3 5 改进的基于有限域c h e b y s h e v 多项式的类e 1 g a m a l 算法 3 4 3 5 1 改进算法的描述 3 5 3 5 2 改进算法的分析 3 5 3 5 3 改进算法的参数选择 3 7 3 6 本章小结 3 8 第4 章基于有限域c h e b y s h e v 多项式的公钥密码算法实现 3 9 4 1 大整数的实现 3 9 4 1 1 大整数的存储 3 9 4 1 2 大整数的简单运算 4 0 4 2 大素数的生成 4 l 4 3 有限域c h e b y s h e v 多项式运算的实现 4 2 4 3 1 普通递归法 4 3 4 3 2 快速递归法 4 3 4 3 3 矩阵特征值法 4 4 4 3 4 三种方法的比较 4 6 东北大学硕士学位论文 目录 4 4 算法的买现 4 7 4 4 1 算法的程序实现结果图 4 7 4 4 2 改进算法的数值测试 4 8 4 4 3 算原法与改进算法的比较 4 9 4 5 本章小结 5 0 第5 章总结与展望 5 3 参考文献 5 5 致谢 5 9 攻读学位期间发表的论文 6 1 v i 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 非对称加密体制简介 加密技术作为一种保证安全通信的重要手段 从古至今人们都在不断地进行着探索 和研究 古典密码 如凯撒密码等 主要应用于政治 军事以及外交等领域 l 随着i n t e m e t 技术和多媒体技术的飞速发展 信息化不可逆转 以数字媒体数据为主的大量个人和公 众信息以各种形式在网络上迅速便捷地传输 尤其是存储技术的迅速发展和网络带宽限 制的突破 越来越多的容量巨大的多媒体信息得以在网络上传输 网络在给人们带来便 利的同时 也暴露出越来越严重的问题 其中信息的安全性就是一个突出的问题 因此 密码学已经成为信息科学与技术的一个重要研究领域 特别是近来年电子商务 电子政 务等活动的兴起 现代密码学的商业价值和社会价值也得到了充分的肯定 密码学是在编码和破译的斗争实践中逐步发展起来的 随着先进科学技术的应用 它已成为一门综合性的尖端技术科学 它与语言学 数学 电子学 声学 信息论以及 计算机科学等多门学科有着广泛而密切的联系 它的现实研究成果 特别是各国政府现 用的密码编制及破译手段都具有高度的机密性 密码体制从原理上可分为两大类 即对称加密体制 也叫做单钥密码体制 秘密密 码体制 和非对称加密体制 也叫做双钥密码体制 公丌密码体制 对称加密体制的基本 特征是加密密钥与解密密钥相同 对称密码体制的保密性主要取决于密钥的保密性 与 算法的保密性无关 即由密文和解密算法不可能得到明文 换句话说 算法无需保密 需保密的仅是密钥 由此 在对称加密体制中 存在的最重要的问题之一就是密钥的分 发问题 k e yd i s t r i b u t i o n 也就是如何将密钥传送给需要它们的用户 密钥分发的经典解 决办法如图1 1 所示 密钥在一个安全的通道内传输 如在被保护的电缆上 由于传输 速度慢并且传输代价昂贵 这一安全通道并不用来直接传输明文p 图1 1 传统对称加密系统示意图 f i g 1 1t r a d i t i o n a le n c r y p t i o ns y s t e m 在军事上 通常是指定专门的情报员以解决密钥分发问题 而在商业系统中 可能 会使用注册邮件的方式 不论使用何种方式 密钥的传送都是缓慢并昂贵的 成为了安 东北大学硕士学位论文第1 章绪论 全通信的障碍 如果需要为任意一次可能的会话产生一组密钥并将其分发到合适的用户 手中 那么代价是令人望而却步的 一个拥有1 0 0 万用户的系统可能需要维护5 0 0 亿的 密钥并进行分发 对于每个用户来说 只拥有一个与网络共享的密钥 而不是与其他用 户共享的密钥 并且网络用该密钥作为主密钥来分发每次会话需要的不同密钥是可以实 现的 这一方法要求分发密钥的网络 叫做密钥分发中心或结点 是安全的 值得信赖的 1 9 7 6 年 美国学者解决了信息公开传送和密钥管理问题 提出一种新的密钥交换协 议 该协议允许在不安全的媒体上的通讯双方交换信息 安全地达成一致的密钥 这就 是 公开密钥系统 相对于 对称加密算法 这种方法也叫做 非对称加密算法 如 图1 2 所示 不需要在会话双方间做任何预处理 也不需要分发密钥的安全通道 就可 以实现安全的通信 图1 2 公钥加密系统示意图 f i g 1 2p u b l i ck e ye n c r y p t i o ns y s t e m 如图1 2 所示 与对称加密算法不同 非对称加密算法需要两个密钥 公开密钥 p u b l i ck e y 和私有密钥 p r i v a t ek e y 公开密钥与私有密钥是一对 如果用公开密钥对数 据进行加密 只有用对应的私有密钥才能解密 如果用私有密钥对数据进行加密 那么 只有用对应的公开密钥才能解密 因为加密和解密使用的是两个不同的密钥 所以这种 算法叫作非对称加密算法 非对称密码体制将加密运算和解密运算分离 通信双方无须 事先交换密钥就可以建立保密通信 并且该体制采用密钥管理技术 大大减少了多用户 通信所需的密钥量 节省了系统资源 自从公钥密码的思想提出以来 国际上已经提出了许多种公钥密码体制 如基于大 整数因子分解问题的r s a 体制和r a b i n 体制 基于有限域上离散对数问题的 d i f f i e h e l l m a n 公钥体制和e i g a m a l 体制 基于背包问题的m e r k l e h e l l m a n 体制和 c h o r r i v e s t 体制 基于代数编码理论的m e e l i e c e 体制 椭圆曲线公钥体制等等 2 大部分公钥加密方法的缺点是加密速度慢 这就决定了传统的公钥加密方法只适合 用来加密小数据量的二进制数据 如密钥 这也意味着在一个实际的加密通信系统中 要将公钥加密方法和私钥加密方法结合起来 即混合加密系统 使用 才能保证较快的加 密速度和较高的安全性 如图l 3 所示 在传输时 将需要使用的私钥用公钥方法进行 了加密 而对需要传输的大量数据使用私钥方法进行加密 在接收端 首先要将密钥解 2 东北大学硕士学位论文第1 章绪论 密 然后用得到的密钥解密接收到的数据 图1 3 混合加密系统不恿图 f i g 1 3h y b r i de n c r y p t i o ns y s t e m 随着密码学商业应用的普及 公钥密码学受到前所未有的重视 公钥密码的用途主 要有以下几个方面 4 1 保密通信 保密通信是密码学产生的动因 使用公钥密码体制进行保密通信时 信息接收者只有知道对应的密钥才可以解密该信息 2 数字签名 数字签名技术可以代替传统的手写签名 并且在安全性方面具有很 好的防伪造功能 因此在政府机关 军事领域 商业领域具有广泛的应用空间 3 秘密共享 秘密共享技术是指将一个秘密信息利用密码技术分拆成n 个称为共 享因子的信息 分发给n 个成员 只有同时拥有刀个合法成员的共享因子才可以恢复该 秘密信息 其中任何一个或m m n 个成员合作都不能得到该秘密信息 利用秘密共享 技术可以控制任何需要多个人共同控制的信息 命令等 4 认证功能 在公开信道上进行敏感信息的传输时 采用签名技术实现对消息的 真实性 完整性的验证 通过验证公钥证书实现对通信主体的身份验证 5 密钥管理 密钥是保密系统中更为脆弱而重要的环节 公钥密码体制是解决密 钥管理工作的有效手段 可以利用公钥密码体制进行密钥分发 保护 密钥托管 密钥 恢复等工作 然而 任何加密方案都存在可能的破解方法 只是有的方案破解需要几十年甚至上 百年或更长的时阳j 而有的只需要一年甚至更短的时间 特别是近年来 随着计算机硬 件技术的飞速发展 计算机性能的不断提高 密码分析理论的不断创新 过去非常安全 的加密技术 现在已变得不再那么安全 高性能的计算机有可能在很短的时间内就能破 解过去根本不能破解的加密方案 因此 需要研究新的加密技术 以适应新形势下信息 安全的要求 1 2 混沌理论与密码学 混沌又称浑沌 人们通常用它来描述混乱 杂乱无章的状态 在这个意义上 它与 3 东北大学硕士学位论文第1 章绪论 无序的概念有相同之处 科学家给混沌下的定义是 混沌是指发生在确定性系统中的貌 似随机的不规则运动 一个确定性理论描述的系统 其行为却表现为不确定性 不可 重复 不可预测 这就是混沌现象 混沌理论所研究的对象是非线性动力系统 目的是 要揭示貌似随机的现象背后可能隐藏的简单规律 以期发现这一类复杂问题所普遍遵循 的共同规律 3 尽管科学界对混沌已经进行了近半个世纪的研究 但至今尚无一个公认的非常严格 的标准数学定义 这是因为混沌系统非常复杂 从不同的角度理解会有不同的内涵 数 学上常用的定义包括 离散动力系统的l i y o r k e 意义下的混沌 4 5 高维空间中相应的 m a r o t t o 定义 6 1 d e v a n e y 定义的拓扑意义下的混沌 7 8 和连续动力系统的s m a l e 马蹄意 义下的混沌1 9 j 混沌运动具有通常确定性运动所没有的统计特征 如局部不稳定而整体稳定 无限 相似 连续的功率谱 奇异吸引子 正的测度熵等 与其它复杂现象相区别 混沌运动 有着自己独有的特征 如确定性 有界性 对初值的极端敏感性 长期不可预测性 正 的最大l y a p u n o v 指数和遍历性等 1 0 1 1 1 2 1 混沌的起源与发展 2 0 世纪下半叶 非线性科学获得了前所未有的蓬勃发展 非线性科学是一门研究非 线性现象共性的基础科学 被誉为2 0 世纪自然科学中的 三大革命之一 科学界认为 非线性科学的研究不仅具有重大的科学意义 而且具有广泛的应用前景 1 3 羽 非线性科 学的主体包括 混沌 c h a o s 分岔 b i f u r c a t i o n 分形 f r a c t a l 孤立子 s o l i t o n 和复杂性 c o m p l e x i t y 的研究 其中 混沌的研究占有极大的份量 从数学上讲 对于确定的初始值 由动力系统可以推知该系统长期行为甚至追溯到 其过去的性态 但是2 0 世纪6 0 年代 美国气象学家l o r e n z 在研究大气对流模型的时 候发现 当选取一定参数的时候 一个由确定的三阶常微分方程组所描述的大气对流模 型变得不可预测了 这就是有趣的 蝴蝶效应 在研究的过程中 l o r e n z 观察到了这 个确定性系统的规则行为 同时也发现了同一系统出现的非周期无规则行为 通过长期 反复地数值实验和理论思考 l o r e n z 揭示了该结果的真实意义 首先发现了混沌运动 为以后的混沌研究开辟了道路 2 0 世纪7 0 年代 特别是1 9 7 5 年以后 是混沌科学发展史上光辉灿烂的年代 在这 时期 作为 f 新兴的科学 混沌学正式诞生了 1 9 7 1 年 法国数学物理学家r u e l l e 和荷兰学者t a k e n s 一起发表了 论湍流的本质 在学术界首次提出了用混沌来描述湍 流形成机理的新观点 他们通过严密的数学分析 发现了动力系统存在的 奇怪吸引子一 东北大学硕士学位论文第1 章绪论 并将它形容为 一簇曲线 一团斑点 有时展现为光彩夺目的星云或烟火 有时展现为 可怕和令人生厌的花丛 数不清的形式有待探讨 有待发现 1 9 7 3 年 同本京都大学 的y u e d a 在研究非线性振动时 发现了一种杂乱振动形态 称为u e d a 吸引子 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 第一次用实 验证明了f e i g e n b a u r n 常数 1 9 8 9 年 召开了美苏混沌讨论会 二十世纪九十年代以后 国际上混沌同步及混沌控制取得了突破性进展 并由此激 发了理论与实验应用研究的蓬勃发展 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 g i 和y o r k e 提出 也称为o g y 方法 随后的几年 国际上混沌控制 方法及其实验的研究迅速发展 混沌同步也获得进一步拓广 大大推进了应用研究 在 诸如电子学 保密通讯 密码学 激光 化学 生物 脑科学及神经网络系统等众多领 域中都具有巨大的应用潜力 近l o 年来 混沌科学更是与其它科学互相渗透 无论是 生物学 生理学 心理学 数学 物理学 电子学 信息科学 还是天文学 气象学 经济学 甚至在音乐 艺术等领域 混沌都得到了广泛的应用 如今 混沌的发现被认为是2 0 世纪物理学的三大成就之一 可以说相对论消除了 关于绝对空间与时间的幻想 量子力学消除了关于可控测量过程的牛顿式的梦 而混沌 则消除了拉普拉斯关于决定式可预测性的幻想 混沌学创立 将在确定论和概率论这两 大科学体系之间架起桥梁 它将揭开物理学 数学乃至整个现代科学发展的新篇章 目 前 混沌理论与其它学科相互交错 相互渗透 相互促进 综合发展 形成许多新的研 究分支 混沌密码学就是其中之一 1 2 2 混沌运动的基本特征 混沌运动是一种不稳定的有限定常运动 即全局稳定和局部不稳定的统一 这个定 义给出了混沌的两个主要特征 不稳定性 该性质可用平均l y a p u n o v 指数大于零来精确 刻画 和有限性 或除了平衡 周期和准周期以外的有限定常运动称为混沌运动 这里 所谓的定常运动 指的是运动状态在某种意义上 以相空间的有限域为整体来看 不随时 间变化 混沌运动具有通常确定性运动所没有的几何和统计特征 如局部不稳定而整体 稳定 无限相似 连续的功率谱 奇怪吸引子 分维 正的l y a p u n o v 指数 正的测度 熵等 为了与其他复杂现象区别 一般认为混沌应具有以下几个方面的特征 1 内随机性 混沌现象是非线性动态系统中出现的一种貌似随机的行为 是确定 东北大学硕士学位论文第1 章绪论 性系统内部随机性的反映 所谓内在随机性是指这种随机性不是由随机外因引起的 而 是由确定方程 e q 因 直接得到的 在描述系统行为状态的数学模型中不包括任何随机项 而是完全由系统内部自发产生的 是与外部因素毫无关联的 确定性随机性 2 整体稳定局部不稳定 混沌态与有序态的不同之处在于 它不仅具有整体稳定 性 还具有局部不稳定性 稳定性是指受到微小的扰动后系统保持原来状态的属性和能 力 一个系统的存在是以结构与性能相对稳定为前提的 但是 一个系统要进化 要达 到一个新的演化状态又不能稳定性绝对化 而应在整体稳定的前提下允许局部不稳定 这种局部不稳定或失稳正是进化的基础 在混沌运动中这一点表现的十分明显 所谓的 局部不稳定是指系统运动的某些方面 如某些维度 熵 的行为强烈地依赖于初始条件 3 对初始条件的敏感依赖性 初值的微小变化经过很长的时间后运动可能相差甚 远 这意味着混沌运动具有l y a p u n o v 指数下的不稳定 随着时间的推移 任意靠近的 各个初始条件将表现各自独立的时间演化 即存在对初始条件的敏感依赖性 4 长期不可预测性 混沌具有正的l y a p u n o v 指数 为了对非线性映射产生的运动 轨道相互间趋近或分离的整体效果进行定量刻画 引入了l y a p u n o v 指数 当l y a p u n o v 指数小于零时 轨道间的距离按指数规律消失 系统运动状态对应于周期运动或不动点 当l y a p u n o v 指数等于零时 各轨道间距离不变 迭代产生的点对应于分岔点 即周期加 倍的位置 当l y a p u n o v 指数大于零时 表示初值相邻的轨道以指数规律发散 系统运 动状态对应于混沌状态 正的l y a p u n o v 指数表明混沌运动轨道按指数分离 值越大 轨道分离越快 其不可预测性越强 应用时保密性也就越好 但是由于吸引子的有界性 轨道不能分离到无限远处 所以混沌轨道只能在一个局限区域内反复折叠 但又永远互 不相交 形成了混沌吸引子的特殊结构 系统的l y a p u n o v 指数有一个为正 则系统中 存在混沌行为 有两个或两个以上为正 则存在超混沌行为 由予初始条件的微小差异 可能对以后的时间演化产生巨大的影响 因此不可能长期预测将来某一时刻的动力学特 性 5 奇异吸引子及其分形结构 系统的某一特定状态 在相空间中占据一个点 当 系统随时间变化时 这些点便组成了一条线或一个面 称之为轨道 随着时间的流逝 相空间中轨道占据的体积不断变化 其极限集合称为吸引子 吸引子分为简单吸引子 或 平凡吸引子 和奇异吸引子 或混沌吸引子 奇异吸引子是一类具有无穷嵌套层次的自相 似几何结构 维数是对吸引子几何结构复杂度的一种定量描述 在欧氏空间中 空问被 看成三维 平面或球面看成二维 而直线或曲面看成一维 平衡点 极限环以及二维环 面等吸引子具有整数维数 而奇异吸引子具有自相似特性 在维数上表现为非整数维数 即分数维 耗散系统的有效体积在演化过程中将不断收缩至有限分维内 吸引子 耗散 6 东北大学硕士学位论文第1 章绪论 是一种整体稳定性因素 而轨道又是不稳定 这就使它在相空间中产生形状拉伸 扭曲 和折叠 形成具有精细的无穷嵌套的自相似结构 分形 6 轨道不稳定性及分俞 长时问动力运动的类型在某个参数或某组参数发生变化 时也发生变化 这个参数值 或这组参数值 称为分翁点 在分岔点处参数的微小变化会 产生不同定性性质的动力学特性 所以系统在分岔点处是结构不稳定的 7 普适性 在混沌的转变中出现某种标度不变性 代替通常的空间或时间周期性 所谓普适性 是指在趋向混沌时所表现出来的共同特性 它不依具体的系数以及系统的 运动方程而变 普适有两种 即结构的普适性和测度的普适性 前者是指趋向混沌的过 程中轨线的分龠情况与定量特性不依赖于该过程的具体内容 而只与它的数学结构有 关 后者指同一映像或迭代在不同测度层次之间嵌套结构相同 结构的形态只依赖于非 线性函数展开的幂次 8 连续的功率谱 混沌信号介于周期或准周期信号和完全不可预测的随机信号之 间 用f o u r i e r 分析混沌频谱发现 混沌信号的频谱占据了很宽的带宽且分布较均匀 整个频谱由很多比较窄的尖峰构成 1 2 3 混沌与密码学的关系 混沌作为一种确定性的非线性现象 有许多值得密码学借鉴和利用的性质 从而可 以为密码学的发展提供新的思路 目前研究发现 传统的密码方法中存在着与混沌的联 系 1 2 比如 传统的加密算法通过加密轮次来达到扰乱和扩散 混沌映射则通过迭代将 初始值扩展到整个相空间 混沌信号具有的类噪声 非周期性的特性 使得它具有天然 的隐蔽性 对初始条件和微小扰动的高度敏感性 又使混沌具有长期的不可预测性 因 此 利用混沌信号的隐蔽性和长期不可预见性 可以构造出非常好的加密系统 应用于 保密通信领域 混沌与密码学存在的联系总结如下 首先 密码系统是一个确定性的系统 它所使用的变换由密钥控制 加密变换 c e k m 计算不困难 但在不知道k 的情况下 解密变换m d k c 的求解却极 为困难 要做到这一点 密码系统须对密钥极端敏感 同时 密文须对明文敏感地依赖 这使得在知道部分密文 和明文 的条件下 猜测全部明文 或密钥 极其困难 要保证这 一点 明文须得到充分的混合 这些对密码系统的要求和混沌的特性有着十分密切的联 系 其次 混沌的许多基本特性 如遍历性 混合性和对初始条件与控制参数的敏感性 都可以和密码学中的混乱与扩散联系起来 香农说过 混乱和扩散是一个好的密码系统 所必备的两个条件 混沌系统中出现的确定性的 类似随机的过程 这种过程既非周期 东北大学硕士学位论文第1 章绪论 又不收敛 并且对初始值有极其敏感的依赖性 从而使初始条件或参数的微小差异将以 指数级被放大 保证良好的扩散性 从时域上看 混沌映射得到的序列类似于随机序列 相关性较弱 具有很好的类白噪声特性 因此可以用来产生伪随机信号或伪随机码 用 以 混乱 明文以致其无法辨认 具有很好的混乱特性 原理上只要增加迭代次数 伪 随机码的周期可以很长 产生长码十分简单 并且 通过混沌系统对初始值和结构参数 的敏感依赖性 可以提供数量众多 非相关 类随机而又确定可再生的信号 便于软 硬件实现 再次 密码变换和混沌映射的联系还可以从计算复杂性的角度来看 密码系统的基 本问题之一就是安全性 而密码的强度依赖于密码问题的计算复杂性 l3 1 也就是说 利 用有限的计算资源 在有限的时问内 一个问题的求解是单向的 无法求其逆 比如在 密码中广泛使用的陷门函数 t r a p d o o rf u n c t i o n 就是一种单向函数 o n e w a yf u n c t i o n 在 传统密码学中 这种单向函数的构造一般都利用一些数论中的难题 比如大数分解问题 离散对数问题等来实现 而一些混沌的系统数字化后也可构成单向函数 目前 混沌在对称加密和非对称加密中都有着广泛的应用 尤其是在对称加密方法 中 很多学者已经做过了大量的工作 1 4 18 1 混沌用于公钥密码是近几年才发展起来的 已提出的单混沌公钥密码算法有 基于分布式动力系统的公钥密码 l 蛆 基于混沌映射 的通用r s a 算法 2 2 1 基于耦合映像格子通用同步的公钥密码 2 3 1 基于切比雪夫多项式 的公钥密码 矧及其改进 基于矩阵扩展与变换的公钥图像加密方案 5 l 等等 混沌除了应 用于对称加密与非对称加密外 近年来又出现了一些新的设计思路 比如把混沌用于生 成h a s h 函数 2 5 乏7 在分组密码中使用混沌生成s 盒 2 8 3 0 域p 盒等 1 3 混沌在公钥密码中的发展现状 目前 混沌公钥密码研究虽处于起步阶段 但由于其优良的密码学性质 混沌公钥 密码已经引起了普遍关注 许多混沌系统的基本特性 如遍历性 混合性和对初始条件 与控制参数的敏感性 都可以和密码学中的混乱与扩散联系起来 混沌加密的研究成为 近年来国内外研究者关注的一个热点 但是大量的研究成果局限于混沌对称加密范畴 利用混沌来构造公钥密码系统的研究还比较少 因此 研究基于混沌的公钥密码算法对 于公钥密码的发展具有十分重要的意义 目前使用的公钥加密系统都是基于数论中的某 些难题 对于基于混沌的公钥加密系统 如果可能的话 可以建立在混沌领域的某些难 题的基础上 关于混沌公钥密码的研究近几年有了一些进展 文献 3 l 提出了基于胞元自动机 c e l l u l a ra u t o m a t a 的混沌公钥算法 不过该方法很 快受至u g u t u w i t z 的批评 东北大学硕士学位论文第1 章绪论 f e n g i 提出了一种e l g a m a l 的变形方梨3 2 1 但是该方案迭代次数即使很大 敌手也 可以根据得到的密文前半部分采用幂模快速算法继续迭代若干次 再用密文第二部分恢 复明文 t e n n y 等 2 0 2 1 1 首先提出基于分布式动力学的混沌公钥密码 将一个多维动力学系统 分解为两个子系统 并通过交互内嵌子系统状态信息与明文信息的标量信号来实现非对 称加密 因为作者采用了混沌同步和预测校正的方法 并且没有给出一个实例 所以它 的安全性和有效性受到广泛质疑 文献 3 5 从安全性上对其进行分析 指出该方案不符 合一切秘密寓于密钥之中的思想 在协议上存在不安全因素 可能存在一些潜在的数字 攻击方法 而且该公钥算法没有数字签名方案 以数学上离散对数求解难道为安全保证 k o c a r o v 和t a s e v 在文 3 6 中提出了一种基 于c h e b y s h e v 多项式的类e 1 g a m a l 公钥密码设计方法 但不久b e r g a m o 利用区间 一l l 上 c h e b y s h e v 多项式的弱点指出该方法并非安全有效 通过反三角函数进行求逆 对其成 功破解 文献 4 6 在文 3 6 的基础上 将x 取为大于1 的数 从而有限抵抗了对反三角函 数求逆的攻击 同时提出了密钥交换协议 文献 3 8 中 k o c a r e v 禾l j 用环面自同构提出的一种类r s a 的加密方法显得格外引人注 目 该方案利用c h e b y s h e v 映射的半群特性 即乙 工 乙 x m n z 构造了一个 与r s a 几乎 样的公钥算法 文献 3 9 指出该算法的安全性与r s a 算法一样 利用了数 学计算上求解素因子分解的难题 但是同等加解密密钥长度下 该算法的正常运算量至 少是r s a 的三倍多 而且计算占用存储器资源l l f i r s a 也要大得多 文献 4 0 指出该方案 并非一种新的方案 而是l u c 系统的一个特例 该方法通过离散混沌映射把问题转化到 剩余类环上 而通常混沌密码设计比较忽视有限域算术方面的工作 这一点国内学者已 开始关注并做了一些重要的工作 4 1 4 2 1 接着文献 4 3 在文献 3 8 1 的基础上将环面自同构 混沌映射应用到r s a 公钥密码算法中 利用了该映射的周期性质 其安全性与r s a 相似 并易于软件实现 由于根据选定的加密密钥产生的解密密钥会与模数的立方数量级相 当 所以解密运算效率较低 虽然l k o c a r e v 和z t a s e v 提出的基于c h e b y s h e v 映射的公钥加密方案有很多漏洞 但 它的提出为混沌技术应用于公钥加密算法提供了全新的思路 国内外学者纷纷在这个基 础上对数据加密方案和身份认证方案进行修正和发展 在文献 3 6 的基础上 文献 4 4 提出了签名方案 文献 4 5 1 提出了认证方案 文献 4 6 在没有改变c h e b y s h e v 多项式的基 础上 提出了密钥交换协议的改进方案 文献 4 7 提出了有限域c h e b y s h e v 多项式的定义 并利用有限域c h e b y s h e v 多项式的单向性和半群属性 构造了一种新的会话密钥协商算 法 该算法l b d i f f i e h e l l m a n 算法实现简单并且破译更加复杂 文献 5 4 提出了基于有限 9 东北大学硕士学位论文第1 章绪论 域c h e b y s h e v 多项式的公钥密码算法 文献 4 l 提出了相应的身份认证方案 最近 r u a n j a n 幂l j 用多混沌系统提出了一种设计公钥密码的技巧 4 引 该算法首先将 多混沌系统伪随机数发生器推广到m 组情况 然后在此基础上结合m 个线性变换并在 d i f f i e h e l l m a n 协议框架下设计公钥密码算法 安全分析表明 攻击该算法等价于求解 d i f f i e h e l l m a n 难题 即只能采用强力攻击 且难度为 尸 其中 尸和m 分别为密 钥空间大小 线性变换计算复杂度和线性变换个数 但是文献 4 9 5 0 相继利用p a r s e v a l 等式给出了破解实例和从理论上证明其设计方法是不可行的 除此之外 还有其它混沌映射应用到公钥密码算法中的研究 如陈关荣等人 5 l 使用 高维的混沌猫映射构造公钥加密方法并将其应用到图像加密方案中 该方案使用了可逆 的矩阵分别做为公钥和私钥 其中 矩阵中的参数由扩展后的高维猫映射产生 黄贤通 等人提出的基于加法及m a t t h e w s 混沌实现的背包公钥密码体系 5 2 研究了m a t t h e w s 混 沌系统构造伪随机向量的方法 然后利用伪随机向量实现了一种新的背包公钥密码体 系 算法举例体现了该体系操作简单 计算量小 安全性强等特性 文献 5 3 实现了一 个改进的b a p t i s t a 类型的混沌加密系统 采用椭圆曲线算法做密钥分配 并可同时产生 出h a s h 表以进行消息