（信号与信息处理专业论文）基于智能算法的s盒设计研究.pdf

基于智能算法的s 盒设计研究 摘要 s 盒是分组密码中的唯一非线性部件，它的密码强度了决定整个 分组密码的安全强度。一般使用传统的数学方法构造出性能优异的s 盒是非常困难和复杂的，近年来仿生智能优化算法已在经典的n p c 等问题的求解和实际应用中表现出强大的生命力。本文提出了三种基 于智能优化算法构造s 盒的方案，主要的工作如下： 1 、采用遗传算法优化s 盒，在染色体的编码方式上保证s 盒是完 全正交的，为定量的描述雪崩效应给出了“雪崩度”的定义，接着使 用优先权布尔矩阵的交算子来实现交叉操作和变异操作，并在迭代过 程中自适应线性地修正交叉概率和变异概率，通过实验获得的s 盒在 非线性度、差分均匀度和雪崩效应上都得到了较大的改善。 2 、采用免疫算法优化s 盒，通过分析布尔函数的w a l s h h a d a m a r d 变换、自相关性和雪崩效应等，推导出布尔函数的两个优化规则，基 于这两个规则提取出抗体的疫苗，从而使生成的抗体能够有策略的进 化种群，通过实验获得的s 盒在非线性度、差分均匀度和自相关性上 都得到了较大的提升，最后将该算法与遗传算法优化s 盒之间的性能 进行了深入的对比与分析。 3 、采用蚁群算法优化s 盒，首先构造出s 盒的城市模型，设计出 选路规则和信息素更新策略，接着对该算法进行优化：引入遗传算法 的设计思想( 利用遗传算法生成一批性能较优的s 盒，将这批s 盒 作为蚂蚁的初始哈密顿回路，从而成初始信息量；将遗传算法的 交叉、变异算子引入到蚁群算法的每次循环遍历过程中) ，最后将实 验结果以及算法的收敛性等与其它算法进行比较，分析各自的优越 性。 关键词：s 盒差分分析线性分析遗传算法免疫算法蚁群算法 c o n s t r u c t i no fs b o x e sb a s e do n i n t e l l i g e n ta l g o i u t h m s a b s t i 认c t s - b o x e sa l et h eo n l yn o r a i n e a rc o m p o n e n t si nm a n yb l o c kc i p h e r t h e i r e r y p t o g r a p h i cp r o p e r t i e sh a v ed e t e r m i n e dt h es e c u r i t yo ft h ew h o l ec i p h e ra l g o r i t h m s i ti sq u i t ec o m p l i c a t e da n dd i f f i c u l tt oc o n s t r u c ts - b o x e sw i t hg o o dc h a r a c t e r i s t i c sb y t r a d i t i o n a lm a t h e m a t i cm e t h o d s i n t e l l i g e n ta l g o r i t h m sh a v es h o w ns t r o n gv i t a l i t yi n t h ef i e l do fn p cp r o b l e m si nr e c e n ty e a r s t h r e ea l g o r i t h m sb a s e do l li n t e l l i g e n t a l g o r i t h m si sp r o p o s e dt oc o n s t r u c ts - b o x e s ，a n dt h r e ep r i n c i p a la c h i e v e m e n t sh a v e b e e no b t a i n e di nt h i st h e s i s f i r s t l y , s b o x e s a r e o p t i m i z e db yg e n e t i ca l g o r i t h m 1 1 1 eg u a r a n t e e o f o r t h o g o n a l i t y i sb e c o m ee f f e c t i v eb yc o d i n gt y p e c r o s s o v e ra n dm u t a t i o n p r o b a b i l i t i e sa r ea d a p t i v ei ni t e r a t i v ep r o c e s s b a s e do nt h i sc o n s t r u c t i o nm e t h o d ，t h e f l o wc h a r to fc o n s t r u c t i n gs - b o x e si sg i v e na n dt h eg r o u po fs - b o x e sw i t hh i 9 1 l n o n l i n e a r i t ya n dl o wd i f f e r e n c eu n i f o r m i t ya r eg e n e r a t e d s e c o n d l y , s - b o x e sa r eo p t i m i z e db yi m m u n ea l g o r i t h m t oa n a l y z e m t t r a n s f o r r n a t i o na n da u t o c o r r e l a t i o no fb o o l e a nf u n c t i o n s ，t w or u l e st oo p t i m i z e b o o l e a nf u n c t i o n sa r ed e d u c e d ，a n dt h e ne x t r a c t i o nv a c c i n eb a s e do nt h e s et w or u l e s b a s e do nt h i sc o n s t r u c t i o nm e t h o d ，t h ef l o wc h a r to fc o n s t r u c t i n gs b o x e si sg i v e n a n dt h eg r o u po fs - b o x e sw i t hh i g hn o n l i n e a r i t ya n dl o wa u t o c o r r e l a t i o nu n i f o r m i t y a r eg e n e r a t e d f i n a l l y , s - b o x e sa r eo p t i m i z e db y , w h i c hc o m b i n e st h em e e h a n i s mo ff e e d b a c k o r g a n i c a l l yw i t ht h et h i n k i n go fe v o l u t i o n ，a c c o r d i n g l yd e v e l o p se n o u g ha d v a n t a g e s o ft h et w oa l g o r i t h m s b a s e do nt h i sc o n s t r u c t i o nm e t h o d ，t h ef l o we h a no f c o n s t r u c t i n gs - b o x e si sg i v e na n dt h eg r o u po fs - b o x e sw i t hh i g hn o n l i n e a r i t ya n d l o wd i f f e r e n c eu n i f o r m i t ya leg e n e r a t e d t h es i m u l a t i o nr e s u l t ss h o wt h a tt h i sk i n do f c o n s t r u c t i o nm e t h o di sb e t t e ra tr e d u c i n gal a r g er e d u n d a n c yc a l c u l a t i o na n d q u i c k e n i n gt h es p e e do fc o n v e r g e n c e ，c o m p a r e dw i t ht h eo n eb a s e do ng e n e t i c a l g o r i t h m k e y w o r i d s ：s - b o x e s ；n o n l i n e a r i t y ；d i f f e r e n c eu n i f o r m i t y ；g e n e t i ca l g o r i t h m ； i m m u n ea l g o r i t h m ；a n tc o l o n ya l g o r i t h m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论 本人签名： 处，本人承担一切相关责任。 日期：塑监晕qi 艟旦 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适用本授权书。 日期：塑堡垒旦墨目兰多a 日期：至煎& 聋乜l ! 目墨臼 北京邮电大学硕士学位论文 1 1 密码学背景 第一章绪论 人类对密码的研究与应用已有几千年的历史，但密码学作为一门系统科学则 仅仅是上世纪5 0 年代的事情。1 9 4 9 年，信息论创始人s h a n n o n 发表的著名论文 “保密通信的信息理论 【l 】将密码学正式成为- - n 科学。密码学的主要任务是解 决信息的保密性和可认证性问题，即保证信息的生成、传递、处理、保存等过程 中不能被未授权者非法的提取、删除、重放、和伪造。密码学是一门正在快速发 展的综合性新学科，目前密码学所需要的知识横跨数学、计算机、物理、信息论、 编码学、通信技术等多种学科。密码学是信息安全的核心，为解决当代信息安全 体系提供了许多有效的核心技术，在保护信息的机密性、认证性等许多方面发挥 着关键性的作用。 密码学主要包括两个重要的分支：密码编码学( c r y p t o l o g y ) 和密码分析学 ( c r y p t a n f l y s i s ) 。密码编码学是对信息进行编码实现隐蔽信息的- - t 0 学科，其主 要的目的是寻求保护信息保密性和认证性的方法。密码分析学是研究分析破解密 码的学科，其主要的目的是研究加密消息的破解和消息的伪造。密码编码学和密 码分析学既相互对立，又相互促进着向前一起发展。目前有两种重要的密码系统： 单钥( 私钥) 和双钥( 共钥) 密码系统。在单钥密码系统中明文的加密和密文的 解密使用的是同一个密钥。1 9 7 6 年d i 伍e 和h e l l m a n 引入公钥密码之蒯2 1 ，所有 的密码都是单钥密码，目前单钥密码主要分两种体制：分组密码和流密码，分组 密码是现代密码学研究中的一个重要分支，其诞生和发展有着重要的理论价值和 广泛的实用背景。最初出现的密码本质上是序列密码，它已经广泛地应用于军事、 外交等方面。分组密码是以二十世纪七十年代d e s ( d a me n c r y p t i o ns t a n d d ) 的出现为标志，在这以后得到了广泛的讨论和发展。 为更好的设计分组密码，需要研究满足不同性质的函数类。特别是其存在性、 构造和计数问题，以及不同性质之间的关系，如等价、相容、相斥、折衷等。实 质上并非满足的性质越多越好，但希望在一定条件下，一个函数能满足更多的性 质，如高非线性正交( 多输出) 函数的构造就是一个值得研究的问题。在多数分 组密码算法中，s 盒都是唯一的非线性部件，其密码学特性直接决定密码算法的 3 北京邮电大学硕士学位论文 安全性。构造安全有效的s 盒是分组密码设计中的重点和难点，常用的构造方法 有：随机选择测试；人为构造；数学方法构造【3 】。虽然全局搜索可以 得到所有好的s 盒，但是对于指数增长的搜索空间和现有的计算资源来说是不现 实的。研究表明，分组密码的一大缺陷是其安全性很难证明。尽管“可证明安全 性 的研究发展很快，但到目前为止，还没有一个著名分组加密算法是真正被证 明安全的。另一方面，未经安全性验证的算法对用户可能是危险的，特别是在关 系到国家利益的时候，盲目引进保密产品的后果可能是灾难性的。因此，密码学 应当是一种本土性的科学，这也是各国都在致力于自行设计和开发保密技术的一 个重要的原因。 1 2 智能算法背景 人类很早就开始思索自身智能，并且也有模拟智能的愿望，在西方，亚里士 多德三段论演绎推理开始了早期人类关于人工智能的思考，随后许多逻辑学家、 哲学家和数学家进行了有益的尝试。在我国，梦溪笔谈、张燕公集等古代 科技文献中也有许多构思巧妙的仿人机械的记录【7 1 ，1 9 世纪以来，数理逻辑、心 理学、信息学、生物学等学科快速发展，尤其是控制论奠基人维纳、信息论奠基 人香农和计算机奠基人图灵分别从各自的领域出发，为人工智能和相关学科的发 展做了开创性的工作。 近年来，通过模拟自然生态系统机制以求解复杂优化问题的仿生智能优化算 法相续出现：遗传算法、蚁群算法、人工免疫算法、人工鱼群算法、人工神经网 络、微粒群算法、蛙跳算法等等，这些智能算法的提出为那些使用传统优化技术 难以处理的组合优化问题提供了切实可行的解决方法【引。伴随着模拟自然与生物 机理为特征的智能优化算法的时代的悄然兴起，一些仿生智能优化算法已经在经 典的n p c 问题的求解和实际应用中表现出强大的生命力和进一步发展的潜 力。 1 3s 盒的设计与研究现状 本文主要的研究重点是分组密码的关键部件s 盒的设计方法。分组密码 4 北京邮电大学硕上学位论文 的设计与分析好比是攻与守的两方，一方的进步同时也促进了另一方的进步。就 分组密码的设计方面，主要的问题在于找到一种算法，能在密钥控制下从一个足 够大且足够“好”的置换子集合中，简单而迅速地选出一个置换。一个好的分组 密码应该是既难破译又容易实现，即加密函数e ( g k ) 和解密函数d ( g k ) 都必须容 易计算，但是至少要从方程y = e ( x ，尼) 或x = d ( y ，七) 中求出密钥应该是一个困难 问题。 在分组密码设计技术发展的同时，分组密码分析技术也得到了空前的发展。 目前已有很多分组密码分析技术，如强力攻击( 包括穷尽密钥搜索攻击、查表攻 击、字典攻击、时间存储权衡攻击) 、差分密码分析、差分密码分析的推广( 包 括高阶差分密码分析、截段差分密码分析、不可能差分密码分析) 、线性密码分 析、线性密码分析的推广( 包括多重线性密码分析、非线性密码分析、划分密码 分析) 、差分线性密码分析、插值攻击、密钥相关攻击、能量分析、错误攻击、 定时攻击等等。 分组密码的分析与设计的核心都是对于分组密码的非线性部件s 盒的研 究，s 盒( s u b s t i t u t i o nb o x ) 首次出现在l u c i f e r 算法中，随后由d e s 的使用而广为 流传，一直是分组密码系统的主要部件之一( 如a e s 的1 5 个候选算法中，就有9 个采用了s 盒，具体见表1 1 ) ，它是许多分组密码算法中的唯一非线性部件，为 表1 - 1a e s 候选算法 算法名称整体结构主要设计核心 提交作者及国家 r c 6广义f e i s t d 基于数据控制的循环移位r s a ( u s a ) s e r p e n t s p 网络类似d e s 的s 盒 a n d e r s o n ，b e r h a m ， k n u d s e n ( u k - i l - - d k ) d f c 8 轮f e i s t e l 基于v a u e n n a y 的抗相关攻e n s - c n r s ( f r ) 击技术 t w o f i s h轮f e i s t e l 密钥控制的s 盒 c o u n t e i p a n e ( u s a ) 16 c a s t - 2 5 6 广义f e i s t e l来自不同群的运算，s 盒 e n t r u s t ( c a ) c i n 个t o ns p 网络 字节矩阵变换，s 盒 f u t u r es y s t e m s ( k r ) m a r s 非平衡的s 盒随机产生并测试i b m ( u s a ) f e i s t e l e 2f e i s t e l 代替置换网络，s 盒 n t t ( j p ) r i j n d a e l s p 网络 宽轨迹策略，s 盒 d a e m e na n dr i j m e n ( b e ) l o k l 9 7 f e i s t e ls 盒b r o w ne ta 1 ( a u ) s a f e r + s p 网络基于指数和对数的字节 c y l i n k ( u s a ) 5 北京邮电大学硕士学位论文 d e a l 6 轮f e i s t e l重用d e s ，s 盒 o u t e r b r i d g e ， k n u d s e n ( u s a d k ) m a g e n t a 6 或8 轮 基于快速p h t ( 哈达马 d e u t s c h et e l e c o m ( d e ) f e i s t e l 变换) f r o g 非f e i s t e l 结通过内容密钥隐藏大部分 t e c a p r o ( c r ) 构 计算过程 h p c 非正规 p i c e s c h r o e p p e l ( u s a ) 密码系统提供s h a n n o n 所描述的混乱作用，其密码强度决定了整个密码算法的安 全强度。因此，如何全面准确地度量s 盒的密码强度，如何设计一个密码学性能 都比较优良的s 盒是分组密码设计的关键，也是分组密码设计和分析中的难题。 经过多年的研究，人们总结出几条s 盒的设计准则并提出了许多构造s 盒的方 法。经过理论与实践检验，目前比较认同的有如下4 种方法8 j ： ( 1 ) 随机选择。在产生s 盒的各项内容时使用某种伪随机数产生方法或某个随 机数码表。显然小的随机s 盒是不安全的，但大的随机s 盒可能足够强。有8 个或 更多个输入的随机s 盒是相当强的，1 4 位的s 盒更好。如果s 盒不仅随机，而且依 赖于密钥，则强度会更高。b l o w f i s h 使用了与密钥有关的s 盒：它从完全由伪随 机数组成的s 盒开始，然后用密钥对其中的内容加以改变。依赖于密钥的s 盒的 一个很大优点是因为它们不是固定的，要事前分析s 盒以寻找弱点是不可能的。 i d e a 即使用了大的且与密钥相关的s 盒。比如a d a m s 和t a v a r e s 提出了一种设计 丹疗的s 盒的穷举方法口劓，但随着的 增大，其过程变得愈加困难。 ( 2 ) 选择和测试。某些密码算法首先随机产生s 盒的各项，然后根据需要的特 性来测试它并进行筛选，丢弃那些没有通过测试的项。只要设计者的时间和计算 能力允许，采用此方式总可以构造出所需要的s 盒，而且可以使用户相信没有陷 门。表1 - 1 中的a e s 的候选算法m a r s 就是用这种方式来产生它的s 盒。 ( 3 ) 数学方法构造。根据数学原理来产生s 盒使得它们能抵抗差分攻击和线性 攻击，且具有好的扩散特性。c a s t 就是用这种方式来产生它的s 盒。为避免存 在“陷门 的嫌疑，采用数学方法构造s 盒越来越受到广大研究者的青睐，出现 了基于指数函数和对数函数( 女l ：i s a f e r + 等) 、代数函数、有限域上的逆映射( s o _ a r k ， s q u a r e ) 和有限域上幂函数的设计方法。一般不直接用幂函数作s 盒，而是以它 为基础构造新的s 盒。例如：e 2 的s 盒是用有限域中的幂函数和模加复合而成。 但以上应用的数学函数构造的s 盒，其代数结构都比较简单，并且所构造的性质 好的s 盒的数量也比较少。 6 北京邮电大学硕士学位论文 ( 4 ) 人为构造。这是一种手工操作方式，它只用到简单的数学或几乎不使用 数学方法，而是使用更直接的方法来产生s 盒。现在看来d e s 设计中采用的就是 这种方式。 某些s 盒的设计方法是在相应的密码分析方法出现之后提出的，比如当差分 密码分析出现后，d e t o m b e 与t a v a r e s 口别，运用5 个变量的近b e n t 布尔函数来构造 5 x 5 的s 盒，以抵抗差分攻击。不过这种方法只能用于构造输入比特是单数的情 况。 从以上描述的s 盒设计方法可以分析看出，如果采用数学方法进行构造一般 难以考虑s 盒的多种密码学特性，并且构造出的s 盒的代数结构一般都比较简单， 所构造的性质好的s 盒的数量也比较少。而使用随机选择、选择和测试的方法构 造，一般需要很大的时间复杂度，即要消耗很大的计算资源采可能找到密码学性 能较好的s 盒。 1 1 1 2 0 世纪8 0 年代以来，人们提出了一类模拟大自然的智能优化算法。智能优 化算法通过模拟或揭示某些生物进化现象和生理现象而得到发展，其思想涉及数 学、生物进化、人工智能、物理学等方面，这类算法为解决复杂问题提供了新的 思想和手段。密码学中许多问题就是非常困难和复杂的，有的甚至是n p c 问 题，近年来已有学者将智能算法应用与密码学和信息安全( 表1 2 ) ，并且取得的 相应的研究成果。考虑到设计s 盒的时间复杂度和s 盒的密码学特性等因素，所 以采用智能算法构造s 盒是一个较优的选择。 表1 - 2 智能算法在密码学中的应用现状 论文名称研究者使用的方法时间 s m a r th i l lc l i m b i n gf i n d sb e t t e rm i l l a n 彤c l a r k爬山算法1 9 9 7 b o o l e a nf u n c t i o n s a ，d a w s o n e s e l f - n o n s e l fd i s c r i m i n a t i o ni nf o r r e s ts ，p e r e l s o na 免疫算法1 9 9 7 c o m p u t e rs ，a l l e nl ，c h e r u k u t i 利用细胞自动机构造密钥流发生器 王培春，李毅等细胞自动机 2 0 0 2 演化密码与d e s 的演化研究张焕国、冯秀涛等遗传算法2 0 0 3 b e n t 函数的演化设计孟庆树，张焕国等演化设计算法2 0 0 4 a ne f f e c t i v ee v o l u t i o n a r ys t r a t e g yf o r c h e n h ，f e n g 演化设计算法2 0 0 4 b i j e c t i v es - b o x e s 基于遗传算法生成序列密码胡能发、邓永发遗传算法 2 0 0 5 基于一维扩展元胞自动机的伪随机赵学龙、王庆梅等细胞自动机2 0 0 5 发生器研究 使用快速收敛遗传算法设计s 盒殷新春、杨洁快速收敛的遗传算法 2 0 0 6 7 北京邮电大学硕士学位论文 l 布尔函数设计中望爬山算法及其改 李超，胡朋松等爬山算法 2 0 0 7 近年来，国内外学者使用人工智能等智能算法对s 盒的安全性进行研究【4 】， 即由己知的s 盒构造具有相同密码指标或是密码性质更好的s 盒。如表1 2 所示， 国内在这个方面也已经有一些成果，张焕国等【5 】提出演化密码的概念，利用演化 算法构造分组密码算法中的s 盒，取得了较好的实验结果。陈华等基于遗传算法 提出改善随机选取的双射s 盒密码特性的算法。殷新春等【6 】贝0 利用快速收敛遗传 算法对s 盒进行优化，给出一批非线性度较高和差分均匀度较低的6 x 6 的s 盒。 所以目前智能算法已经在密码学和信息安全领域已经由比较丰富的应用，智能算 法凭借其在处理很多复杂问题中的出色表现，可以预见智能算法未来将在信息安 全和密码学领域有更多的贡献。 1 4 本文的研究内容与意义 对于信息安全产品，除非能完全确信它在软件和硬件上没有陷门，否则，可 能带来不可预测的后果。而要做到软、硬件上的确认通常是十分困难的，因此科 学的方法是依靠我们国家自己的力量并吸取现有的先进经验进行研究，设计和开 发。密码学是信息安全的核心技术之一，密码学的研究与开发应该具有较大的本 土性，而s 盒是分组密码中的唯一非线性部件，它的密码强度将决定整个分组密 码的安全强度。用传统的数学方法构造出性能优异的s 盒是非常复杂和困难的， 近年来仿生智能优化算法已在经典的p c 问题的求解和实际应用中表现出强 大的生命力，由表格1 2 可以看出，目前已有将遗传算法用于构造s 盒的先例，并 且取得了一定研究成果，同时是也可以看出当前比较新的智能算法，比如：免疫 算法、蚁群算法等还没有在s 盒上应用的研究。 本文将在目前已有的研究基础之上进一步深化智能算法在s 盒的构造中应 用，同时将研究当前比较新的智能算法( 免疫算法、蚁群算法) 并将其应用n s 盒的构造中，本文具体的研究内容包括：l 、采用改进的遗传算法构造s 盒，同时 分析其构造的效果；2 、采用人工免疫算法构造s 盒，同时分析其构造的效果；3 、 采用蚁群算法构造s 盒，同时分析其构造的效果；4 、分析这三种算法及其在构造 s 盒过程中的相同点和各自的特点。 北京邮电大学硕士学位论文 使用智能优化算法来对s 盒进行优化，具有多方面的意义：能够在有限的时 间、有限的计算资源内寻找到满足一定密码学标准的优良s 盒；为s 盒的构造提 供了一种新的研究方向，深化智能算法在密码学中的应用；进一步推广智能优化 算法的在信息安全和密码学的应用。同时由表格1 1 可以看出，西方国家，尤其 是美国和一些欧洲国家在分组密码的设计与分析方面拥有更多的核心技术，所以 我们国家更应该加大在这个领域研究深度与自主创新能力。 1 5 本文内容组织 第一章绪论部分。背景知识介绍，本文的研究范围和目的。 第二章分组密码和s 盒相关理论知识。完整的给出了一种分组加密算法的 流程，分析目前对于设计s 盒的准则，这些准则将是本文设计s 盒的目标。 第三章智能算法简介。详细描述了本文将要使用的3 种智能优化算法：遗 传算法、免疫算法、蚁群算法。 第四章基于遗传算法的s 盒的构造。在编码方式上使用全排列方式来保证s 盒的正交性，使用优先权布尔矩阵的交算子来实现交叉和变异操作，并在迭代过 程中自适应的设置交叉和变异概率，最后实验获得的s 盒在非线性度、差分均匀 度和雪崩效应上都得到了很大的改善。 第五章基于免疫算法的s 盒的构造。通过分析布尔函数的w a l s h - h a d a m a r d 变换和自相关性，推导出布尔函数两个优化规则，基于这两个规则提取出抗体的 疫苗，从而使生成的抗体有策略的进化种群，实验获得的s 盒在非线性度、差分 均匀度和自相关性上都得到了很大的提升。 第六章基于蚁群算法的s 盒的构造。构造出s 盒的城市模型，设计出选路 规则和信息素更新策略；接着对该算法进行优化：引入遗传算法，并将实验结果、 收敛性等与其它算法进行比较，分析其优越性。 第七章回顾目前s 盒的几种设计方法，包括其中两个主流设计方法：数学 方法构造和随机测试生成，阐述了目前的比较重要的三种智能算法( 遗传算法、 免疫算法和蚁群算法) 以及它们在设计s 盒过程中的具体步骤，分析这三种智能 设计方法的公共特性，同时比较这三种智能算法在设计过程中的各自的优缺点。 9 北京邮电大学硕士学位论文 第八章总结本文的成果，分析本文的不足。 1 0 北京邮电大学硕士学位论文 第二章分组密码与s 盒的理论基础 2 1 分组密码的描述与设计原则 分组密码是将明文消息序列( 铂，鸭，l ，l ) 分成等长的消息组 ( 铂，l ) ，( m n + p m n 彩lm 2 。) ，l ，然后在使用密钥控制下使用加密算法乓一组 一组的加密。可以用图2 1 来表示，分组密码又分三类：代换密码、移位密码和 乘积密码。如果密文是由明文多次运用轮函数获得，称这样的乘积密码为迭代分 组密码，d e s 和目前的多数分组密码都是迭代分组密码。 明文( 而，l ) 图2 1 分组密码系统 一个分组密码是一种映射【g j ：f f 专f ，其中f 为明文空间，g 为密 钥空间，刀为密文空间，刀和m 表示明文和密文的分组长度，通常情况下是 以= m 。分组密码的设计就是找出一种算法，在密钥的控制下从一个足够大并且 够“好的置换子集合中简单灵活的选出一个置换，用来对输入的明文进行加密。 如何度量一个分组密码的安全性，s h a n n o n 从理论上给出了表达式，而且提 出了混乱与扩散性原则，用于隐蔽明文消息中的冗余度i l j 。 混乱( c o n f u s i o n ) 用于掩盖明文和密文之间的关系。这可以挫败通过研究密 文以获取冗余度和统计模式的企图。做到这点最容易的方法是通过代替，一个简 单的代替密码，如凯撒移位密码，其中每一个确定的明文字符被一个密文字符所 代替。现代的代替密码更复杂：一个长的明文分组被代替成一个不同的密文分组， 并且代替的机制随明文或密钥中的每一位发生变化。这种代替也不一定就够了， 德国的思尼格马是一个代替复杂算法，但在第二世界大战期间就被破译了。 扩散( d i f f u s i o n ) 通过将明文冗余度分散到密文中使之分散开来。密码分析 者寻求这些冗余度将会更难。产生扩散最简单的方法是通过换位( 也称之为置 换) 。一个简单的换位密码，如列换位体制，只简单地重新排列明文字符。现代 密码也有这种类型的置换，但它们也利用其他能将部分消息散布到整个消息的扩 北京邮电大学硕士学位论文 散类型。 2 2d e s 的描述与设计原则 d e s 是第一个公开的分组加密算法，分组长度为6 4 b i t ，密钥长度为5 6 b i t 。 加解密使用一样的算法，唯一区别是解密子密钥是加密子密钥的反序。图2 2 描 述了加密整个流程，首先对输入的6 4 b i t 明文进行一次初始置换俨，以打乱明文 的次序【9 】。 图2 - 2d e s 加密流程 具体可描述为下面几个方面的步骤： 1 ) 置换输出的6 4 b i t 数据分成左右两半，各3 2 位，记为厶和r ； 1 2 北京邮电人学硕士学位论文 2 ) 每轮变换由加密函数，实现子密钥k 对数据置一。的加密，将产生的3 2 b i t 数据组f ( r 书k ) 与厶进行异或运算获得数据组厶一。of ( 置中k ) ，将它作 为下一轮的r ，将r 一，作为下一轮的厶； 3 ，加密过程可用公式简洁的表达为： 竺三之：。，置- l ，k i = i , 2 l 1 6 ； 4 ) 在第1 6 次迭代后并没有交换厶。，曷。，而是直接将厶6 ，置。作为俨1 的输入， 这样使得d e s 的加密和解密完全相同。 加密轮函数f 是d e s 的核心四1 ，它的作用在于第碑台加密迭代中用于密钥k 对r 一的加密，而其中的核心又在s 盒上，f 函数可记为f ( a ，j ) ，其中a 为3 2 b i t 输入，为4 8 b i t 输入，在第辟台a = 置- l ，j = k ，k 为由初始密钥导出的子密 钥。图2 3 描述了加密轮函数f 的运算流程：将彳经过扩展运算e 变成4 8 b i t 的 e ( 彳) ，对e ( a ) 和j 进行异或运算得b ，对b 实施代换s ，该代换由8 个s 盒所 组成s ，( 1 j 8 ) ，其中s ，的输入为6 b i t ，输出为4 b i t 。将4 8 b i t 的分成8 组， 每组6 b i t ，记b = 蜀岛l 岛，将b ，( 1 j 8 ) 作为s ，的输入，输出记为c ， c = c 1 c 2 lg 即是代换的输出。所以整个代换是一个4 8 进、3 2 出的压缩运算， 最后对c 进行置换p 即得f ( a ，) 。 图2 - 3 加密轮函数运算框图 s 盒是d e s 的唯一非线性部件，也是整个算法的安全性所在。美国国家安全 局曾确认过3 条设计原则： 北京邮电大学硕士学位论文 1 ) 任意一个s 盒的输入与输出必须是非线性的关系； 2 ) 改变任意一位输入至少影响两位以上的输出； 3 ) 当固定某一位输入，s 盒的输出的“o ”和“1 之差越小越好。 s 盒的本质就是数据压缩，并且若输入发生了改变，则输出至少改变2 位， 而d e s 使用的1 6 次迭代，所以即是输入改变一位，最终的输出都会发生3 2 位 的变化。 2 3s 盒的设计原则 s 盒是许多密码算法中的唯一非线性部件，因此它的密码强度决定了整个密 码算法的安全强度。任一r l xm 的s 盒看作映射s ( x ) = ( z ( x ) ，l ，厶( x ) ) ：刀专f ， 当参数刀和肌选择的很大时，几乎所有的s 盒都是非线性的，但是当疗和m 过大 将给s 盒的设计带来困难，而且增加算法的存储量。目前，s 盒的安全性主要用 以下指标来度量：非线性度，差分均匀度，代数次数和项数分布，正交性，鲁棒 性，雪崩效应和扩散特性等【蚋。 l 、非线性度 非线性度最初由p i e p r z y k 等人在1 9 8 8 年引入的，它是s 盒的主要设计原则之 一，它决定了基于s 盒的密码算法抗击线性密码分析的能力。 定义2 1 令厂( x ) ：霹专e 是一个刀元布尔函数，称虬= m 。i n d , ( f ，) 为厂( x ) 的非线性度，其中厶表示全体线性函数之集，如( f ，) 表示厂和，之间的汉明距 离。 定义2 2 设s ( x ) = ( 石( x ) ，l ，厶( x ) ) ：f 专f 是一个多输出函数，称 虮。0 ；* u e 景，心d ( u - s ( x ) ，7 ( x ) ) 为s ( x ) 的非线性度。 非线性度是衡量密码系统安全性的一个重要标准，如果所选用的s 盒的非线 性度比较低，则相应的密码系统易受到最佳仿射逼近法的攻击。 2 、差分均匀度 定义2 3 设s 盒的差分分布表为a ( s ) = 称s 盒差分均匀度为： 1 4 。 如。 m 五。 如。 m 气劓) o 气n ) i l 磊( 叫 l t ( ) mm l 气) ，则 北京邮电大学硕士学位论文 8 ( s ) = m a x & i 扛1 ，2 ，l ，2 ”- 1 ；，= o ，1 ，l ，2 “一1 ) = m a x l 缸曰ls ( x ) os ( x o 口) = 仍| i 口霹，口o ，f ) ，简记为磊，其 中乃= l x 足ls ( x ) o s ( 工。嘭) = 红) l ，f = 1 ，2 ，l ，2 “一1 ；j = o ，1 ，l ，2 ”- 1 ，吒，色 分别为f ，的二进制表示。 差分攻击是分组密码最为有效的攻击方法之一。大量研究表明，s 盒的抗差 分攻击的能力可从其差分分布矩阵人( s ) 给出，因为差分攻击主要是利用s 盒差分 分布矩阵中的特殊元素，如果某些元素值，明显大于其它元素，则这些位置有助 于差分攻击。具有较小的文是s 盒抗击差分攻击的必要条件。 3 、代数次数及项数分布 代数中已经证明，任何布尔函数厂( x ) ：霹一e 都可以唯一地表示成如下形 式：厂( 石) = 口o + 口社k x x 6l 气，工= ( 玉，x 2 ，l 毛) ，a o ，气如l e ，通常将该式 1 瓠d q 臼 l ! 汪! 加 称为厂( x ) 的代数正规形式。 定义2 4 令f ( x ) ：霹专e 是一个布尔函数，它的代数正规形式中的最高项次 数成为f ( x ) 的次数，它的代数正规形式中的f 次项数的个数称为厂( 力的f 次项 数，所有i ( o f 刀) 次项数之和称为f ( x ) 的项数。 4 、正交性 定义2 5 称s ( x ) = ( 石( x ) ，l ，厶( x ) ) ：f f 是正交的，若对任意的口f 恰有2 ”肘个x e ，使得厂( 力= 口。 5 、鲁棒性n u 定义2 6 设s 盒的差分分布表为a ( s ) = ( 乃) ，差分均匀度为4 ，记 q = 莩“c 以。，其中“。，= 0 二三三，称仉= c - 一争一争，为的鲁棒性。 6 、雪崩效应 定义2 7 s ( x ) = ( 彳( x ) ，l ，厶( x ) ) ：g 专f 满足雪崩效应，是指改变输入的 1 比特，大约有一半的输出比特发生改变。 7 、扩散特性 定义2 8 设f ( x ) ：曰专最，称f ( x ) 关于非零向量满足扩散准则，如果 厂o o 口) o f ( x ) 是一个平衡函数。称f ( x ) 满足k 次扩散准则，如果对所有的向量 口日：1 ) k ，厂( 曲关于口满足扩散准则。 克g x 2 9 设s ( z ) = ( 石( x ) ，l ，厶( 工) ) ：g f ，如果每个分量函数关于非零 向量口片满足扩散准则，则称s ( x ) 关于口满足扩散准则。如果每个分量函数 北京邮电大学硕士学位论文 满足k 次扩散准则，则称s ( x ) 满足k 次扩散准则。 2 4 本章小结 本章主要是综述分组密码以及s 盒的基本理论。首先描述了分组密码的设计 原则：混乱与扩散性原则，接着详细描述了d e s 的设计方案以及d e s 的s 盒的加 密流程，最后给出了s 盒的若干个重要的设计准则：非线性度、差分均匀度、代 数次数及项数分布、正交性、鲁棒性、雪崩效应和扩散特性，这几个准则将成为 本文所有设计s 盒算法效果的评价标准，是评价设计方案优劣的最重要的指南。 1 6 北京邮电大学硕士学位论文 3 1 引言 第三章智能仿生优化算法 自2 0 世纪8 0 年代以来，人们提出了一类模拟大自然的智能仿生算法：智能 型全局优化方法。智能仿生算法通过模拟或揭示某些自然现象或过程而得到发 展，其思想涉及生物进化、人工智能、数学、物理学等方面，为解决复杂问题提 供了新的思想和手段。由于智能仿生算法本身是一个优化系统，具有自适应性和 鲁棒性等特点，所以对于有多个局部最优解的问题，不会陷入局部优化，目前已 经在很多领域都有应用。t a i l l a r de d 等人首先提出了仿生算法的统一概念，目前 研究较多的仿生算法有：遗传算法( g a ) 、免疫算法( n ) 、蚁群算法( a c o ) 、 模拟退火法( s a ) 、禁忌搜索法( t s ) 等。 3 2 遗传算法 遗传算法是由美国m i c h i g a n 大学的h o l l a n d 于2 0 世纪6 0 年代末基于达尔文的 进化论和孟德尔的遗传学原理提出并创立的【1 2 1 。它模拟了自然选择和遗传过程 中发生的繁殖、交叉和变异现象，根据适者生存、优胜劣汰的自然法则，利用选 择、交叉和变异逐代生成候选解，最终搜索到较优的个体。 基本遗传算法【l3 】首先对参数进行编码，生成一定数量的个体，形成初始种群。 其中每个解是一维或多维矢量，以二进制数串表示，称为染色体。染色体的每一 位数称为基因。自然界生物被客观环境选择，优胜劣汰，算法中则需要设计适应 度函数作为评判每个个体性能优劣的标准，性能好的个体以一定概率被选择出来 作为父代来参加以后的遗传操作以生成新一代种群。算法中的遗传算子为染色体 选择，染色体上基因杂交和基因变异。杂交的结果使父代的特性更集中，变异则 有益于产生新个体，利于进化。生成新一代种群后，算法循环进行适应度评价、 遗传操作等步骤，逐代优化，直至满足结束条件。 基本遗传算法的一般流程【1 4 】如图3 1 所示： 1 7 北京邮电大学硕士学位论文 s t e p l ：随机产生初始种群，初始种群大小可以自取，每个个体表示为染色体 的编码 s t e p 2 ：计算个体的适应度，并判断是否符合终止准则。若符合，则输出最佳 个体及其代表的最优解，并结束计算：否则转向s t e p 3 s t e p 3 ：依据适应度选择父个体，适应度高的被选中的概率高，适应度低的被 淘汰的概率高 s t e p 4 ：按照一定的交叉概率和交叉方法，生成新的个体 s t e p 5 ：按照一定的变异概率和变异方法，生成新的个体 s t e p 6 ：经过交叉和变异产生的新一代组成新的种群，返回s t e p 2 图3 - i 遗传算法的基本流程图 下面介绍若干遗传算法的若干理论基础【1 2 , 2 4 】： 1 ) 模式理论 模式定理【1 2 】是遗传算法的基本原理，j h o l l a n d 用它和隐并行性原理来解释 g a ，即：模式定理从进化动力学的角度为解释遗传算法机理提供了一种数学工 具，同时也是编码策略、遗传策略等分析的基础。 模式定理：在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以 及平均适应度高于种群平均适应度