（应用数学专业论文）一种基于分组密码算法的设计和分析.pdf

j c l a s s i f i e di n d e x ：0 1 7 5 8 u d c ：3 4 8 3 7 3 4 c 2 5 d i s s e r t a t i o nf o rt h em a s t e rd e g r e ad e s i na n da n a l y s i s c i p h e ra l g o t c a n d i d a t e ： s u p e r v i s o r ： d e p u t ys u p e r v i s o r ： a c a d e m i cd e g r e ea p p l i e df o r ： s p e c i a l i t y ： d a t eo fs u b m i s s i o n ： d a t eo f0 r a le x a m i n a t i o n ： u n i v e r s i t y ： l us h e n q i a n g p r o f h ub 0 p r o f g u oy a n p i n g m a s t e ro fs c i e n c e a p p l i e dm a t h e m a t i c s n o v e m b e r , 2 0 0 9 d e c e m b e r , 2 0 0 9 h e b e iu n i v e r s i t yo fs c i e n c ea n d t e c h n o l o g y 。， 作所 式标 表或 1 ，。7 年1 1 月jz 日 加矿7 年肛月i z 日 河北科技大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权河北科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 口保密，在一年解密后适用本授权书。 本学位论文属于 而保密。 ( 请在以上方框内打“) 学位论文作者签名：卢 ；也弓毒 加。7 年1 1 月j 调 指导教师签名：胡坡 励口7 车f 2 ，月f 日 一 t 1 1 j 、 随着计算机 的需求越来越迫 效手段之一是使 际上公开的密码 分组密码的设计就是找到一种算法，能在密钥的控制下从一个足够大且足够好 的置换子集中简单而迅速的选出一个置换，用来对当前输入的明文进行加密交换， 其设计理念是保密依赖于密钥，而算法大多公开。 本文主要研究了分组密码算法的一般原理和设计方法，给出了一种分组密码算 法的设计并分析了它的一些性质，全文共分四部分，主要内容如下： 第一章，介绍分组密码的研究背景和国内外的研究现状以及本文研究的主要内 容。 第二章，介绍分组密码的基本概念，简要分析了它的基本结构包括s 盒和p 盒， 并研究了它的设计原理和设计准则如：混乱和扩散及f e i s t e l 密码结构，给出了两种 重要的密码分析方法。 第三章，在结合分组密码算法的设计原理和遵循分组密码算法的设计准则下， 提出了一个嵌套f e i s t e l 结构的s p 型分组密码的模型。采用该模型，只需适当选取 密码特性好的非线性模块和线性模块，就可以构造出具有很好地抵抗差分密码分析 和线性密码分析的能力、加解密相似的分组密码算法。 第四章，采用上述密码模型，给出了一个用该模型构造的具体的分组密码算法。 并对该算法作了一些初步的密码分析和详细的统计测试，结果表明：该算法足够抵 抗一些已知的密码分析、具有很好的统计性能。 第五章，对该算法进行安全性评估并最终得出结论：该算法能够有效抵抗目前 一般的攻击和分析方法，且算法简单、快捷、易于实现。 关键词分组密码；s 盒；p 盒；混乱；扩散；攻击 河北科技大学硕士学位论文 - _ - - 置昌盲蕾墨墨暑昌昌置_ - _ _ _ _ 田暑昌昌董皇重暑昌昌昌昌篁昌皇墨昌目篁薯昌墨= = = 薯= = = = = 昌昌昌昌昌昌昌昌；_ - _ 蕾- _ - 阜l _ 昌自皇葺皇昌- 皇盲昌昌昌昌昌昌昌= = 鲁皇= = = 昌置一 ：。 a b s t r a c t w i t ht h ed e v e l o p m e n ti nt e c h n o l o g yo fc o m p u t e ra n dc o m m u n i c a t i o n s ，d e m a n d so f s e c u r es 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 m i s s i o no fi n f o r m a t i o ni n c r e a s e su r g e n t l y t h ep r o b l e mo fi n f o r m a t i o n s e c u r i t yp r o t e c t i o nb e c o m em o r ea n dm o r ei m p o r t a n t o n eo f t h ee f f e c t i v em e a n st 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 s n o wak i n do fw i d e l yu s e dc i p h e r , i sa l s oam o s ta c t i v eb r a n c ho ft h ec o d ea l g o r i t h mi nt h e i n t e r n a t i o n a lp u b l i c t h ep u r p o s eo fb l o c kc i p h e r sd e s i g ni st of i n da na l g o r i t h m ，w h i c hc o u l ds i m p l ya n d q u i c k l ys e l e c tar e p l a c e m e n tf r o ma ne n o u g hg r e a ta n dg o o ds u b s e to ft h er e p l a c e m e n ti n t h ec o n t r o lo ft h ek e y , u s e dt oe n c r y p ta n dc h a n g et h ec u r r e n td e f i n i t eo r d e r si n p u t e d t h e i d e ai st h a tt h es e c u r i t yr e l i e so nt h ek e y , a n dt h ea l g o r i t h mi sm o s t l yp u b l i c t h i sa r t i c l eh a sm a i n l ys t u d i e dt h eg e n e r a lp r i n c i p l ea n dt h ed e s i g nm e t h o do fb l o c k c i p h e ra ! g o r i t h r n ，g i v e n o n ed e s i g no fb l o c kc i p h e r a l g o r i t h ma n da n a l y z e ds o m e p r o p e r t i e so ft h ea l g o r i t h m t h ef u l l t e x ti sd i v i d e di n t of o u rp a r t s ，t h ep r i m a r yc o v e r a g ei s a sf o l l o w s ： i nc h a p t e ro n e ，w eh a v ei n t r o d u c e dt h eb a c k g r o u n da n dc u r r e n ts i t u a t i o no ft h et h e o r y o fb l o c kc i p h e ra th o m ea n da b r o a d ，i n t r o d u c e dt h em a i nc o n t e n ti nt h i sp a p e r i nc h a p t e rt w o ，w eh a v ei n t r o d u c e dt h eb a s i cc o n c e p to fb l o c kc i p h e r ；a n a l y z e di t s b a s i cs t r u c t u r eb r i e f l y , i n c l u d e i n gs - b o xa n dp - b o x ，h a ss t u d i e di t sp r i n c i p l ea n dc r i t e r i o n i nd e s i g n ，s u c ha s ：c o n f u s i o n , d i f f u s i o na n df e i s t e lc i p h e rs t r u c t u r e ，g i v e nt w oi m p o r t a n t c r y p t a n a l y s i sm e t h o d i nc h a p t e rt h r e e ，f o l l o w i n gt h ep r i n c i p l ea n dc r i t e r i ao fb l o c ke i p h e ra l g o r i t h mi n d e s i g n ，ab l o c ke i p h e rm o d e lc o n t a i n i n gf e i s t e ls t r u c t u r ei sp r o p o s e d a d o p t i n g t h i sm o d e l a n dp r o p e r l ys e l e c t i n gs o m en o n l i n e a ra n dl i n e a rm o d u l e sw h i c hh a sg o o dc r y p t o g r a p h i c p r o p e r t i e s ，ac o n c r e t eb l o c kc i p h e rc a nt h u sb ec o n s t r u c t e d , w h i c hi sp r o v a b l ys e c u r e a g a i n s td i f f e r e n t i a la n dl i n e a rc r y p t a n a l y s i s ，a n d a l s oh a ss e l f - i n v e r s es t r u c t u r ef o r e n c r y p t i o na n dd e c r y p t i o n i nc h a p t e rf o u r , a d o p t i n gt h ea b o v em o d e l ，ac o n c r e t eb l o c kc i p h e ri sp r o p o s e d s o m e i n i t i a lc r y t a n a l y s i sa n dd e t a i l e ds t a t i s t i c a lt e s t so ft h ea l g o r i t h ma r eg i v e n ，t h er e s u l t ss h o w t h a tt h ea l g o r i t h mc a nr e s i s ts o m ek n o w nc r y p t a n a l y t i ca t t a c k sa n dh a se x e l l e n ts t a t i s t i c a l p r o p e r t i e s i nc h a p t e rf i v e ，b ye v a l u a t i n gt h es e c u r i t yo ft h i sa l g o r i t h m ，w ec o m e t oac o n c l u s i o n ： i i 霭， i i i 目录 目录 摘要i a b s t r a c t - i i 第1 章绪论一1 1 1分组密码的研究背景与意义l 1 2国内外研究现状2 1 3 本文研究的主要内容”4 第2 章分组密码的基本理论和技术问题5 2 1密码体制”5 2 2 分组密码的概念”6 。 2 3 分组密码的整体结构6 2 3 1代换盒7 2 3 。2 置换盒7 2 4 分组密码的原理和设计准则“7 2 4 1分组密码的加密原理7 2 4 2 分组密码的设计准则8 2 5 差分分析和线性分析”9 第3 章分组密码模型的设计1 2 3 1f e i s t e l 模型和s p 网络模型1 2 3 2 有单位元的交换环上向量的非线性对等变换1 3 3 3 一个类f e i s t e l 密码模型1 6 3 4 新的加密模型1 7 第4 章对s 盒代数性质的分析2 0 4 1布尔函数的定义与表示2 0 4 2s 盒的次数2 2 4 3 布尔表达式的非线性度和s 盒的非线性度2 2 4 4 代换盒的严格雪崩特性与扩散特性2 4 4 5s 盒差分特性”2 5 4 6s 盒布尔函数w a l s h 谱2 8 4 7s 盒代数表达式31 4 8s 盒的循环特性和不动点3 2 第5 章算法的安全性3 4 i l l 结论” 参考文献 攻读硕士学位期间所发表 致谢 i v 一 叫 1 1 分组密码的 随着计算机和通 的需求越来越迫切。特别地，随着i n t e m e t 的广泛应用，以及个人通信、多媒体通信、 办公自动化、电子邮件、电子自动转账支付系统和自动零售业务网的建立与实现， 信息的安全保护问题就显得更加重要。而解决这一问题的有效手段之一是使用现代 密码技术。 1 9 7 6 年d i f f i e 和h e l l m a n 的“密码学新方向【l 】，的发表和1 9 7 7 年美国数据加密标 准d e s 的颁布实施标志着现代密码学的诞，从此揭开了商用密码研究的序幕。此后实 用密码体制的研究基本上沿着两个方向进行，即以r s a 为代表的公开密钥密码体制 和以d e s 为代表的秘密密钥分组密码体制。分组密码具有速度快、易于标准化和便 于软硬件实现等待点通常是信息与网络安全中实现数据加密、数字签名【2 j 、认证及 密钥管理的核心体制，它在计算机通信和信息系统安全领域有着最广泛的应用。 当前，分组密码之所以受到广泛关注并且成为密码学研究的热点课题之一，主 要是由于以下几个原因： ( 1 ) j 3 1 1 密算法标准化的需要 标准化是工业社会的一个基本概念，它意味着生产规模化、降低成本、方便维 修和更换为了实现非相关团体之间的保密通信，加密体制的标准化 3 1 是必要的。分组 密码由于其固有特点，已经成为标准化进程的首选体制。1 9 7 7 年美国国家标准局颁 布了联邦信息处理标准d e s 以保护非机密信息在存储和传输过程中免受未经授权的 篡改或泄露。此后，d e s 作为数据加密的工业标准，得到了i b m 等计算机制造厂商 的大力支持，并陆续被其他组织机构所采1 9 7 9 年美国银行家协会批准使用d e s ， 1 9 8 0 年d e s 又成为美国标准化协会( a n s i ) 的标准。继而，d e s 也受到国际标准化组 织( i s o ) 的关注，1 9 8 4 年成立的数据加密技术委员会s c 2 0 准备在d e s 基础上制定数 据加密的国际标准。尽管d e s 是目前世界上使用最广和最成功的算法，但是它的5 6 比特密钥对今天的许多安全应用已太短了，三重d e s 作为临时的解决方案己出现在 许多像银行这类安全性高的应用中，但是对于某些应用，它的加密速度太慢。最根本 的是，当同一密钥加密大量数据时，d e s 的6 4 比特分组长度为密码攻击开了方便之门。 正是由于这些原因1 9 9 7 年4 月1 5 日美国国家标准技术研究所( n i s t ) 发起征集 a e 5 ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 算法的活动，并专门成立了a e s 工作组，目的是为 了确定一个非保密的、公开披露的、全球免费使用的分组密码算法，用于保护下一世 纪政府的敏感信息，也希望a e s 能够成为秘密和公开部门的数据加密标准。 河北科技大学硕士学位论文 ( 2 ) 加密算法本土化的需要 信息安全的最大特点之一是自主性，因而其核心技术密码学的研究与开发 应当是一种本土性的科学。对于有些产品，可以通过外方引进来解决由于技术落后 而带来的问题。然而对于安全产品，除非能完全确信它在硬件和软件上没有陷门， 否则，贸然使用可能带来不可预测的后果。而要做到软硬件上的确认通常是十分困 难的。因此，最明智的方法是依靠自己的力量并汲取现有的先进经验进行研究、设 计和开发。 ( 3 ) 官方组织维护通信和社会安全的需要 为了维护通信安全、打击犯罪，1 9 9 3 年4 月，美国政府宣布了一项新的建议， 该建议倡导联邦政府和工业界使用新的具有密钥托管功能的联邦加密标准。该建议 称为托管加密标准( e s c r o w e de n c r y t i o ns t a n d a r d ，e e s ) ，又称c l i p p e r 建议。其目的是 为用户提供更好的安全通信方式，同时允许政府机构在必要情况下进行监听。e e s 系统中嵌入了分组加密算法s k - i p j a c k t 4 “l ，尽管目前对该系统和算法有许多争议， 但从维护国家通信安全的角度，这项建议是有积极意义的。 ( 4 ) 多级安全的需要 在区域通信系统中，用户较多，他们的地位、作用都不相同，所流通的信息的 重要性也不可能完全相同，因此他们要求得到的安全保护等级也不应该相同。由此 可见，研究多安全级密码算法非常必要。迭代分组密码( 所谓选代分组密码就是以迭 代一个简单的轮函数为基础的密码，即通过选择某个较简单的密码变换，在密钥控 制下以迭代方式多次利用它进行加密变换，例如f e i s t e l 型密码【7 咧就是一种选代密 码，是分组密码的典型代表，其数学思想简单而灵巧。特别是在相同的轮函数之下， 迭代次数的不同即代表了安全强度的不同级别。 ( 5 ) 网络安全通信的需要 在i n t e m e t i n t r a n e t 中随着通信量和业务种类的增加，对安全认证和保密业务的 需求日益迫切。比如，p g p ( p r e t t yg o o dp r i v a c y ) 就是一种广泛应用于i n t e r n e t 中e m a i l 系统的一种安全技术方案，它也可以用于其他网络中。p g p 的安全业务包括机密性、 认证性、不可抵赖性等，其中的机密性就是利用分组密码算法i d e a 来保证的。另 外，分组密码的工作模式可提供一些人们所需要的其他密码技术，比如流密码技术 和杂凑技术【1 0 1 2 】等。 1 2 国内外研究现状 现代分组密码的研究始于2 0 世纪7 0 年代中期，至今已有2 0 余年历史， 这期间人们在这一研究领域已经取得了丰硕的研究成果。大体上，分组密码的 研究包括三方面：分组密码的设计原理，分组密码的安全性分析和分组密码的 统计性能测试f 1 3 。15 1 。 2 第1 章绪论 分组密码的设计与分析是两个既相互对立又相互依存的研究方向，正是由 于这种对立促进了分组密码的飞速发展。早期的研究基本上是围绕d e s 进行， 推出了许多类似于d e s 的密码，例如，l o k i 、f e a l 、g o s t 等。进入9 0 年代， 人们对d e s 类密码的研究更加深入，特别是差分密码分析( d i f f e r e n t i a le r y p t a n a l y s i s ) 和线性密码分析( 1 i n e a re r y p t a n a l y s i s ) 的提出，迫使人们不得不研究 新的密码结构。i d e a 密码的出现打破了d e s 类密码的垄断局面，i d e a 密码的 设计思想是混合使用来自不同代数群中的运算。随后出现的s q u a r e 、s h a r k 和s a f e r 6 4 都采用了结构非常清晰的代替置换( s p ) 网络l l 引，每一轮由混淆层和 扩散层组成。这种结构的最大优点是能够从理论上给出最大差分特征概率和最 佳线性逼近优势的界，也就是密码对差分密码分析和线性密码分析i l 卜”j 是可证 明安全的。 a e s 的征集掀起了分组密码研究的新高潮，15 个a e s 候选算法反映了当 前分组密码设计的水平，可以说是近几年研究成果的一个总汇。目前分组密码 所采用的整体结构可分为f e i s t e l 结构( 如c a s t 2 5 6 、d e a l 、d f c e 2 等) 、s p 网络( 如s a f e r + 、s e r p e n t 等) 及其他密码结构( 如f r o g 和h p c ) 。f e i s t e l 结构由于d e s 的公布而广为人知，已被许多分组密码所采用。f e i s t e l 结构的最 大优点是容易保证加解密相似，这一点在实现中尤其重要。而s p 网络比较难 做到这一点，但是s p 网络的扩散特性【1 7 】比较好。在现有的分组密码中，所有 的基本运算有异或、加、减、查表、乘及数据依赖循环等。查表运算提供了d e s 的安全基础，仔细地选择s 盒【1 8 】能较好地抗击线性和差分密码分析，提供好 的数据及密钥比特的雪崩特性【1 9 2 0 1 。不过，s 盒需要一些存储器，所以s 盒的 规模不能太大。1 5 个a e s 候选算法所采用的s 盒规模有6 种【2 1 2 2 j ，分别是4 4 、8 8 、8 x 3 2 、1 1 8 、1 3 8 、及8 x 3 2 。s 盒的另一中称呼是黑盒子，它常给人 造成故意设置陷阱的嫌疑，因此，s a f e r + 等选取公开的数学函数，避免嫌疑。s 盒的设计与分析是分组密码设计中的重要环节，它的好坏直接影响密码体制的 安全性，目前对s 盒的设计并没有一个完备的要求，但总的希望是增强s 盒的 非线性度、差分均匀性及分量函数的代数次数和项数l z 3 乃】。 目前对分组密码安全性的讨论主要包括差分密码分析、线性密码分析和强 力攻击等。从理论上讲，差分密码分析和线性密码分析是目前攻击分组密码的 最有效的方法，而从实际上说，强力攻击是攻击分组密码最可靠的方法。到目 前为止，已有大量文献讨论各种分组密码的安全性，同时推出了譬如截段差分分 析、非线性密码分析及插值攻击1 2 6 - - 2 7 】等多种分析方法。自a e s 候选算法公布以后， 国内外许多专家都致力于候选算法的安全性分析，预计将会推出一些新的攻击 方法，这将进一步推动分组密码的发展。 3 河北科技大学硕士学位论文 分组密码是现代密码学中的一个重要研究分支，其诞生和发展有着广泛的实用 背景和重要的理论价值。目前这一领域还有许多理论和实际问题有待继续研究和完 善。这些问题包括：如何设计可证明安全的密码算法；如何加强现有算法及其工作 模式的安全性；如何测试密码算法的安全件；如何设计安全的密码组件，例如s 盒、 扩散层及密钥扩展算法【2 8 l 等。 1 3 本文研究的主要内容 本文主要介绍了分组密码的一般设计原理，并详细阐述了分组密码结构类型及 其各个部件的设计准则和构造方法，给出了国内外现有的几种攻击分组密码的典型 方法，包括差分密码分析、线性密码分析等；在此基础之上，给出了构造交换环上 m 维线性空间的对等非线性变换的一种方法，并且设计了基于对等变换的分组加密 模型。新的加密模型既有f e i s t e l 模型的对称性，又有s p 网络模型扩散速度快的优点， 然后从布尔函数【2 9 1 角度给出了s 盒的主要设计准则的严格数学描述1 3 0 1 ，并深刻阐述 了各准则的密码学意义，然后基于有限域上的幂函数，构造了一批可度量密码强度 的高速s 盒，并给出由幂置换1 3 i 】派生出的新的幂函数的性质和密码局限性，最后对 它进行了安全性评估和分析。 量 4 性、认证、身份识别、可控性及不可抵赖性等问题中的一个或几个系统。对一个密 码体制的正规描述需要用数学方法清楚地描述其中的各种对象、参数、解决问题所 使用的算法等。在一个密码系统中，通常将最初要发送的消息称为明文，经过秘密 变换后的消息称为密文。消息的隐藏过程称为加密，其逆过程即吧密文转变为明文 的过程称为解密。加密时所采用的规则为加密算法，相应地，解密规则称为解密算 法。一般而言，加密和解密操作都在密钥的控制下进行，( 密钥是一种参数，它是在 明文转换为密文或将密文转换为明文的算法中输入的数据) ，分别称为加密密钥和解 密密钥。下面给出用于加解密的密码体制的正式定义p 副 定义2 1 1 一个用于加解密( 保密) 的密码体制( 或系统) 是一个五元组 ( 尸，c ，k ，e ，d ) ，其中： 一 ( 1 ) p 称为明文空间，是所有可能的明文构成的集合。 ( 2 ) c 称为密文空间，是所有可能的密文构成的集合。 ( 3 ) k 称为密钥空间，是所有可能的密钥构成的集合。 ( 4 ) e 和d 分别表示加密算法集和解密算法集，它们满足，对每一个k k ，必存 在一个加密算法e k e 和一个解密算法反d ，使得对任意的m p ，恒有 反( 吼( 垅) ) = m 成立。 密码分析【3 4 】是研究密码体制的破译问题，即试图在不知道密钥的情况下，从截 取到的密文恢复出明文消息或密钥。根据密码分析着可能取得的分析资料的不同， 密码分析( 或称攻击) 可分为下列四类： ( 1 ) 唯密文分析( 攻击) ，密码分析者取得一个或多个用同一密钥加密的密文。 ( 2 ) 已知明文分析( 攻击) ，除要破译的密文外，密码分析者还取得一些用同一 密钥加密的明密文对。 ( 3 ) 选择明文分析( 攻击) ，密码分析者可取得他所选择的任何明文所对应的密 文( 当然，不包括他要恢复的明文) ，这些密文对和要破译的密文是用同一密钥加 密的。 ( 4 ) 选择密文分析( 攻击) ，密码分析者可取得他所选择的任何密文所对应的明 文( 要破译的密文除外) ，这些密文和明文和要破译的密文是用同一解密密钥解密 的，它主要应用于公钥密码体制。 5 河北科技大学硕士学位论文 2 2 分组密码的概念 从密码体制类型来看，有两种重要类型的密码系统，单钥( 私钥) 和双钥( 公 钥) 密码系统。在单钥密码系统中，明文的加密和密文的解密是用同样的密钥。直 到1 9 7 6 年d i f f i e ，h e l l m a n 引入公钥( 双钥) 密码学之前，所有的密码都是单钥系统， 因此单钥系统也称为传统密码系统。传统密码系统在今天被广泛使用，分为两类： 一是分组密码，二是流密码。分组密码又分为三类：代替密码，移位密码和乘积密 码。随着计算机技术的发展，早期的代替和移位密码已无安全可言。一个增加密码 强度的显然方法是合并代替和移位密码，这样的密码称为乘积密码。如果密文是由 明文运用轮函数多次而得，这样的乘积密码又称迭代分组密码。 所谓分组密码，也称块密码，它是将明文消息序列：m ，m ：，m 3 ，一，掰分成等 长的消息组( ，肌：，鸭，) ，( + p m n 彬m n ，m 2 。) ，。各组分别在密钥k 的控制下， 按固定的算法e 一组一组进行加密。加密后输出等长密文组( m ，y 2 ) ， ( 小虼伽y 2 。) ，。一般地，可以对分组密码作如下定义【3 5 】： 定义2 2 1 一个分组密码是一种映射：霹gj 矽，记为e ( x ，k ) 或& ( x ) ， x 霹，k ，霹为明文空间，f 为密文空间，片为密钥空间。 当刀 m 时，称为有数据压缩的分组密码； 当聆 m 时，称为有数据扩展的分组密码； 当刀= 朋且为一一映射时，毛( 功就是g f ( 2 ) ”到g f ( 2 ) ”的置换。以为明文分组长 度。通常最常见的情况是以= m ，在不作特别说明时，都是指这种情况。 2 3 分组密码的整体结构 一般分组密码的构造都应遵循下列几项原则： ( 1 ) 要有足够大分组长度，保证足够大的明文空间，避免给攻击者提供太多的明 文统计特征信息。 ( 2 ) 密钥空间要尽量大，以抵抗攻击者通过穷举密钥破译密文或者获得密钥信息。 ( 3 ) 保证足够强的密码算法复杂度，以增强分组密码算法自身的安全性，使攻击 者无法利用简单的数学关系找到破译缺口。增强密码算法复杂度常用的方法有两种， 一种是先将一个明文分组划分为若干子组分别进行处理，然后合并起来再做一些适 当的变换，以增大密码算法强度。采取这样的措施也便于密码算法的实际分析和评 测。第二种是采用成绩密码的思想。通过两种或两种以上简单密码的逐次应用，构 成强度比其中任何一个更强的加密结果，有效克服单一密码变换的弱点。 遵循这些原则非常重要，尤其在如何保证足够强的密码算法复杂度方面，分组 密码采用了不少措施来保证。具体来说，在分组密码算法的安全策略中，用的最多 的就是采用代换一置换网络( s u b s t i t u t i o n p e r m u t a t i o nn e t w o r k ) ，简称s - p 网络。它是 6 第2 章分组密码的基本理论和技术问题 由s 变换( 代换) 和p 变换( 置换或换位) 交替进行多次迭代而形成的变换网络 实际上，它属于迭代密码，也是乘积密码【3 q 的一种常见的表现形式。s 变换和p 换是分组密码中的基本构件。 2 3 1 代换盒 代换盒是一个变换，它把输入的一个以长的比特串a = ( 口l a 2 ，吒) 转化为另一个 m 长的比特串a = ( 口：，反，口卅) 输出。其中珂m 或，z m 。在分组密码中，也常把代 换盒称为s 盒，亦称黑盒子变换，其每个输出变量都是挖个输入变量的布尔函数( 主 要是非线性的) 。从数学的观点来看，一个具体的代换盒是一个从，2 长比特串的集到 m 长比特串的集合的映射兀： o ，1 l “寸f o ，1 1 ”。其中：k 为输入控制变量，这里即为密钥 k 。在分组密码的设计中，代换盒的设计往往是最核心的地方。它通常是密码算法的 最主要的非线性部件。因此要求每一个输出变量作为所有输入变量的布尔函数应具 有高的非线性度【3 7 】。在数据加密标准d e s 中使用了门= 6 ，m = 4 的代换盒，而在高级 加密标准a e s 中，使用了刀= m = 8 的代换盒。通常小的代换盒设计和实现都更容易， 但安全性能一般不如大的代换盒。 2 3 2 置换盒 置换盒是通过把一个比特串中各比特的位置次序重新排列而得到新的比特串的 变换。设置换盒尸的输入是m 长的比特串q 吒口卅，输出是等长的比特串6 1 6 2 6 卅， b i b 2 b m 是把口l a 2 a m ，重新排列次序而得到的，因此必有集合 1 ，2 ，m ) 上的一个置 换万，使得b , b 2 6 脚= 尸( 口l a 2 a m ) = ( 1 ) ( 2 ) a a ( 肘) 。 一个代换置换网络由一个代换盒和一个置换盒构成一层，然后反复迭代多次而 形成。其中的一层可以看做由一个代换密码和一个置换密码构成的乘积密码，这个 乘积密码就是迭代密码的轮函数p m 。 2 4 分组密码的原理和设计准则 2 4 1 分组密码的加密原理 分组密码一般采用代换置换网络的结构。这种结构的一个典型代表是f e i s t e l 密 码结构，而且大量的对称密码算法中有不少采用了这种结构模型，其中最具代表性 的是数据加密标准d e s 。因此研究f e i s t e l 结构模型很有必要。其密码算法的基本思 路是采用“扩散与混乱 两种主要思想，这是s h a n n o nc 为了有效抵抗攻击者对密 码体制的统计分析，提出的两个基本设计思想【3 1 l 混乱原则和扩散原则，这种 思想也是设计对称分组密码的一条主线。 混乱是指明文与密钥以及密文之间的统计关系尽可能复杂化，使破译者无法理 7 河北科技大学硕士学位论文 出相互问的依赖关系，从而加强隐蔽性。采用复杂的非线性( 比如s 盒单元) 就可以达 到比较好的混乱效果。 扩散是指让明文中的每一位( 包括密钥的每一位) 直接或间接影响输出密文中 的许多位，或者让密文中的每一位受制于输入明文以及密钥中的若干位，以便达到 隐蔽明文的统计特性。密码学中的重要指标“雪崩效应”，讲的就是迅速扩散的概念。 它强调输入位只要很小的变化，经过多轮变换后将导致输出发生多位变化，即明文 的每位比特变化将引起密文许多比特位迅速发生改变。 f e i s t e l 密码结构是2 0 世纪6 0 年代末由i b m 公司提出来的，其特点是：通过代 替和置换( s - p 网络) 交替的方式来构造分组密码，其实就是基于混乱和扩散原理实 现加解密运算。f e i s t e l 结构属典型的迭代结构，是一种乘积密码的思想。 2 4 2 分组密码的设计准则 正因为f e i s t e l 密码结构具有较多优点，许多重要的密码算法都采用这种结构或 类似的结构进行密码设计。在分组密码具体设计中除了前面的设计分组密码必须遵 循的基本原则外，还需要重点考虑：s 盒的设计，p 盒的设计，轮函数f 的设计，迭 代轮数以及密钥扩展算法等。 1 s 盒的设计准贝t j t 4 2 j s 盒是分组密码的非线性部分的核心部件，起着加密算法的混淆作用，直接影响 整个分组密码算法的安全强度。s 盒大小的设计要适中，过大易造成设计困难，存储 容量增加；过小易遭受破译者的分析。s 盒的设计不是孤立的，要考虑与它相关参数 的平衡性。对于s 盒的设计准则来说，如何保证它的非线性指标是非常重要的。不 少密码学家建议s 盒各列的线性组合应符合b e r n 函数( 它是一种特殊的布尔函数， 具有很高的非线性) 要求。在这方面，衡量s 盒的主要指标包括： ( 1 ) 非线性度。为抵抗线性密码分析，非线性度越高越好。 ( 2 ) 差分均匀性。这是差分密码分析的一个概念，度量一个密码函数，其抵抗差 分密码分析的能力要强 ( 3 ) 雪崩效应【4 3 】。这与p 盒的功能有关，是混淆扩散特性的进一步反映，要求有 良好的雪崩效果，即要求当输入有1 比特发生变化时，将导致输出有一半的比特位 发生变化。 ( 4 ) i j i 解密互逆，没有“陷门 。 2 p 盒的设计准则 分组密码中的s - p 网络，是一个集掩蔽、混淆、扩散于一体的综合性部件，目 的就是实现高度的非线性化和良好的雪崩效应。由于p 盒多半在s 盒部件之后，因 此p 盒的设计准则就是要实现良好的雪崩效应，进一步提高扩散和混淆程度。 3 轮函数f 的设计准则 8 第2 章分组密码的基本理论和技术问题 轮函数f 通常是指迭代分组密码中单轮加密算法的非线性函数，s 盒与p 盒是 其最主要的构成部件。有时还会增加一些线性变换，或者用一个线性变换取代p 盒。 主要考虑的是如何快速实现密钥与明文的混淆与扩散，并使密文的差分分布均匀。 在设计中要遵循独立和雪崩效应准则。安全性、速度盒灵活性是轮函数f 的主要性 能指标。 ( 1 ) 安全性。轮函数f 必须能抵抗所有已知的密码攻击方法的攻击，尤其是抵抗 差分密码分析和线性密码分析。 ( 2 ) 速度。轮函数的复杂性和迭代轮数的多少直接影响密码算法的速度。不论是 用简单的还是复杂的方法来构造轮函数，都必须综合平衡轮函数的各项指标，保证 构造出实际安全而且运行效率高的密码算法。 ( 3 ) 灵活性。支持密码算法能在多平台和多处理器上实现。 4 迭代轮数的考虑 迭代型分组密码就是用简单的、安全性弱的加密算法进行多轮迭代运算，使得 安全性增强。一般来说，分组密码迭代轮数越多，密码分析越困难。但也不是追求 迭代轮数越多越好，多会使输入和输出的关系复杂化。分组密码迭代轮数一般采用 r = 8 , 1 0 ，1 2 ，1 6 ，2 0 的居多。设计迭代轮数i 删的准则是：使密码分析的难度大于简单穷 举攻击的难度。 5 密钥扩展算法的设计 密钥扩展是迭代分组密码算法的一个重要组成部分，是从初始( 种子) 密钥产 生迭代的各轮要使用的子密钥的算法1 4 5 1 。严格的说，轮函数f 的功能是在子密钥的 参与和控制下实现的。因此，子密钥的生成很重要，其目标主要是保证子密钥的统 计独立性。评价子密钥的生成方法的性能指标包括：结构尽量简单，便于软硬件实 现；密钥扩展算法至少应保证密钥和密文符合位独立准则和严格雪崩效应准则；不 存在简单的数学关系，获取一些子密钥比特的关系在计算上是困难的；没有弱密钥， 弱密钥通常是指因设计不当或不可避免存在的会明显降低密码算法安全性的一类密 钥；保证种子密钥的各比特对每个子密钥比特影响的均衡性；速度也是衡量子密钥 扩展的一个重要指标。 2 5 差分分析和线性分析 密码分析和密码设计是相互对立、相互依存的。伴随着任何一种密码的设计，分 析者便会千方百计地从该密码中寻找“漏洞”和缺陷进行攻击。对现代分组密码更 是如此，一直以来对它的分析工作一刻未停。归纳起来，对分组密码的分析主要方 法有如下几种类型：穷尽密钥搜索( 强力攻击) ；线性分析方法；差分分析方法；相 关密钥密码分析：中间相遇攻击。 9 河北科技大学硕士学位论文 这些分析方法的出现对现代分组密码的安全性构成了威胁，也对分组密码的设 计提出了更高的要求。其中，差分密码分析法和线性密码分析法是两个被人们熟知 和广泛使用的分析方法。 差分密码分析法简单地说就是选择明文攻击，实际上是一种攻击迭代分组密码 的选择明文统计分析破译法。虽然实用性差些，但理论价值更大些，适合作为评估 分组密码的整体安全性的重要指标。它与一般统计分析法的本质区别是，不直接分 析密文或密钥的统计相关性，而是通过对明文对的差值与对应的密文对的差值之间 的统计关系的分析，对密钥的有关位进行合理的推断和猜测。在输入输出的非线性 关系下，往往给定一个密钥将导致两个明文的差值和对应的两个密文之间的差值是 不一样的。而大量的分组密码的s 盒设计又都是非线性的，因此某些差异关系有可 能暗示一些密钥值的蛛丝马迹。利用这种关系，可以通过分析明文对的差值对密文 对的差值的影响来恢复某些密钥比特，从中进一步找出潜在的密钥关系。 定义2 5 1 【4 6 j 设两个不同的明文x 和x ，在一个r 轮迭代密码中，其差分值定 义为：a x = x ( x ) 一。式中：符号“o 表示r l 长比特串的集合( 明文空间) 上 的一种群运算( 常用逐比特异或) ；) 。1 为x 在群运算。下的逆元。 在密钥k 的作用下，经过，轮迭代产生的两个不同的中间密文差分为： a y ，) = y c j ) ( 】，1 1 0 j ，。其中，】，( o ) = a x ，上试同时也是，+ 1 轮的输 入差分。若记第轮的子密钥为k ，轮函数为f ，则e = ，( l 小k ，) 。 利用差分定义分析分组密码的基本策略是根据已知r = ，( _ 小k ，) 和 ，= f ( y ，一，k ，) 来确定子密钥k ，或者根据已知密文对，以及最后一轮的输入对 的差分来找出最后一轮的子密钥或一部分。研究表明，通过选择特定差分值孱的明 文对( z x ) ，在特定值屏一。处获取最后一轮的