（计算机软件与理论专业论文）sms4算法分析及其在3g中的应用.pdf

s m s 4 算法分析及其在3 g 中的应用 摘要 为了保障3 g 通信系统的安全，3 g p p 定义了数据加密算法f 8 和完整性认证算法 f 9 ，这两个算法都是以同一个分组密码作为内核算法的。从安全性角度考虑，我国需 要自主设计一个分组密码作为f 8 和f 9 的内核算法。本文从以下几个方面研究了国产 算法s m s 4 作为f 8 和f 9 内核算法的可行性： 1 安全性方面，分析了s m s 4 抵抗线性攻击和差分攻击的能力。对非平衡f e i s t e l 结构的s m s 4 ，采用类似于平衡f e i s t e l 结构下的分析方法，从理论上建立了s m s 4 线 性偏差概率和s m s 4 轮函数f 线性偏差概率之间的关系式，再进一步根据轮函数f 的 一轮s p 结构特点，建立与s 盒线性偏差概率之间的关系式。通过这个关系式求出3 2 轮s m s 4 线性偏差概率的一个上界。采用类似的分析方法，求出3 2 轮s m s 4 差分特征 概率的一个上晁。按照k n u d s e n 的安全标准，根据求出的两个概率上界对s m s 4 作安 全评估。结果表明3 2 轮s m s 4 具有很强的抗线性攻击和差分攻击能力，满足3 g p p 对 内核算法的线性安全性和差分安全性要求。 内 按 为 同 文 均 s m s 4a l g o r i t h ma n a l y s isa n di t sa p p l i c a t i o ni n 3 gc o m m u n i c a t i o ns y s t e m a b s t r a c t d a t ac o n f i d e n t i a l i t ya l g o r i t h mf 8a n di n t e g r i t ya l g o r i t h mf 9h a v eb e e nd e f i n e db y 3 g p pt op r o t e c tt h es e c u r i t yo f3 gc o m m u n i c a t i o ns y s t e m s t h e ya r eb a s e do nt h es a m e b l o c kc i p h e ra sc o r ea l g o r i t h m f r o mt h es e c u r i t yp o i n to fv i e w , c h i n as h o u l dd e s i g na b l o c kc i p h e ra sc o r ea l g o r i t h mo ff 8a n df 9 f r o mt h ef o l l o w i n ga s p e c t s ，t h i sp a p e rs t u d i e s t h ef e a s i b i l i t yo fm a k i n gs m s 4a sc o r ea l g o r i t h mo ff 8a n df 9 s e c u r i t y , t h ea b i l i t yf o rs m s 4t or e s i s tl i n e a ra t t a c ka n d d i f f e r e n t i a la t t a c ki sa n a l y z e d al i n e a rb i a sp r o b a b i l i t yr e l a t i o n s h i pb e t w e e ns m s 4a n di t sr o u n df u n c t i o ni se s t a b l i s h e d t h e o r e t i c a l l yb yu s i n gt h es i m i l a rm e t h o du s e dt oa n a l y z ef e i s t e ls t r u c t u r e o w i n gt oo n e r o u n ds ps t r u c t u r eo fr o u n df u n c t i o n ，a n o t h e rl i n e a rb i a sp r o b a b i l i t yr e l a t i o n s h i pb e t w e e n s m s 4a n ds - b o xi se s t a b l i s h e dt h e o r e t i c a l l y t h e no n el i n e a rb i a sp r o b a b i l i t yu p p e rb o u n d o f3 2 r o u n ds m s 4i sd e d u c e db yt h el a t t e rr e l a t i o n s h i p s i m i l a r l y , o n ed i f f e r e n t i a l c h a r a c t e r i s t i cp r o b a b i l i t yu p p e rb o u n do f3 2 - r o u n ds m s 4i sd e d u c e d b a s e do nt w ou p p e r b o u n d ，c o r r e s p o n d i n gs e c u r i t ye v a l u a t i o ni sm a d ea c c o r d i n g t ok n u d s e n ss e c u r i t ys t a n d a r d t h er e s u l t ss h o wt h a t3 2 r o u n ds m s 4h a sas t r o n ga b i l i t yt or e s i s tl i n e a ra n dd i f f e r e n t i a l a t t a c k s os m s 4m e e t st h es e c u r i t yr e q u i r e m e n to f3 g p e r a n d o m n e s s ，k e y s t r e a m sg e n e r a t e db yf 8w i t hs m s 4a sc o r ea l g o r i t h ma r et e s t e di n r a n d o m n e s s f i r s to fa l l ，t h ef 8i sr e a l i z e db ycl a n g u a g e ，a n dg e n e r a t e s10 0g r o u p s 2 0 0 0 0 一b i tk e y s t r e a m su s i n g10 0d i f f e r e n tc i p h e rk e y s t h e nr a n d o m n e s so ft h ek e y s t r e a m s i st e s t e db yf i p s14 0 2s t a n d a r d t h er e s u l t ss h o wt h a tk e y s t r e a m sg e n e r a t e db yt h ef 8 b e h a v ee x c e l l e n tp e r f o r m a n c eo fr a n d o m n e s s s os m s 4m e e t st h er a n d o m n e s sr e q m r e m e n t o f 3 g p e i e f f i c i e n c y ，e n c r y p t i o ns p e e do ff 8w i t hs m s 4a s c o r ea l g o r i t h mi st e s t e dw h e n r e a l i z e di ns o f t w a r e f i r s to fa l l ，t h ef 8g e n e r a t e s6 - g r o u pk e y s t r e a m s w i t ht h e s e k e y s t r e a m s ，s i xg r o u p st i m eo fs a m ep l a i n t e x te n c r y p t e db y 10 0 0t i m e sa r er e c o r d e d r e s p e c t i v e l y a c c o r d i n g t ot h e s i z eo fp l a i n t e x t ，s i xg r o u p st i m ea r ec h a n g e di n t o e n c r y p t i o ns p e e d s t h er e s u l ts h o w st h a ta v e r a g es p e e do ft h ef 8i ns o f t w a r e r e a c h e st o 1 9 2 4m b p s s os m s 4m e e t sa p p r o x i m a t i v e l yt h ee f f i c i e n c yr e q u i r e m e n to f3 g p p k e yw o r d s ：s m s 4 ；f 8 ；f 9 ；c o r ea l g o r i t h m ；l i n e a rb i a sp r o b a b i l i t y ； d i f f e r e n t i a lc h a r a c t e r i s t i cp r o b a b i l i t y 一 目录 摘要i a b s t r a c t i i 目录i v 第1 章绪论1 1 1 研究背景1 1 2 国内外研究现状分析3 1 3 本文研究工作和意义4 1 4 研究思路及本文内容安排4 第2 章密码学概述及s m s 4 算法介绍7 2 1 密码学安全概述。7 2 1 1 密码学安全7 2 1 2 密码学攻击类型8 2 2 分组密码1 0 2 2 1 分组密码原理1 0 2 2 2 分组密码一般设计原理。1 0 2 2 3 分组密码整体结构1 1 2 2 4 分组密码设计准则1 2 2 3s m s 4 算法介绍1 4 2 3 1 轮函数f 14 2 3 2 加密解密算法1 5 2 3 3 密钥扩展算法l6 2 4 本章小结16 第3 章s m s 4 抗线性攻击和差分攻击分析1 7 3 1 预备知识1 7 3 2s m s 4 设计结构分析2 1 3 2 1 整体结构分析2 1 3 2 2s m s 4 算法的s 盒性质2 2 3 2 3s m s 4 算法线性变换2 4 3 3s m s 4 抗线性攻击分析2 5 3 4s m s 4 抗差分攻击分析3 6 v 3 5 本章小结4 7 第4 章s m s 4 在3 g 通信加密和认证中的应用4 8 4 1f 8 算法和f 9 算法简介4 8 4 1 1f 8 算法简介4 8 4 1 2f 9 算法简介5 0 4 2 内核为s m s 4 的f 8 算法和f 9 算法5 1 4 2 1 内核为s m s 4 的f 8 算法5 2 4 2 2 内核为s m s 4 的f 9 算法5 3 4 3 内核为s m s 4 的f 8 算法随机性测试5 5 4 3 1 随机性测试标准f i p s1 4 0 2 介绍5 5 4 3 2 内核为s m s 4 的f 8 随机性测试5 6 4 4 加密速度测试6 1 4 5 本章小结6 2 第5 章总结与展望6 3 参考文献6 5 攻读学位期间取得的研究成果6 7 致 谢6 8 浙江师范大学学位论文独创性声明6 9 学位论文使用授权声明6 9 v i 1 1 研究背景 第1 章绪论 随着计算机网络和通信技术的迅速发展与普及，信息安全在现代信息社会中占据 着越来越重要的地位，然而，要构建安全的信息系统，必须使用密码技术，密码技术 是安全信息系统的核心。密码技术在信息系统中应用主要体现在数据保密、身份认证、 数据完整性认证、不可抵赖、访问控制和数据可用性n3 。数据保密要求做到只有发送 人和所有接受人才能访问某个消息内容。身份认证用于证明身份，保证正确标识电子 消息或文档来源。数据完整性认证用于保障数据在通信传输过程中不会发生改变，若 发送方发出的消息内容到达接收方时，消息内容发生篡改，则破坏了数据的完整性。 不可抵赖用于防止消息发送者拒绝承认发送过消息。访问控制用于确定谁可以访问系 统，能访问哪些内容。数据可用性要求服务器实时地向授权用户提供资源。 由此可见，密码技术在信息系统的重要性。在通信领域，安全需求更是不可或缺。 最近，国家工业信息部给三大电信运营商正式颁发了3 g 牌照，标志着中国正式进入 了3 g 通信时代。3 g 通信系统空中接口安全是在手机、基站等通信实体间对等地进行 安全保护，要求通信实体间必须采用相同的密码算法。为保障3 g 通信系统通信安全， 3 g p p ( 3 r dg e n e r a t i o np a r t n e rp r o j e c t ，第三代移动通信合作组织) 安全部门针对 不同的安全需求，共定义了1 0 种密码算法乜3 ，即随机数产生算法f 0 、通信网络鉴别 算法f 1 、重新同步情况下消息认证算法f 1 、用户鉴别算法f 2 、加密主密钥产生算法 f 3 、完整性认证主密钥产生算法f 4 、正常情况下使用的匿名密钥产生算法f 5 、重新 同步情况下使用的匿名密钥产生算法f 5 、数据加密算法f 8 以及数据完整性认证算法 f 9 。前八个算法没有被标准化，f 8 和f 9 是3 g p p 已经标准化的算法b 1 。这两个算法都 是以同一个分组密码作为内核算法的，其中内核算法可以由各个国家根据本国实际需 要自主设计，并在本国通信系统中应用。为了保证该内核算法在全球通信系统中通用， 第1 章绪论 内核算法需要被标准化。目前，分组密码算法k a s u m i 是3 g p p 唯一已经标准化的内核 算法h 3 ，3 g p p 允许可标准化的内核算法共1 5 种陆1 ，对每种内核算法要求达到3 g p p 规 定的安全标准和实现效率标准，才可以被标准化。标准化后的内核算法将分配到4 比 特算法标识符，其中0 0 0 0 表示不加密，0 0 0 1 至1 1 1 1 共可以表示1 5 种内核算法，目 前3 g p p 已标准化的内核算法k a s u m l 分配到的算法标识符为0 0 0 1 。3 g p p 允许使用1 5 种标准内核算法是为了满足全球电信运营商对不同安全算法的自由选择，但每次互联 通信时两个基站或基站与手机之间都必须采用同一个标准内核算法。 k a s u m i 算法是3 g p p 在日本三菱公司开发的算法m i s t y 基础上改进的，它是分组 长度为6 4 位的分组密码算法，密钥长度为1 2 8 位，采用了f e i s t e l 网络结构，共迭 代八轮。3 g p p 安全工作组已经论证了该算法的安全性和其它指标，研究结果表明该 算法各方面性能都很优越，因此能被3 g p p 很快地确定为标准内核算法。使得各国移 动通信设备都可以采用k a s u m 工作为f 8 和f 9 的内核算法，达到数据加密和完整性认 证。然而，根据国务院1 9 9 9 年出台的商用密码管理条例砸3 ，k a s u m i 算法是境外 研发的密码产品，从安全性角度考虑，未经国家有关部门许可不允许在我国国内商业 使用。因此内核为k a s u m i 的f 8 和f 9 算法不能在中国3 g 通信系统中使用，为了保障 3 g 通信系统的相关安全，中国3 g 通信系统必须自主开发f 8 和f 9 的内核算法口1 ，并 经国家有关部门评审通过，可以商用并公开设计结构，再报送3 g p p 相关部门进一步 评审，若能评审通过，将会被标准化并获得国际上通用的标准内核算法标识符，使得 国内3 g 通信系统和国外3 g 通信系统都可以使用此内核算法达到数据加密和完整性认 证。如今，我国各大电信运营商、国家相关部门以及信息安全i t 企业正致力于开发 符合3 g p p 安全性要求以及实现效率要求的候选内核算法。目前，很少有候选内核算 法方面的研究成果发布。而3 g 通信己经在全国推广，亟需内核算法达到安全性。当 务之急是在已有的国产分组密码中挑选。目前国内已公布的优秀分组密码中首推 s m s 4 算法呻1 。它是国内第一个公布的商用分组密码算法( 国家商业密码办公室于2 0 0 6 年1 月发布) ，已经在国内无线局域网产品中广泛使用，但它能否充当f 8 和f 9 的标 准内核算法还需要在安全性、实现效率等方面作进一步的研究。 2 第1 章绪论 1 2 国内外研究现状分析 s m s 4 是一种分组密码算法，分组长度和主密钥长度均为1 2 8 位。对s m s 4 的攻击 或分析方面，由于算法2 0 0 6 年才公布，所以国内外关于这方面的研究成果不是很多。 文献 9 用差分故障分析法恢复s m s 4 的1 2 8 位主密钥时，平均大约需要4 7 个错误密 文，说明s m s 4 对差分故障攻击是不免疫的，但只要对相关的硬件设备加以保护，便 可避免此类攻击。文献 1 0 利用s q u a r e 攻击思想攻击了1 4 轮s m s 4 。文献 1 1 使用 不可能差分分析法攻击了1 7 轮s m s 4 。文献 1 2 讨论了i n t e g r a l 分析法攻击1 3 轮 s m s 4 。在运用r e c t a n g l e 攻击方面，文献 1 3 1 4 1 5 分别攻击了1 4 轮、1 6 轮和1 8 轮s m s 4 。文献 1 3 还用不可能差分法攻击了1 6 轮s m s 4 。文献 1 5 详细讨论了用 b o o m e r a n g 分析法攻击1 8 轮s m s 4 。在上述各种攻击中，由于攻击所需要的数据复杂 度和处理复杂度都在0 ( 2 o ) 以上，如此高的复杂度，使得在实际硬件环境下，攻击很 难实现，所以上述攻击只在理论上有效，实际并不能达到有效攻击的目的，攻击过程 有待进一步优化。 根据密码学常识，差分密码分析和线性密码分析( 简称差分攻击和线性攻击) 是 分组密码最有效的两种攻击算法。目前，文献 1 4 1 5 1 6 1 7 分别对s m s 4 进行了 2 1 轮、2 2 轮、2 2 轮和2 3 轮差分攻击。其中最好的是文献 1 7 所作的2 3 轮攻击，它 所需要的选择明文数据复杂度为0 ( 2 1 哺) ，加密处理复杂度为o ( 2 1 2 4 。3 ) 。在对s m s 4 进行 线性攻击方面，主要有文献 1 5 和文献 1 8 所作的2 2 轮攻击。最好的是文献 1 5 所 作的2 2 轮攻击，它所需要的明文数据复杂度为0 ( 2 7 ) ，处理复杂度为0 ( 2 1 伸邮) 。以 上各种差分攻击及线性攻击的数据复杂度和处理复杂度都接近o ( 2 1 龃) ，根据分组密码 攻击相关知识n 训，如果某个分组密码算法的分组长度为n ，密钥长度为k ，如果一种 攻击方法是有效的攻击，则它所需要的数据复杂度远小于0 ( 2 “) ，而且处理复杂度远 小于0 ( 2 0 ) 。由此可见，以上对s m s 4 的差分攻击和线性攻击的各种复杂度都没有远 小于0 ( 2 1 2 8 ) ( s m s 4 的n 和k 都为1 2 8 ) ，所以它们都不是有效的攻击。但不排除对上 述攻击算法改进优化后差分攻击或线性攻击成功的可能。 3 第1 章绪论 1 3 本文研究工作和意义 目前，国内外尚无关于3 2 轮s m s 4 的差分攻击和线性攻击。那么，是否说明3 2 轮s m s 4 对差分和线性攻击是免疫的呢? 显然，不能根据有限的攻击实例来臆断。s m s 4 抵抗差分攻击和线性攻击的能力又是怎样的呢? 假若s m s 4 能抵抗差分攻击、线性攻 击以及其它现有的一切攻击，在安全性方面有了一定的保障，那么从随机性和实现效 率角度，国产算法s m s 4 能否成为f 8 和f 9 的标准内核算法呢? 以上两个问题正是本 文将要研究的课题。研究该课题的意义在于： 1 作为s m s 4 抵抗差分攻击和线性攻击的理论依据。设计一个密码并不难，难的 是如何从理论上分析清楚该密码抗攻击的复杂度，研究该课题，即分析清楚s m s 4 抗 差分攻击和线性攻击的复杂度，从理论上论证s m s 4 抗差分和线性攻击的能力。 2 分析清楚各轮s m s 4 抗攻击能力，根据实际安全要求，在保证抵抗所有已知抗 击的前提下，适当降低s m s 4 迭代轮数，提高算法实现效率。 3 为推荐s m s 4 充当f 8 和f 9 标准内核算法，提供安全方面的可行性依据。差分 攻击和线性攻击是目前最有效的两种的攻击算法，按照3 g p p 对安全算法的要求，f 8 和f 9 的内核算法要确保能抵抗差分攻击和线性攻击，分析s m s 4 抵抗这两种攻击的能 力，为推荐s m s 4 作为f 8 和f 9 标准内核算法提供安全依据。 4 为推荐s m s 4 充当f 8 和f 9 标准内核算法，提供随机性和实现效率方面的可行 性依据。研究内核为s m s 4 的f 8 所产生的密钥流随机性以及用软件实现时的加密速度， 为进一步推荐s m s 4 充当f 8 和f 9 标准内核算法提供随机性和实现效率方面的可行性 依据，有助于加快国产算法作为f 8 和f 9 标准内核算法的脚步，尽快解决国内外3 g 通信系统互联通信时的数据加密和完整性认证问题。 1 4 研究思路及本文内容安排 本文的重点是评估s m s 4 抗差分和线性攻击的能力，那么如何评估一个密码算法 抵抗差分攻击和线性攻击的能力呢? k a n d a 给出了下述四种方法圳： 精确估计：计算出密码算法的差分特征概率平均值和线性偏差概率平均值。若两 4 第1 章绪论 种平均值都小于某一个标准值，则认为能抵抗相应的攻击。通常，这种方法在实际操 作中是不可行的； 理论上的估计：给出密码算法差分特征概率平均值的一个上界和线性偏差概率平 均值的一个上界。若两种上界都小于某一个标准值，则认为能抵抗相应的攻击。这种 方法曾经评估过许多算法，如m i s t y 算法； 经验上的估计：计算出最大差分特征概率和最大线性偏差概率。首先罗列出密码 算法的最大或者一系列相对较大的差分特征概率和线性偏差概率，由此找出密码算法 的高概率差分特征和线性逼近，并计算出最大差分特征概率和最大线性偏差概率。若 两种最大概率都小于某一个标准值，则认为能抵抗相应的攻击。这种方法在实际计算 中要耗费大量的硬件资源； 实用的估计：计算出差分特征概率的一个上界和线性偏差概率的一个上界。根据 k n u d s e n 的研究陋，若计算出的两个上界都小于某一个标准值( 通常这个标准值为2 。n ， n 为分组长度) ，则认为该密码算法是抗差分和线性攻击的。这种估计是目前最有效、 实用的方法，被大多数分组密码算法用来评估抵抗攻击能力，如r i j n d a e l 算法、 c a m e l l i a 算法、e 2 等等。 本文将采用第四种方法来评估s m s 4 抵抗差分和线性攻击的能力，即计算出s m s 4 差分特征概率的一个上界以及线性偏差概率的一个上界。 本文的创新点： 1 根据s m s 4 的非平衡f e i s t e l 结构特点，采用类似于平衡f e i s t e l 结构下的分 析方法2 2 2 驰，从理论上建立了s m s 4 差分特征概率及线性偏差概率和s m s 4 轮函数f 差分特征概率及线性偏差概率之间的关系式，再进一步根据轮函数f 的一轮s p 结构 特点，建立与s 盒差分特征概率及线性偏差概率之间的关系式。从而将求两种概率的 一个上界问题转化为求s 盒最大差分特征概率、s 盒最少差分活动数、s 盒最大线性 偏差概率和s 盒最少线性活动数。 2 将s m s 4 作为f 8 和f 9 内核算法：研究其参数配置；对内核为s m s 4 的f 8 产生的密钥流从随机性角度进行分析：将内核为s m s 4 的f 8 软件实现下的加密速度 进行了测试。进一步探索s m s 4 真正作为内核算法的可能性，尽快解决国内外3 g 通信 5 第1 章绪论 系统互连通信时的数据加密和完整性认证问题。 本文的内容安排： 第1 章：绪论。首先在3 g 通信安全背景下提出课题，并阐述了课题的意义。最 后是本文的内容安排。 第2 章：密码学概述及s m s 4 算法介绍。介绍了密码学安全和密码学攻击类型， 并简述了密码学中两种重要的攻击：差分密码分析和线性密码分析。接着介绍了分组 密码原理。鉴于本文的研究对象s m s 4 为分组密码，本章还阐述了分组密码的一般设 计原理、整体结构和各组件的设计准则，最后简要介绍了分组密码s m s 4 算法结构。 第3 章：s m s 4 抗线性攻击分析和抗差分攻击分析。首先给出了本章中需要用到 的相关定义、公式和算法。接着对s m s 4 的整体结构、s 盒线性特性、s 盒差分特性及 p 置换的线性变换矩阵进行了分析。采用类似于平衡f e i s t e l 结构下的分析方法，从 理论上建立了s m s 4 线性偏差概率和s i d s 4 轮函数f 线性偏差概率之间的关系式，再进 一步根据轮函数f 的一轮s p 结构特点，建立与s 盒线性偏差概率之间的关系式。并 将求s m s 4 线性偏差概率的一个上界问题转化为求s 盒最大线性偏差概率和s 盒最少 线性活动数。由此得出4 至3 3 轮s m s 4 各轮线性偏差概率相应的一个上界。同时评估 了s m s 4 抵抗线性攻击的能力。接着对s m s 4 差分特性采取类似方法进行了处理。并评 估了s m s 4 抵抗差分攻击的能力。 第4 章：s m s 4 在3 g 通信加密和认证中的应用。首先介绍了3 g 通信加密算法f 8 和完整性认证算法f 9 。接着对内核为s m s 4 的f 8 和f 9 的参数设置进行了研究，并对 内核为s m s 4 的f 8 产生的密钥流随机性以及用软件实现的加密速度进行了检测，并对 两种检测结果进行了分析。 第5 章：总结与展望。总结本文所获得的各种结论，并提出未来可以展开的一些 工作和思路方向。 6 第2 章密码学概述及s m s 4 算法介绍 密码学的发展大致经历了两个阶段：传统密码学和现代密码学。传统密码学主要 采用代换和换位技术。现代密码学是一门交叉学科，它涉及数学、计算机科学、电子 和通信等各方面的知识。目前，密码学在通信和信息系统安全领域有着广泛的运用。 本章第一节介绍了密码学安全、密码学攻击类型，并简述了密码学中两种重要的攻击 方法：差分密码分析和线性密码分析方法。第二节介绍了分组密码工作原理，并阐述 了分组密码的一般设计原理、整体结构和各组件的设计准则。第三节简要介绍了分组 密码s m s 4 算法原理。第四节为本章小结。 2 1 密码学安全概述2 4 1 2 1 1 密码学安全 评价密码体制的安全性主要有两种方法：理论安全性和实际安全性。若在一种密 码体制中，密码分析者无论知道多少密文以及采用何种方法都得不到明文或者密钥的 信息，即使具有无限计算资源( 如时间、空间、资金和设备) 也无法破解某个密码系 统，则称该密码体制为理论安全的。理论安全性与攻击者的计算能力或时间无关。实 际安全性是根据破解密码系统所需的计算量来评价其安全性，它又分为计算安全性、 现实安全性和可证明安全性三种。若破解一个密码系统是可行的，但使用已知的算法 和现有计算工具不可能完成所要求的计算量，则称该密码体制在计算上安全。计算安 全性是计算并估计出破解密码系统的计算量下限。现实安全性是破解该密码系统的成 本超过被加密信息本身价值或者破译该密码系统的时间超过被加密信息的有效生命 周期。可证明安全性是将密码体制的安全性归结为求解某个经过深入研究但尚未解决 7 llllllll7l。ll。lllllllllllil_rllllllllllll-_lllll卜 第2 章密码学概述及s m s 4 算法介绍 的数学难题，即将某种密码体制的安全性问题等价为一个数学难题的求解问题。 2 1 2 密码学攻击类型 密码分析俗称密码破译或密码攻击，是指非授权者在不知道解密密钥的条件下对 密文进行分析，试图得到明文或密钥的过程。根据密码分析者可获得的密码分析信息 量把密码体制的攻击划分为以下五种类型： 唯密文攻击：密码分析者除了拥有截获的密文外( 密码算法是公开的) ，没有其 他可以利用的信息。密码分析者的任务是恢复尽可能多的明文，最好是能推导出加密 密钥，以便可采用相同的密钥推导出其他被加密的信息； 已知明文攻击：密码分析者不仅掌握了相当数量的密文，还拥有一些已知的明密 文对。密码分析者的任务就是用加密信息推出用来加密的密钥或导出一个算法，此算 法可以对用同一密钥加密的任何新的信息进行解密； 选择明文攻击：密码分析者不仅能够获得一定数量的明密文对，还可以选择任何 明文并在使用同一未知密钥的情况下得到相应的密文； 选择密文攻击：密码分析者能选择不同的被加密的密文，并还可得到对应的明文， 密码分析者的任务是推出密钥及其他密文对应的明文： 选择文本攻击：它是选择明文攻击和选择密文攻击的组合，即密码分析者在掌握 密码算法的前提下，不仅能够选择明文并得到对应的密文，而且还能选择密文得到对 应的明文。 以上概要介绍了五类密码攻击。目前，差分密码分析和线性密码分析是分组密码 的最有效的两种攻击算法他5 蚓。鉴于本文的研究内容与这两种攻击相关，对两种攻击 算法简要介绍如下。 差分密码分析：它是一个选择明文攻击，通过分析输入明文对的异或差分对输出 密文对的异或差分的影响来恢复某些密钥比特。假设一个攻击者拥有大量的四元组 x ，x ，y ，y ) ，其中明文二元串x 和x + 的异或值a x = x x 是固定的，明文二元串x 和 x 用同一个密钥k 加密分别得到密文y 和y + 。四元组可以是一系列差分特征构成，差分 特征概率要达到最大或几乎最大。对这些四元组中的每一个，应用所有可能的候选密 8 第2 章密码学概述及s m s 4 算法介绍 钥来对密码的最后一轮进行解密。对每一个候选密钥计算某些状态比特的值，并确定 它们的异或是否有一个确定的值( 即对给定的最可能取的输入异或值) 。每当上述叙 述成立时，就把对应于特定候选密钥的计数器加1 。在这个过程的最后，那些最高频 率的候选密钥极有可能含有真正密钥的比特取值。根据k n u d s e n 的实际安全理论，差 分密码分析攻击成功前提是存在一个或多个差分特征，且差分特征概率远大于2 咱( n 为分组长度) 。 线性密码分析：它是一种已知明文攻击。这种方法的基本原理是寻找明文、密文 和密钥间的有效线性逼近，当该逼近的线性偏差足够大时，就可以由一定量的明密文 对推测出部分密钥信息。线性分析的关键是确定有效线性方程的线性偏差和线性组合 系数。假设明文分组长度和密文分组长度为n 比特，密钥分组长度为m 比特。将明文分 组记为p ( 1 ) ，p ( 2 ) ，p ( n ) ，密文分组为c ( 1 ) ，c ( 2 ) ，c ( n ) ，密钥分组为k ( 1 ) ， k ( 2 ) ，k ( m ) 。同时，定义表达式 彳( f ，七) = 彳( f ) o 彳0 ) o oa ( k ) 那么，线性密码分析的目标就是找出具有以下形式的线性方程： 尸( f 1 ，i 2 ，屯) o c “， ，五) = k 瓴，k ：，七c ) ( 2 1 ) 其中，l 口刀，l b 丹，l c m 。该等式意味着，将明文的一些位和密文的一 些位分别进行异或运算，然后再将这两个结果异或，将得到密钥的一个比特位信息， 如果t n 2 ， 第2 章密码学概述及s m s 4 算法介绍 k 。，乞，包) = ? ；二 j ； 从而得到关于密钥若干比特位的一个线性方程。如果有一组有效线性逼近，就可 以得到一组关于密码的线性方程，从而确定出密钥。研究表明，线性密码分析的有效 性取决于两个因素：明文数n 和线性偏差ip 一1 2i 。明文数n 越大，攻击有效性越强； 线性偏差ip 一1 2i 越大，攻击越有效。根据k n u d s e n 的实际安全理论，线性密码分析攻 击成功前提是存在一个或多个线性偏差，且线性偏差概率远大于2 巾( n 为分组长度) 。 2 2 分组密码 2 2 1 分组密码原理 分组密码是现代密码学的重要体制之一，具有加密速度快、安全性好、易于标准 化等特点，广泛地应用于数据的保密传输、加密存储、构造伪随机数生成器、序列密 码、消息认证码等。分组密码是将明文消息编码表示后的二进制序列，划分成固定大 小的块，每块分别在密钥的控制下变换成等长的二进制序列。 一个分组密码算法包含五个元素 m ，c ，k ，e ，d ) ，其中m = 片称为明文空间， k = 劈称为密钥空间，c = e 称为密文空间，e 和d 分别表示加密和解密变换，定义 如下： e ：m k cd ：c k m 若x e ，k 聪，则存在】，& 伍) 和x 仇p ) ，n 为明文分组长度，k 为密 钥长度。当k e 确定时，加密和解密变换为一一映射，瓯伍) 是6 f ( 2 “) 上的置换。 2 2 2 分组密码一般设计原理 分组密码的设计应满足下述要求： 1 满足扩散和混淆原则 1 0 第2 章密码学概述及s m s 4 算法介绍 为了有效抵抗攻击者对密码体制的统计分析，s h a n n o n 提出了两个基本的设计原 则：扩散原则和混淆原则。扩散，是指使每一个比特的明文变化尽可能多地影响到输 出密文比特，以隐藏明文的统计特性。混淆是指在加密解密变换过程中，明文、密文 及密钥之间的关系尽可能地复杂，以防密码破译者采用统计分析法进行破译； 2 分组长度和密钥长度要足够大 足够长是为了防止对明文和密钥的穷举攻击。但密钥又不能过长，过长不利于密 钥的管理，而且会影响加解密速度； 3 由密钥确定的置换算法要足够复杂 复杂的置换算法是为了抵抗各种已知的攻击，如差分密码分析和线性密码分析 等，使攻击者除了用穷举法以外，无其它更好的攻击方法； 4 加密和解密算法简单，易于软件和硬件快速实现 一个复杂的算法由许多相对简单的运算构成，为了便于软件编程或逻辑电路实 现，算法中的运算应该尽量简单，如二进制加法或移位运算，参与运算的参数长度也 应该选择8 的整数倍，可以充分发挥计算机中字节运算的优势； 5 一般无数据扩展 明文和密文长度应该相同。采用同态置换和随机化加密技术时可引入数据扩展。 6 差错传播应尽可能的小 总之，一个分组密码在设计中需要在安全性和实用性之间寻求一种平衡，使得算 法在足够安全的同时，又具有尽可能短的密钥、尽可能小的存储空间以及尽可能快的 运行速度，这使得分组密码的设计工作极具挑战性。 2 2 3 分组密码整体结构 分组密码的整体结构可以分为平衡f e i s t e l 网络、非平衡f e i s t e l 网络和s p 网 络三大类。 平衡f e i s t e l 网络( 简称f e i s t e l 网络) ：将一个分组分成左右两个相等长度的 子部分，在每轮子密钥的作用下进行加密变换，再经过一定迭代轮数后得出密文。 f e i s t e 网络的最大优点是加减密相似，它的缺点是扩散速度比较慢，需要两轮才能 1 1 第2 章密码学概述及s m s 4 算法介绍 使得每一个输入比特发生变化； 非平衡f e i s t e l 网络：将一个分组分成左右两个长度不等的子部分。非平衡 f e i s t e l 网络扩散速度较快，混淆性也较好，但在理论分析和硬件实现时相对比较困 难。目前采用此结构的算法有s m s 4 等； s p 网络：由s 盒代换和p 置换交替进行多次迭代而形成的变换网络。其中s 盒 起到混淆作用，它是唯一的非线性部件，它的密码强度决定着整个密码算法的安全强 度。p 置换起扩散作用。每一轮迭代中，分组首先经过s 盒进行代换，接着通过p 置 换进行置换。为了增强安全性，分组长度一般比较大，而s 盒输入和输出长度要达到 分组那样的长度不易实现，所以实际中常将分组分成若干个部分，对每一个部分用s 盒进行代换。s p 网络结构具有雪崩效应，明文或密钥输入即使只有很小的变化，也 会导致密文输出产生巨大的变化，所以它的扩散速度快。 2 2 4 分组密码设计准则 如何更好地保证分组密码的安全强度，这是密码算法设计时必须认真考虑的问 题。在分组密码具体设计中要考虑分组长度、密钥长度、轮函数f 、迭代轮数、子密 钥的生成方法等各方面的安全指标。 1 分组长度 分组长度越长意味着安全性越高( 从穷举攻击角度来看) ，但是会影响加密和解 密速度。目前，很多分组密码是6 4 位的分组长度，但随着计算速度和分析技术的提 高，当前建议使用的分组长度是1 2 8 位。 2 密钥长度 密钥较长同样意味着安全性较高，但会影响加密和解密的速度。现在一般认为 6 4 位的密钥是不安全的，通常使用的密钥长度是1 2 8 位。 3 轮函数f 轮函数f 通常是指迭代分组密码中单轮加解密算法的实现部分，是分组密码结构 的核心。轮函数一般由s 盒和p 置换构成，依赖s 盒实现混淆，p 置换实现扩散。s 盒的安全性指标有非线性度、差分均匀性、代数次数及项数分布、完全性及雪崩准则、 12 第2 章密码学概述及s m s 4 算法介绍 可逆性、没有陷门等。p 置换的安全性指标主要是分支数。在设计中，轮函数f 要遵 循雪崩效应准则，即要求输入中一位的变化应尽量引起输出中很多位的变化。 评价轮函数设计质量的指标主要有三个。 安全性：轮函数f 的设计应保证其对应的密码算法能抵抗现有己知的所有攻击， 特别是能够抵抗差分密码分析和线性密码分析，要求能估计出最大差分特征概率和最 大线性偏差概率或它们的一个上界； 速度：轮函数和迭代轮数直接决定了算法的加密、解密处理时间。现有的密码算 法有两种设计趋势：是构造复杂的轮函数，使得轮函数本身就能抵抗现有许多已知 的攻击方法，这使得轮函数的轮数较少；二是构造简单的轮函数，轮函数本身对已知 的攻击方法不够安全，需要轮函数迭代多轮达到安全保证。现有算法较多采用后一种 思想，如s m s 4 算法； 灵活性：有助于密码算法在多平台、多种处理器上实现。例如算法在8 比特、1 6 比特、3 2 比特及6 4 比特处理器之间容易移植。 4 迭代的轮数 迭代分组密码的本质是单轮不能提供足够的安全性而多轮迭代能增强其安全性。 也就是说，迭代分组密码使用简单、安全性弱的加密算法进行多轮迭代运算，使得安 全性增强。一般而言，分组密码迭代轮数越多，密码分析就越困难，但也不是迭代轮 数越多越好，过多迭代会使输入与输出的关系复杂化，影响加密解密处理速度，而且 安全性增强也不明显，分组密码迭代轮数一般采用8 、1 0 、1 2 、1 6 、2 0 、3 2 的居多。 通常决定迭代轮数的准则是：使密码分析的难度大于简单穷举攻击的难度。 5 子密钥的生成方法 子密钥生成方法是迭代分组密码的一个重要组成部分，是实现