（测试计量技术及仪器专业论文）基于混沌的数据加密算法研究及fpga实现.pdf

南京航空航天大学硕士学位论文 摘要 随着信息技术的发展和计算机网络的普及，信息安全显得尤为重要。考虑到 传统密码学的不足和密码分析者破解水平的不断提升，基于混沌的数据加密技 术正成为当前密码学研究的一大热点，并有可能成为密码学新的发展方向。 本文主要论述了基于混沌的数据加密算法的设计及其f p g a 实现过程。在基 于混沌的流密码设计部分中，详细叙述了基于l o g i s t i c 映射的c p r b s 发生器、 l f s r 的设计以及整个流加密算法的v h d l 描述，该算法f p g a 实现后加解密 速度达8 3 6 m b i t s ，并通过了f i p s1 4 0 2 的安全性能验证：在d e s 算法的f p g a 实现及其混沌增强部分中，重点叙述了d e s 算法的f p g a 设计过程，包括运算 模块、子密钥生成模块以及控制逻辑模块的设计，并针对d e s 密钥空间不足和 d e s 算法本身的特点，提出了基于k o l m o g o r o v f l o w s 增强d e s 的方法，使算法 的密钥空间由原先的5 6 位增加到1 3 6 位。论文的最后设计了e p p 模式的并行通 信接口，实现了p c 机与f p g a 之间数据加密系统的调试验证。 关键词：混沌，加密，f p g a ，d e s ，v h d l ，密钥 基于混沌的数据加密算法的研究及f p g a 实现 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n dt h ep r e v a l e n c eo f c o m p u t e r n e t w o r k ，i n f o r m a t i o ns e e u r i t yi sak e yp r o b l e m i nc o n s i d e r a t i o no f t h ed e f i c i e n c yo f t r a d i t i o n a l c r y p t o l o g y a n dt h ec e a s e l e s s i m p r o v e da b i l i t y o fc r y p t a n a l y s i s ，d a t a e n c r y p t i o nb a s e do nc h a o sh a s b e c a m eaf o c u so fr e s e a r c ha n dm a yb ean e w p r o s p e c t i v ea p p r o a c h i nt h ef u t u r e t h ed a t ae n c r y p t i o na l g o r i t h mb a s e do nc h a o sa n di t sf p g ai m p l e m e n ta r e m a i n l yd i s c u s s e di nt h i sd i s s e r t a t i o n i nt h ep a r to fd e s i g n i n gs e q u e n c ec i p h e rb a s e d o nc h a o s ，t h ed e s i g nf o rc p r b s g e n e r a t o rb a s e do nl o g i s t i cm a p p i n g a n dl f s ri s d i s c u s s e di ng r e a td e t a i l ，t h e nt h es e q u e n c ec i p h e ra l g o r i t h md e s c r i b e di nv h d li s i n t r o d u c e d t h e e n c r y p t i o n d e e r y p t i o ns p e e d a t t a i n s8 3 6 m b i t sa n dt h e a l g o r i t m p a s s e st h ev e r i f i c a t i o no ff i p s1 4 0 - 2s e c u r i t yr e q u i r e m e n t s i nt h ep a r to ff p g a i m p l e m e u to fd e sa n d i t s i m p r o v e m e n tb a s e d o nc h a o s ，t h e d e s i g n f o rd e s i m p l e m e n t e di n f p g ai s e m p h a s i z e d ，i n c l u d i n gt h ed e s i g n o fo p e r a t i o nm o d u l e ， s u b k e yg e n e r a t o rm o d u l ea n dc o n t r o lm o d u l e f o rt h ed e f i c i e n c yo fk e ya n dt h e f e a t u r eo fd e s a l g o r i t h m ，a ni m p r o v e dm e t h o di sp r e s e n t e db a s e do nk o l m o g o r o v f l o w sm a p p i n ga n dt h ek e yo fe n h a n c e da l g o r i t h mi n c r e a s e sf r o m5 6b i t st o1 3 6 b i t s ， w h i l et h er e l i a b i l i t yo fd e si sr e m a i n e d f i n a l l y , t h e p a r a l l e li n t e r f a c ei ne p p m o d ei s d e s i g n e da n dt h ew h o l ed a t ae n c r y p t i o ns y s t e md e s i g n i n gb e t w e e nf p g a a n dp ci s g i v e n t oc a r r yo u tt h ev e r i f i c a t i o no f d a t a e n c r y p t i o nr e s u l t s k e y w o r d s ：c h a o s ， e n c r y p t i o n ， f p g a ，d e s ，v h d l k e y 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工 作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的研 究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出贡 献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被查 阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： 日期： 南京航空航天大学硕士学位论文 3 一d e s ： a e s ： c l b ： c p l d ： c p r b s d e s e p p ： f i p s f p g a ： f s m ： i p ： k f l o w s l f s r ： l u t ： p l d ： p r n g ： x s t ： s r l l 6 ： v h d l 注释表 t r i p l ed a t ae n c r y p t i o ns t a n d a r d a d v a n c e d e n c r y p t i o ns t a n d a r d c o n f i g u r a b l el o g i c b l o c k c o m p l e xp r o g r a m m a b l el o g i c d e v i c e c h a o t i cp s e u d or a n d o mb i n a r y s e q u e n c e d a t a e n c r y p t i o ns t a n d a r d e n h a n c e dp a r a l l e lp o r t f e d e r a li n f o r m a t i o n p r o c e s s i n g s t a n d a r d s f i e l dp r o g r a m m a b l eg a t e a r r a y f i n i t es t a t em a c h i n e i n t e l l e c t u a lp r o p e r t y k o l m o g o r o vf l o w s l i n e a rf e e d b a c ks l l i rr e g i s t e r l o o k u pt a b l e p r o g r a m m a b l el o g i cd e v i c e p s e u d or a n d o mn u m b e rg e n e r a t o r x i l i n xs y n t h e s i st o o l s 16 b i tp r o g r a m m a b l e o u t p u tt a ps h i f t r e g i s t e r si nas i n g l e4 - l u t v h s i ch a r d w a r ed e s c r i p t i o nl a n g u a g e 3 重数据加密标准 高级加密标准 可配置逻辑模块 复杂可编程逻辑器件 混沌伪随机二进制序列 数据加密标准 增强型并口 联邦信息处理标准 现场可编程门阵列 有限状态机 知识产权 柯尔莫哥洛夫流 线性反馈移位寄存器 查找表 可编程逻辑器件 伪随机数发生器 x i l i n x 综合工具 基于查找表的1 6 位可编 程移位寄存器 高速集成电路硬件描述 语言 南京航空航天大学硕士学位论文 第一章绪论 计算机网络通信技术的蓬勃发展，给人们的工作和生活提供了巨大的方便， 缩短了人与人之间的距离，淡化了国与国之间的界限。但也随之产生了越来越 严重的信息安全问题，大量的敏感数据直接通过公共信道进行传递和交换，给 非法的第三方提供了盗取、查看、篡改甚至攻击的可能，信息安全己成为当前 以及未来相当长时期内亟待解决的一大难题。 1 1 密码学概述 提到信息安全，人们首先会联想到密码学。密码学是以研究数据秘密通信为 目的的一门科学，它的理论基础之一是1 9 4 9 年香农( s h a n n o n ) 发表的保密通 信理论l l j ，经过数十年的发展和应用。密码学已逐渐成为- - 1 7 崭新的、系统的学 科门类，许多密码标准已经广泛融入到了人们的工作、生活之中，如d e s ( d a t a e n c r y p t i o ns t a n d a r d ) ，i d e a ( i n t e r n a t i o n a l d a t a e n c r y p t i o na l g o r i t h m ) ， a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 等密码标准。 一、密码学的一些基本概念 加密前的信息简称为明文( p l a i n t e x t ) 在本文中以p 或m 表示； 加密后的信息简称为密文( c i p h e r t e x t ) ，以c 表示； 从明文到密文的变换称为加密运算( e n c r y p f i o n ) ，以e ( ) 表示； 从密文到明文的逆变换称为解密运算( d e c r y p f i o n ) ，以d ( ) 表示； 密码系统的典型模型如图1 ，1 所示。 图1 1 密码系统模型 囝趣 磊 矿 ，厂一厂_ 一 l c 一 獬髫翌 对一 i 匡虱 基于混沌的数据加密算法的研究及f p g a 实现 加密和解密都是在密钥( k e y ) 的控制下进行的，给定一个密钥，就可以确定一 个具体的加密变换和解密变换。一个密码体制通常由以下五部分组成： ( i ) 明文空间：全体明文的集合。 ( 2 ) 密文空间：全体密文的集合。 ( 3 ) 加密算法：由加密密钥控制的加密变换的集合。 ( 4 ) 解密算法：由解密密钥控制的解密变换的集合。 ( 5 ) 密钥空间：全体密钥的集合，包括加密密钥也和解密密钥如。 在密码体制中，要求加密变换和解密变换是一对可逆变换，即对任意的明文 m 要求有 ( & ( m ) ) = m ( 1 1 ) 成立。密钥空间中不同密钥的个数称为密码体制的密钥量，它是衡量密码体制 安全性的一个重要指标。 如果一个密码体制的加密密钥与解密密钥相同，即( 1 1 ) 式中吒= 缸则称其为 对称密码体制，否则为非对称密码体制。本文研究的是对称密码体制，而且是 以如何设计算法、保护和隐藏明文信息来抵抗窃听型对手的被动攻击为主要研 究内容。 二、密码安全性能分析 对于一个密码体制，分析者主要采取以下四种攻击方法瑚： ( 1 ) 唯密文攻击法：破译者只能截获到密文c ，欲由密文直接破解出明文。 ( 2 ) 已知明文攻击法：破译者拥有一些明文一密文对 m l ，q ， n ：，c ： ，q ) ，欲由这些明文一密文对，求出解密密钥，或求出下一个密 文c 。 ( 3 ) 选择明文攻击：破译者可选择明文码，m ：，m ，由密码系统将 其加密为c 1 ，c ：，c j ，并送回给破译者，破译者据此进行攻击。 ( 4 ) 选择密文攻击：破译者选择一些密文，由密码系统将其解密为踢文( 可 能该明文并无任何意义) ，并送回给破译者，破译者据此进行攻击。 以上四种攻击方法的强度依次增强，选择密文攻击方法是破译者获取信息最 多和对密码系统最具威胁的一种攻击手段。传统的密码系统，只需密码能抵抗 唯密文攻击即可，但现在的密码系统必须经得起选择密文攻击，方可称得上安 全。 2 南京航空航天大学硕士学位论文 为了确保算法的安全性，一个好的密码体制至少应满足以下两个条件吲： ( 1 ) 在已知明文m 和加密密钥屯时，计算c 2 & ( m ) g n 在已知密文c 和 解密密钥屯时，计算州2 ( c ) 容易。 ( 2 ) 在不知解密密钥幻时，由密文c 推知明文m 几乎不可能。 1 2 基于混沌的数据加密技术及其研究现状 近年来，芯片的运算速度按照摩尔定律指数增长，加上密码分析者的破译水 平不断提升，传统密码学在一些领域已经不能满足当前的需要。如1 9 7 7 年被美 国国家标准局n i s t ( n a t i o n a li n s t i t u t eo fs t a n d a r d sa n dt e c h n o l o g y ) 公布为数据 加密标准的d e s ，就于1 9 9 8 年被电子边境基金会e f f ( t h ee l e c t r o n i cf r o n t i e r f o u n d a t i o n ) 用2 5 万美元制造的专用计算机，用5 6 小时破解了d e s 的密钥，这 些都对传统密码学提出了新的要求。 与此同时，混沌现象的发现及其快速发展，尤其是混沌同步、控制与反控制 的研究，混沌作为一种特殊的非线性现象，可以用来解决传统密码学中的一些 不足，为现代密码学的发展提供新的思路1 4 【s 1 【6 1 1 1 6 1 。 一、混沌加密技术分类 关于混沌加密技术的大致可以分为以下两大研究方向【7 】【1 5 】【3 0 】： ( 1 ) 以混沌同步技术为核心的混沌保密通信系统，主要是基于模拟混沌电 路系统。 ( 2 ) 利用混沌系统构造新的流密码和分组密码，主要基于计算机有限精度 实现的数字化混沌系统。 混沌保密通信系统的基本思想是，用混沌信号作为整个保密通信系统的载 波，对待加密的数据信息进行调制，将有用信号隐藏在载波信号中，通过收发 双方的混沌同步实现保密通信9 】 1 5 】。目前，国内外关于这方面的理论研究相对 成熟，但是该系统要求收发双方“严格”同步，对模拟电路中的元件精度、传 输信道干扰噪声等提出了苛刻的要求等，这些关键技术限制了目前其在实际中 的广泛应用。 对于另外一个研究方向也即本课题研究的主要内容一一混沌密码，关于这方 面的研究目前相对较少，混沌密码又可以细分为基于混沌的流密码和基于混沌 基于混沌的数据加密算法的研究及f p g a 实现 的分组密码。混沌流密码也称混沌流加密，其核心思想是利用混沌的动态特性 在数字域上构建性能优越的伪随机数发生器p r n g ( p s e u d or a n d o mn u m b e r g e n e r a t o r ) ，然后用此序列与明文序列执行可逆运算，实现加密。例如，本文第 三章中的c p r b s 发生器的设计就是利用了该原理。混沌分组密码则是利用混沌 系统的动态特性，由于混沌的输入输出转换关系复杂，通过多次的置乱和替代 运算，可以达到信息隐藏的效果。本文的第四章中d e s 的柯尔莫哥洛夫流的增 强就是该思想的具体实现。 二、研究现状 数据混沌加密技术是当前国内外研究的一大热点。在混沌流密码领域，主要 有英国数学家r m a t t h e w s 最先利用混沌映射构造随机序列进行数据加密的研 究【1 0 1 ，以及其他一些学者对混沌二进制伪随机序列的设计方法的研究【“1 。而在 混沌分组密码方面，有t h a b u s t u 提出的采用分段帐篷映射的混沌反系统方法， 国内的李树钧等人提出的引入扰动的h a b u s t 增强算法，以及一些学者提出的采 用混沌映射替代传统分组密码中的s 盒等【l 甜。然而，由于密码是有限域上的运 算，连续域上的混沌系统在离散的相空间里将出现严重的特性退化问题，出现 固定的稳定状态，呈现周期性，而具体的特性退化和量化位数之间的关系，至 今还没有被发现，这也是当前混沌密码学中的一大难题。 根据混沌密码实现方式的不周，可以将其分为两个方向；一是软件实现的方 法，采用双精度浮点数运算，借以提高混沌映射数字化后的周期，其致命缺点 是，要求内存大，运算速度慢，尤其对图像、视频等多媒体数据而言，不能满 足实时性的要求；另外一种也就是本文研究的主要内容，是利用硬件实现的方 法如采用专用集成电路a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 、可编程逻 辑器件f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) c p l d ( c o m p l e xp r o g r a m m a b l e l o g i cd e v i c e ) 的硬件设计，对混沌进行数字化处理来产生伪随机序列，实现对 明文的加密，在尽量提高精度，逼近混沌特性的同时，提高运算速度，满足工 程中实时处理韵要求。采用f p g a 设计可以满足高速实时处理的要求，对于加 密算法，虽然定点数运算会使混沌特性下降更为严重，但只要能满足计算上安 全等要求，仍可以成功的运用到工程实际中。 三、基于f p g a 的数据加密方案可行性 4 南京航空航天大学硕士学位论文 由于f p g a 是基于s r a m ( s t a t i cr a m ) 的技术，用f p g a 设计的电路不具 保密性，也即本课题实现的算法电路可以被破译者轻松获得 1 ”，这一缺点并不 影响其采用f p g a 实现的可行性。在经典密码学中，k e r e k h o f f 在文献 1 3 1 中提 出了最大假设理论，该理论认为，一个密码系统之所以安全仅依赖其解密密钥， 而不在于算法本身的保密性，即在一个密码系统中除解密密钥外，其余的a n 解 密算法等，均应假设为破译者完全知道，只有在这个假设下，破译者仍无法破 解密码系统，此系统方有可能被称为安全。现行的密码标准d e s 、a e s 等都是 以k e r c k h o f f 最大假设理论为前提，密码算法都是公开的。因此，采用f p g a 来 实现加密算法的硬件电路，并不影响本课题的可行性。 1 3 本文研究的主要内容 目前基于混沌的数据加密技术主要采用软件方法来实现，软件实现具有便于 修改、易于实现和适应性好等优点，但其实现速度受到制约，尤其是为了尽量 保留原有混沌特性，采用浮点数运算，所需内存极大，造成a n 解密速度非常缓 慢，难以满足当前高速实时性处理的要求。 本文主要对基于混沌的数据加密算法及其f p g a 实现进行了探讨和研究。提 出了基于l o g i s t i c 映射和线性反馈移位寄存器结构的流加密算法；针对d e s 算 法本身的特点，提出了在d e s 中引入柯尔莫哥洛夫流的混沌增强方案：两个算 法都具有安全性能高、密钥空间大、适于f p g a 高速实现等特点。由于整个数 据加密系统是基于f p g a 实现的，不仅解决了快速a n 解密的要求，而且大大缩 减了电路体积，提高了系统的稳定性和密钥存储的安全管理。 本文研究的主要内容安排如下： 第二章：在简要介绍了混沌的概念及其三大基本特性后，从五个方面详细分 析了混沌与密码学之间的关系，并以具体实例讲述了理论安全和实际安全概念。 通过本章的分析叙述，为后两章基于混沌的数据加密算法设计提供了理论指导。 第三章：首先对流密码和l o g i s t i c 映射分别作了简要介绍。然后提出了基于 混沌映射的c p r b s 伪随机序列发生器的设计原理，该发生器利用l o g i s t i c 映射 替代了线性反馈移位寄存器l f s r ( l i n e a rf e e d b a c ks h i f tr e g i s t e r ) 中的线性布 尔反馈函数，结合了混沌和l f s r 的各自优点；在v h d l 描述时，通过调用s r l l 6 ( s h i f tr e - g i s t e rl u t 4 ) 宏单元设计，显著降低了片内资源消耗。在此基础上提 5 基于混沌的数据加密算法的研究及f p g a 实现 第四章：首先简要介绍了d e s 分组密码算法，然后详细研究了d e s 在f p g a 上实现的过程，包括运算模块、子密钥扩展模块以及控制模块的v h d l 设计， 并根据所选x c 2 s 1 0 0 t q l 4 4 芯片的特征结构，对d e s 的核心s 盒进行了优化设 f l o w s 增强d e s 的置乱功能，进而实现增加密钥空间的混沌增强方案：最后对本 第五章：在前面提出的算法及实现的基础上，设计了基于p c 机与f p g a 间 的数据加密系统，用以实现数据加解密的现场调试。首先叙述了f p g a 的选用 原则，重点阐述了e p p 模式并行接1 3 的f p g a 实现，包括上位机p c 的编程和 踢蒸疰 6 明文 图1 2 数据加密系统结构 明文 南京航空航天大学硕士学位论文 第二章混沌及其与密码学关系 2 1 混沌及其特性 混沌( c h a o s ) 现象的发现，可以上溯到十九世纪末法国庞加莱( i - i p o i n c a r e ) 的 工作，由于当时理论基础与实验条件的不足，对混沌现象本质的揭示还不够彻 底。而现代意义的混沌起源于2 0 世纪6 0 年代，美国气象学家洛仑兹在用计算 机作数值天气预报研究时发现，气候不能精确重演，指出了非周期性与不可预 见性之间的联系，即著名的“蝴蝶效应”，之后关于混沌的研究进入了飞速发 展阶段，进而使其成为- - f l 新的学科混沌学【1 3 】。 所谓混沌就是指确定性系统中出现的一种貌似无规则、类似随机的现象。虽 然有关混沌的研究文献众多，但科学界对于混沌至今没有一个统一严格的定义。 以下是一个关于混沌的定义，在实际中较为常用，并被国内外大部分学者所接 受，是由d e v a n e y 提出的【l ”。 设矿是一个度量空间，映射，：矿专y 如果满足以下三个条件，便称厂在y 上是混沌的： ( 1 ) 对初值敏感依赖：存在5 0 ，对任意的 0 和任意的羔矿，在x 的 邻域内总存在y 和自然数n ，使得d ( f ”( x ) ，厂“( y ) ) 占成立： ( 2 ) 拓扑传递性：对v 上的任何一对开集x ，r ，存在k 0 ，使得 f 。( x ) n y 西： ( 3 ) 厂的周期点集在v 中稠密。 若一个系统能同时满足以上三个条件，则一般认为该系统为混沌系统。虽然 各种关于混沌的定义略有不同，但总结起来可归纳如下：对于由系统任意两个 初始点，其引出的两条轨道时而无限靠近，时丽相互远离，两种情形无数次交 替出现，系统的长期行为不具规律性，是一种随机现象。并且具有以下三大基 本特性： ( 1 ) 蝴蝶效应：即对初值的极端敏感性，无论两个点x ，y 离得多么近，在 映射厂的作用下，两者的轨道都可能分开。 ( 2 ) 拓扑性：即任一点的邻域在，的作用下将“扩散”到整个度量空间， 这就说明厂不能细分为两个在厂映射下不相互影响的子系统。 ( 3 ) 确定性：尽管混沌具有类似随机的性质，但是它是确定性的运动，其 7 基于混沌的数据加密算法的研究及f p g a 实现 运动的轨迹仅决定于初值和混沌映射的参数。 这三大基本特性是混淹表现出的性质，并非是判断个系统是否属于混沌系 统的充要条件。在实际较为实用的判决公式是l y a p u n o v 指数公式： 捌：，；族羲溉一的。 ( 2 1 ) 蔡氏电路、l o g i s t i c 映射、k o l m o g o r o vf l o w s 都是典型的混沌系统，也是当 前研究的热点。 2 2 混沌与密码的关系 混沌与密码分属两个不同的学科，但两者之间具有很强的联系性和相似性， 密码中隐含着一定的混沌，混沌中隐含着密码。一个好的密码可以看成是一个 特殊的混沌系统系统。如d e s 中的s 盒就是与混沌相似的确定性类随机操作， k o c a r e v 等人甚至给出了分组密码与混沌之间的联系 1 6 】 1 9 1 1 2 0 川】。 通过本课题的研究，关于混沌与密码之间的联系性和相似性进行了以下五个 方面的总结。 ( 1 ) 都属于确定性的变换 在密码体制中，明文数据无论经过多少次的轮运算，只要密钥与明文确定， 其输出也是确定的。例如在分组加密中，明文数据在密钥控制下，通过置乱、 替代反复操作，在可取的相空间里，其值分布具有类随机性，但其密文是确定 的，有且只有一个，不会出现个明文对应多个明文情况的出现。 对于混沌系统而言，给定一个动态时间序列方程的控制参数、初始值，经 过多次迭代后，从其输出的分布来看，具有类随机性，但是这些输出又是确定 的，而不是随机的，只要知道控制参数、初始值，任意时候的输出是可以预测 的。 总结起来讲，密码与混沌都是决定性的随机性，只要知道初始状态( 密钥 和明文) 和动态方程( 密码算法) ，其输出又是确定的，正是基于这一点，才 使得混沌和密码可以被运用到工程实际中。 ( 2 ) 都具有拓扑传递性 流密码中通常采用密文反馈的形式，前面的明文序列和密钥序列间接参与到 后续密文的生成，使得明文或密钥的每一位影响到密文的许多位；分维密码中， 8 南京航空航天大学硕士学位论文 初始密钥和明文都存在多轮的移位置乱操作，来产生不同的中间密文，替代运 算将会根据不同的中间密文得到截然不同的输出，从而产生“雪崩效应”。密 码中的这种拓扑传递性可以有效抵抗分析者的逐段分块破译。 而在混沌系统中，从某个初始点出发的轨道将在整个相空间中遍历，而不会 被分割成几个独立、互不影响的子空间。 ( 3 ) 都对对初始条件极端敏感 在流密码中，对于两个略有差别的明文序列，给定相同的密钥，其密文输出 显著不同，在第三章的混沌流密码设计中，本文就专门以l e n a 图作为例子对此 特性进行了验证。在分组密码中，给定相同的密钥，只改变明文块的某个比特 位的值，加密后得到的两个密文块间也几乎找不出必然的联系性。 而在混沌系统中，对于无论如何靠近的两个点，经过多次迭代，其轨道最终 趋于分开。 ( 4 ) 都需多轮运算 在分组密码中，一般具有多轮的f e i s t e l 网络或s p 网络，f e i s t e l 网络或s p 网络主要包括置乱和替代操作，经过多次轮函数运算，利用拓扑传递特性，将 明文信息打乱。 而在混沌系统中，则是利用动态系统方程的循环迭代，使系统表现出强有力 的混沌特性。 ( 5 ) 都具有较高的计算复杂度 在密码系统中，安全性是最为关键的，而安全性是通过计算复杂度来保证的。 也就是使破译者利用有限的计算资源，在有限时间和不知密钥的情况下，解密 变换p = d ( k ，c ) 的求取是相当复杂，不可能实现的。而对于知道密钥的收发双方 却可以轻松实现解密，这就使得密码相当于一个单向函数。 而在混沌系统中，动态方程虽然形式简单，但其表现出的行为特性却极其复 杂，知道系统的控制参数和初值情况下，要求出其下一时间序列的输出是轻易 的，但只要其中有一个条件未知，则无论如何计算也是无法确定其下一个点的 具体状态。 混沌与密码虽然关系紧密，然而，两者却存在很大的区别，其中最重要的一 点是就是两者定义域的不同。混沌是定义在连续域上的，取值范围是无穷大相 空间，而密码是定义在有限的离散域g f ( 2 ”) ，其l e b e s g u e 测度为0 ，n 越大， 其可取范围越大，但仍为可列子集，测度为0 。因此，将混沌引入到密码中，会 q 基于混沌的数据加密算法的研究及f p g a 实现 涉及到混沌特性退化的问题，原来连续域上不曾出现的周期性问题，将重新出 现，n 越大，其周期长度也相应变长，但具体的周期长度与量化位数以关系尚未 被揭露，而且与所取初值相关。因此，利用混沌来设计密码时，不能将数字化 的混沌系统直接用于密码学。 2 3 理论安全及实际安全 前面叙述了混沌在有限相空间所产生的严重问题，使得密码学中应用混沌变 得相当困难，本节通过理论安全与实际安全的分析，来探讨密码中引入混沌的 可行性。 在密码学中，安全性是最高的评价准则，再好的密码系统，若其安全性不足 仍不可取，为此，香农在混沌保密通信理论中对理论安全和实际安全进行了定 义 t l 。理论安全是指破译者无论截获多少密文c ，并对之加以分析，其结果是与 直接猜明文m 是一样的。实际安全是指在不能满足理论安全情况下，选用最佳 破译方法，对于具有有限计算能力及内存的破译者，无法在合理的时间内破解 密码系统。 香农用理论证明了要达到理论安全，必须使加密密钥的长度大于等于明文长 度，也及一次一密密码本系统。但是，当明文长度较长，如何获得和管理比明 文更长的密钥是一大难题，特别是对于利用硬件实现时，资源相对不足使这一 问题尤为突出。 可见，理论安全在实际中难以得到满足和应用，现行的各种加密标准都是针 对实际安全的目标而设计的。香农在其保密通信理论中提出假设假设每一密 码系统在给定开位密文时，均有一破解此系统的最少工作次数( 竹) ，显然n 趋 于无穷大时，( n ) 也为无穷大，实际设计时，只要使矿( 以) 满足相应指标即可。 例如，假设n l = n 5 ，n 2 = 2 “，m = n ! ，若破译者的运算速度为1 0 6 次s ，表 2 1 列出了t l 与破解时间关系。 表2 1l , l 与解密时间关系 胛52 “”1 1 , 1 = 1 00 1 s0 0 0 0 l s3 6 s n = 1 0 01 0 4 j 2 8 h1 0 1 6 年 1 0 1 7 6 每 以= 1 0 0 01 0 9 j 1 0 年1 0 2 “盔1 0 2 9 ”世纪 l o 南京航空航天大学硕士学位论文 前面分析了混沌的特性退化问题，由表2 1 可知，只要在设计过程中合理的 运用混沌，最大可能的保留和发挥混沌的特性，使其产生的周期足够长和足够 乱，破解所需运算次数足够大，满足实际安全标准即可。 2 4 基于混沌的密码设计步骤 根据本课题的研究，对基于混沌的数据加密方法的设计步骤进行了如下总 结： ( 1 ) 选择合适的混沌映射。所选混沌应具有很好的混迭特性，输出特性复 杂，控制参数集应足够大，另外，由于本课题是基于f p g a 实现的，因此混沌 映射本身的算法不能过于复杂，否则难以数字实现。 ( 2 ) 引入加密参数。选择哪些参数可以作为密钥，参数范围是什么，以及 如何适当的选择以利于f p g a 设计。 ( 3 ) 混沌映射离散化。将原始连续域上的混沌映射离散化，在此过程中应 力求保证混沌原有的混迭特性，并分析其特性退化、周期性等问题。 ( 4 ) 分配密钥。选定用来加密的密钥，使密钥空间足够大，以抵抗穷举攻 击。 ( 5 ) 安全性能分析。密码算法设计过程或之后，应根据测试标准进行安全 性能测试，但需指出的是，由于无法预估破解者的分析水平，即使满足了测试 标准，也很难能保证算法是绝对安全的。 基于混沌的数据加密算法的研究及f p g a 实现 第三章基于混沌的流加密算法设计及其f p g a 实现 流密码的设计关键在于伪随机序列发生器的设计 2 1 ，本章设计的c p r b s 发 生器充分发挥了l o g i s t i c 映射和l f s r 的各自特点，其输出的密钥序列通过了 f i p s1 4 0 2 标准测试。在此基础上，文章给出了适于图像、视频等大批量数据的 流加密算法及其f p g a 实现过程，实现后的加密速度可达8 3 6 m b i t s ，密钥空间 达1 2 8 位。 3 1 流加密概述 一、基本原理 流加密也称为序列加密，属于对称密码系统，其加( 解) 密原理非常简单， 就是用一个随机序列与明文序列进行运算来产生密文，再用同一个随机序列与 密文序列进行可逆运算恢复明文，初始密钥通过秘密信道传送给接收方既。其密 码体制模型如图3 1 所示。 图3 1 流密码体制模型 流加密是一种记忆性组件，即前面的密钥流影响后续密钥流的输出 3 l 。从理 论上来说，当流密码的密钥长度大于被加密信息的长度，且密钥是完全不可预 测的随机数时，可以获得理论上的绝对安全性，但这种密码系统在实际使用中 是无法实现的，也是不可行的。于是，人们考虑可否寻找一种方法，采用短的 密钥种子产生具有足够长周期的伪随机序列，实现这种一次一密密码本的基本 思想【2 】【3 】。 由于流密码的安全性主要依赖于伪随枫序列，为了抵抗攻击者对密钥流的统 1 2 列一 一 蝴蒌一i蒌著 姘坠 ，一 道 划 熊 燃 娥 篓 艘羞凼军一互盥篆 罂 南京航空航天大学项士学位论文 计分析，应使密钥流足够“乱”，周期足够“长”，为此，香农提出了密码体制 设计的两种基本方法：混淆( c o n f u s i o n ) 和扩散( d i f f u s i o n ) 【1 。混淆就是将密 文与密钥间的关系尽可能复杂，使得攻击者即使知道密文的统计特性也无法推 敲密钥的统计特性。扩散就是让明文中的每一位影响密文中的许多位，或者说 是密文中的每一位受到明文中许多位的影响，这样可以有效隐蔽明文的统计特 性。 可见设计一个好的流密码的关键，在于如何设计一个性能优良的密钥序列发 生器，由该密钥序列发生器输出的密钥流应具有便于软硬件实现、周期长、不 可预测性等特性。 二、伪l 睫机序列发生器 目前流密码中采用的随机序列发生器主要有线性反馈移位寄存器l f s r 、线 性同余器，以及在此基础上的线性组合或非线性组合。 ( 1 ) 线性反馈移位寄存器l f s r l f s r 具有易于硬件实现和便于安全性能分析的优点，目前在流密码中获得 广泛应用，调整其内部的抽头反馈，可以获得m 序列。l f s r 主要由两部分组成： 移位寄存器和线性反馈函数。其典型结构如图3 _ 2 所示。 q ha 0 图3 2l f s r 结构图 图中的a o ，q ，为二值存储单元d 触发器( 寄存器) ，构成移位寄存器部 分，为该反馈移位寄存器的级数，在时钟控制下，q 将其内容赋给相邻的a 。， 寄存器中的内容( 口0 ，q ，) 为l f s r 每一时刻的状态；其余部分构成布尔反馈 函数f ( a l ，a 2 ，q ) = c 1 8 。o c 2 一l e c n a o ，当各个抽头系数满足本征多项式条 件时，该l f s r 可以获得脚序列输出。 ( 2 ) 线性同余器 1 3 嚣蒜 基于混沌的数据加密算法的研究及f p g a 实现 线性同余发生器也是应用较为广泛的一种伪随机数发生器，其一般形式为 x = ( n 靠+ 6 ) r o o d n ( 3 1 ) 而为初始值，以此公式展开便可产生伪随机数，再与给定的某个数比较，用来 产生二进制伪随机序列。当式( 3 1 ) 中的口，b ，n 满足一定的条件时，可以获得 最大周期长度。 l f s r 和线性同余器虽然都能产生较长周期的伪随机序列，尤其是l f s r 的 结构简单，非常适合f p g a c p l d 的高速实现，然而目前的许多研究表明，单纯 由l f s r 或线性同余器设计的密码已被成功破译【2 5 l 。以1 0 级的l f s r 为例，m 序列周期长度为2 ”一1 = 1 0 2 3 ，其最大线性复杂度为工= 1 0 ，由式( 3 2 ) 知，破 译者只需知道任意一段连续的2 0 个输出序列( a n + ，g n ，a n 。) ，即可求出其 特征多项式，从而成功破译下一段密文。 引斗 ( 3 2 ) 因此，用已知明文攻击方法对此类序列密码的攻击非常奏效，密码设计时不 能仅以简单的l f s r 来生成伪随机序列。对于线性同余器，式( 3 1 ) 可以被认 为是式( 3 3 ) k l = ( d 靠+ b ) m o d l ( 3 3 ) 的数字化，由l y a p u n o v 指数公式计算公式 五：l i m 土争l i l 一”智 = 1 n a 当式( 3 4 ) 中a i 时，该映射是混沌的。 本身就与混沌存在着紧密的联系，因此， 能更优的伪随机序列发生器。 3 ，2l o g i s t i c 映射及其数字化 1 4 ( 3 4 ) 可见，一些传统的伪随机序列发生器 可以考虑采用混沌映射来重新构造性 一维l o g i s t i c 映射是典型的虫口模型之一，其表达式如下 1；j ；警； 之 南京航空航天大学硕士学位论文 x 。+ l = “x 。( 1 一工。) ，( 疗= 1 ，2 ，) ( 3 5 ) 其中初始值x o ( o ，1 ) ，当3 茎“茎4 时，系统的动力学形态十分复杂，系统由倍周 期变为混沌1 1 8 i 。一般取“= 4 ，式( 3 5 ) 变为： h 。= 瓴( 1 一籼伽= l 夸 ( 3 6 ) 由式( 3 6 ) 构成的动态系统在连续域上是混沌的，而在( 0 ，1 ) 内任意取值，例如 取x o = o 0 0 1 5 ，其动态时间序列如图3 _ 3 所示。 图3 3 l o g i s t i c 映射动态时间序列 其中，式( 3 6 ) 混沌成立的条件是矗取值是( 0 ，1 ) 的连续域，其分辨率是无 穷大的。当其在计算机上采用软件实现时，由于是有限字长运算，存在计算误 差，原先混沌的系统将重新出现周期性，计算精度越高，周期有相应变长的趋 势，两者之间具体关系目前尚未揭露。对l o g i s t i c 映射的n 位数字化，其结果如 下： 确= k 口飞) l = q l 2 一) ( 3 7 ) 初始值取 0 ，1 ，2 ，2 “一1 ) 之间的整数。可见，由式( 3 7 ) 输出的序列，其 最大的周期不可能超过2 ”。实验过程中，取量化位数井等于8 进行了实验，初 始状态而的取值不同，其周期长度也互不相同，其平均周期长度约为3 7 ，可见 混沌映射数字化后，其混沌特性急剧下降。这是由于数字化过程中，存在计算 误差，在式( 3 7 ) 中，输出矗+ 忽略了小数部分，经过多次循环迭代将出现固定 的周期或稳定点；当量化位数刀显著增大时，计算精度显著提高，其周期长度也 相应变长，周期性逐渐减弱；当丹取无穷大时，不存在计算上的舍去误差，此时 等同于连续域上的混沌映射。 1 5 基于混沌的数据加密算法的研究及f p g a 实现 3 3 基于混沌映射的流加密算法设计及其f p g a 实现 由前两节分析发现，l f s r 虽具有周期长、随机性好、易于f p g a 高速实现 等优点，但由于其布尔反馈函数的缺陷，在已知明文攻击下，密码系统非常脆 弱，很容易被攻击者分析破译。而混沌映射具有内在的伪随机性和遍历性特点， 很适合用于伪随机序列发生器的设计。通过最简单的一维混沌映射式( 3 3 ) 所 构成的线性同余器，揭示了混沌与密码的内在联系，有力的证明了混沌在设计 伪随机序列方面具有的优势。为此，本文提出了基于l f s r 和混沌映射构建的 c p r b s 发生器，该发生器结合了l f s r 和混沌各自特点。且适于f p g a 的高速 实现。 3 3 1 基于l o g i s t j c 映射的c p r b s 发生器的设计 l f s r 的线性反馈函数已经能被现有的统计方法分析，求出其特征多项式， 然而，l f s r 产生的m 序列具有周期最大化的优点，而且适合