（计算机科学与技术专业论文）遗传算法对s盒的优化改进研究.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得武汉理工大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 签名：王商童日期：丛f21 墼2 0 学位论文使用授权书 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的 全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制 手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有 关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息 服务。 ( 保密的论文在解密后应遵守此规定) 研究生( 签名) ：师( 签期如f 1 s 船 摘要 随着计算机和通信技术的发展，用户对信息的安全存储、安全处理和安全传 输的需求越来越迫切，信息安全的问题就显得更加重要。而解决这一问题的有效 手段之一是使用现代密码技术。其中分组密码是密码学的一个重要分支，它具有 速度快、易于标准化、同时便于软硬件实现等优点。而s 盒是分组密码中的唯一 非线性部件，它的密码强度决定了整个分组密码的安全强度。 s 盒的构造方式很多，使用传统的数学方法构造出性能优异的s 盒是非常困 难和复杂的。因此，如何快速、高效生成s 盒成为密码学领域的研究重点。 本文采用遗传算法串行地对s 盒进行优化，利用遗传算法前期收敛速度较快、 交叉变异操作避免陷入局部最优的特性，保持种群的多样性，同时引入了启发式 变异策略，防止早熟收敛，这种变异规则能够显著地提高算法的搜索效率，可以 加快算法的收敛速度，提高求解的效率。此外，采用最佳个体保存法的选择策略可 以减少额外的计算量。实验结果表明，优化后获得的s 盒在非线性度、差分均匀 度和雪崩效应上都得到了较大的改进。 为了进一步的提高执行效率，在串行遗传算法优化的基础上，考虑遗传算法 的并行执行，并研究了并行数量与算法执行效率之间的关系。实验结果表明遗传 算法并行优化s 盒时有一个上限值，当并行数量增加到一定数量时候，达到优化 最佳时刻，之后继续增加并行处理器数量，效率反而会降低。故而，使用并行遗 传算法对s 盒进行优化时，不能通过无限制的增加并行处理器的数量来提高求解 效率。 关键词：分组密码算法；遗传算法；s 盒；混淆；扩散；并行遗传算法 a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dc o m m u n i c a t i o nt e c h n o l o g y , t h es e c u r i t y o fi n f o r m a t i o ns t o r a g e ，s a f eh a n d l i n ga n ds e c u r et r a n s p o r ti sa ni n c r e a s i n gn e e d ，t h e p r o b l e mo fi n f o r m a t i o ns e c u r i t yb e c o m e sm o r ea n dm o r ei m p o r t a n t a ne f f e c t i v e m e a nt os o l v et h i sp r o b l e mi st ou s em o d e mc r y p t o g r a p h y b l o c kc i p h e ri sa n i m p o r t a n tb r a n c ho fc r y p t o g r a p h y , w h i c hh a saf a s ts p e e d ，e a s ys t a n d a r d i z a t i o na n d e a s eo fh a r d w a r er e a l i z a t i o n t h es - b o xi st h eo n l yn o n - l i n e a rc o m p o n e n t so ft h e b l o c kc i p h e r , a n ds - b o x sp a s s w o r ds t r e n g t hd e t e r m i n e st h es e c u r i t yo ft h ew h o l e b l o c kc i p h e rs t r e n g t h t r a d i t i o n a lm a t h e m a t i c a lm e t h o d st oc o n s t r u c th i 曲p e r f o r m a n c es - b o xa r ev e r y d i f f i c u l ta n dc o m p l e x ，t h e r e f o r e ，h o wt oc o n s t r u c tf a s ts p e e d ，e f f i c i e n ts - b o xi st h e r e s e a r c hp r i o r i t yo fc r y p t o g r a p h yf i e l d i nt h i sp a p e r , s e r i a lg e n e t i ca l g o r i t h mi su s e dt oo p t i m i z et h es - b o x ，b a s e do n g e n e t i ca l g o r i t h m s f a s tp r e - c o n v e r g e n c e ，c r o s s o v e ra n dm u t a t i o no p e r a t i o n st o a v o i df a l l i n gi n t ol o c a lo p t i m u mc h o i c e ，m a i n t a i nt h ep o p u l a t i o n sd i v e r s i t y , w h i l e i n t r o d u c i n gt h e h e u r i s t i cm u t a t i o ns t r a t e g yt op r e v e n tp r e m a t u r ec o n v e r g e n c et h i s m u t a t i o nr u l ec a ns i g n i f i c a n t l yi m p r o v et h ea l g o r i t h m ss e a r c he f f i c i e n c y ，a c c e l e r a t e t h ec o n v e r g e n c es p e e da n di m p r o v et h es o l v i n ge f f i c i e n c y i na d d i t i o n , as e l e c t i o no f t h eb e s ti n d i v i d u a ls t r a t e g yc a l lr e d u c et h ea m o u n to fa d d i t i o n a lc o m p u t a t i o n t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h eo p t i m i z e ds - b o xh a sb e e ng r e a t l yi m p r o v e di nt h e n o n - l i n e a r i t y , t h ed i f f e r e n t i a lu n i f o r m i t ya n da v a l a n c h e t of u r t h e ri m p r o v et h ee f f i c i e n c y , b a s e do nt h es e r i a lg e n e t i ca l g o r i t h m ， c o n s i d e rt ou s ei m p l e m e n t a t i o no fp a r a l l e lg e n e t i ca l g o r i t h m st oi m p r o v et h e e f f i c i e n c y a n ds t u d yt h er e l a t i o n s h i pb e t w e e np a r a l l e la l g o r i t h mp r o c e s s o rn u m b e r a n de f f i c i e n c y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h e r eh a sa nu p p e rl i m i tw h e nb s et h e p a r a l l e lg e n e t i ca l g o r i t h mo p t i m i z a t i o no fs - b o x 。 w h e nt h ep a r a l l e lp r o c e s s o r , n u m b e ri n c r e a s e dt oac e r t a i nn u m b e r ，r e a c ht ot h eb e s tt i m eo p t i m i z ee f f i c i e n c y , t h e nw i t ht h e p a r a l l e lp r o c e s s o rn u m b e rc o n t i n u et oi n c r e a s e ，e f f i c i e n c yw i l lb e r e d u c e d t h e r e f o r e ，t h eu s eo fp a r a l l e lg e n e t i ca l g o r i t h mt oo p t i m i z et h es - b o x ，y o u c a n tb yu n l i m i t e di n c r e a s et h en u m b e ro fp a r a l l e lp r o c e s s o r st oi m p r o v et h es o l u t i o n e f f i c i e n c y k e y w o r d s ：a e s 、s b o x 、g a 、d i f f u s i o n 、c o n f u s i o n 、p g a u 目录 摘要。i a b s t r a c t i i 第1 章绪论1 1 1 研究背景和意义1 1 2 国内外研究现状4 1 3 本文的研究内容6 第2 章分组密码算法中s 盒的理论基础7 2 1 分组密码与s 盒的设计原则及理论描述7 2 1 1d e s 密码算法的s 盒设计理论8 2 1 2a e s 算法的s 盒设计原理1 0 2 2 s 盒的设计规则1 5 2 3 分组密码s 盒的构造与实现1 8 2 3 1s 盒构造方式18 2 3 2s 盒实现方式1 9 2 4s 盒的攻击2 0 2 4 1 差分密码分析2 0 2 4 2 线性密码分析2 1 2 4 3 代数攻击2 l 2 5s 盒研究现状2 2 第3 章串行遗传算法对s 盒的优化2 4 3 1 遗传算法j 。2 4 3 2 遗传算法的基本算子。2 6 3 3 串行遗传算法对s 盒子改进2 9 3 3 1 双射s 盒的优化编码2 9 3 3 2 初始种群生成2 9 3 3 3 适应值函数。3 0 3 3 4 选择方法31 3 3 5 交叉策略3 2 3 3 6 变异规则3 3 3 3 7 停止准则3 4 i i i 3 4 算法实现3 5 3 5 参数控制3 6 3 5 1 种群规模n 3 6 3 5 2 交叉概率b 3 6 3 5 3 变异概率3 7 3 5 4 终止进化代数t 3 7 第4 章实验结果分析3 8 4 1s 盒使用的初始种群完全随机生成3 8 4 2 引入部分预先生成的s 盒4 0 4 3 交叉概率和变异概率动态线性修正4 2 4 4 三组实验结果分析对照4 3 第5 章并行遗传算法对s 盒子的优化4 6 5 1 遗传算法的并行性分析4 6 5 2 并行遗传算法常见模型4 6 5 2 1 主从式并行遗传算法模型4 7 5 2 2 粗粒度并行遗传算法模型4 8 5 2 3 细粒度模型4 8 5 2 4 混合模型一4 9 5 3 并行遗传算法对s 盒的优化4 9 5 3 1 并行任务分配5 0 5 3 2m p i 程序结构5 1 5 4 实验结果分析5 2 第6 章前景展望5 4 6 1 总结5 4 6 2 展望5 4 致谢5 6 参考文献5 7 附录：攻读硕士学位期间公开发表的论文6 0 i v 武汉理工大学硕十学位论文 1 1 研究背景和意义 第1 章绪论 密码学的应用可以追溯到人类社会最初的阶段，到如今为止，对密码的应用 已有几千年的历史，但是作为- f - j 系统的、理论的、科学的学科，密码学研究则 仅仅是上世纪5 0 年代才开始的事情。在1 9 4 9 年，信息论创始人香农( s h a n n o n ) 发表的著名论文保密通信的信息理论( c o m m u n i c a t i o nt h e o r yo fs e c r e c ys y s t e m ) 【l 】以后，密码学才正式成为- f 理论学科受到重视，被学者和专家广泛的研究。 现代密码学，作为一门正式的理论科学产生于2 0 世纪7 0 年代，其重要性体 现在一下两方面，其一是于1 9 7 7 年1 月美国制定并批准公布执行的数据加密标 准d e s 到，其二是公钥密码体制r s a 3 】的诞生；密码学新方向的发表、公用 数据加密标准d e s 的颁布以及实施，标志着密码学作为专门的、系统的科学的 诞生，从此密码学作为一门信息安全科学，在保护网络安全方面发挥着重要的作 用。 密码学的主要研究任务，是系统地解决传输信息过程中的保密性以及可 认证性问题，防止在信息在产生、传输、处理、存储等过程中被未经授权的非 法入侵者提取、篡改、删除、重放、和伪造等攻击行为，导致信息的泄密而造成 的损害。密码学作为一门理论与应用相结合的综合性新学科正在取得快速发展 的，密码学的研究主要融合了数学、计算机、物理、信息论、编码学、通信技术 等多门学科的知识，由于涉及的知识面比较广发，故而密码学是一门相当复杂的 学科，其研究也相对困难。概括地说，信息安全的核心问题是密码学问题，密码 学为解决当代信息安全体系提供了许多有效的解决方案以及关键技术，在保护信 息的认证性、机密性等许多方面发挥着至关重要的作用。 保密要求是密码学理论研究和应用的核心，而加密是实现信息保密的必然选 择，现代加密技术的主流研究方向就是一些基于数学变化( 也称作数学算法) ， 大都可归约为一个数学难题( 比如大数分解等) ，其加密方式是，将消息看做是 某一空间中的数字或者代数元素，在这个空间种进行相应的数学变换( 比如相加、 乘积等) 。目前常用的密码系统根据其加密方式分类为两类，一类是基于信息理 论【4 】的密码系统，它以香农定理【5 】为理论依据，主要有d e s ( d a t ae n c r y p t i o n s t a n d a r d ) 分组密码算法1 6 】、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 ) 分组密码算 法【7 】；另一类是基于复杂性理论的密码系统，后者则是通过复杂算法来实现的公 钥密码算法，最具代表性的是美国的r s a ，还有欧洲的e i g a m a l 公钥密码算法【8 】。 武汉理丁大学硕士学位论文 当今社会，数据库技术、通信技术和网络技术在社会生产生活中得到广泛应 用，网络通信已经渗透到社会的各个领域，同时信息安全问题也越来越受到人们 的广泛关注。随着各种应用需求的产生，人们对信息的安全存储、安全处理和安 全传输的需求越来越紧迫。如何保证信息在发送方和意定接受方之间传送时不会 被第三方窃密者截获，并破译恢复出原文，是摆在从事网络工作的技术人员， 以及密码学研究者面前的首要问题。要想使信息实现可靠性传输，发信者必须对 所要发送的数据( 以称作明文或者原文，通常是可以直接被理解的) ，通过加密 算法转变成密文( 不可直接理解，通常是需要解密还原才能理解的输出) ，信息 接收者收到密文后再用相应的解密系统( 包括解密所需硬件，软件，解密密钥) 对密文进行解密，从而恢复成可直接理解的明文( 原文) ，这就是数据加密所要 完成的工作。加密算法是实现数据保密性、完整性、有效性和网络安全性的关键， 通常加密算法、解密算法都需要结合相应的密钥作运算参数，为了恢复信息，加 密变换必须是可逆的，逆变换就是解密操作。 人们通常提及的密码学只是一个统称，密码学主要涉及两个重要的、相互对 立的分支：即是密码编码学【9 1 ( c 妒t o 黟a p h y ) 和密码分析掣1 川( c r y p t a n a l y s i s ) 。密 码编码学是对信息进行编码，从而实现信息转换、隐蔽、伪装的一门学科，其主 要的目的是为了达到保护信息的保密性和可认证性。密码分析学则正好 相反，它是研究、分析、破解密码编码学的一门学科，其主要的目的是，研究加 密消息的可能加密算法、密钥，破解加密算法，以及消息的伪造、篡改等，达到 以假乱真、攻击的目的。密码分析学与密码编码学研究内容既相互对立，同时又 相互促进着对方向前一起发展；当前广泛使用的有两种重要的密码系统，一个是 单钥( 也称作私钥) 密码协同，另一个是双钥( 也称作公钥) 密码系统；在单钥密码 系统中，明文消息分组的加密、密文消息分组的解密使用的是同一个密钥变化操 作。直到1 9 7 6 年d i f f i e 和h e l l m a n 发表论文提出公钥密码加密方式之前的所有 密码都可以算是单钥密码，当前的单钥密码分组算法主要分两种加密体制，依据 加密时候采用的不同方式可分为序列密码【l l 】和分组密码【1 2 1 。 分组密码是以2 0 世纪7 0 年代d e s ( d a t ae n c r y p t i o ns t a n d a r d ) j j h 密算法在美 国的提出作为标志，随后得到了密码学专家、爱好者的广泛讨论和改进，分组密 码在通信网络和系统安全等相关重要领域中有着广泛的应用。分组密码是对固定 长度的一组明文进行加密保护的一种密码算法，是现代密码学研究中的一个重要 分支，它是现代密码中最重要的对称加密算法之一，其诞生和发展有着重要的理 论价值、以及广泛的实用背景，分组密码是以2 0 世纪7 0 年代d e s 的出现为标 志，d e s 的出现有两方面的重要意义，一方面d e s 出现使得密码算法的公开化， 另一方面使得密码算法的标准化，d e s 在产生以后得到了广泛的讨论和发展， 2 武汉理t 大学硕士学位论文 为设计出更好的分组密码，必需研究满足算法中不同性质的函数类，以及这些函 数的存在性、构造实现、计数等问相关题，以及所有这些不同性质之间的依赖关 系，比如等价、包含、互斥、等特性，在实际应用中并非满足以上的性质越多越 好，不过希望在某给定条件下，设计出来的算法能尽可能多的符合以上的性质。 分组密码的整体结构可以概括为下面两种： 1 、f e i s t e l 型网络【1 3 】：目前所广泛使用的、基于f e i s t e l 分组密码结构分组密 码算法有d e s 、c a s t 2 5 6 、d e a l 、g o s t 、e 2 、b l o w f i s h , 等，f e i s t e l 网络是 由i b m 内部开发的设计l u c i f e r t l 4 j 分组密码时发明，由于d e s 使用了这种结构而广 为流行，加密过程和解密过程相似是f e i s t e l 型密码结构的显著特点之一。 2 、s p 型网络【1 5 】：而现在所使用的基于s p 型网络的分组密码结构分组密码算 法有i d e a 、a e s 、s a f e r + + 、s e r p e n t 等分组密码。s p 型网络中的s 是s u b s t i t u t i o n 的首写字母，表示替换操作、p 是置换p e r m u t a t i o n 的首字母，轮函数一般e h s 盒层 和置换层( 一称作线性变换层) 组成，a e s 分组密码算法采用了s p 网络结构，对于s p 型密码结构来说，一般情况下它加密和解密过程是不相同的。 最早被人们使用的密码算法其依照其性质应该属于序列密码，序列密码已经 被广泛地应用于军事国防、国家外交等领域，序列密码在专用领域、机密机构 中保持着优势。序列密码也称作流密码【1 6 】( s t r e a mc i p h e r ) ，它是对称密码 算法中的一种，1 9 4 9 年s h a n n o n 发表论文证明了只有一次一密【l 7 】的密 码体制是绝对安全的，这篇论文中提出的理论给在理论上强有力支持了序 列密码技术的研究提供，序列密码加密方式本质上是对一次一密系统的改 进尝试，也可以认为“一次一密”的密码方案是序列密码的初始形式，其加密 方式是将明文消息字符串逐位地加密，生成相应的密文。序列密码是一个 随时间变化而相应变化的随机加密变换算法，如果序列密码所使用的是真 正随机方式【1 8 】( 在实际应用中几乎都是伪随机方式) 的、与消息流长度相 同的密钥流，则可以把这样的序列密码看做是真正的一次一密的密码算法； 若能找到恰当有效的方式，产生一随机序列( 也叫密钥流) ，同时这一随机 序列由密钥参数所确定，那么利用这样的序列就可以执行加密操作，即将 密钥消息分组、明文消息分组表示成连续的符号或二进制等不可直接理解 形式的输出，对应地可以进行解密操作。序列密码最显著的优点是它的转 换速度较快、低差错传播概率的，而且它硬件实现起来电路也不复杂；其 缺点是：由于一次一密的密码体制存在密钥产生、分配和管理极为困难等 不足，低扩散( 意味着混乱不够充分) 、插入及修改的不敏感性。 正是由于序列密码具有转换速度较快、低差错传播概率，而且它硬件 实现起来电路也不复杂的优点，在实际应用中，使其应用范围受到一定的限 武汉理工大学硕士学位论文 制，在保密强度要求高的场合，特别是专用或机密机构中极具竞争力，典型 的应用领域包括无线通信、外交通信，如大量军事密码系统，仍多采用序列 密码。 序列密码的研究涉及到大量相关学科的复杂理论知识，众多学者也提 出了各类的设计原理，也得到了广泛的分析，但许多研究成果并没有对公 众完全公开，其原因是序列密码目前主要应用于军事和外交等机密部门， 需要保密。目前，公开的序列密码算法主要有r c 4 1 9 1 、s e a l 2 0 】等。 序列密码的工作原理是，利用少量的密钥( 也称作制乱元素) ，通过某种复 杂的运算( 密码算法数学函数) ，计算机生成大量的伪随机【2 1 】位流，运用这些 位流对明文消息分组逐位流执行加密操作；解密时候必须要用与加密时候采用的 一致的密钥和密码算法，以及与加密相同的伪随机位流，才能恢复出被加密的明 文分组的位流。一般来说流密码算法设计的原则是：采用多轮密钥、多重环节、 多重安全措施等技术，来无限趋近香农的信息安全理论，从而达到“一次一密 的安全性能。总的来说，要达到流密码的安全还得依靠密钥的保密，即“密码保 密寄寓于密钥之中。由于流密码的核心技术是如何设计能生成随机密钥序列的 算法，其密码系统的安全性有这个随机产生的密钥序列的安全性来确定；目前流 密码算法的重点研究方向包括以下几个主要的研究方向：同步序列密码在失步后 重新同步的问题；自同步流密码的研究；高速密码芯片的开发：有记忆前馈网络 密码系统的研究；多输出密码函数的研究；高速密码芯片的开发：混沌序列密码 以及一些新研究方法的可能性探索等。 1 2 国内外研究现状 在已开发设计出的、绝大多数的分组密码算法中，s 盒都是此类密码算法中 唯一的非线性部件，为整个加密算法提供安全保护，其密码学特性的安全性直接 决定整个密码算法的安全性能。为了设计出更加合理、安全、高效、便于实施的 分组密码算法，需要研究满足不同性质的数学函数类。特别是这些函数的存在性、 构造实现、计数操作等相关问题，以及所有这些不同性质之间的关系，如等价、 包含、互斥等数学特性。实际应用中，一个加密算法，并非满足以上的性质越多 越好，要根据实际应用做出相应的取舍，但希望在一定条件下，一个加密算法( 或 者称作函数) 能满足更多以上提及的性质，故而如何研究并设计、构造出安全有 效s 盒是分组密码设计中的重点，也是研究的难点，当前常用的构造方法有： 随机选择测试【2 2 】；人为构造【2 3 】；数学方法构造【2 4 1 等。虽然利用全局搜索【2 5 】 可以得到所有最好的s 盒，但是对于成指数增长的搜索空间需求，而现有的计算 4 武汉理r t 大学硕十学位论文 机硬件资源来说，其实现成本太高而不现实。充分的理论研究说明，对于分组密 码来所目前存在的一个很大的缺陷分组密码算法的安全性很被人们证明。尽管目 前“可证明安全性 已经取得很好的研究成果，发展迅速，但到目前为止，还没 有一个著名分组加密算法是被真正被严格数学证明其绝对安全性的；另一方面， 未经安全性验证的算法可能存在陷阱( 也称作陷门) 的，这对不知情的用户将存 在信息泄密的危险，特别是在一些涉及到国防安全、国家利益的重要应用领域的 时候，不加分析的引进保密产品可能会导致灾难性的后果，鉴于以上因素，密码 学应当成为一种本土性的、自有的科学，这也是当今世界各国都在致力于自主研 发、设计并实现保密技术的重要原因之一。 密码学中许多问题就是非常困难和复杂的，有的甚至是n p 难题( n p h a r d ) 、 n p 完全( n p c ) 、n p 问题，自2 0 世纪8 0 年代以来，研究密码学的专家、学者 们提出了一类基于模拟大自然的，某些生物特性的智能优化算法。智能优化算法 是基于这样的理念产生，它通过模拟、从而揭示某些自然界生物进化特性、生理 特性而发展起来的- - i 1 理论学科，其算法原理包括数学、生物进化理论、a i ( 人 工智能) 、物理学等相关学个的大量知识，智能算法的提出为解决一些之前很多 难以解决的复杂问题提供了新的思想和途径，已有不少专家学者提出将智能算法 应用于密码学研究以及信息安全运用的设想，同时有的研究已经取得了相应的实 际运用成果。在设计分组密码算法的s 盒的时，其时间复杂度和s 盒的密码学 特性等困难因素实我们要考虑的重要因素，故而采用智能算法构造性能优良的s 盒将是极具竞争力的选择之一。 自从提出智能优化算法设计思想以后，国内外学者广泛致力于探索使用人工 智能相关的智能算法对s 盒的安全性、效率进行优化、改进性研究，即如何由己 知的s 盒设计构造出具有密码学性能相同，甚至是密码性能更好的s 盒；国内 在这个方面也已经有一些显著的研究成果，张焕国【2 6 】等提出演化密码的概念， 其设计思想是，利用演化算法构造分组密码算法中的s 盒，已经取得了较好的实 验结果。殷新春【2 7 】等则从快速收敛遗传算法方向出发对s 盒进行优化改进，并 研究得到一批非线性度较高，差分均匀度良好的6 * 6 的s 盒。陈华则从基于遗传 算法提出了改进的、随机选取的双射s 盒密码特性的智能优化算法。现在智能算 法已经在密码学研究以及信息安全运用领域有着大量的应用实例，智能算法由于 其在处理以前难以结局的基于大量复杂度的困难问题中的出色表现，已经得到专 家学者的广泛一致性认可和应用，可以预见智能算法未来将在信息安全和密码学 领域以及其他领域有更多的发展。 5 武汉理工大学硕士学位论文 1 3 本文的研究内容 s 盒( s u b s t i t u t i o nb o x ) 分组密码算法的唯一非线性部件，是研究分组密码构 造与设计的关键所在，s 盒( s b o x ) 这个概念最早出现在有i b m 实验室提出的 l u c i f e r 加密算法中，随后由于在d e s 加密算法设计中被采用而为大家所熟悉， s 盒一直是分组密码系统的主要部件之一( 如a e s 的多个个候选算法中，就有超 过一半的加密算法采用了s 盒设计思想) ，s 盒作为许多分组密码算法中的唯一 的非线性部件，为密码系统提供s h a n n o n 论文中所描述的混乱作用，它的安全性 能能为整个密码算法的安全性强度、为信息安全提供重要保证。因此，如何全面 准确地度量s 盒的密码强度，设计并构造实现一个密码学性能相对优良的s 盒 是分组密码算法研究的关键，同时这也是分组密码算法设计和分析中面临的难 题，经过专家学者多年的研究分析，总结得到几条关于s 盒的设计准则，同时也 提出了许多构造s 盒的方法，当前己有将遗传算法用于构造设计并得到s 盒的 成功例子，同时取得了不错的研究成果，与此相关地也有研究者结合一些当前比 较新的智能算法，比如：模拟退火算法、遗传免疫算法、蚁群优化算法等在s 盒 上应用的研究以及实现。 文中的研究实验室在目前已取得研究基础之上，通过改进的遗传算法的使用 更进一步深化研究遗传算法在s 盒的构造中的改进作用，在第一步基础之上进一 步研究遗传算法并行执行对s 盒的构造的影响，本文具体的研究内容如下： l 、采用遗传算法串行地对s 盒进行优化，充分利用遗传算法前期收敛速度较 快来实现快速收敛，同时其交叉变异操作避免算法陷入局部最优的特性，保持种 群的多样性，并引入了启发式变异策略，防止早熟收敛，加快算法的收敛速度，提 高求解的效率；此外，采用最佳个体保存法的选择策略可以减少额外的计算开销， 依据算法执行结果实时、动态、线性修正个参数取值来优化s 盒。 2 、采用遗传算法并行的对s 盒进行优化改进，研究遗传算法并行优化时，并 行数量与算法执行效率之间的关系，通过实验得出的结果分析使用并行遗传算法 对分组密码算法的s 盒进行优化时，增加并行处理器的数量和求解的率的关系。 使用遗传算法来对s 盒的密码学特性进行改进，具有以下几方面重要的研究 意义：可以使得算法能够在有限的时间开销内、在有限的计算资源耗费内寻找到 满足密码学性能标准的s 盒；智能算法优化构造实现、优化s 盒为分组密码算法 提供了一种新的研究方向，推进遗传算法在密码学研究中的应用：进一步深化智 能优化算法与信息安全领域研究、密码学运用领域的结合。发达的西方国家，特 别美国和少数欧洲国家在分组密码的设计与分析领域掌握了较多的核心技术，我 们国家也应该加大在密码学领域的研究深度、广度和力度，提升我们的自主创新 能力，保护我们的信息安全。 6 武汉理工大学硕十学位论文 第2 章分组密码算法中s 盒的理论基础 2 1 分组密码与s 盒的设计原则及理论描述 分组密码算法的工作原理是将明文消息序列 【m - ，m ：，m 3 ，朋_ 毛掣m ，m ” ，分成等长的消息分组 m t ，m z ，”鸠】，+ t ，呜彬m 】 ，【鸠，m 小，m ”，然后在密钥控制下使用加密算 也置对消息分组一组一组地、逐个进行加密。加密过程可以用图2 1 来表示如 下，分组密码根据实现方式可以分移位密码、代换密码、和乘积密码三类。如 果把明文多次运用轮函数运算后才产生密文，称这样的乘积密码被称作为迭代 分组密码，当前，d e s 分组密码算法和其它大多数分组密码算法都是属于迭代 分组密码。 加密规卿- j 明文，密文 加密过程 加密规则 密文 逆推 ， 解密过程 图2 - 1 分组密码加密及解密流程 一个分组密码是一种映射：曰霹专霹，其中f 是算法的明文空间，e 是算法的密文空间，群是算法的密钥空间，e 和m 分别代表密文的分组长度和 明文分组长度和，一般情况下其密文长度取值等与明文长度即：e = m 。分组密 码的设计的工作就是找出一种代价合理的算法，让算法在密钥的控制下，从一个 足够大同时又足够“好 的置换子集合中，简单而且快速的得到一个置换函数， 用这个函数来对输入的明文消息分组进行加密运算；香农( s h a n n o n ) 从理论上 给出了表达式来更好的衡量一个分组密码算法的安全性，而且首次提出了基于混 7 武汉理t 大学硕十学位论文 乱特性与扩散特性的原则，通过这样的原理来道道掩藏明文消息中存在的冗余 度，使得密码分析变得困难，增强密码算法抵抗密码分析的目的，达到对信息加 密保护的目的。 混乱【2 8 1 ( c o n f u s i o n ) ：通过混乱操作实现扰乱明文和密文之间的关系的作用， 混乱操作做可以达到抗击攻击者通过研究密文以获取冗余度以及统计模式而攻 破密码算法的攻击手段，要达到这个目的最简单的操作是通过替代操作来完成， 一个简单的代替密码算法，在这样的算法中中每一个确定的明文字符，都被一 个确定的密文字符所代替，如凯撒移位密码就是这样的密码算法。相比较而言， 现代的代替密码算法更加复杂：一个本来很长的明文分组也许会被替代成为一 个不同长度的密文分组，并且提到的机制随明文、密钥分组中的每一位变化而 发生相应的改变。尽管现代加密如此复杂，随着密码分析学的发展，即使是这 样复杂的替代操作也不能说就足够安全，德国的恩尼格马是一个著名的代替复 杂算法，但在第二世界大战期间就被破译了。 扩散【2 9 1 ( d i f f u s i o n ) ：通过将明文的冗余度分散到密文中，使之分散开来，让 针对冗余度的密码分析变得困难，难以实现，扩散操作将使得密码分析者寻求 这些明文中的冗余度变得困难。实现扩散最简单的方法是通过换位( 也称之为置 换) 函数来运算实现，一个简单的换位密码函数，如列换位操作，只简单地重新 排列明文字符，便足以达到分散明文中存在冗余度的目的；现代密码学中也有 这种类型的置换操作，但它们更多地利用，其他能将部分消息散布到整个消息 空间的扩散类型，来降低对冗余度分析的风险。 2 1 1d e s 密码算法的s 盒设计理论 分组密码算法d e s 是第一个被公开的分组加密算法，加密时算法中消息分 组长度采用6 4 b i t 位的长度，然而其密钥长度却为5 6 b i t 位长度。加密运算、解密 运算时候使用的是同一个加密算法，只有一个不同就是执行解密运算时候使用 的子密钥是执行加运算时使用子密钥的反序；我们通过下图2 2 来描述了d e s 算法的整个加密执行过程，d e s 算法首先对即将输入的6 4 b i t 位的明文进行一次 初始置换俨，重新排列明文的次序。d e s 加密流程图见下图2 2 ： 武汉理工大学硕士学位论文 图2 2 ：d e s 加密流程图 算法操作具体可描述为下面几个方面的步骤： l 、置换输出的6 4 b i t 位数据被均分成左半部分厶和右半部分r ，分组的长度均 是3 2 比特位， 2 、算法中每轮运算操作都通过加密函数f 结合子密钥k 对输入的数据墨一。进行 变换来实现，将产生的3 2 b i t 数据组f ( 墨印墨) 与厶；进行异或运算获得数据组 厶o f ( 置 k ) ，将它作为下一轮的足，将r 一。，作为下一轮的厶。 3 、算法的加密过程用公式简洁表达为： f r l = l fof ( r h ，k j ) ，i = 1 ，2 ，1 6 【工l = r f 1 4 、算法经过1 6 次迭代后并不直接交换厶。，墨。，而是直接将厶。，墨。作为i p 。1 ( 逆 9 武汉理工大学硕十学位论文 置换) 的输入分组，通过这个操作使得d e s 分组密码算法的加密运算和解密运 算操作完全相同。 d e s 算法设计的核心是加密轮函数f 的引入，轮函数f 作用在于对算法中 第i 轮加密迭代时用于对密钥k 对足一的加密操作，s 盒又是轮函数f 的核心， 在论函数f ( r k ) 中，足一。是第i 轮的运算的输入，足一。的长度是3 2 b i t 位，密钥 k 为4 8 b i t 位长度输入分组，在第i 轮加密操作运算中，轮密钥k 为由初始密钥 导出的子密钥，加密轮函数f ( r 圳k ) 的运算执行流程如下：将r 一。经过扩展运算 e 变成4 8 b i t 的e ( g 一。) ，对e ( r 一。) 和k 进行异或运算得到b ，接着对b 实施代换 操作s ，该代换由8 个s 盒所组成s i ( 1 f 8 ) ，其中单个s 盒的输入为6 b i t ，输 出为4 b i t 。将4 8 b i t 的分成8 组，每组6 b i t ，记b = e ，最，马，最，将毋( 1 f 8 ) 作为最的输入，输出记为c ：f ，c = c l ，c 2 ，g ，g 即是代换的输出。所以整个代 换是一个输入长度为4 8 比特位、输出长度为3 2 比特位的压缩运算，算法执行最 后一步运算的时候对输出c 进行置换即得f ( 足”k ) ，接着重复执行直到算法满 足设定的迭代次数方返回结果并停止执行。 2 1 2a e s 算法的s 盒设计原理 a e s 算法是分组加密算法d e s 的改进，被国际社会广泛接受并作为a e s 算法 标准的r i j d e a l 算法是由比利时的密码专家j o a nd a e m a e n t 博士( 国际质子世界公 司) 和v i n c e n t r i j m e n 、博士后k a t h o l e k e ( u n i v e r s i t yl e u v e n 电子工程系) 共同 设计开发的。a e s 算法的原型是s q u a r e 【3 0 ( s q u a r e 加密算法是l k n u d s e n ，j d a c m e n ，与v r i j m c n 合作于1 9 9 7 年开发设计的) 算法，到如今，除了 鼬j n d a c l 算法的设计者所提出的s q u a r e 攻击法之外还没有研究者声称另外发现 有效的针对r i j n d a e l 分组加密算法的攻击方法，s q u a r e 攻击法它适合于针对迭代 次数是4 轮迭代、5 轮迭代和6 轮迭代e 撕r i j n d a e l 分组密码加密算法，而标准的 鼬 n d a e l 分组密码加密算法根据消息分组长度以及密钥分组长度的不同，其加密 迭代的轮数可达至l j1 0 轮至l j1 4 轮甚至更多。r i j n d a e l 分组密码