（通信与信息系统专业论文）数据加密算法的分析改进及应用研究.pdf

原创性声明 本人郑重声明：所呈交的学位论文是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：圣竺日期：里：! ：型 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：至竺 导师签名：乏坦西乏口期：兰兰竺：型： 山东大学硕士学位论文 摘要 数据加密是个由来己久的话题了，在当今信息时代更是如此数据加密技术 的研究也越来越受到人们的重视 目前常见的密码体制共分为两大类：对称钥和非对称钥密码体制；其中对称 钥密码又分为分组密码和序列密码d e s 作为第一个分组密码的数据加密标准， 经过了2 0 年的风雨考验，它的诞生是密码学界的里程碑。开创了密码学界的新 纪元，使得密码算法彻底摆脱了依照单表或多表进行置换加密的时代，进入了安 全性依靠密钥而不是算法本身的新时代。 然而随着计算机性能的迅速提高，目前在安全性要求很高的场合下，d e s 已不再适用，本文以此为切入点，对影响d e s 算法安全性的因素进行了分析。 在此基础上提出了d e s 算法的一种改进方案一3 m d e s ( 3m i x e d d e s ) 算法 3 m 二d e s 算法在不改变d e s 的核心f 函数的情况下，将3 个d e s 分组( 同 样可以按照相同的方法推演到n 个分组) 的数据交叉连接，构成1 9 2 b i t s 分组， 1 9 2 b i t s 密钥的新算法，经过1 6 轮迭代，使得各个分组的数据与密钥实现充分的 扩散和混淆，从而将原d e s 算法的分组长扩展到1 9 2 b i t s ，密钥长扩展到1 9 2 b i l s ( 去掉奇偶校验位实际还有1 6 8 b i t s ) 。 本文还用v c6 0 实现了3 m - d e s 与其他7 种分组密码算法并调试通过，通 过3 m d e s 与d e s 的对比分析表明：3 m d e s 算法基本保持了d e s 算法的运算 速度，但凭借加长的数据分组与密钥长度，所以其混淆和扩散的效果比d e s 算 法好很多，因此其安全性得到了很大的提高。 一 但是，由于3 m d e s 的3 组密钥是各自独立生成，与明文进行加密前没有经 过充分的混合，因此，1 9 2 b i t s 的密钥长度可能会打一些折扣。 关键词：数据加密，对称密码，非对称密码，3 m - d e s 山东大学硕士学位论文 a b s t r a c t t h ec i p h e ri sv e r yi m p o r t a n ti no u ri n f o r m a t i o ns o c i e t y , g o v e r n m e n t a ld o c m n c n t s ， m a r t i a ls e c r e t , c o m m e r c i a ls e c r e ta n d 弘i 由cs e c r e t 瞅a l ln e e d 协b ee n c r y p t e d m o r e a n dm o r ep e o p l eh a v et a k e nh i g ha t t e n t i o nt oc r y p t o l o g y t h eu s u a l l y c i p h e rn o wa r es y m m e t r i c - k e ye n c r y t i o ns c h e m e s a n dt h e a s y m m e t r i c - k e ye n c r y t i o ns c h e m e s t h e r ea r ct w op a r t so fs y m m e t r i c - k e ye n c r y t i o n s c h e m e s - b l o c kc i p h e ra n ds t r e a mc i p h e r t h i sa r t i c l ea n a l y z e ds e v e r a la r i t h m e t i c so f t h e ma n dd e s i g n e d3 m - d e sw h i c hs t r o n g e rt h a nd e sb u tm a d ef r o md e s m uc e s h a n n o n sc 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 si n1 9 4 9 c r p h t o l o g yh a sb e c o m eaf o r m a ls c i e n c e a n dt h ea p p e a r a n c eo fd e s i n1 9 7 7m a d e h i g h l ya t t e n t i o no f t h ew o r l d t h er e s e a r c ho f c i p h e r h a sg r e a t l yi m p r o v e d h o w e v e r c o n t i n u e da d v a n c e si nc o m p u t a t i o ns p e e dh a v en o wp l a c e dd e si n r a n g eo fa t t a c lf o rt h ef u t u r ew en e e das t r o n g e rc i p h e r b u ti nt h ef a c tt h ea r i t h m e t i c o fd e si t s e l fi sg r e a t , i ti sw e a k l yi ni t s6 4 b i t sb l o c ka n d6 4 b i t sk e y , i t se v i d e n t s h o r t l y b a s e do ft h i s , ii n c r e a s e dt h ej 锄g i ho fd e s sb l o c ka n dk e ya n dd e s i g n e da n e w c i p h e r3 m - d e s 3 m d e sm a i n t a i n e dt h ec o r eff u n c t i o no fd e s ，j o i n3o fd e sb l o c k s ( a ss a m e a st om o r eb l o c k s ) m a d ean 哪c i p h e rw i t h1 9 2 b i t sb l o c ka n d1 9 2 b i mk e y b y1 6 r i m so f d e s ，t h ed a t aa n dt h ek e yc a nb eo v e r a l ld i f f u s e d ia l s ou s e dv c6 0d e s i g n e dad a m - e n c r y f i o ns o f t w a r ei n c l u d i n gd e s ，3 d e s ， g o s t , a e s ，i d e a ，r c 一5 ，s a f e rk - 6 4a n d3 m d e st oa n a l y z et h e s ea r i t h m e t i c s t h e f a c ti s , t h ei n c r e a s e dl e n g t ho fb l o c ka n dk e ym a d e3 m - d e s 飞d i f f u s i o nm u c hb e t t e r t h a nd e s ，a n da l m o s tt h es a m es p e e da sd e s ，t oe n c r y p tt h es a m es i z ef i l e ，3 m - d e s h a so n l yl 珥0 1 ，s 0s l o wt h a nd e s t h ed i s a d v a n t a g eo f3 m - d e si st h eg e n e r a t eo fk e yi su n a t t a c h e d , n o to v e r a l l d i f f u s e db e f o r ee n c r y p tt h ed a t a , t h i sm a yb ed i s c o u n tt h el e n g t ho f1 9 2 b i m k e yw o r d ：d a me n c r y p f i o n , s y m m e 口i c - k e ya i c 删o ns c h e m e , s , a s y m m e t r i c - k e y e n e r y t i o ns c h e m e s ，3 m - d e s 山东大学硕士学位论文 第一章绪论 如今社会已经进入信息社会，“信息”已经渗入到人们社会生活的各个领 域，人们越来越依赖于计算机对各种数据进行储存，这些数据有的是国家机密， 有的是科研成果，商业机密，还有的或许是个人隐私，而计算机的特殊性使得这 些数据的安全性随时受到威胁；同时网络的发展又使得信息的传播和交流变得越 来越容易，而互联网的自由特性又为居心叵测的人盗窃这些资料提供了方便，因 而人们对数据加密的要求越来越强烈，密码学也正是在这样的环境下蓬勃发展起 来的，如今密码学已经成为了一门极为重要的学科，引起了世界各国政府和学者 的高度关注。 密码学的真正兴起是1 9 7 7 年d e s 1 啷的诞生，到现在仅有短短的2 8 年时间， 然而仅仅是这2 8 年的时间，密码学就有了空前的发展，到现在已有了对称钥和 非对称钥两大密码体制，同属于对称钥密码的分组密码和序列密码主要用于主流 的数据加密，二者的主要区别在于序列密码需要建立实时通信。目前仅分组密码 算法就有上百种，各种各样的算法变形更是不计其数( 例如仅d e s 就有3 d e s 、 x d e s 、r d e s 、g d e s 、s d e s 、x d e s 。等等) ，是国内外研究最多的密码体制； 而目前对于序列密码的研究也开创了全新的领域并取得了较大的进展，如目前最 优秀的基于量子力学的量子密码等。非对称密码体制的特点是密钥无需在信道中 传输，多用于数字认证中，现阶段对于数字认证体系的相关算法的研究也取得了 突破性的进展，如我校王小云教授分别在去年和今年对m d 5 和s h a - i 散列算法 的破解，对密码学的研究方向产生了巨大的影响。 本文共分五章，内容涉及了对分组密码、序列密码和公钥密码体制的几种算 法的讨论，提出了一种对d e s 的改进算法3 m d e s ；并设计了一个包括改进的 算法在内的8 种分组算法的加密软件l 讨论了不同的加密体制在不同的场合下的 不同应用，并给出了两个实际应用的例子。 本文第一章是绪论。 第二章简单介绍两种密码体制的基本概念 第三章介绍了两种密码体制下的几种算法，如对称钥密码体制下的d e s 、 a e s 删【州，i d e a 1 删、r c 5 f l l f 3 】、s a f e rk - 6 4 1 1 】等几种比较著名算法，并对这 山东大学硕士学位论文 几种算法的特点、难点以及编程实现所需要注意的问题进行了说明；非对称钥密 码体制 9 - l o l tr s a w n - 1 2 l 、e i g a m a l 1 - 3 1 、椭圆曲线【l 训1 3 1 等几种算法，并就 非对称钥密码体制在数字认证i 悱1 6 1 等网络安全技术中的应用作了描述 第四章通过对d e s 算法缺点的分析，提出了种对d e s 的改进算法 3 m - d e s ，详细介绍了其构成，并对改进算法的可逆性、强度、运算时间以及软 硬件实现性等方面进行了分析，与d e s 算法在速度上进行了比较，证实了改进 算法的实用性；最后介绍了采用v c6 0 ，在w m x ps p 2 环境下实现的包括改进 算法在内的加密软件，并对对称密码算法的特点作了总结 第五章就g s m 网络 1 7 _ 2 0 1 和数字电视的条件接收系统彩1 ，结合实际分析介 绍了数据加密算法在实际情况中的具体应用。 6 山东大学硕士学位论文 第二章常见的密码体制 2 1 对称钥密码体制 对称钥密码体制，顾名思义，就是对数据进行加解密的密钥是相同的或相似 的( 即很容易从一个推出另一个) ，几乎所有成熟的对称钥密码算法的特点都是 加密速度快，加密强度高( 一般都只能强力破解，又称穷举破解) ，软硬件实现 容易，特别适合对大数据量加密，是几乎所有数据保密工作的第一步，可以说， 在当今计算机的计算能力下，没有对称钥密码算法，就没有数据的安全和加密。 对称钥密码根据对数据加密的方法不同，又分为分组密码【1 刁】【撇5 】和序列密 码 2 6 - 2 7 1 2 1 1 分组密码 2 1 i 1 概述1 1 旬瑚 分组密码的加密思想是将明文数据分成大小相等的组，然后利用密钥对各个 明文组进行加密得到密文组，密文组与明文组大小数量都相等，即通常加密之后 的数据没有大小的扩展和压缩。 大多数基于这种密码体制的密码算法的一个很大的特点就是迭代加密，迭饯 加密就是指利用密钥生成多个密钥分组，并与明文数据进行多次运算，每一次运 算的步骤往往相同但密钥分组不同，多次运算后生成密文，充分实现了对明文的 混淆和扩散，使得明密文之间的关系非常复杂，从而使密文具有良好的抗统计分 析能力和抗差分攻击能力 分组密码中另一个重要的概念是s 盒，在很多算法中s 盒实际上是一个代换 表，将输入的数据变换成相同字符集的输出数据，s 盒的代换往往不是随意安排 的，它不仅要保证输入输出数据的对应唯一性，还要保证达到良好的扩散和混淆 的功能。以抵抗各种密码分析的攻击，s 盒往往是一个加密算法的核心，对它的 设计的好坏与否往往决定一个算法的好坏，它往往存在于每一轮迭代之中。 分组密码的安全性主要依赖于密钥，而不是加解密算法本身，在当今社会， 各种对数据解密的方法和计算机的计算能力不断提高，任何不公布加解密算法， 不经过所有人公开测试的加密体制都是不能信任其安全性的。 7 山东大学硕士学位论文 目前对于分组密码的破解分析方法大致有强力攻击、线性分析、差分分析、 统计分析等，设计成熟的分组密码算法必须要能够抵抗这几种攻击，使得攻击者 只能通过强力攻击法对算法进行攻击。 2 1 1 2 分组密码的设计要求 分组密码设计的首要要求就是一个密钥只能对应一个明文密文对，既对任意 给定的密钥k ，对任意的u ，v e g f ( 2 ) “，如果u c v ，则一定有 & ( 1 1 ) # e k ( v ) 。 其中e k 表示加密变换密钥长度不能太大，否则难以实现，也不能太小， 否则不能有效的抵抗攻击，尤其是穷举攻击。 分组密码体制中另外两个重要的概念是扩散和混淆，这是s h a n n o n 提出的设 计密码体制的两种基本方法，也是分组密码设计的一个基本要求。我们知道，在 实际应用中，每个字的出现概率都是不一样的，密码破解的统计分析方法正是针 对这一特点而设计的 所谓扩散既是让明文中的每一位都影响密文中的尽可能多的位，或者说使密 文中的每一位都受明文中尽可能多的位的影响，这样的设计在加密有着严格格式 的明文时可以很大程度上隐蔽明文的统计特性，例如，对于总是以。你好”开头， 以“此致敬礼”结尾的明文，如果密文不能实现很好的扩散，即使中间数据再变 化，“你好”和。此致敬礼”的密文也不变，这样很容易使得密码分析者掌握此 密文所对应的中文含意，从而增加了密文被破解的风险 所谓混淆就是指使密文与密钥之间的关系尽可能的复杂。使得解密者即使知 道了一部分明文密文对，也无法根据现有的密文推测出密钥，从而破译其它明文， 在实际应用中，有效的利用乘积和迭代，可以取得比较好的混淆和扩散的效果【l 】， 达到增强算法安全性的且的 2 1 2 序列密码 2 1 2 1 概述 ， 序列密码又叫做流密码，也是对称钥密码体制中的一种，它的加密和解密思 想非常简单，就是用一个随机序列( 密钥) 与明文序列进行逐比特叠加( 异或) 来产生密文，用同一个随机序列与密文序列进行叠加来恢复明文，序列密码较多 的应用在政府和军事等能做到严格实时通信的部门中，在能做到实时通信的民用 s 山东大学硕士学位论文 领域如g s m 和数字电视条件接收等中也有其应用 利用异或原理的序列密码体制加密过程非常简单，也正因为这样，所以其安 全性不像分组密码那样来自密钥与明文的混淆和明文在加密过程中的扩散，它的 安全性是完全依赖于密钥的；根据香农的。一次一密”( 即每次加密都是用不同 的密钥) 理论，我们知道在。一次一密”体系中，即便是再简单的密钥与明文的 运算，所得到的密文都是不可破译的，但除了在间谍、外交或者军事部门等极其 重大且数据量比较少的场合使用一次一密之外。在大多数情况下实现这样的密钥 是不现实的，这也是序列密码体制在政府军事部门应用较多的原因。一次一密不 仅仅是由于其实现的复杂度，还由于密钥储存的困难，因此引出了伪随机序列的 概念。 伪随机序列顾名思义就是看起来好像是随机的序列，但它是有一定周期的： 决定伪随机序列好坏的关键参数之一就是序列的周期，序列的周期越长，伪随机 性就越好，同时实现起来也就越复杂。对于守列密码来讲，其核心就是伪随机序 列的生成。 伪随机序列的生成通常是由一段较短的序列，通过计算( 通常是通过k 阶线 性反馈移位寄存器l f s r ，k 与密钥长度相等) 得出的，典型的计算框图如图2 1 所示： 输出 图2 15 阶l f s r 示意图 在该图中，序列x 幽x 3 x 2 x ，中的两位进行异或作为第一个输出，然后该两位 排至队列尾端，用新的两位异或生成第2 个输出，以此类推。 现举例说明如下： 设一个g f ( 2 ) 上的5 阶线性反馈移位寄存器如图2 1 所示，其反馈函数为 f ( x l ，x 3 ，】【4 ，x d 喊l 垂x 3 ， 初始状态为s o - ( o ，l ，0 ，0 ，1 ) 第一轮变化后，输出0 ，状态变为( 1 ，0 ，0 ，l ，o ) ，第二轮变化后，输出 l ，状态变为( o ，0 ，l ，0 ，1 ) 。同理可以得出输出序列为： 山裹大学颈士学位论文 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 0 1 0 0 所以可以得出输出序列是一个周期序列，周期为3 1 。对序列的一个周期 0 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 0 1 0 0 0 分析可知，0 、l 出现次数近似相等( 0 出现 1 5 次，l 出现1 6 次) ，符合概率随机的性质，其周期也足够大，在这个简单的例 子里是3 1 ，是原来序列的6 倍。 2 1 2 2 序列密码的设计要求 从上面对于序列密码的分析可以看出，在实际应用中，单单靠一个线性反馈 移位寄存器生成的密钥序列其强度是远远不够的，这主要是其非线性程度不够， 容易受到己知明文的攻击，在实际应用中我们通常是对一个或多个线性移位寄存 器序列进行非线性的组合，以获得安全性能良好的非线性序列。要达到这种目的， 一种方法是将线性移位寄存器的输出序列即当作密钥的伪随机序列通过一个非 线性滤波函数f ，生成非线性序列；另一种方法是将几个线性序列通过一个非线 性组合函数f 进行非线性组合，生成非线性序列。他们的运行框图盍图2 2 、2 3 所示： 伪麓辊序 回韭叶一臣巫圆 图2 2 伪随机序列通过非线性滤波函数f 2 1 3 小结 图2 3 几个线性序列通过 一个非线性组合函数f 分组密码与序列密码相比，有如下的不同； 1 、从加密方法上讲，分组密码是逐组加密，每个分组可能是6 4 b i t s 、1 2 8 b i t s 或者2 5 6 b i t s 等等，而序列密码是逐b i t 进行加密，当然，序列密码也可以看成是 分组非常大的分组密码，但它的分组是不固定的，可能是数据的总长，也可能是 用来作为密钥的伪随机序列的周期； 2 、他们的安全性来源于不同的两方面，分组密码主要依赖于加密过程的复 1 0 一一一一 山东大学硕士学位论文 杂度，而序列密码主要依赖于密钥生成过程的复杂度； 3 、序列密码对加解密的实时性有很大要求，而分组密码没有这方面的要求 相对于序列密码，分组密码因为没有实时性要求：所以应用的场合更多一些， 又因为绝大多数分组密码算法都是公开的，所以对于分组密码算法的研究和分析 是最多的，提出的具体加密算法在各种加密算法体制中也是最多的，加上很多算 法的数量庞大的变形，其算法数量甚至达到了数百种之多 由于序列密码具有内部记忆并运用了非线性变换，加之很多序列密码算法并 没有公开，故序列密码一般是难于分析的，所以目前对于序列密码的分析和研究 较之分组密码很少，相对于分组密码的上百种的算法和变形，序列密码算法只有 有限的几种，而且很多算法是保密的，最多也是只有一部分泄露了出来，并且具 体的结构各方面还在争论之中而又因为其实现需要通信双方较高的同步性( 也 正是这种对同步性的较高要求，可以有效的抵抗各种主动攻击，这也正是该密码 体制在政府军事部门应用较多的原因) ，因此在大多数民用领域，序列密码的研 究和使用相对分组密码较少在我们所熟悉的场合中。g s m 和数字电视条件接 收系统等可以实时通信的系统中都有序列密码算法的应用 除了线性移位寄存器生成序列密码算法之外，目前有很多崭新的关于序列密 码算法的技术，如混沌密码序列和量子密码，这些都是关于序列密码算法的最新 成果有些国家在这些方面已经取得了不小的进展。 2 2 非对称钥密码体制 非对称钥密码体制又称公钥密码体制，就是加密和解密密钥不同的密码体 制，它的最大的特点就是密钥无需在网络中传输：在该体制中，没有明确的加解 密密钥的概念，而称为公钥和私钥：公钥是公开的，私钥是需要保密的，仅为自 己所知的。公钥私钥都可作为加解密使用；当公钥作为加密密钥，私钥作为解密 密钥时，是正常的保密通信：当私钥作为加密密钥，公钥作为解密密钥时，是数 字认证。 与分组密码不同，非对称密码往往基于一个难解的数学问题，例如，著名的 r s a 算法基于大素数分解的难解性，而椭圆曲线密码是基于离散对数问题的难 解性这些数学难解的问题保证了攻击者很难从公开的公钥推出保密的私钥，从 而很难解出密文也正是由于这些复杂的数学问题作为核心，使得非对称密码算 山东大学硕士学位论文 法构成非常严密，可变动性少，不像分组密码算法，可变动性大，对公钥密码算 法的分析需要坚实的数学基础，因此与对称密码相比，国际上对非对称密码算法 研究相对较少，无论是算法的数量还是算法本身的改进算法都比分组密码少得 多 。 非对称密码在加解密速度上往往比对称钥密码慢很多，所以通常用在小数据 量的加密上，比如加密传送对称钥密码的密钥，进而用来数字认证和签名。 山东大学硕士学位论文 第三章典型的数据加密算法 3 1 对称密钥加密算法 3 1 1 d e s 算法 1 9 7 7 年d e s ( 数据加密标准) 的诞生使得密码学发生了革命性的变化，是密 码学界的里程碑，是第一个被作为国际标准的密码算法；在它诞生之前，密码算 法的安全性取决于对算法的保密，因此国际上有着各种各样的保密的算法但是没 有一个作为标准的算法，而且这些算法大多都是以单表多表为基础的置换型的算 法( 从d e s 的构成上还可以看出这一点的影子) ，一旦密码表被破获，算法即毫 无安全性可言，就必须更换新的算法；d e s 诞生之后，使得密码的安全性不再 依赖于密码算法本身而依赖于密钥，这不仅使得一个算法可以公开的在全世界的 范围内接受检验以验证其安全性，还使得在万一密钥泄漏的情况下仅更换密钥就 可以继续维持安全性，而无需重新设计算法：因此，d e s 作为密码算法的里程 碑，作为密码算法的经典算法是当之无愧的d e s 的加密流程如图3 1 所示： 重复1 6 次： 图3 1d e s 加密流程图 山东大学硕士学位论文 d e s 采用6 4 b i t s 分组6 4 b i t s 密钥( 除去8 个字节中每字节的最后一位奇偶校 验位只有5 6 b i t s ) ，明文经过初始置换后分成左右各3 2 b i t s ，右路数据经过核心函 数f 函数变换与左路3 2 b i t s 异或，如此经过1 6 轮变换后( 第1 6 轮数据变换方向 不同) 生成密文。 其中f 函数结构如图3 2 所示。 图3 2 d e s 中f 函数的结构 关于d e s 的补充说明： l 、d e s 采用的这种结构叫做f d s t e l 结构，这是一种对称结构，是实现加密 和解密对称关系的重要基础由此结构还衍生出很多其它算法，例如g o s t ；在 此结构中，整个流程框架是固定不变的，可以改变的只是其核心f 函数，设计者 可以灵活的设计f 函数而不必担心算法的可逆性问题 2 、还需要指出，该结构的可逆性与最后一轮迭代有着相当大的关系，最后 一轮迭代的左右数据交换方式与前1 5 轮相反，决定了这一结构的可逆性我们 还可以看出，在编程实现d e s 算法的时候，只要结构保持正确，即使f 函数出 现错误( 相当于更换一个f 函数) ，也会实现正确的加解密，因此这一点需要我 们注意，在编程实现的时候要多加揣摩、分析，避免出现这样的问题。 3 、编程实现d e s 时，s 盒的6 输入4 输出特性是编程的难点，s 盒是用到 频率最多的运算，一个8 m 的文件加密就需要用到1 m 1 6 x 8 次的s 盒运算，因 此s 盒的运算速度将极大的影响整个算法的速度。在对d e s 的编程中，位的运 算用布尔数组实现是很方便的。 4 、d e s 中的初始置换和逆初始置换对于提高算法的强度影响很小，同时去 掉这两组置换也不影响d e s 的可逆性，但需要注意的是，这两组置换必须同时 存在或消亡 直到目前除了强力破解还没有发现针对d e s 的有效破解方法，d e s 的缺点 1 4 山东大学硕士学位论文 在于它仅仅使用6 4 b i t s 密钥( 实际5 6 b i t s ) ，随着计算机计算能力的增加和互联 网协作破解的广泛采用，使得强力破解d e s 越来越容易，如表3 1 所示，我们 可以看出密钥长度和破解时间以及花费的关系； 表3 1d e s 密钥长度( b i t ) 和破解时同以及花费( 美元) 的对照 破解所i 耄钥长度 4 0 b i t s5 6 b i t s6 4b i t s 8 0 b i t s1 1 2b i t s1 2 8 b i t s i 尹逊迭 1 0 万 2 秒3 5 小时1 盔7 x l o 包1 0 “年1 0 1 9 年 1 0 0 万0 2 秒3 5 小时3 7 天7 x l o 年1 0 1 3 年 1 0 1 0 年 这个表是就1 9 9 5 年的计算能力而言的，根据摩尔定律，计算机的计算能力 每1 8 个月就会翻一番，也就是说大约每5 年计算成本就变为原来的1 1 0 ，因此 在今天计算成本实际上只有上表的1 1 0 0 ；因此可以看出目前仅强力破解就使得 d e s 难以招架，所以在很多重要的部门和地方，采用d e s 加密已经不能保证足 够的安全性了。当然在很多并不是很重要的领域，比如民用领域，采用d e s 加 密还是很安全的 为了延续d e s 的生命力，后来出现了d e s 的许多增强算法，例如两重、三 重d e s 等，其中三重d e s 应用比较多，而两重d e s 因为易受中间相遇攻击( 中 间相遇攻击使得两重d e s 对强力破解的抵抗能力仅为原d e s 的两倍) 因此应用 不多 3 1 2 a e s 算法 a e s ( 高级数据加密标准) 是2 0 0 0 年推出的一种全新的分组密码加密标准， 它在强度和速度上都高于三重d e s ，它是比利时人j o a n d a e m e n 和v m c c n t r i j m e n 提出的，并将算法命名为r i j n d a c l 。目前a e s 已经取代d e s 成为新一代数据加 密标准。a e s 加密流程如图3 3 所示： l 。 - 匡丑 互 + 园- 鲁17 x i 计算轮密钥l l 用户密钥 重复n r 次 l 用户密钥。 图3 3a e s 加密流程图 山东大学硕士掌位论文 从图中我们可以看出，a e s 与d e s 的结构完全不同，它的可逆性并不来自 于它的结构；a e s 中用到的比较多的概念是有限域里的多项式相乘，并将其推 演为可逆矩阵的乘积，因此很容易看出这种算法本身是可逆的，a e s 中的s 盒 替代和列混合都是用到这一思想；至于行移和异或运算本身就是可逆的。 a e s 的分组长度和密钥长度都是可变的，它们可以是1 2 8 、1 9 2 、2 5 6 b i t s 的 任意组合，用户可以根据实际需要进行选择；算法的分组长度、密钥长度和加密 轮数的关系如表3 2 所示 表3 2a e s 分组长( b i t ) 、轮致、密钥长( b i t ) 的组合 舞盆 1 2 81 9 2 2 5 6 1 2 81 01 21 4 1 9 21 21 21 4 2 5 61 41 41 4 有几点需要补充说明的是： l 、a e s 的s 表并非随意生成，它是对输入数据的每一字节做乘法逆之后进 行式3 1 所示的仿射变换 + ( 3 1 ) 的所有结果的列举，编程时仅需对s 表进行查询就可以替代上述计算，s 表 的存在大大简化了a e s 中s 盒的编程实现 2 、关于a e s 的列混合运算，a e s 的列混合运算其实质就是与一个常数矩阵 相乘，每一行与每一列各个项相乘之后再进行异或运算，以此类推a e s 的每一 列( 如果按1 2 8 b i t s 分组长度来算，每一列是4 项) 。与矩阵相乘后为4 项，其中 各个项之间的相乘关系其本质又是域2 8 上的多项式相乘，这一步我们可以通过 查表法来进行运算完整的计算过程如式3 2 所示 1 6 山东大学硕士学位论文 j o j 葶1 j j 2 ， j ，。 3 2 ) ( 3 3 ) 方框中的两项的计算可以查表求得，然后互相异或既得出结果中的一项，以 此类推可以求得其它三项。 3 、关于a e s 的密钥求法 对于f 函数中s ( r ( 1 【i ) ) 审c ( i l n k ) 的解释： s ( r ( k i ) ) 表示将输入的4 字节的字通过每次循环左移一个字节的办法依次 通过s 盒； c ( 1 i n k ) 中， i n k 表示小于等于i 的最大整数值，c ( x ) 为4 字节 的字，值为 r c ( x ) ，0 0 。0 0 ，o o ，其中r c ( x ) 有表可查为： 0 x 0 1 ，0 x 0 2 ，0 x 0 4 ，0 x 0 8 ，0 x 1 0 ，0 x 2 0 ，o x 4 0 ，0 x 8 0 ，0 x i b ，0 x 3 6 ，0 x 6 c ，0 x d 8 ，0 x a b ，0 x 4 d 。0 x 9 a ) 3 1 3 i d e a 算法 i d e a 是i n t e r n a t i o n a ld a t a e n c r y p f i o n a l g o r i t h m 的缩写，是1 9 9 0 年由瑞士联 邦技术学院来学嘉x j l a i 和m a s s c y 提出的，后来经过改进，强化了抗差分分 析的能力后正式命名为i d e a i d e a 采用6 4 b i t s 分组，1 2 8 b i t s 密钥；它的加密 流程如图3 4 所示，图3 4 是8 轮迭代中的最后一轮，右边的是8 轮之后的输出 轮，其中： i d e a 将输入明文数据分组分成4 组，每组1 6 b i t s ，经过一系列的模乘模加8 轮后，得到输出结果，图中虚线部分为i d e a 韵s 盒，s 表示某一分组，z 表示 某一部分密钥 补充说明： l 、与前面算法不同的是，i d e a 仅采用模乘和模加这两种简单的运算，经过 他们之间的巧妙结合，使得算法对密码分析具有很强的抵抗能力；可见好的算法 并不一定基于复杂的数学运算 1 7 跏 “ 船 t上 叭叭叭 叭 毗叭舵仇叭叮 山东大学硬士学位论文 2 、在结构方面，与d e s 的f e i s t e l 结构虽然不同，但内涵相似，在最后一轮 都有一个与前方向相反的数据变换( 对i d e a 来讲就是图3 4 中的右图) ，作为 使整个算法可逆的重要组成部分 7 4 7 “ 7 4 7 s 7 ：5 2 蠕lq 9 2根1 t r 4 图3 4d e a 加密流程图 0 是模2 1 6 + 1 乘，田是模2 1 6 加，0 是模2 加 3 、在i d e a 中的各种运算中，模2 ”+ 1 乘和模2 ”加主要是对数据进行混淆和 扩散，面异或运算则是为了实现算法的可逆。s 盒的设计是可以改变的，不影响 算法的可逆性 4 、编程实现的时候需要注意0 的乘法逆的问题虽然i d e a 算法是对1 6 b i t s 数据进行操作的，但是因为涉及到模2 ”+ 1 乘，所以如果仅用双字节数据进行编 程会出现把6 5 5 3 6 认成0 的误差，或者在模2 , 6 + 1 乘之前输入了数据0 ，这都会 造成错误。改正的方法是在需要进行2 。1 乘之前对所涉及的数据进行判断如 果是0 则改成6 5 5 3 6 。 3 1 4r c - 5 算法 r c 5 算法是r i v e s t 于1 9 9 4 年提出的一个新的替代分组密码与前面几种算 法不同之处在于它的分组长度、密钥长度、迭代轮数都是可变的，这使得使用者 可以在加密强度和速度上任意倾向于任意方。它还引入了新的密码基本变换一数 据相倚旋转算法它的含义是假设分组长度为x ，对于两组数据，其中一组数据 山东大学硕士学位论文 循环左移另一组数据的低l o g ：位它的加密流程如图3 5 所示：图中s 表示密 钥。 ： 重复r 次 ： 卤卤 田是模r 加法 图3 5r c 5 加密流程 r c 5 的安全性来自于它的复杂的s 表以及它的数据相倚旋转算法不同于 别的算法的是，r c 5 的s 表应用在密钥生成上 对于r c 5 来讲，5 轮的r c 5 的统计特性已经相当好，6 轮的r c 5 即可抗线 性攻击，8 轮之后明文的每一b i t 都会对旋转有影响，1 2 轮可以保证足够的安全 性，r c 5 的设计者建议采用1 6 轮迭代。 编程实现时需要注意对于3 2 b i t s 一组的r c 5 来讲。左移3 2 位是原数据，而 对于v c 来讲则是0 3 1 5s a f e rk - 6 4 算法 s a f e r1 ( - 6 4 是j l m a s s e y 于1 9 9 3 年提出的一种分组密码算法，算法流程如 图3 6 所示。算法采用6 4 b i t s 分组，6 4 b i t s 密钥( 该算法有k - 1 2 8 版本，是1 2 8 b i t s 密钥) 在该算法中所用到的基本算法主要有模2 5 6 加运算以及一组可逆交换对 4 5 。和l o gs 5 ；算法的解密密钥由加密密钥推导得出，使得其能实现模2 5 6 加的逆。 图3 6 中的p h t 包含的运算是： 1 9 山东大学硕士学位论文 s i = ( 2 e l + e 2 ) m o d 2 5 6 ( e l 、e 2 位输入。s 1 、s 2 位输出) s 2 = ( e l + e 2 ) m o d2 5 6 x o r 和a d d 运算均是与密钥进行的运算，a d d 是模2 5 6 加。 轮输入( 8b y t e s ) 士 + x o ra d dx o f x o rx o t a d da d dx o r 亭亭亭孛亭亭亭亭 a d dx o rx o ra d da d d x o r x o r a d d 巨五习臣五日圃圃 12345678 图3 6s a f e rk - 6 4 加密流程图 值得注意的是这一组可逆变换对在域2 0 中有相应的表可供编程查询。 3 1 6 对称密钥的运行模式与h a s h 函数 3 1 6 1 四种运行模式 讨论分组密码的运行模式，是因为在实际应用中，分组密码算法还有着一些 缺点，首先大部分的分组密码算法对于同样的明文秘密钥往往其加密的密文相 同，这一定程度上容易暴露明文的统计规律：其次大多数分组密码算法都无记忆， 即前后密文无关联，不能抵抗攻击者对密文的删除、修改、插入等攻击。 以d e s 为例，d e s 大体有四种工作模式( 当然这四种工作模式也适用于其 他的分组密码算法) ，他们分别为电码本( e c b ) 、密码反馈连接( c b c ) 、密码 反馈( c f b ) 和输出反馈( 0 f b ) 。它们的特点如表3 3 所示： 山东大学硕士学位论文 表3 3 分组密码四种模式的特点 工作模式特点用途 每个明文组独立的以同一密 单个数据加密( 如一个加密密 电码本( e e b ) 钥加密钥) 将前一组密文与当前明文组加密，认证 密码反馈链接( c b c ) 逐位异或后再进行分组、加密 每次只处理kb i t 数据，将上 一般传送数据的流加密，认证 一次的密文反馈到输入端，从 密码反馈( c f b )加密器的输出取kb i t 。与当 前的kb i t 明文逐位异或。产 生相应密文 类似于c f b ，以加密器输出 对有扰信道传送的数据流进 输出反馈( o f b ) 的kb i t 随机数字直接反馈到 行加密( 如卫星数传) 加密器的输入 在e c b 模式中实际上就是进行普通的加密，显然不能克服上述缺点 c b c 模式的运行原理是明文每一个分组经过d e s 加密前都要和上一个分组 的经过加密后的密文做异或操作，第一个分组和一个预置的初始矢量i v ( i n i t i a l v e c t o r ) 异或后再经过d e s 加密当然本身也需要使用相同的密钥经d e s 进 行加密加密过程即y i = d e s ( x loy “) 运行框图如图3 7 所示 k 图3 7 c b c 模式示意图 c f b 密码反馈模式是每一组生成的密文都要经d e s 再次加密后与下一组的 明文异或后生成下一组的密文，即：y i - - d e s ( y 。- 1 ) 毒x i 在生成第一个分组的密文 时，也需要预先定义一个初始矢量，把当作y j i 代入运算。 c f b 模式有一种变形叫做t 位c f b 模式，在这种模式中，明文分组将不再是 “位，而是t 位，t 有可能取l 或8 ，分别用于每次加密l 位或l 字节。上面介 绍的其实可以看作t 取6 4 的c f b 模式。t 位c f b 模式最大的不同在于生成的t 位密文分组如何经过d e s 加密的问题，方法也是利用一个初始“位向量， 至于存储器中，经d e s 加密后取出最左面的t 位与第一个明文分组异或，生成 2 i 山东大学硕士学位论文 的密文导入存储器最右端，存储器内容相左移t 位。再经过d e s ，再取出左边t 位，与第二组明文异或，如此往复如图3 8 示。 。 左移t 位 y g t 位) 图3 8 分组密码的c f b 模式 还有最后一种模式是o f b 模式，它和c f b 模式稍有不同，仅是在取完最左 边t 位数据后就返回6 4 位移位寄存器，并同时与明文异或。 在这四种运行模式中，e c b 和o f b 模式一个明文块或密文块的改变在加解 密的时候只会影响到相应密文明文块的改变，不会影响到其他的密文块或明文块 的改变而c b c 模式和c f b 模式中，一个密文块y l 的改变只会引起相应的明文 块】【_ 和x i + 1 的改变，不会引起其它明文块的改变，而一个明文块x i 的改变，在 加密时会引起相应的密文块y i 以及其后的所有密文块的改变由此可以看出， c b c 和c f b 模式有着良好的隐蔽明文统计特性的特点，其中c b c 模式的这一 特性还可以被用来作为数字认证过程中的h a s h ( 杂凑函数) 算法 3 1 6 2c b c 模式与i 【a s h ( 杂凑) 函数 h a s h 函数是一种将任意长度的消息通过算法压缩为某一固定长度的消息 摘要的函数，压缩算法必须能够使得消息中任意比特的变化都能引起摘要的变 化因此我们可以看出这里的消息摘要并不是传统意义上的摘要，即不是对整个 消息的有意义的总结，而是一组会随着数据中任一比特的变化而变化的数据将 消息压缩为摘要的目的是接收者可以检测出消息在传送过程中是否被篡改过 假设用户通过h a s h 函数将要发送的数据压缩为假如l 字节，并将此l 字节 也就是消息的摘要提前发送给接收者，收到回执后，再将消息全文发送给接收