（通信与信息系统专业论文）基于fpga的硬件加密卡研究与设计.pdf

武汉理工大学硕士学位论文 摘要 随着i n t e m e t 的发展和网络应用的日益增多，网络安全问题逐渐成为人们不 容忽视的一个问题，因而能很好解决网络安全问题的虚拟专用网( v p n ，v i r t u a l p r i v a t en e t w o r k ) 安全网关也成为近年来的研究热点。但v p n 安全网关要应用 于市场，不得不面对的是日益发展的网络带宽和它自身相对较慢的网络数据处 理速度之间的瓶颈问题。本论文研究目的正是针对于此问题，提供一个安全、 可靠、高速的v p n 网关，以适应日益增加的网络带宽的发展要求。 在分析研究各种相关v p n 解决方案的基础上，论文提出了基于网络处理器 i x p 4 2 5 和硬件高速加密卡的嵌入式网关的解决方案。该方案将数据加密处理任 务从主处理器工作任务中分离出来，很好地解决了网络交换处理和加密处理之 间的矛盾，大大提高了网关的安全性能和处理速度。对基于p c i 总线插槽的硬 件高速加密卡的设计，不但解决了速度瓶颈问题，同时也可用于其他加密应用 处理。 论文对基于p c i 总线接口的加密卡进行了硬件设计，并重点对d e s 3 d e s 等 加密算法的硬件f p g a 实现迸行了设计和优化。在分析和研究算法原理的基础 上，结合d e s 3 d e s 加密算法的自身特征，采用多级流水线结构设计，实现了 加密数据的线速输出，大大提高了性能。结合a l t e r a 公司a p e x 2 0 k 的f p g a 产 品结构特征和v e r i l o gh d l 设计语言的优势，采用双c a s e 语句，实现了很好的资 源优化。并结合f p g a 硬件设计的自身功能，进行了毛刺处理等综合优化，使 整个加密算法的实现速度很好地满足了项目设计的要求，同时为整个硬件高速 加密卡的实现奠定了基础，也为整个高速v p n 网关的实现提供了保障。 关键词：虚拟专用网网络处理器p c i 总线数据加密标准流水线设计 丛坚堡三_ 大兰堡主堂竺笙奎 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e m e ta n dt h en e t w o r ka p p l i c a t i o n ，t h en e t w o r k s e c u r i t yp r o b l e mi sb e c o m i n g o n eo ft h ep r o b l e m st h a tp e o p l ec a n n o ti g n o r e s ot h e r e s e a r c ho fv p n ( v i r t u a lp r i v a t en e t w o r k ) s e c u r i t yg a t e w a yi sb e c o m i n gw h i t eh o t f o ri t sw e l ld o n et on e t w o r ks e c u r i t yp r o b l e m b u ti f t h ev p n s e c u r i t yg a t e w a y w a n t s t ob ea p p l i e dt om a r k e t ，i th a st of a c et h eb o t t l e n e c kb e t w e e nt h ef a s t s p e e do f n e t w o r kt r a n s p o r ta n dt h er e l a t i v es l o w e rs p e e do fn e t w o r kd a t ap r o c e s s i n g t h e p r i m eo b j e c to f t h i sp r o j e c t ，b yw h i c ht h i sp a p e ri ss u p p o r t e d ，i st op r o v i d eas e c u r e ， c r e d i b l e ，a n dh i g hs p e e dv p ng a t e w a y f o r e g o v e r n m e n t a n dt of i tf o rt h e d e v e l o p m e n t o f n e t w o r kb a n d w i d t h b a s e do nt h er e s e a r c ha n da n a l y s i so fs e v e r a lr e l a t e dv p n r e s o l v e s ，t h i sp a p e r b r i n g s f o r w a r da ne m b e d d e dg a t e w a ys o l u t i o nb a s e do nt h en e t w o r kp r o c e s s o r i x p 4 2 5a n dah a r d e n e dh j 曲s p e e de n c r y p t i o nc a r d t h i ss o l u t i o ns e p a r a t e st h ed a t a e n c r y p t i o n t a s kf r o mt h em a i nc p u i tr e s o l v e st h ec o n f l i c tw e l lb e t w e e nt h en e t w o r k s w i t c ha n d e n c r y p t i o np r o c e s s i n g ，a n dh i g h l yi m p r o v e s t h e g a t e w a ys e c u r i t y p e r f o r m a n c e a n dp r o c e s ss p e e d t h ed e s i g no f h a r d e n e dh i g hp e r f o r m a n c ee n c r y p t i o n c a r db a s e do np c il o c a lb u sb o t hr e s o l v e st h es p e e db o t t l e n e c kp r o b l e ma n di ta l s o c a nb eu s e di no t h e re n c r y p t i o n p r o c e s s i n g t h i sp a p e rd e s c r i b e st h eh a r d w a r ed e s i g no ft h ee n c r y p t i o nc a r da n di te m p h a s e s t h ef p g a d e s i g na n do p t i m i z a t i o no fd e s 3 d e sa r i t h m e t i c b a s e do nt h ea n a l y s i s a n ds t u d yo f t h e s ea r i t h m e t i cp r i n c i p l e s ，ak i n do f p i p e l i n ef l o wi sd e s i g n e dt og e tt h e l i n e ro u t p u to fe n c r y p t e dd a t a , a n dt h i sf l o wc a nh i 【曲l yo p t i m i z et h ep e r f o r m a n c e b a s e do nt h ec h a r a c t e r sa n a l y s i so ff p g a p r o d u c t sf r o m a l t e r ai n c t h ed o u b l e c a s e s t r u c t u r eo f p r o g r a ml a n g u a g ei sd e s i g n e dt oo p t i m i z et h er e s o u r c ea r e a a n df u r t h e r b a s e do nt h ea d v a n t a g eo ff p g a d e s i g n ，s o m em e a s u r e ss u c ha sb u r rp r o c e s s i n ga r e u s e dt os y n t h e s i z ea n d o p t i m i z e t h ea r i t h m e t i c a l lt h e s eh e l pt h ee n c r y p t i o ns p e e do f t h ew h o l ee n c r y p t i o na r i t h m e t i cs a t i s f y i n gt h ed e m a n do ft h ew h o l es y s t e m ，t h i sc a n e s t a b l i s ht h eb a s eo ft h ei m p l e m e n t a t i o no ft h ew h o l eh i 曲p e r f o r m a n c ee n c r y p t i o n c a r d ，a n da l s oi te n s u r e st h er e a l i z a t i o no f t h eh i g hs p e e dv p n g a t e w a y k e y w o r d s ：v p n ，n e t w o r kp r o c e s s o r , p c ib u s ，d a t ee n c r y p t i o n s t a n d a r d ， p i p e l i n ed e s i g n 武汉理工大学硕士学位论文 第1 章绪论 随着i n t e m e t 和电子商务的蓬勃发展，经济全球化的最佳途径是发展基于 i n t e m e t 的商务应用。同时随着商务活动的日益频繁，各企业开始允许其生意伙 伴、供应商也能够访问本企业的局域网，从而大大简化信息交流的途径，增加 信息交换速度。这些合作和联系是动态的，并依靠网络来维持和加强，但是 i m e m e t 是一个开放性的、基于t c p i p 技术的、不可管理的国际互联网络，因 此，基于i n t e m e t 的商务活动就面临非善意的信息威胁和安全隐患。v p n 概念的 提出正是基于这种安全问题的考虑而产生的- - v ：低成本的网络连接方式。相对 于物理专线实现的网络而言的，采用v p n 方式比租用物理专线可节约通讯成本 2 1 4 5 ，对于远程电话拨号方式，则可节约通讯成本5 0 8 0 1 1 】。 因此，对v p n 的研究成为近年来的一个研究热点，国内外学术界和企业界 对v p n 的研究都极为关注。 1 1嵌入式v p n 网关 1 1 1v p n 网关 对于v p n 的实现，根据其功能的不同可以采用不同的实现方式。v p n 按照 功能分类，主要分为以下3 大类1 2 j ： 1 远程访问v p n ( r e m o t e a c c e s s v p n ) 又可称之为v p d n ，即v i r t u a lp r i v a t ed i a ln e t w o r k ，是远程客户端到本地网 关的连接，主要用于流动人员远程办公、远程用户拨号接入到本地i s p ( i n t e m e t s e r v i c ep r o v i d e r ) 后进入本地局域网进行资源访问。其实现过程如下：用户拨号 网络服务提供商( n s p ，n e t w o r ks e r v i c ep r o v i d e r ) 的网络访问服务器m a s ， n e t w o r ka c c e s ss e r v e r ) ，发出点对点协议( p p p ，p o i n tt op o i n tp r o t o c 0 1 ) 连接请 求，n a s 收到呼叫后，在用户和n a s 之间建立p p p 链路，然后n a s 对用户进 行身份验证，确定为合法用户后才启动v p d n 功能，与公司内部网络资源连接。 2 企业内部v p n ( i n t r m a e tv p n ) 武汉理工大学硕士学位论文 在公司远程分支机构的局域网( l a n ，l o c a l a r e a n e t w o r k ) 和公司总部l a n 之间建立v p n ，通过i n t e m e t 将公司的各地分支机构和总部的l a n 连接起来， 以便公司内部进行资源共享、文件传递等。这种是网关到网关的连接，用于在 i n t e m e t 上组建世界范围内的企业网，只要考虑隧道、加密等特性。 3 扩展的企业内部v p n ( e x t r a n e t v p n ) 在供应商、商业合作伙伴的l a n 和公司的l a n 之问建立v p n 。考虑到不 同公司之间网络环境的差异性，这种v p n 产品必须能兼容不通的操作平台和协 议，同时公司的网络管理员还应该设爱特定的访问控制表( a c l ，a c c e s s c o n t r o l l i s t ) ，根据访问者的身份、网络地址等参数来确定他所相应的访问权限，开发部 分网络资源给外联网的用户。这也是一种网关到网关的连接。 从以上v p n 的功能分类可以看出，在v p n ( 特别是构建企业v p n 架构) 中网关是个非常重要的组成元素。因此，如何提供一个安全、易于实施且高性 价比的v p n 网关成了众商家的竞争热点。 同时根据v p n 网关的实现的层次，也就是所依赖于实现的协议不同，目前 市场上也出现了不同类别的v p n 产品。主要包括两种各具特点又有一定互补性 的v p n 架构：一种是二层隧道协议用于传输二层网络协议，主要应用于构建 a c c e s sv p n 和e x t r a n e tv p n ，对应的主要协议有点对点隧道协议( p p t p ，p o i n tt o p o i n tt u n n e l i n gp r o t o c 0 1 ) 、二层转发协议( l 2 f ，l a y e r2f o r w a r d i n g ) 和二层隧 道协议( l 2 t p ，l a y e r 2 t u n n e l i n g p r o t o c 0 1 ) ，其中l 2 t p 结合了前两个协议的优点， 因此具有更优越全面的特性；另一种是三层隧道协议用于传输三层网络协议， 主要应用于构建i n t r a n e t v p n 和e x t r a n e t v p n ，对应的主要协议是i e t f 的i p s e c t a 协议和最新的m p l s ( 3 l 协议，m p l sv p n 是建立在共享的i p 骨干网上的网络。 现在还出现了基于t l s ( t r a n s p o r tl a y e rs e c u r i t y ) 传输层安全和安全套接层协 议( s s l t ”，s e c u r es o c k e tl a y e r ) 的v p n 产品，主要应用于w w w 的认证和实 现w e b 安全。 总的来看，从协议的安全性考虑，其中基于i p s e e 协议的v p n 是安全强度 最大的，因此在核心网络路由模块中，基于i p s e c 的v p n 是使用得最广泛的一 种方式。正是基于这种考虑，针对网络中存在的安全间题，我们提出了一种基 于嵌入式系统的安全网关设计方案，通过在低成本的嵌入式系统平台上，实现 基于i p s e c 协议的v p n 网关。在i n t e r n e t 中通过加密和认证的方法建立一条隧道， 能够保证一个安全网络所需要的5 种安全保护，即：数据起源地验证、无连接 数据的完整性验证、数据内容的机密性、抗重播保护以及数据流机密性保证。 武汉理工大学硕士学位论文 而且采用单板的嵌入式平台设计模式使得在组网上变得十分简单和灵活，应用 中可以根据实际要求实现点对点、点到端、端到端之间的任一v p n 网络。 1 1 2 嵌入式系统设计 一般认为f “，嵌入式系统是指一类以应用为中心，软硬件可剪裁，适应于对 功能、可靠性、成本、体积有严格要求的应用系统的一类专用计算机系统。它 一般由嵌入式微处理器、外围硬件、嵌入式操作系统及相关应用程序，或者以 s o c e 7 】f s y s t e mo nc h i p ) 物理形态存在的专用计算机系统。目前，从尖端的航天 飞机国防到家用微波炉，嵌入式建算计系统广泛应用于社会的工业、交通、能 源、通信、科研、医疗卫生、国防以及日常生活( 消费电子、c e ) 等领域，并 发挥极其重要的作用m j 。 嵌入式系统的优点在于其灵活的可配置和裁剪性能，针对特定的应用提供全 面同时又不冗余的所有功能，在保证性能的稳定和功能的齐全基础上提供最低 成本的优化设计，因此在近年来得到了很好的发展。在嵌入式系统的发展历程 中，关键的参考因素是嵌入式处理器的发展和嵌入式操作系统软件平台的发展。 随着各方面的应用需求发展，嵌入式处理器体系结构经历了从c i s c 到r i s c 和c o m p a c tr i s c ：处理器的位数也从4 b i t 、8 b i t 、1 6 b i t 升到3 2 、6 4 b i t ：寻址空 间从6 4 k b 到1 6 m b 甚至更大；处理速度从0 1 m i p s 到2 0 0 0 m i p s ；常用封装从 8 个引脚发展到1 4 4 个引脚；处理器的功耗明显降低；集成度明显提高，目前嵌 入式微处理器技术的最高集成度是美国国家半导体公司退出的一款高度集成的 微处理器s c l 4 0 0 ( 属于片上系统s o c ) 。总的来说，嵌入式处理器是随着应用 要求的提高逐步向经济化( 成本) 、微型化( 封装和功耗) 和智能化( 功能和速 度) 发展。对通信行业来说，目前国外许多大处理器生产厂商( m o t o r o l a 、i n t e l 、 a m d 、日立、n e c 等) 都推出了各种高性能的嵌入式通信处理器。最具代表性 的是m o t o r o l a 的p o w e r p c 系列和i n t e l 的s t r o n g a r m 系列。 在相关课题的研究过程中，我们采用了多款p o w e r p c 系列的通信处理：占片 来作为嵌入式网关的主处理芯片，主要是从性能的优越性、系统的集成度和扩 展能力上进行衡量比较。经过分析比较，我们最后确定了在i n t e l 的网络处理器 i x p 4 2 5 的通信平台上实现网关功能，后面的章节中将会对此进行详细的分析。 作为嵌入式计算机系统设计的另一个重要因素就是嵌入式操作系统软件平 台的选择。虽然早期的嵌入式设计可以考虑不使用操作系统，而能够直接使用 武汉理工大学硕士学位论文 类似于8 位单片机，采用主控程序来负责各个任务的调度，但随着应用的发展 和用户标准的提高，要实现实时系统，必须使用到嵌入式实时操作系统( r t o s ) 。 r t o s 的功能总体上类似于主控程序，但又有区别。它将c p u 时间、中断、i o 、 定时器等资源都封装起来形成一个实时多任务内核，基本功能是进行资源管理， 包括任务管理、定时器管理、存储器管理、资源管理、事件管理、系统管理、 消息管理、队列管理、信号量管理等。只留给用户一个标准的a p i 接口( 内核 服务函数形式) 供用户调用。 目前的嵌入式操作系统有许多版本，市场上的嵌入式操作系统提供厂商超过 1 0 0 多家。其中比较出色的包括免费的嵌入式l i n u x 、p s o s 、v x w o r k s 、e c o s 、 m i c r o w a r e 等。在前期的课题项目研究中，我们根据需要，选用了w i n dr i v e r 公 司的v x w o r k s 作为我们的r t o s 平台，主要是利用v x w o r k s 的稳定而强大的网 络处理能力以及方便易用快速的开发工具。 当然，嵌入式系统设计涵盖的范围相当广泛，除了微处理器外，一些附加的 外围设备和相关的接口模块，包括各种类型的存储器，一些模拟电路、电源， 接口控制器和插件等。嵌入式系统设计的另外一个重要分支是作为辅助处理模 块出现的数字信号处理( d s p ，d i g i t a ls i g n a lp r o c e s s i n g ) 和现场可编程门阵列 ( f p g a ，f i e l dp r o 掣a n u n a b l eg a t ea r r a y s ) 应用。采用d s p 的好处就是可以大 大减少系统内c p u 的数目，提高效率，并使编程简单化。而f p g a 器件则是实 现自主产权的嵌入式设计最低成本的解决方案。 1 2v p n 加密技术 不同的v p n 方式通过不同的机制来保障网络连接和数据传输的安全：例如 m p l sv p n 采用路由隔离、地址隔离和信息隐藏等多种手段提供了抗攻击和标 记欺骗的手段；i p s e cv p n 则通过隧道协议和数据加密、认证等机制来保证网络 和用户的安全。这里我们对基于i p s e c 的v p n 网关中的加密技术稍作分析。 i p s e cv p n 中的数据加密技术贯穿整个数据传输阶段，主要体现在3 个方面： 1 认证( a u t h e n t i c a t i o n ) 认证是为了确保连接的远程设备身份的正确性，i p s e cv p n 认证使用一个共 享密钥和因特网密钥交换( i k e ，i n t e m e tk e ye x c h a n g e ) 协议来实现，这里需要 实现预共享密钥、公钥加密和数字签名机制。预共享密钥需要验证i k e 键控哈 武汉理工大学硕士学位论文 希值是否一致来实现对对方的认证；公钥加密需要用到r s a 公钥加密算法。 2 加密 加密是为了确保所传输的数据对于第三方是没有任何意义的，数据的保密性 通过采用不同的加密算法来实现。目前用于i p s e c v p n 的加密算法是d e s 、3 d e s 和具有更高加密强度的a e s 加密算法。 3 完整性 完整性检查用于确保任何对数据的修改都可以被检测出来，这可以通过对 数据进行哈希函数和校验和运算( s h a 1 或者m d 5 算法) 来完成。 由此可见，加密技术在整个i p s e cv p n 网关的实现过程中的重要性。可以说， 如果没有这些加密算法和加密技术，或者说v p n 中使用的加密算法和技术很容 易就被解密，那么所谓的v p n 网关的安全性将不复存在，v p n 安全网关也就 失去了它本身的应用意义了。因此加密技术是v p n 网关的安全基础，而加密算 法的安全强度和加密速度则是衡量v p n 网关的重要指标，实现安全、可靠、高 速的v p n 网关关键就在于实现安全、高速的加密技术和算法。 1 3课题的研究背景及主要内容 本论文是湖北省科技攻关项目“宽带v p n 的研究与开发”工作的一部分。 该课题项目的根本目的就是要提供一个安全、可靠、高速的v p n 网关，以适应 日益增加的带宽的发展。要实现基于宽带的高速v p n 网关，其中最关键的是解 决网络数据处理速度和宽带传输速度之间的瓶颈问题。为此，在本论文设计中 从2 个方面考虑： 首先。我们采用专用的嵌入式通信处理器来进行网路数据处理。采用i n t e l 网络处理器系列1 x p 4 2 5 作为主要的通信处理芯片，利用i x p 4 2 5 的专用网络数 据处理引擎和加密引擎可以大大提高数据处理速度和网络数据吞吐率。 另一方面，由于d e s 等加密算法和其他各种杂凑运算的实现会消耗大量的 c p u 计算资源，即使网络处理器有高效的加密引擎，也会消耗该资源，从而影 响整个系统的处理性能。因此，我们将网络数据处理中的加密算法实现部分分 离出来采用专用硬件模块来实现。通过f p g a 芯片来硬件实现d e s 3 d e s 等加 密算法，同时采用3 2 位、6 6 m h z 的高速p c i 总线连接方式实现在i x p 4 2 5 和p c i 加密卡间进行数据传输。 武汉理工大学硕士学位论文 基于以上2 个方面的考虑，本论文在研究分析了基于网络处理器i x p 4 2 5 的 嵌入式系统设计基础上，设计实现了一个基于p c i 总线接口的硬件加密卡，在 加密卡上利用f p g a 芯片实现优化设计的d e s 3 d e s 加密以及m d 5 算法。本论 文的主要内容和组织结构如下： 全文共6 章，第1 章是绪论，阐述了论文课题的研究背景和意义；第2 章 简要地分析并阐述了数据加密算法及其基础理论；第3 章研究介绍了基于i x p 4 2 5 网关的架构，并重点对v p n 网关实现过程中的加密过程和网络处理器软件加密 引擎进行了分析；第4 章重点研究设计了基于p c i 的加密卡硬件设计结构、各 模块的划分实现以及对i x p 4 2 5 外部总线接口的分析：第5 章介绍了加密算法在 f p g a 上的设计实现，重点论述了d e s 3 d e s 加密算法的实现和优化设计，并进 行了波形仿真和结果分析：最后在第6 章对论文工作的成果做了总结，并针对 设计中存在的问题和后续工作进行了展望。 6 武汉理工大学硕士学位论文 第2 章密码技术基础 密码技术是研究传送信息采取何种的变换以防止第三者对信息的窃取，是实 现所有安全服务的重要基础，也是网络安全的核心技术【9 1 。本章主要介绍了目前 计算机安全的一些密码算法和技术，主要包括对称密码算法，非对称密码算法 和杂凑算法等。 2 1对称加密算法 对称加密算法 l ，又称分组密码算法，使用单个密钥对数据进行加密或解密， 其特点是计算量小、加密效率高。但是由于收发双方必须使用相同的密钥，因 此在不安全的环境中，密钥的传播和分发成为最薄弱的一个环节。首先需要对 明文进行等长的分组，然后用分组密码对每组明文分别加密得到等长的密文。 分组密码的特点是加密密钥和解密密钥相同，分组密码算法的安全性完全依赖 于密钥，而不依赖于对加密和解密算法的保密。 2 1 1 数据加密标准d e s m l 2 1 1 1 基本概念 数据加密标准d e s 是1 9 7 7 年7 月1 5 日美国正式公布实施的分组密码算法。 在介绍d e s 算法之前，先说明2 个概念： 1 置换设s 是一个有限集合，妒是从s 到s 的一个映射。如果对任意d ，y s ， 当y 时，矿( ) y ( y ) ，则称为s 上的一个置换( p e r m u t a t i o n ) 。 2 扩散与混淆扩散( d i f f u s i o n ) 和混淆( c o n f u s i o n ) 是c e s h a n n o n 提出 的设计密码体制的两种基本方法，其目的是为了抵抗对手对密码体制的统计分 析。扩散就是让明文中的每一位影响密文中的许多位，或者说让密文中的每一 位受明文中的许多位影响。这样可以隐蔽明文中的统计特性。所谓混淆就是将 密文与密钥之问的统计关系尽可能变得复杂，使得对手即使获取了关于密文的 武汉理工大学硕士学位论文 一些统计特性，也无法猜测密钥。使用复杂的非线性代替变换可以达到比较好 的混淆效果。在分组密码的设计中，充分利用扩散和混淆，可以有效地抵抗对 手从密文的统计特性推测明文或密钥，他们是现代分组密码算法的设计基础。 2 1 1 2 d e s 加密过程 d e s 的加密过程如图2 2 所示，设 z 2 x t x 2 x 6 4 是待加密的6 4 位明文，其中x ， 0 ，1 ) ，l f 6 4 。d e s 首先利用置换上尸对x 进 行换位处理，然后对如图2 一l 所示的与密钥有关的圈变换进行1 6 次迭代；最后 经过逆初始置换伊“的处理得到密文： y5y i y 2 y “， 其中m o ，1 ) ，1 f 6 4 。 图2 - 1d e s 的圈变换 武汉理工大学硕士学位论文 l l - s = r t l r 1 5 2 l 1 4 x o rf ( r 1 4 k 1 5 ) 扣：【 i r t 6 = k x o r f ( r - s k 1 6 ) il l 1 6 - r 。s i逆初始置换i p “ 图2 - 2 d e s 加密算法过程 9 k 2 k 1 6 武汉理工大学硕士学位论文 初始置换口及逆初始置换伊。如表2 1 ，2 - 2 所示，显然，从两表中数据可 以看出伊。就是伊的逆。初始置换，p 用于对明文x 中的各位进行换位，目的在 于打乱明文x 中的各位的次序，经过初始置换，_ ) f 变为 x2x l x 2 x 6 42x 5 8 x 5 0 x 7 即x 中的第5 8 位变为x 中的第1 位，x 中的第5 0 位变为x 中的第2 位，依次 类推，最后将x 中的第7 位变为算中的第6 4 位。 表2 1初始置换i p 5 85 04 23 42 61 8 1 0 2 6 05 24 43 62 82 01 24 6 25 44 63 83 02 21 46 6 45 64 84 03 22 41 68 5 7 4 94 13 32 51 791 5 95 l4 33 52 71 91 13 6 15 34 53 72 92 11 35 6 35 l4 73 93 l2 31 57 表2 2 逆初始置换护一 4 08 4 81 6 5 6 2 4 6 43 2 3 9 7 4 7 1 5 5 52 36 33 l 3 8 64 61 45 42 26 2 3 0 3 7 54 51 35 32 16 12 9 3 6 44 41 25 22 06 0 2 8 3 534 3 1 15 l1 9 5 92 7 3 42 4 2 1 05 01 85 82 6 3 314 l94 91 75 72 5 设密钥k = k a k 2 丸4 ，其中t 0 ，1 ) ，l i s 6 4 ，d e s 中与密钥k 有关的 1 6 次迭代可以形式化地表示为： 武汉理工大学硕士学位论文 厶= 尺i 1 r i = l i 一| x o r f ( r i i ，k 0 i = l ，2 ， 其中l ，和r ，的长度都是3 2 位，l 。= x x ：，r 。= 矗x o x 0 ，是一个 加密函数，k 。是由密钥k 产生的一个4 8 位的子密钥。烙只，。，。进行逆初始置换 ，尸。1 的处理后就得到密文y = y a 坎 y 6 4 ，不将月6 与上。左右交换而直接对 r 1 。工。进行逆初始置换处理是为了使加密和解密可以使用同一个算法，这里 r 1 6 三1 6 表示将三1 6 排在r 1 6 的右边。 2 1 1 ，3 子密钥的产生 从密钥k 生成予密钥k 的算法如图2 3 所示。 武汉理工大学硕士学位论文 图2 3 子密钥k ；的算法结构 密钥k 中有8 位是奇偶校验位，分别位于第8 ，1 6 ，2 4 ，3 2 ，4 0 ，4 8 ，5 6 ， 6 4 位，用于检查密钥k 在产生和分配以及存储过程中可能发生的错误，选择置 换p c - 1 用于去掉密钥k 中的8 个奇偶校验位，并对其余的5 6 位打乱重新排列。 选择置换p c - 1 如表2 - 3 所示，将p c - 1 输出中的前2 8 位作为c 。，后2 8 位作为 d 。，c 。中的各位从左到右依次为密钥k 中的第5 7 ，4 9 ，4 4 ，3 6 位，d 。中 的各位从左到右依次为密钥k 中的第6 3 ，5 5 ，1 2 ，4 位，对于1 i 1 6 ， c ，= l s ，( c h ) ，d ，= l s ，( d h ) ， 其中上s ，表示对c 。和d 。进行循环左移变换，醪，嬲2 ，上s ，s 。是循环左 移1 位变换，而其余的船。是循环左移2 位变换。选择置换p c - 2 如表2 。4 所示， c 。d ，表示从左到右将d ，排在c ，的后面，c ，d 。的长度为5 6 位。子密钥世。中的 殇 ； 武汉理工大学硕士学位论文 各位从左到右依次位c ，d ，中的第1 4 ，1 7 ，2 9 ，3 2 位。 表2 - 3 选择置换p c - 1 5 74 94 l3 3 2 51 79 15 8 5 04 23 42 61 8 1 025 95 1 4 3 3 52 7 1 91 l36 05 24 43 6 6 35 54 73 93 12 31 5 76 25 44 63 83 02 2 1 466 15 34 53 72 9 2 l1 352 82 0 1 2 4 表2 4 选择置换p c 2 1 4 1 7 1 l2 41 5 32 8 1 56 2 11 0 2 31 91 2 4 2 68 1 672 72 01 32 4 15 23 13 74 75 5 3 04 05 l3 74 7 5 5 4 44 93 95 63 45 3 4 64 25 03 62 9 3 2 2 1 1 4 加密函数( r 卜l ，盔) d e s 的核心是加密函数f ( r 。，k ；) ，如图2 - 4 所示是加密函数厂的操作步骤， 它的输入是3 2 比特数据和4 8 比特的子密钥。 墓堡堡王查鲎堡主兰垡堡苎 图2 4 f ( r 。，k 。) 的计算 ( 1 ) 扩展置换( 功：将数据的右半部分r ，从3 2 位扩展为4 8 位，位选择函数 ( 即e 盒) 如表2 5 所示： 表2 - 5 扩展置换占 3 21 2 34 5 456789 8 9 1 01 l 1 21 3 1 21 31 41 51 61 7 1 61 71 81 9 2 02 l 2 02 1 2 2 2 32 42 5 2 42 52 62 72 82 9 2 8 2 9 3 0 3 13 23 3 武汉理工大学硕士学位论文 ( 2 )异或：经过扩展置换后的4 8 位输出e 俾，j 与压缩后的4 8 位密钥k 作 异或运算得到一个4 8 位的运算输出 ( 3 ) s 盒替代； 将异或得到的4 8 位输出结果分成8 个6 位的块，每一块通 过对应的一个s 盒产生一个4 位的输出，对应的s 盒见附录a 所示。s 盒的具 体置换替代过程为：某个s ，盒的6 位输入的第1 位盒第6 位形成一个2 位的 二进制数0 3 。对应表中的某一行；同时该输入的中间4 位构成一个4 位的 二进制数o 1 5 ，对应表中的某一列。例如第8 个s 盒的输入为0 0 1 0 1 1 ，前后 两位形成的二进制数为0 l ，对应的就是s 。中的第一行，中间的4 位是0 1 0 1 ， 对应的就是s 。中的第5 列( 注意行和列都是从0 开始计数) ，从附录a 的表中 可得到s 。中的第1 行第5 列的数是3 ，因此输出就是0 0 1 l ，来代替原输入 0 0 1 0 1 1 。 ( 4 ) p 盒置换：将8 个s 盒的输出连成一起生成一个3 2 位的输出，输出结 果再通过置换尸产生一个3 2 位的输出，即尸俾，k ，表2 - 6 为p 盒置换 表2 - 6p 盒置换 1 622 02 1 2 91 22 81 7 1 1 52 3 2 6 51 83 1l o 2 82 4 1 4 3 22 739 1 9 1 33 0 6 2 21 142 5 ( 5 ) 输出：至此密码函数f ( r 。，k i ) 的操作即完成，最后将p 盒置换的结果 与最初的6 4 位分组的左半部分异或，然后左右半部分交换，就可以进入下一 轮的计算。 2 1 1 5 d e s 的工作模式 d e s 的工作模式可实现为4 种工作模式；电子密码本模式( e c b ) 、密码分 组链接模式( c b c ) 、密文反馈模式( c f b ) 和输出反馈模式( o f b ) ，这四种工作模 武汉理工大学硕士学位论文 式同样适用于其他分组密码。在实际应用中，可根据应用环境的不同而选用不 同的工作模式。 l 。e c b ( e l e c t r o n i cc o d e b o o k ) 模式 电子密码本e c b 模式是直接应用密码算法的工作模式，将明文m 分成6 4 位的分组p ，对各分组用给定的密钥k 进行加密，得到密文分组c ，= d 压s 。 伊。j ，将各密文分组按顺序连接起来即得到明文的密文，如图2 - 5 所示。 e c b 模式的缺点是在给定密钥的条件下，同一明文组总是得到同样的密文 组，这样会暴露明文数据的格式盒统计特征。 图2 5e c b 模式 2 c b c ( c i p h e rb l o c kc h a i n i n g ) 模式 在密码分组链接c b c 模式下，每个明文组p ，在加密之前与前一密文组 c 。按位模2 求和( 即异或) 后，再对结果运用d e s 算法。对于第一个明文组 由于还没有反馈明文，需预置一个初始向量i v ，如图2 - 6 ( b ) 所示。 cl = d e s t ( p 、x o ri v ) c l = d e sk ( p 1x o rcl ) c 。- - - - d e s 女伊，x o rc ，一ij c b c 模式通过反馈使输出密文与以前的各明文相关，从而实现了隐蔽明文 图样的目的，但这样也会导致错误传播的发生。 3 c f b ( c i p h e r f e e d b a c k ) 模式 密码反馈c f b 模式将d e s 作为一个流密码产生器，如图所示2 - 6 ( c ) 所 示。p ，和c ，为n 位分组，移位寄存器的最右边6 4 位送到d e s 进行加密；将加 武汉理工大学硕士学位论文 密结果的最左边n 位与n 位明文分组尸作异或运算得到密文分组c ，。然后将得 到的密文分组送到移位寄存器的最右端，其他位向左移n 位，最左端n 位丢弃， 然后进行下一分组的运算，对第一个分组同样需要预置初始向量j n 算法描述 为： c 2 p 、x o rl e f t ，l d e sk i d l c 12 p2x o rl e f th d e sk ( c t ) 1 c i2 p i x o r l 西， d e sk c t j c f b 是密文反馈，因此对信道错误会比较敏感，易造成错误传播。 4 o f b ( o u t p u t f e e db a c k ) 模式 输出反馈o f b 模式也将d e s 作为密文流产生器，与c f b 不同的是它将输 出的n 为密钥直接反馈至移位寄存器，即d e s 的输入端如图2 - 6 ( d ) 所示 武汉理工大学硕士学位论文 ( a ) e c b 模式 ( b ) c b c 模式 ( c ) c f b 模式 ( d ) o f b 模式 图2 - 6d e s 的四种工作模式 2 1 1 6 d e s 的解密和安全性分析 在d e s 算法中，初始置换p 和逆初始置换p 一1 各使用一次，其目的在于将 待加密数据彻底打乱重新排列，对数据加密所起的作用不大，因为他们与密钥 无关，置换关系固定，所以一旦公开，他们对数据的加密便没什么价值。这样 武汉理工大学硕士学位论文 看来，d e s 中除了s 盒是非线性变换外，其余变换均为线性变换，因此s 盒是 d e s 加密的关键所在。 任意改变s 盒输入中的几位，其输出至少有2 位发生变化。由于在d e s 中 使用了1 6 次迭代，所以即使改变明文或密钥中的l 位，密文中就大约有3 2 位 发生变化。根据目前的研究，s 盒的设计原则一直没有完全公开，虽然很多人怀 疑s 盒设计中可能隐藏着某种陷门，使了解陷门的人能够成功地进行密码分析， 但至今还没有发现s 盒的致命缺陷。 d e s 中子密钥的产生也比较有特色，它确保密钥中的各位的使用次数基本相 等，实验表明，5 6 位密钥中的每一位使用次数大概在1 2 1 5 次之间。随着密码 分析技术和计算能力的提高，d e s 的密钥长度较短成了主要缺陷。d e s 密钥的 实际使用长度为5 6 位，密钥量仅为2 ”“l o ”，就目前的计算设备和计算能力而 言，是不能抵抗密钥的穷举搜索攻击的。因此，在d e s 基础上，出现了改进版 的算法多重d e s 和高级加密标准a e s 。 2 1 2 三重d e s ( t r i - d e s ) 为了提高d e s 的安全性能，并充分利用有关d e s 的现有软件和硬件资源， 可以使用多重d e s ，采用多个密钥利用d e s 对明文进行多次加密，这样可阻增 加密钥量，从而可以大大提高抵抗对密钥的穷举搜索攻击的能力。三重d e s 即 3 d e s 是目前被广泛采用的多重d e s 算法，它还可以抵抗中途相遇攻击。 首先分析d e s 的解密过程：d e s 的解密过程和加密过程使用同一算法，只 不过在1 6 次迭代中使用子密钥的次序和加密过程正好相反。解密时第1 次迭代 使用子密钥k 。第2 次迭代使用子密钥k 1 5 依次类推，第1 6 次迭代使 用子密钥k ，解密时的1 6 次迭代可以形式化地表示为 r i | = l l j 。l = r lx o r f ( l i jk a 如果用d e s 。表示当密钥为k 时利用d e s 对明文x 进行加密得到的密文，用 d 瓯1 ( 力表示当密钥