（计算机软件与理论专业论文）数字混沌加密技术研究.pdf

信息工程大学硕士学位论文 摘要 本文首先简要介绍了混沌加密技术的发展现状。在此基础上，对一类混沌加密算法 b a p t i s t a 型混沌加密算法进行了深入的分析，并针对此类算法存在的问题进行了探讨， 并提出了有效可行的改进措施及新的加密算法。具体内容包括以下几个方面： 首先，本文针对b a p t i s t a 型算法存在的密文长度过长及密文中o ，l 比例不均匀等 问题，以信息论和编码理论为基础，通过计算信息熵，给出了不同明文分组时密文明文长 度之比的期望的下界；进而讨论了明文分组对密文明文比例及加密时间的影响；进一步提 出了新的编码方式截断h u f 赫a n 编码( t r i l i l c a t e dh u 伍n a nc o d i n g 简记为1 h c ) ，以尝 试提高算法的效率。给出了该编码方式下密文明文比例及0 ，1 比例与截断位置的关系， 并通过调整截断位置以期接近或达到密文明文比例期望的下界，算例分析表明采用t h c 可有效缩短密文长度，提高o ，l 比例的均匀度。 其次，迸一步提出了基于双查找表的搜索机制混沌加密算法；该算法首先利用b a p t i s l a 型查找表( b a p t i s 诅- 咖el o o k u p1 a b l e 简记为b l u t ) 对待加密的明文进行预处理，然后 通过引入新型查找表( n e w - t y p el o o k u p1 a b l e 简记为n l u t ) 对处理后的明文进行加密， 以提高算法的安全性；通过调整n l u t 的长度对算法进行了优化，有效地缩短了明文长度。 分析表明新的算法在有效提高算法安全性的同时缩短了密文长度，提高了算法的效率。 最后，针对数字混沌系统的动力学特性退化的问题，提出了基于控制符的混沌加密算 法，通过控制符来确定对明文的预处理方式，并将查找表中与“预处理后的明文”对应的 索引值作为密文。同时利用控制符不断改变混沌轨道，从某种程度上克服了数字混沌动力 学特性的退化，对b a d t i s t a 型加密算法可能出现的安全性问题进行了进一步的强化。算例 分析表明基于控制符的加密算法是有效的。 关键词：数字化混沌；混沌密码；b a p t i s t a ；双查找表；控制符；动力学特性退化 第v 页 信息工程大学硕士学位论文 a b s t r a c t mt 1 1 i st h e s i s ，也eb a c k 群o u n do fd 噜i t a l 吐i a o t i ce n c r y p t i o nt e c h n o l o g yi si n n d d u c e df i r s t l y t h e n ，b a p t i s t “y p ec h a o t i cc r y p t o s y s t e mh 嬲b e e nc a r e f u l l ys t i l d i e d 锄dn e ws c h e m eh a sb e e n p r o p o s e d c o r d i n g l y t h em a i nr c s e a r c h c o n e n t sa n do r i g i n a l i t yo ft h j st l l e s i sc a l lb e 乳l m m a r i z e da sf b l i o w s ： f i r s t l y ，t os o l v et h e 抑om a j o rd m 、v b a c k so fb a p t i s 协咖ec h a o t i c 哪s y s t e m ，t h el o w e r b o l l l l do ft h ee x p e c 诅t i o no ft h ec i p h e r - t o p l a i n t e x t 枷oi sw o r k e do u tb yt l l ee m r o p yo f t h e c i p h e n e x t t h e 印p m x i r i l a t i o nf o m u i ai sp r e 鸵n t e dt 0c a i c u i a t et h ee x p e c t a t i o no f b i t 0m t i oo f c i p h e r c e x t t oi i i l p m v et l l ee 伍c i e n c yo fb a p t i s 诅_ t y p ec r y p t o s y s t e m ，t 1 1 ep l a i l l t e x t - b l o c ks i z ei s a n a l y t i c a l l yi i l f l i l i l e n c e du p o ni t sl o w e rb o l l l l da 1 1 dt l l ee n c r y 州o nt i m e ，嵋t n l l l c a t e dh u 仃m 觚 c o d i n g ( t h c ) i si n 打o d u c e dt oa p p r o x i m a l e l yr e a c ht h el o w e rb o m l d n u m e r i c a lp a r a d i g m sp r o v e ”v a l i d i t y s e c o n d l y ，d o u b l el o o k - u p 诅b l eb a s e ds e a r c hm e c h a l l i s mc l l a o t i cc r y p t o s y s t e mi sp r o p o s e d ， 坨p r e 仃e 栅e mt 0t h ep l a i m e x ti sp e r f o 硼e d 埘mt i l eb a p t i s 诅- t y p el o o k u pt a b l e ( b l u t ) w i t ht l l ed e f i n i t i o no fn e w - t y p el o o k u pt a b l e ( n l u t ) ，m e p 陀t r e a t e dp l a m t e x ti se n c r ) ，p 【e d a n dt l l e 印p r o x i m a t i o nf o 彻u l ai s p r e s e n t e d t oc a l c u l a t et ke x p e c t a t i o no fb i t om t i oo f c i p h e r t e x t t h e nc o m m i l i n gt h ee x p e c 僦o no fc i p h e r t 0 p l a i n t e x t 硎o ，t h es c h e m ei so p t i m i z e d b ) r 删u s t i n gt i l el e n g t l lo f n l u t ni s 疗0 me x p e r i 眦n t st h a tm es c h e m e 他s u i t sml l i g h e r s e c 埘t ya n db e t t e rc i p h e r t e x tc 1 1 a r a c t e r i s t i c f i i l a l l y ，t 0s c t t l et l l ed y n 锄i c a ld e g r a d a t i o no fd i g i t a lc 1 1 a o s ，ac o n 叻lc h a t t e rb a s e d c h a o t i cs c h e m ei si 1 1 打o d u c e d f i r s t l y ，i t e 喝t et h ec h a o t i cs y s t e m ；t h cc o n t r o lc h a r a c t e i j sp r o d u c c d c o r d i n gt 0t h ec h a o t i cs t a t e t l ep r e 仃i 班t i l l e n tt ot l l ep l a i n t e x ti sp e r f b m l e dw i t ht h ec o r m d l c h a r a 曲旺t h e nm ep l a i m e x ta f t e rp r e t r e a 恤e mi se n c r y p t e db yt l l el o o k u pt a i b l e m e a l l w i l i l e ，m e l o o k - 叩t a b l ei su p d a t c da c c o r d i n gt 0t 1 1 ec o n t r o lc l l a r a c t e rc o m i n u o l l s l y o m e r 、i s e ，t h ec h a o t i c 喇e c t o r yi sc h a i l g e dc o m i l l u o u s l ya c c o r d i n gt ot h ec o n t r d lc h a r a c t e r ，w h i c he 1 1 1 1 a n c e s 也e s e c 埘t yo fm es c h e m eu l t e r i o r l y a tl a s t ，锄a l y s i sa n de x p e r i m e m sp r o v et h ev a l i d i t yo ft l l e s c h e m e k e yw o r d s ：d 酒协1c i l a o s ，c l l a o t i cc i p h e r ，b a p t i s t a ，d o u b l el o o k - u pt a b l e ，c o n 仃o lp a r a m e t e r ， d y n a m i c a ld e 掣谊d a t i o n 第v l 页 信息工程大学硕士学位论文 表目录 表1 密文明文比例期望的下界 表2t h c 中截断位置参考值表1 4 表3t h c 的参数表1 5 表4 最佳n l u t 长度下算法的参数表2 4 第1 i l 页 信息工程大学硕士学位论文 图目录 图1 密文明文比例期望的下界及加密所需时间随明文分组变化图1 0 图2t h c 下密文明文比例期望1 4 图3t h c 下试验值与理论期望对比图1 6 图4 密文明文比例的期望及6 打o 所占比例图2 3 图5 基于双查找表算法试验值与理论期望对比图2 5 图6 查找表示意图 图7 加解密过程示意图 图8 查找表更新过程 图9 加密前后明文密文统计特性对比图( w i l l l l e x e ) 【e ) 图1 0 加密前后明文密文统计特性对比图( 全0 文件) “ 图1 1 扰动前后混沌状态分布 图1 2 扰动前后混沌状态的自相关函数 图1 3 扰动前后序列的线性复杂度 第1 v 页 2 7 2 9 3l 3l 3 2 3 2 3 3 原创。性声明 本人声明所提交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写 过的研究成果，也不包含为获得信息工程大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 意。 学位论文题目： 学位论文作者签 作者指导教师签 学位论文版权使用授权书 本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 学位论文作者签 作者指导教师签 信息工程大学硕士学位论文 1 1 课题背景 第一章绪论 随着通信及计算机技术的飞速发展，2 l 世纪世界已进入了信息化时代。国民经济的增 长，国防实力的增强，国家综合竞争能力的提高，都与信息技术的发展紧密相关。然而， 在信息技术发展给社会带来巨大利益的同时，信息安全也成为愈来愈不容忽视的重要问 题。特别是在互联网出现之后，由于互联网具有开放性和匿名性，它在给人们的生活、工 作等方面带来数不尽的便捷和好处的同时，也给人们的生活带来了安全上的隐患。这已引 起众多国家的政府、组织、学者的高度关注【1 ，2 1 。设计安全的易于实现的加密方案是目前研 究的热点和迫切需要解决的问题。 混沌理论在确定论和概率论这两大科学体系之间架起了一座桥梁，深刻地改变着人们 的科学观，被誉为继相对论和量子力学之后的第三次革命。2 0 世纪初，庞加莱在研究三 体问题时发现了混沌的存在。在2 0 世纪6 0 年代，美国气象学家洛仑兹在耗散系统中首 先发现了混沌运动，为以后混沌研究开辟了道路【3 1 。1 9 7 5 年，李天岩和y o r k e 提出了“混 沌”这一科学名词，混沌理论迅速发展为非线性科学的一个新的分支h 。混沌理论研究 目前已经取得了相当丰富的成果，包括许多有效的度量和处理方法。其发展不仅有助于 重新认识各种复杂的现象，例如湍流；而且随着研究的深入，它已经开始进入实际应用， 如用于控制化学反应的震荡、保密通信等领域。 近年来，混沌理论在信息安全领域的应用研究已经越来越受到人们的关注。混沌序列 的非周期性，连续宽带频谱、类似噪声等特性，使它具有天然的隐蔽性。另外，混沌序列 对初始条件的高度敏感性使其具有长期不可预测性，人们认为利用混沌可能更有助于设计 有效快速的加密算法i z j 。 混沌加密技术自1 9 8 9 年首次被m a l t h e w s f 5 】提出后，经过数十年的发展取得了许多成果。 然而，时至今日，仍然有不少重要问题尚未解决，例如混沌的通用定义，基本特性以及混 沌加密系统安全性等方面的问题。因而关于混沌理论和基于混沌的应用技术研究成果大多 仍处于实验室的研究阶段，离实际应用还有一段距离。但也应看到混沌在密码学中的应用 前景仍是乐观的。 本文正是基于这一背景而展开研究的，主要对b a p t i s t a 等人提出的一类基于搜索机制混 沌加密算法进行了深入探讨。首先理论上分析了此类算法的密文特性，并利用截断h u f f m 锄 编码来改善算法效率，缩短密文长度。随后提出基于双查找表的搜索机制混沌加密算法， 通过引入新型查找表( n l u t ) 对利用b a p t i s 协型查找表( b l u t ) 处理后的明文进行加密； 并通过优化n l u t 的长度有效改善了算法性能。但在数字化环境中，由于计算机有限精度 的限制，混沌系统将不可避免地出现动力学特性退化现象这是众所周知的事实。针对这一 事实，本文提出了基于控制符的混沌加密算法，通过控制符来确定对明文的预处理方式， 第l 页 堕璺三塑盔堂堡主堂垡堡壅 并将查找表中与“预处理后的明文”对应的索引值作为密文，利用控制符不断改变混沌轨 道，从某种程度上改善了数字混沌动力学特性。同时，本课题得到了国家自然科学基金 ( n o 6 0 3 7 4 0 0 4 ) 、国家8 6 3 项目( n o 2 0 0 6 a a o l z 4 0 9 ) 及河南省杰出青年基金项目 ( n o 0 4 1 2 0 0 0 2 0 0 ) 项目的资助。 1 2 混沌加密技术的发展概况 混沌加密技术一般又分为混沌保密通信技术口，6 。1 2 】和数字化混沌加密技术【1 ，5 ，1 3 4 ”。前 者一般在模拟电路系统中利用混沌同步技术实现；目前混沌系统的同步现象可分为混沌系 统完全同步1 8 】、相同步【10 1 ”、耦合同步4 2 ，4 3 1 、滞后同步【1 m 、广义同步m 、投影同步【4 5 1 等。 按其实现方法有可以分为：混沌掩盖f 9 ，4 6 1 ，参数调制【4 7 ，4 9 】，键控m 】，扩频【5 0 5 ”，脉冲定位 调制【2 3 】等。 一般说来，基于同步的混沌加密方案主要用来实现有扰信道上的保密通信，一般不能 直接推广到传统密码学中去，且大量的密码分析工作已经表明大部分基于混沌同步技术的 保密通信方案都不够安全，恶意的攻击者可能从截获的信号中恢复出和秘密参数相关的部 分有用信息，甚至可以近似确定这些参数。因此尽管混沌同步技术已在保密通信领域取得 了许多研究成果，但相关成果在传统密码学中应用仍较为困难。 混沌密码按照传统密码学分类方法来分，可分为混沌序列密码【2 5 ，3 4 。7 ，3 9 ，5 2 拼】和混沌分 组密码f 1 7 ，8 ，2 7 ，3 1 ，4 1 ，5 5 - 5 6 】等。从算法的设计思路和方法来分，又可分为基于搜索机制的混沌 密码【5 2 q 2 2 ，2 4 ，2 8 。q4 n 5 7 删；基于混沌的公钥密码f 6 1 删和基于动态s 盒的混沌密码【1 7 9 ，3 “， 以及一些将混沌映射和传统密码学或其他混沌映射相结合的组合密码等等。 1 2 1 混沌序列密码 混沌序列密码即混沌流密码，使用混沌系统生成伪随机密钥流，并将其直接用于掩盖 明文。其中混沌伪随机数发生器的设计是这类混沌密码算法的核心问题。目前主要有两种 设计思路：其一，抽取混沌轨道的一部分或全部二进制比特【2 5 l ：其二，将混沌系统的状态 空间划分为若干个不相交的部分，给每个部分标记一个唯一的数字，通过判断混沌状态落 入那个部分来生成伪随机数【3 6 ，5 2 ，5 卦。为了增强安全性或提高加密速度，一些研究者建议在 构造伪随机数发生器时使用高维混沌系统或同时使用多个混沌系统f 2 5 托5 2 删。如 p r o t o p o p e s c u 【2 5 1 在设计加密算法时，首先将b e m o u l l i 移位映射和l o g i s t i c 映射的状态进行 异或，然后再掩盖明文；李树钧【5 4 1 通过比较两个混沌系统的状态来构造混沌伪随机数发生 器c c s p r b g 。 1 2 2 混沌分组密码 混沌分组密码使用明文和或密钥作为初始条件和或控制参数，通过迭代反向迭代多 次的方法得到密文。1 9 9 8 年，f 删r i c h l 5 5 】使用定义在圆环面或正方形面上的二维可逆混沌映 射构造了一种混沌分组密码算法。1 9 9 9 年，c h u 【5 6 j 使用不同的混沌吸引子对明文分组的每 第2 页 笪星三堡查兰堡主堂垡笙奎 个字节进行加密构造了一种基于同步混沌系统得加密算法。2 0 0 1 年，l 幻c a r e v 【1 8 j 使用混沌 映射构造了一种类似d e s 的分组密码的通用方法。2 0 0 2 年，x u n 【3 l l 提出了一种基于t e n t 映 射的分组密码，将t e n t 映射生成的十进制序列一方面二值化为4 栉一6 个向量，另一方面通 过查表产生1 、2 、3 、4 的随机置换；交替使用噪声向量和随机置乱加密明文分组，明文分 组和密文分组的长度都是4 盯一6 ( 玎1 6 ) 且可灵活调节。2 0 0 6 年，陈军等人【4 l j 提出一种 利用外键控制的密文反馈混沌分组密码算法，利用1 2 8 位外部键生成系统密钥，系统参数、 初始条件和迭代次数将随着密文反馈动态生成。 1 2 3 基于动态s 盒的混沌密码 1 9 7 6 年美国n s a 提出了s 盒设计标准，在差分分析公开后，1 9 9 2 年i b m 进一步公布 了s 盒和p 盒的设计准则。从本质上讲，要求s 盒的输入向量的任何变动在输出方都产生 看似随机的变动。这两种变动之间的关系是非线性的，并难以用线性函数拟合。设计时， 常用的数学函数有指数函数和对数函数。近年来，利用混沌构造动态s 盒的思想得到发展 【1 7 ，2 7 ，3 1 ，6 5 1 。其中李树钧陋5 】及x l l i l 【3 1 1 提出的算法较受关注。李树钧6 5 1 提出了利用混沌系统构 造动态s 盒的思想。李树钧在该文中共使用了2 ”+ 1 个逐段线性混沌映射，其中一个作为 控制器控制整个密码系统的运行，其初始条件和控制参数作为系统的密钥。其他的2 ”个混 沌系统被随机选择迭代用于加密。x u n p l 】等人提出了使用t e m 映射生成的序列产生l 、2 、 3 、4 的随机置换( s 盒) ，该密文运行在c b c ( c i p h e r b l o c k c l l i n g ) 模式下，密文反馈 使得已知选择明文分析变得困难，从而提高算法的安全性。 1 2 4 组合密码 近些年来，一些将混沌映射和传统密码学或其他混沌映射相结合的组合密码方案相继 出现【3 2 ，3 3 ，矧，权安静【3 3 1 使用l o g i s t i c 映射改进分组密码的思想，针对传统分组密码中初始 密钥固定不变的不足，提出不断改变初始密钥以增强密码算法的安全性。丘水生【3 2 】提出将 混沌加密和传统加密相级联，首先利用混沌系统对明文加密，然后再使用传统的加密方法 进一步加密，既利用了混沌信号的不可预测性，又利用了传统密码的优点。此外，p a r e e k l 叫 建议使用一个混沌系统的输出作为另一个混沌系统的初始条件或控制参数，以增强加密算 法的安全性。 1 2 5 混沌公钥密码 与基于混沌理论的对称密码的研究比较起来，利用混沌来构造公钥密码的研究成果就 显得比较岁6 1 删。f e n 西h 、“6 1 1 于1 9 9 3 年在其博士论文中提出了一种混沌公钥密码可 以看作e i g 锄a l 公钥方案的变形，但由于该算法选择混沌系统的初始状态及加密过程中的 状态作为公钥，迭代次数作为私钥，安全性较低。2 0 0 3 年，rt e m y 6 2 1 在其博士论文中提 出了一种新的混沌公钥密码方案分布式动力学加密( d d e ，d i s 啊b u t e dd ”a m i c a l e n c f y p t i o n ) ，该系统的工作方式类似于混沌参数调制通信，通过吸引子的切换来完成对明 第3 页 信息工程大学硕士学位论文 文的加密和解密；但由于加解密过程需要双方的共同参与且作者是在模拟信号下进行的实 验，故此算法更象一种保密通信方案。同时，lk o c a r c v 【6 3 魄出一种利用c h e b y s h “混沌映 射的半群特性来实现的公钥密码方案，此算法不仅可用于加密而且也同时可用于数字签 名，是一篇创新性和实用性并举的文章。但是，有学者1 6 7 】发现k o c a r e v 公钥密码方案存在 着安全漏洞。在此之后，2 0 0 4 年l k o c a r e v 嘲】又刊出新的基于混沌的公钥密码文章。 1 2 6 基于搜索机制的混沌密码 这类混沌密码的共同特点是从伪随机序列中搜索明文。其中又包括： 1 ) 由ea l v a r e z 【3 0 j 首次提出，被搜索的伪随机序列是将混沌序列 x 。) 二值化生成的： 毛u o ，矗 ( ，一1 ，其中( ，是一个阈值参数，对于一个长度为6 f 比特的明文，加密 时，任选一个初始条件，迭代混沌系统按照上述方法产生一个伪随机序列s ，在该序列中 寻找当前明文，如果找到则输出当前混沌系统的状态、当前的阈值参数【，。和明文长度6 。作 为密文，如果在很长一段序列中都未找到明文，则将明文长度减少一个比特重复上述过程。 在此方案提出后不久，ga l v a r e z 唧】指出这种加密方案易于被四种不同的攻击方法攻破。 j a k i m o s k i 【j 4 】使用一种选择明文的方式攻破了该系统。李树钧1 2 叫等人详细分析了此算法的缺 陷，提出了改进算法：用斜t e n t 映射或分段线性混沌映射取代原算法中的1 i e n t 映射，选 择混沌系统的初始状态和控制参数作为密钥，将迭代次数取代原算法中的混沌状态作为密 文。2 0 0 6 年，王兴元1 3 s j 在此算法的基础上进一步提出一种基于遍历性的混沌加密新算法。 2 ) 由msb a p 矗s 协【2 1 ) 提出，被搜索的伪随机序列是混沌轨道本身；相较而言，b 印t i s t a 算法自提出以来得到了更为广泛的关注渺1 5 ，地2 2 ，2 4 ，2 s ，2 岫5 删，一些学者相继提出了一系 列改进算法f 1 3 ，1 5 ，2 0 2 2 ，2 4 ，2 8 ，2 9 ，绷。针对密文分布不均匀问题，w k w b i l g 于2 0 0 1 年提出在加 密每组明文之前预迭代混沌系统k 次( 足为随机数) ，但降低了加密速度1 2 s 1 ；李树钧等人 尝试对密文进一步加密以改善b a p t i g t a 算法中密文分布，但以增加算法实现复杂度为代价， 加密速度较型1 5 ，5 引。kww o n g 等人从不同角度对b 印t i s 诅算法进行了改进i 地2 4 ，2 9 5 7 1 。首 先，提出动态更新b a p t i s t a 算法中的双射( 文中称为查找表) ，并去掉原算法中的附加参数 以获得更快的加密速度阱】；其次在文【2 0 】中进一步提出了增强的动态查找表技术，同时引 入一个会话密钥以增强安全性，并使用了每个明文字符在动态查找表中的索引值作为密 文，有效地降低了密文长度；据加密每组明文对应的查找表不同，在文1 5 7 】中将查找表作为 消息认证码，并引入加密参数，动态决定每组明文的加密次数，以提高算法的安全性。而 在文【2 9 】中，进一步改进了查找表的更新方式，把查找表的大小扩充到? “( 斥为明文分组 的长度) 。此外，a p a l a c i o s 和hj u a r e z 建议使用多个耦合混沌映射网络中产生的交替混沌 ( c y c l i i l gc l l a o s ) 来增强原加密算法的安全性【2 2 】；王兴元【帅】等人使用一个额外的伪随机数 以改善b a p t i s t a 算法中不平衡的密文分布。增强算法的安全性。2 0 0 6 年，j 啪w c i 【”】等人针 对b a p t i s t a 算法密钥独立于明文，难以抵抗密钥流攻击等缺陷，提出使混沌参数与明文相 关，其动态更新混沌参数不仅增强了抗密钥流攻击的能力，而且避免了混沌动力学特性退 第4 页 信息工程大学硕士学位论文 化现象带来的影响，提高了算法的安全性，改变了查找表更新方法，去掉了最少迭代次数， 提高了加密速度。与此同时，一些学者也对此类算法的安全性提出了质疑，相关结论见文 f 1 4 照删。 上述改进算法主要从加密过程入手改进其存在的缺陷，也尝试利用不同的密文编码方 式来改善密文长度过长及密文中o ，1 比例不均匀的问题【1 3 1 5 ，巩2 引。然而，截至目前，未 见相关文献深入探讨编码方式对此类问题的影响。那么密文长度是否存在下界? 是否存在 编码方式达到或接近其下界? 通过怎样编码方式能使o ，1 比例均匀或接近于均匀? 这是 一系列值得探讨的问题。本文将对这些问题的具体分析并结合这些给出新的算法。 1 3 数字混沌动力学特性的退化 在混沌学理论中，所有的混沌系统都是定义在连续域上的，他们的动力学特性只有在 具有正的l e b e s g u e 测度的连续域上才有意义。当在数字化环境下实现( 通常意义下的数字 混沌系统一般指的是二迸制数字空间中的离散化混沌系统，即有限精度为m 时的2 “离散 化空间中的混沌系统) 时，混沌系统的动力学行为会在时间和空间两个方面被离散化，系 统将不再保持原有的动力学特性。 一般地，对于同个数字化混沌系统而言所有的轨道最后都将进入到少量的几个有限 循环中去。由于目前缺乏数字混沌系统的遍历性理论【1 6 ，坶，鲫，严格估计最小循环周期和循 环的个数仍很困难；但通过统计实验和随机映射理论可对数字混沌系统在宏观上进行研 究，如使用标度率( s c a l i n gi a w ) 来刻画拟混沌轨道，有效地描述了混沌动力学特性退化 现象1 7 0 ”】。并指出循环周期的最大值和平均值服从指数规律；不同循环周期的出现频率随 着循环周期的增加而按指数级衰减，即存在着大量具有短循环周期的拟混沌轨道。但目前 仍没有较好的寻找所有这些短周期的方法，只能穷尽模拟搜索【1 6 1 。并且标度率只是在一般 意义下成立，某些特殊的数字化混沌还是不满足这个规律。针对这类问题，李树钧等人研 究了数字化一维分段线性混沌映射，给出了定点算法下的一组描述其动力学特性退化的概 率指标6 9 ，7 2 1 。另一方面，在文删中还研究了浮点算法下t e 毗映射和b e n l o u l l i 映射的动力 学特性，指出了它们的拟混沌轨道收敛到不动点o 所需的迭代次数( 5 4 ) 远小于1 0 7 5 ( 双 精度下【o ，l 】之间所有合法浮点数在定点算法下的等效精度) 。 目前仍无可用的系统框架从理论层面克服数字混沌动力学特性退化问题，但许多可能 的补救措施已经提出，如提高运算精度，使用多个混沌系统级联，对混沌系统施以主动的 扰动阮7 3 一q 等。周红等人指出其中提高精度的方式是一种消极的策略，难以保证混沌信 号的周期绝对达到指定的要求且精度的提高并不能保证混沌信号的平均周期显著地增加； 而级联多个混沌系统的方法也不能保证完全避免短周期的出现。实际应用表明，对混沌系 统进行扰动是目前所知的最简单有效的方法【7 2 】。现有的扰动方法有三类：扰动混沌系统变 量【5 3 7 5 1 ，扰动混沌系统参数f 7 q 和同时扰动系统变量和参数f 7 3 t7 4 1 等。在扰动混沌系统变量方 面，周红【5 3 】等人使用线性反馈移位寄存器( l f s r ) 产生m 序列对系统变量进行扰动，后 第5 页 堕星三堡查兰堡主兰垡堡皇 来，桑涛【7 5 1 等人改用满足均匀分布的伪随机数发生器( p r n g ) 对混沌变量进行扰动；j c c m 酞【7 6 1 给出了另外一种方案：扰动系统的控制参数；刘钭7 3 1 ，张士杰【7 卅等人提出的一种 选择性扩散系统变量的扰动方案与第三种方法有着异曲同工之妙。 1 4 本文的主要工作 数字混沌加密技术在信息安全领域得到了广泛关注，本文仅对b a p t i s t a 等人提出的一 类基于搜索机制的混沌加密算法进行了详细的分析，并针对此类算法中存在的问题进行了 深入探讨，取得了一些结果。本文结构安排如下： 第一章，介绍了本文的研究背景，对已有的混沌加密方案尤其是由b a p t i s l a 等人提出 的基于搜索机制的混沌加密算法进行了介绍。 第二章，针对b a p t i s t a 型算法存在的问题密文长度过长及密文中0 ，l 比例不均匀， 结合信息论和编码理论，给出了密文明文比例期望的下界：讨论了明文分组对密文明文比 例及加密时间的影响；提出了新的编码方式截断h u 街n a n 编码( t h c ) ，以提高算法 的效率。给出了该编码方式下密文明文比例及o ，1 比例与截断位置的关系，并通过调整截 断位置以期接近或达到密文明文比例期望的下界。最后，通过算例分析验证了n c 的有效 性。 第三章，在第二章的分析改进基础上，进一步提出了基于双查找表的搜索机制混沌加 密算法；首先利用b a p t i s t a 型查找表( b l u t ) 对待加密的明文进行预处理，通过引入新 型查找表( n l u t ) 对处理后的明文进行加密，以提高算法的安全性；同时通过调整n l u t 的长度对算法进行了优化，有效地缩短了明文长度。算例分析验证了算法的有效性。 第四章，针对有限精度下数字混沌将出现动力学特性退化这一事实，提出了基于控制 符的混沌加密算法。通过控制符来确定对明文的预处理方式，并将查找表中与“预处理后 的明文”对应的索引值作为密文。同时利用控制符不断改变混沌轨道，从某种程度上改善 了数字混沌动力学特性。与b a p t i s t a 型算法相比具有较高的安全性和较均匀的密文分布。 最后，对本文进行了总结，并对下一步的研究工作作了展望。 第6 页 信息工程大学硕士学位论文 第二章b 印t i s t a 型算法分析及改进 2 1 引言 本文在第一章中对b a p t i s 诅型算法进行了较为详尽的介绍，并指出了此类算法目前仍 存在的问题。本章将针对这些问题，以信息论和编码理论为基础，使用密文明文比例来刻 画密文长度，利用信息熵给出了密文明文比例期望的下界；井对明文分组对密文明文比例 及加密同一明文所需时间的影响进行分析；提出了截断h u m n 锄编码( 1 1 c ) 的思想，基 于该思想对编码方式与密文长度之间的关系进行了描述；给出了0 ，l 比例的近似计算方 法( 使用6 打o 在密文中所占的比例来衡量 7 7 】) ，通过调整截断位置以期接近或达到密文明 文比例期望的下界，算例分析表明采用t h c 可有效缩短密文长度，提高o ，1 比例的均匀 度。 2 2b a p t i s t a 及其改进算法中密文的信息熵 2 2 1b a p tis t a 及其改进算法的基本思想 虽然针对b a p t i s t a 算法有不同的改进思路，但所有这些b a p t i s t a 型算法的基本思想却 是相同的，都可以用下面的七元组伽，只l 仍y ，砌c ，d p 0 来描述，其中： ( 1 ) n 表示把待加密的明文聊按柚i t 分组，分组后的明文可表示为，其中第f 组 明文m 州= 0 ，1 ，2 ，一1 ，朋即为明文空间。 ( 2 ) f 为一合适的混沌系统，其初始状态粕和混沌控制参数6 作为密钥。 ( 3 ) r 为f 状态空间的子空间( 可以为一部分或者全部) ，将r 均匀划分为2 ”个部分正， f = 1 ，2 ，3 2 ”。记f = 7 i ，五，一，正。) 。 ( 4 ) 伊是双射，且妒月= ：绷_ q ，有的改进算法中称此映射为查找表，不失一般 地本文将其定义为b a m i s t a 型查找表。 ( 5 ) y 是自然数集寸 o ，1 ) 的映射，其作用为在中选择合适的子集作为密文空间。 令c = 扣i y ( 行) = 1 ，将c 作为密文空间。 ( 6 ) 砌c 为加密方案，其描述如下： 加密前置嚣卜；加密第f 组明文码：以爵为初始状态，对混沌系统，进行迭代。 若对于第次迭代，满足( o ) 烈m ) 且i c ，则终止迭代。此时，令c = 露为卅l 的密 文，并令嚣“= f ( 露) 。 ( 7 ) 眈c 为解密方案，其描述如下： 解密前置霹卜而；解密第f 组密文g ：以霹为初始状态，对混沌系统f 迭代g 次， 若f c ( ) 妒( 码) ，则碾为c i 对应的明文；并令硝“= f 。( 矗) 。 第7 页 文c 的定义域。在最新的改进算法【1 3 】中，y 在上取值均为l ，也就是说，选取的密文 空间c 为。本章下面均设密文空间c 为进行讨论，也即以文【2 1 】中描述的改进思路为例 进行讨论。 2 2 2b a p t i s t a 及其改进方案中明文分组情况讨论 本节讨论第2 2 1 节描述的加密算法在明文不同分组时，密文的信息熵及加密的复杂 度问题。为此据混沌系统相关性质假设：在理想状态下混沌系统每次迭代后的状态落入各 个区间( 互，瓦，1 ，参见第2 2 1 节) 的概率相同1 3 4 3 7 1 。 本节将在明文分组的般形式下进行讨论，即明文采用珂6 缸分组，把混沌系统的状态 空间均匀划分为2 ”个区间7 i ，疋，l 。，故加密每组明文后的密文e 可以看成一个随机变 量，该随机变量服从几何分布，即： p c = = p ( 1 一p ) 4 - 1 ( 1 ) 其中p = 击，= l ，2 ，3 ，。则存在如下命题： 命题2 1 密文e 的信息熵为( 密文使用6 打表示，故对数函数的底取2 ) ： 崛，= 恤p + 半 c 矽 证明：令： s = l + ( 1 一p ) + ( i p ) 2 + + ( 1 一p ) p 1 ( 3 ) 是= ( 1 一p ) + 2 ( 1 一p ) 2 + + ( 一1 ) ( 1 一p ) 一1 ( 4 ) 将( 4 ) 式两端同时乘以( 1 一p ) 得： ( 1 一p ) s 2 = ( 1 一p ) 2 + + ( 一2 ) ( 1 一p ) 4 - 1 + ( 一1 ) ( 1 一p ) ” ( 5 ) ( 4 ) 式减去( 5 ) 式得： 鹕= ( 1 一p ) + ( 1 一p ) 2 + + ( 1 一p ) 川一( 一1 ) ( 1 一p ) “ 则有： 牌s 。而高2 言 ( 6 ) 腮是= 事 ( 7 ) p - + o 口 故： 日( e ) = 烛一乏p c l = m l o g ：( p c = ) ) ：一l i m 扫l o g ：p + p ( 1 一p ) l o g ：b ( 1 一p ) 】+ + p ( 1 一p ) 一1l o g ：k ( 1 一p ) 一一1 i 第8 页 ：一f l 0 9 2 p + 坠业墨趔i l j 证毕 根据命题2 1 可知，加密每组明文后的密文( 后称一组密文) 所包含的信息量的统计 平均值为( c ) 。因此密文明文比例期望的下界为： 如：旦盟：1 一坠业! 墨业 ( 8 ) n r i p 根据以上事实，存在如下命题： 命题2 2 凡( 功是单调减函数，且舰如= 1 。 证明；因( 1 一p ) l o g ：( 1 一力是单调增函数，二= 三一也是单调增函数；故 ! ! 二盟! ! 墅! ! 二盟为单调减函数 印 即风。( 功关于n 单调递减。由( 8 ) 式知 l i m r 。( n ) ：1 一l i m 坠世剑 印 ：1 一l i m ! 二旦l i m ! ! 2 1 1 二盟 n ”。 p = l 证毕 注2 1 只要符合2 2 - 1 节所描述的方案，不管对密文使用何种编码方式，密文明文比 例的期望均不会小于震。( n ) 。在可以采用合适的编码前提下，明文采用的分组长度越长( n 越 大) ，如印) 越小，但不可能小于l ；即加密同一明文时，明文分组长度越长，加密后密文 的长度越短，但始终大于明文长度。 根据式( 8 ) ，表l 给出了明文分别采用l ，2 ，j 6 研分组时的胄。( h ) 的值。例如，第2 行 第3 列的1 6 2 2 5 5 6 意味着；如果明文采用2 肋分组，则密文明文比例的期望不可能小于 1 6 2 2 5 5 6 。 表l 密文明文比例期望的下界 拧( 施) l23 4 5 67 8 r 。( 疗) 2 0 0 0 0 0 01 6 2 2 5 5 61 4 4 9 5 0 51 3 4 9 1 6 01 2 8 3 9 8 3 1 2 3 8 5 6 11 2 0 5 2 9 21 1 7 9 9 8 4 门( 6 打) 91 01 l1 21 31 41 51 6 如( 力 1 1 6 0 1 4 31 1 4 4 1 9 91 1 3 1 1 2 21 1 2 0 2 1 01 1 1 0 9 7 01 1 0 3 0 4 71 0 9 6 1 7 81 0 9 0 1 6 8 由上面分析知，从加密后密文明文比例的角度看，明文分组越长越好。下面分析在明 文不同分组下加密同一明文所需时间变化情况。据加密算法有如下命题： 第9 页 焦星三堡查兰堡主堂垡丝塞 命题2 3 加密同一明文所需时间随明文分组长度的增加呈指数级增加。 证明：由于在此算法中加密所需时间主要源自混沌迭代所需时间。故不妨设保存密文 及编码所用时间为石，可以看作常数；平均每次迭代所需时间为，对于给定的混沌系统 也可以看作常数。则加密所需时间r 的期望为： 旦，、 耳( ，哆= 于+ p r = 以j 乞 = 亭十屯p ( 1 一p ) 川 “1 = 手+ 乞2 ” 其中h 为明文分组长度。故加密同一明文所需时间随明文分组长度的增加呈指数级增加。 证毕 ( a ) 董 l 图1 密文明文比例期望的下界及加密所需时间随明文分组变化图 图1 ( a ) 为据命题2 2 得到的密文明文比例期望的下界随明文分组变化图，可知随着明 文分组长度的增加，密文明文比例期望的下界逐渐减小；图l ( b ) 为据命题2 3 得到的加密 所需时间随明文分组变化图( 不失一般地，取石= o ，乙= l ，时间单位为f d 毫秒) ，可知随着 明文分组长度的增加，加密所需时间逐渐增长。综上