（计算机软件与理论专业论文）软件加密组件的分析、设计与实现.pdf

摘要 目前网络安全理论已经应用到现代计算机保密通信的各个领域，而且技术也 | i = ：| 益成熟；基于组件技术的j 2 e e 规范也发展地相当成熟，并且基于b s 架构的 三层及多层体系结构应用系统也已经广泛地运用于企业级应用中，因此如何构建 基于j 2 e e 规范的网络安全应用将十分有社会价值和应用价值。本文所做的工作 就是与此相关的，本文的主要贡献如下： 1 设计的组件完全基于国际标准，并且具有完备功能性。 2 详细分析了公开密钥密码体制的特点，并设计出基于j 2 e e 规范的密钥发 布组件，该组件完全能够提供发布公开密钥对的功能。 3 详细分析了公开密钥密码体制的功能，并按照规范建立自己的公钥基础 设施( p k i ) 体系，设计出其核心模块组件：c a ，r a 和c r l 。 4 详细分析了数字签名算法，并利用前面设计的组件构建数字签名组件。 5 基于j a v a 语言，设计的组件具有平台无关性。 6 容易部署，可以快速构建安全应用系统。 7 基于b s 架构，具有容易维护，能够降低软件系统的成本。 8 在设计上采用严格的访问控制和安全管理，并且可以保证用户对数据访 问的合法性和不可抵赖性。 9 在传送数据的过程中，采用s s l 连接，可以保证数据传输的保密性。 1 0 设计一个简单的b s 架构的交易系统，来测试前面设计的组件。 关键词：软件加密组件，密钥，证书，c a ，j 2 e e t h ea n a l y s i s ，d e s i g na n di m p l e m e n t a t i o no fs o f t w a r e e n c r y p t i o nc o m p o n e n t m a j o r ：c o m p u t e r s o f t w a r ea n dt h e o r y n a m e ：r u a nr e n m i n g s u p e r v i s o r ：p r o f l o n gd o n g y a n g a b s t r a c t n o w a d a y s ，t h et h e o r yo fn e t w o r ks e c u r i t y i su s e di ne v e r yf i e l do fs e c u r i t y t e l e c o m m u n i c a t i o n s ，a n dt h et e c h n o l o g yi ss o p h i s t i c a t e t h ec r i t e r i o n so fj 2 e et h a t b a s e do nc o m p o n e n tt e c h n o l o g ya r ed e v e l o p e di nar a p i ds p e e d ，a n dm o r es o p h i s t i c a t e n o w t h et e c h n o l o g yo ft h r e el a y e ra n dm u l t i l a y e rt h a tb a s eo nb ss t r u c t u r ea r e w i d e l y u s e di ne n t e r p r i s ea p p l i c a t i o n s ，s oh o wi od e s i g nt h en e t w o r ks e c u r i t y c o m p o n e n tw h i c hb a s eo nj 2 e e w i l lh a v eal o to fs o c i a lv a l u ea n da p p l i c a t i o nv a l u e + t h ew o r ko ft h i sp a p e ri sr e l a t e dt ot h i s ，t h ec o n t r i b u t i o n so fm yp a p e ra r ed e s c r i b e d a sf o l l o w s ： 1 t h ec o m p o n e n t sa r ed e s i g n e db a s e do ni n t e r n a t i o n a ls t a n d a r d ，a n dh a v ef u l l f u n c t i o n st h a ta r en e e d e d 2 w ea n a l y s i st h ec h a r a c t e r i s t i c so fa s y m m e t r i cs y s t e mi nd e t a i l ，a n dd e s i g nk e y d i s t r i b u t ec o m p o n e n tb a s e do nj 2 e e ，i tc a no f f e rf u l lf u n c t i o n so fd i s t r i b u t eap a i ro f k e y so fa s y m m e t r i cs y s t e m ， 3 w ea n a l y s i st h ef u n c t i o n so fa s y m m e t r i cs y s t e mi nd e t a i l ，a n dd e s i g nm yo w np k i s y s t e ma c c o r d i n gt or e l a t e dc r i t e r i o n ，a n dd e s i g nc o r ec o m p o n e n t s ：c a ，r a a n dc r l 4 w ea n a l y s i st h ea l g o r i t h mo fd i g i t a ls i g n a t u r e ，a n du s et h ep r e - d e s i g n e dc o m p o n e n t t od e s i g nd i 硝t a ls i g n a t u r ec o m p o n e n t 5 。b a s e do nj a v a , t h ec o m p o n e n t sa r ei n d e p e n d e n to fo p e r a t i n gs 秽t e m 。 6 t h ec o m p o n e n t sa r ee a s yt od e p l o yo nt h es e r v e r , a n dt h e yc a l ld e s i g nn e t w o r k s e c u r i t ya p p l i c a t i o n sr a p i d l y 7 t h ec o m p o n e n t sa r eb a s e do nb ss t r u c t u r e ，t h e ya r ee a s yt om a i n t a i n ，a n dc a nc u t t h ec o s to fs o f t w a r es y s t e m i i i 8 w en s es t r i c ta c c e s sc o n t r o la n ds a f e t yc o n t r o l ，a n dc a na s s u r et h ev a l i d i t ya n dc a d n o td e n ya n y t h i n gw h e nu s e ra c c e s sd a t a 9 w h e nw es e n dd a t a ，w eu s es s l ，i tc a na s s u r et h es e c u r i t yo fd a t a 。 1 0 w ed e s i g nab u s i n e s ss y s t e mt h a tb a s eo nb ss t m c t u r et ot e s tt h ec o m p o n e n t s k e y w o r d s ：s o f t w a r ee n c r y p t i o nc o m p o n e n t ，k e y , c e r t i f i c a t e ，c a , j 2 e e 第1 章引言 计算机网络的诞生使现代信息技术发生了重要的变化，在当今社会经济发展 巾起着非常重要的作用，它对人类社会的发展进步做出了重要的贡献。现代计算 机网络已经成为人类生活中不可缺少的。一个重要的组成部分，并且计算机网络也 用到了国民生产中的各个领域。从某些意义上讲，计算机网络的发展水平不仅反 映了一个国家计算机科学和通信技术的水平，而且也成为衡量一个国家国力和现 代化程度的重要标志之一。不仅仅如此，随着计算机硬件及相关耗材的价格降低， 网络也普及到了普通人民的生活中，而且据目前统计上网的人数是越来越多。虽 然网络能够给我们带来方便、快捷的服务，但是它也给我们带了不必要的麻烦， 比如它使我们的个人计算机感染上病毒，或者它使我们的网上交易密码被盗，或 者它使我们希望保密的重要资料被外人截取等等。既然出现了问题我们就要采取 相关的措施去解决问题，于是伴随网络发展的网络安全理论也日益体现其重要 性。它可以帮助我们解决上述种种问题，从而解决因上网带来的不必要麻烦。 1 1 网络安全发展史 网络安全是一个非常复杂的体系，其中包括了加密、解密等等很多内容，但 是交主要豁海容怒是密弼学。密码学帮黻保涯两个逶倍者在不安全静傣遥中遴信 薅不被攻壹者发现。普遴密码学在缀零以懿就是予簿单懿擐塞遴信了f l ”，历史 上出现过的密码体制有：移位密码体制、代换密码体制、仿射密码体制、维吉尼 弧密码体制、希尔密码体制、置换密码体制和流密码体制【”。这些密码体制比较 简单，但是在保密通信的历史上曾经麓过作稍，但是到了船来随蓿计算机的出现， 计葵憝力大大挺毫之螽，这些密妈嚣涮瓣破译工雩# 裁魄较褰易了，因戴这些密码 体制目前已经被淘汰。 后来在1 9 7 3 年5 月1 5 月，美国国家标准局( n i s t ) 在联邦记录中公开征 集密码俸稍，这一举獾最终导致了数据加密檬准( 砸s ) 翻的出堍，它曾经成为 瞧爨一最广泛馒用的密鹨体毒。d e s 由i b m 公司舞发，它是对旱期被称为l u c i f e r 体制的改进。d e s 在1 9 7 5 年3 月1 7f 酋次在联邦融录中公布，在经过大量的 公 讨论之后，1 9 7 7 年2 月1 5 日d e s 被采纳作为“非密级”应用的第一个标 穗。d e s 被采瘸之螽，每5 年麓要评率一次，在最轰一次评事中( 1 9 9 9 年1 月) ， 一个d e s 的替代品a e s 也融经开始使用了。随着d e s 的诞生，一种类型的密 码体制出现了一对称密码体制，其中包括d e s ，a e s 和i d e a 等铸加密算法， 德们靛优点赣怒宠薤密帮簿密遮渡较浚。餐楚宙予它髓只侵蘑对称熬露镶，繇殴繇 果密钥丢失，后果会很严重。 之后，有些密码学家氨尝试去采用多个密钥进行保密通信，厝采在1 9 7 6 年由d i f f i e 和h e l l m a n 提出了公锶密码体制的思想 3 1 。其中主要的思想就是加整 霸鳐寮簿候采瘸瓣密钥不一弹，帮采瘸嚣令密锈，热密时经臻一个密镑麓解密鹣 时候使用另一个。然后在经过年的研究r i v e s t ，s h a m i r 舰a d l e m a n 在1 9 7 8 年 提出了蘑名的r s a 密码体制。r s a 密码体制的安全性是罄子分解大整数的困难 瞧。它戆整现代表了双密锈熬密黪法匏胃镌瞧，开翎了密码攀豹一个灏静发展方 向，我们通常把这种密码体制叫做公开密镧密码体制，因为它经常是公开一个密 钥的。公开密码体制的优点就是可以避免像对称密钥体制勇5 样在不安全的信道中 转输密镅对酶蕊殓。穗蹩它嘏番令缺点：细密和解密速发较疆，邋常魄对称热 密体制腰慢了很多，因此相关的改进公铜加密速度的算法也成了研究的热点 f ，】( 4 j f 5 j f 6 j ”。但是它可以被用在密锈分配、数字签名和数字鉴别中。如果我们把对 称密鹳体铡和公开密钥密码体涮缀合起来，将会产生爨好的保密效柴。 扶第一个公开密镯密码体制算法的产生到现在已经有很多种公开密锯密码 体制算法，并且已经威用到多种实际情况中。翳靛已经应蠲的舞法存r s a 秘e c c 等等，后者是基予离散对数的难求解性 “。 不仅仅包禽密筠体带，潮络安全还包括系统安全，它毹括入侵者与病毒和防 火遮等等。入绞雾鞋痰毒帮楚程瑗实审经磐袋至l 的耀终安垒涟题，茏荑楚瘸薅经常 嗣扰着广大上网的朋友，目前随着病毒的出现，大量杀毒软件也在不断升级。另 外，基于包过滤的防火墙技术也怒日常防止计辣机遭受外界侵扰的技术之一。这 些方良静是器嘉誊瓣终安全静磷巍热门 2 l 。 2 1 2j a v a 技术的发展 j a v a 来自于s u n 公司的一个n qg r e e n 的项目，其原先的的目的是为家用消费 电子产品，1 ：发个分布式代码系统，这样我们可以把e 。m a i l 发给电冰箱、电视 机等家用电器，对它们进行控制，和它们进行信息交流。开始，他们准备采用 c + + ，但是c + + 太复杂，安全性也差，最后他们基于c + + 开发了一种新的语言 o a k o a v a 语言的前身) ，o a k 是一种用于网络的精巧而安全的语言，s u n 公司曾依 此投标一个交互式电视项目，但结果是被s g i 打败。可怜的o a k 几乎无家可归， 恰好这时m a r k a r d r e e s e n 开发的m o s a i c 和n e t s c a p e 启发了o a k 项目组成员，他 们用j a v a 编制了h o u a v a 浏览器，得到了s u n 公司首席执行官s c o t tm c n e a l v 的 支持，触发了j a v a 进军i n t e m e t 。后来随着j a v a 的强大，逐渐发展成为三个体系： j 2 s e ( j a v a2s t a n d a r de d i t i o n ) ，j 2 e e ( j a v a2 e n t e r p r i s ee d i t i o n ) 和j 2 m e ( j a v a2 m i c r oe d i t i o n ) 。其中j 2 s e 是j a v a 基础标准平台，而j 2 m e 则是开发移动平台的 j a v a 版本，j 2 e e 是开发企业级应用的最好平台。在本文中，我就用到j 2 e e 平台。 j 2 e e 是s u n 公司提出的一种分布式企业级应用开发的技术架构。目前经过实践 检验，证明j 2 e e 技术是一种可以信赖的企业级软件开发技术，受到许多i t 业的 大厂商的支持，具有十分广阔的前景【9 】【”l 1 i i2 】【1 3 l 。 j 2 e e 是一种利用j a v a 2 平台简化企业解决方案的开发、部署和筲理相关复杂 阀题静体系结构。j 2 e e 技术静基磁筑是梭，1 1 j a v a 平台或j a v a 2 平台酌标准舨， j 2 e e 不仅巩固了标准版中的许多优点，例如“一次遮行、隧处运霉亍”的特性、 方便存取数据霹的j d b c a p i 、c o r b a 技术，以及能够在i n t e m e t 应用中保护数 攒麓安全模式等，同辩还提供了对e j b ( e n t e r p r i s ej a v a b e a n s ) 、j a v as e r v l e t s 、 j s p o a v a s e r v e r p a g e s ) 及x m l 技术蟪全露支持。其最终县躲就是成为一个黢够使 企业开发者大幅度缩短投放市场时间的体系结构。 j 2 e e 俸系结构掇供中间件层集成框架用来满足无需太多费用褥又需瑟高可 用性、麓可靠髅及霹扩震性瓣应嗣麴嚣求。通道提供阕蛉舞发乎鑫，j 2 e e 降 低了开发多层威用的赞用和复杂性，同时提供对现有腹用程序集成强有力的支 持，完全支持了e n t e r p r i s ej a v a b e a n s ，有良好酌向导支持打截和部署应用，添加 目录支持，增强了安全桃铡，提悫了性黪。 3 一= 。： ，= 皇些筮兰堡燮 虽然网络安全技术已经在实际的保密通信中起到了很大的作用，同时j 2 e e 撬范在实际褐架b s 结构的企韭级应用系统中溆运劂广泛，但蹙籍两者结合起来 设计成软件细餐维 牛鲍应用倒不是多见，阕此在这个方露做螺工作，设计如适合 企业应用的软件加密组件还是有千h 当的应用前景。 1 。3 国内外研究现状 关于密码体制和j 2 e e 规范的应用历史，在文章的背景中已经详细分析了。 以前很多安全寝用都愚翔的颁件方法，如硬件拥密狗，阂为它们具膏较高的速度， 蕊且安全性也较裹。但是它们的缺点也是有的：馀捂毖较昂贵，瑟且秘敬孛系统 结合起来不是很方便等等。随着计算机处理芯片价格的降低，并且处理速度的加 快，软彳牛加密也越来越多的被应用到实际中。虽然目前密钥发布方丽有很多硬件 方法，当然也鸯缀多较传懿方法，健是篓子j 2 e e 组件戆密钥发毒方式避没有。 至于p k i ，美国是最早致力于这方面研究的工作。1 9 9 4 年1 0 月，美国国家标准 和技术研究局( n i s t ) 成立了p k i 工作小组，进行相关技术的研究，在1 9 9 6 年制 定tp k i 援蕊。露瞳在1 9 9 5 年l o 足，爨特骥工程小缀( i e t f ) 成立了p k i x 王臻 小组，专门从事因特网的p k i 研究，设计基于x 5 0 9 证书的因特网p k i 威用。 在1 9 9 6 年由成立了简单公钥基础设施( s p k i ) 工作组，进行简化的x 5 0 9 证书系 缝的繇突。在瓣钤有一些认涯供应亵，懿r s a ，e n t r u s t 等公霉都邑经设毒幸凄 分成熟的产品，但是这些产晶通常价格十分昂贵，而且外国政府还对这些技术的 出口进行严格鞭制，使得我国引进的产品通常无法适应特定的安全应用。因此， 秀发其套我重爨主产投瓣p k i 应溪将一卜分有应 蘑j l 俊篷，曩 l 蓍毽蠢缀多公司逡彳亍这 方面的开发，但是大部分都是基于c s 结构的，或者莉少数凝于w e b 的，但是 基于j 2 e e 组件方式，将p k i 应用设计成缀件的应用目前来说是没有的。同时， 虽然数字签名懿应用凌基经窍了穰久静掰囊，毽惩墓予软俘缮件方式静数字签名 模块也不多见。 4 1 4 本文所做的工作 本文提出了软件加密组件的思想，并基于j 2 e e 体系实现了部分常用组件。 所做的主要工作如下： 1 详细分析了公开密钥密码体制的特点，并分析了r s a 算法及相关算法 的复杂性。 2 介绍了j 2 e e 的相关知识，并指出相关技术的用法。 3 设计出基于j 2 e e 规范的密钥发布组件，该组件完全能够提供发布公丌 密钥对的功能。 4 详细分析了公开密钥密码体制的功能，并按照规范建立自己的公钥基础 设施( p k i ) 体系，设计出其核心模块组件：c a ，r a 和c r l 。 5 详细分析了数字签名和鉴别理论，并利用前面设计的组件构建数字签名 组件。 6 在设计上采用严格的访问控制和安全管理，并且可以保证用户对数据访 问的合法性和不可抵赖性。 7 在传送数据的过程中，采用s s l 连接，可以保证数据传输的保密性。 8 设计一个简单的b s 架构的交易系统，来测试前面设计的组件。 1 5 本文的结构 本文分为六章，第1 露就是本章魏穿言；第2 豢为密鹃学毽论知识鳃分橱， 在这一章中分析了各种密码体制包括但单钥密码体制和公钥密码体制的各自特 点及运行时效性。第3 章分析了相关公开密钥密码体制r s a 算法，并对相关簿 法避行了跑较，戳及分耩了与与r s a 稳关的算法淡效率。在第4 章中分褥了签 别和签名和慧础知识，并指出了几种常用散列函数及签名算法，并分析了各种算 法的优缺点。在第5 章中绘出本文的核心内容，并分析了当前较热门的基于1 3 s 鞫絮静j 2 e e 俸系，疆窭了其中关键技术豹嗣法，最后说翡在奉文中我将会采爝 的相关技术，并设计出三个软件加密缎件。在第6 章给出在w e b l o g i cs e r v e r 8 0 服务器下钡i 试组件，并提供糨荚截圈。最蘑在结束谬分板了本文的优缺点，然露 指出本文符绥豹工律。 5 2 1 简介 第2 章公开密钥密码学 在密码学的发展史上，出现了两种密码体制：单钥密码体制和公钥密码体制。 在我们研究的经典密码学模型中，a l i c e 和b o b 秘密地选择密钥k ，并且给出一 条加密规则和一条解密规则d 。在这些密码体制中，d 。或者和e 。相同，或者 解密过程和加密过程相反方向进行，例如d e s 解密等同于加密，就是密钥方案 相反而已。这些密码体制就是所谓的单钥密码体制，仔细研究之后可以发现几乎 所有这些密码体制都建立在基本的祷代和置换工具的基础上。在用了数千年的本 质上可以手算完成的算法之后，常规的密码编码学随着转轮加密解密机的发展 刁出现了一个重大的进步。机电式变码旋转件使得极其复杂的密码系统被研制出 来。有了计算机后，更加复杂的系统被设计出来，其中最有名的就是l u c i f e r 在 i b m 设计的数据加密标准d e s 。但是不管是转轮机还是d e s ，却仍然依赖于替代 和置换这样的基本工具。 然而在1 9 7 6 年由d i f f i e 和h e l l m a n 提出了公钥密码体制思想f “。公， ：密码 编码学刘与以前的所鸯方法都截然不同，一方面公开密钥算法蒸于数学函数耀不 是替代和鬣换。更重要的是，公开密钥密码编码学是非对称的，它用到两个不同 的密钥，蕊对称的常娥鸯爵密则只使鲻一个密钥。使爆两个密钥对于保密通信、密 镅分配署弱纂剐等领域都有着深远的影响。 其实在d i f f i e 和t i e l l m a n 之前，公钥密码学的思想已经内j a m e se l1 i s 在 1 9 7 0 年1 月一篇为“裴秘密加密的可鲢性”的文露中提出。j a 1 e se l l i s 蹩泡子 通讯安全，、缀( c e s g ) 的成员，这个小组是英国政府通信总部( g c h q ) 的一个特剐部 门。这篇文章没有公开发表，而是在1 9 9 7 年1 2 月由g c h q 正式解密的五篇文章 中的一篇。在这五篇文豢中，还有蕊是c l i f f o r dc o c k s 在1 9 7 3 年发表的蘧为 关于罪秘密加密的渡记”的文章，菸中描述的公锶密码体制躐r s a 密码体制基 本一致。 公开寮钥算法雳一个密锈遴幸亍艇密，瑟爆另一个不嚣毽是蠢关酶密锈遴摇艇 密。公钥密钥算法有个震要的特性就是：仅仅知邋密码算法和加密密钥而要确定 7 8 解密密钥，在计算上是不【q 。能的，图2 一l 给出了公 密钥加密过稔，公开密钢加 密有两个作用：加密和鉴别。其中主熨的步骤如下： l 。嬲终中熊每令慈系统都产生一鼹建予它季霉接收夔摄文逡行趣密( 公钥) 和解密( 私钥) 的密钥。 2 每个终端把自己的公钥放到一个登记本或者文件目录来公布，另一个密 鞠鄹强莠密镪裂爨己僳蜜。 3 如果a 想给b 发送一个报文，仇就用b 的公开密钥加密报文。 4 b 收到这个报文后就用他的私有密钥解密报文。其他所有人都无法解密 掇文，因为哭套8 才知道交己鹣私锾。 a l i c e 从公开目录中获得b o b 的公开密铜 一传输 2 - 1 ( a ) 加密 a l i c e 使用自己 b o b 使用a l i c e 传输 2 - a ) 搂剃 2 , 1 公开密钥加密过程 使用公丌密钥方法，所有参与者都可以扶得各自的公开密钥，而各参与者的 私有密钥由各自本地产生，不需要被分配得到。只要一个终端控制住它的私有密 钥，它收到的内容就是安全的。 2 2 公开密钥密码系统的应用 公开密钥系统的特点是它们使用具有两个密钥的加密和解密算法，这两个密 钥一个是保留的，一个则可以公开得到。在正常情况下，人们认为当发送方发送 报文给接收方的时候，发送方用的是接收方的公开密钥，然后当接收方收到报文 之后，就用自己的私有密钥解开加密的报文，从而完成一个保密通信过程。其实， 根据应用的需要，发送方还可以使用自己的私有密钥，以完成发送方所需要的功 能。我们可以将公开密钥密码系统功能分为三类： 加密解密：发送方使用接收方的公开密钥加密报文。 数字签名：发送方使用他自己的私有密钥“签署”报文。签署功能是通 过对于报文，或者报文的一个函数的小块数据应用密码算法完成的。d s a 算法就是通过h a s h 函数处理过的报文来签署的。 密钥交换：交换双方的会话密钥。例如d i f f i e h e l i m a n 密钥交换算法 【1 5 】。 图2 - 2 中分析了公开密钥系统的主要功能( 密钥交换后面要详细讨论，这里就暂 时不讨论了) ： 1 0 卜泺点a 叫 fi r 一终点b 叫 l l 卜源点a j 2 - 2 0 ) 保密 卜飞点旷一 2 - 2 ( b ) 鉴剐 2 - 2 ( e ) 保密承l 鉴别 鼙2 2 公开密钥系统的主要功能 在罄2 2 0 t e m p 。t o q t t o t t “t e m p t e m p “s 一驴 s n 。s 渤l s - t e m p 8 0p b o b o + ， 譬。例 r 。a o 一驴o r - k r e t u r n p s ，) c o m m e n t ：r = g c d ( a ，6 ) r s a + t b r 事实上，如梁g c d ( a ，b ) 一l ，女l j s a + t b 。1 。 两边溺辩横磨，, 羹l j t bs l m o d a ，敖t * b 。r o o d a m u l t i p l i e a t i v ei n v e r s e 雾法 虽然扩袋e u c l i d e a n 算法狠好，健楚在实际中，我们焉褥嚣多静算法魁 下面的算法，因为它更霄效： 1 6 璧! 塞! 墼：耋塑堡型一， t e m p 8c 一q t ) m o d a f o 。f t _ t e m p d o r a o b 疆玩1 t h e nb 没有横日的逆 e l s e r e t u r nt 。 该算法之所以有效是因为它将算法3 中所有的计算，过程去掉了，并且在 主撩环中每一次求f 时都进 楼口运算。 2 r s a 算法的复杂度 r s a 中| ；i j 于夫部分计算都与8 有关，因此大部分婊靛于8 静二进 制表示位数。假设x 和y 是t 和，位二进制正整数，即= 【1 0 吼x j + t ， f * # o g z y j , l ，假设t f 则可以把x 耨y 静备静运算复杂度规鼹如下： 和d j 吖 j d$眸 6 。b掷=叫唯 剃 驴铲”卜 旷 一 i i 驴恒h 旷 广 卜 卜 口 r - x + y 计算的时问复杂腰为o ( k j ；一y 计算的时闽复杂度为o ( k ) x sy 计冀的时闻复祭俊为o ( 肼) l 形! 的计算删复杂度为。啡) ) g c d ( x ，y ) 计算对闻复杂度为o ( k 3 ) 现在分析模算术，假设月：i 勾- - 4 k 比特数，且og m 。，m 。g h - 1 。设c 为 一一令整数。列骞麴下缝象； ( 卅。+ 州2 ) m o d n 的计算时间复杂度为o ) 如：一掰：) m o d n 靛计算对间复杂度为o 辑 ( m 。m ：) m o d n 的计算时间复杂度为o ( k2 ) 加1 - 1 ) m o d n 的计算时间复杂度为o ( k 3 ) ，泐，) r o o d n 的计算时阕复杂度为o ( 1 0 9 c4 蠡2 ) 对于似。) m o d 咒来说，如果c 非常大，其效率将会很低。事实上前人已经提 蠢了著名滟平方一乘舞法可鞋把计算x 5r o o d n 掰嚣模乘的次数降低为最魏 2 1 次，其中z 是c 的二进制表示位数，本文的系统中也是采用这种算法，下 面给出； 将c 转化戚二进案l 格式，郎： c 一薹c f 2 i 其中c i = 0 或1 。鲥引。，则计算z x e m o d n 的算 法为， 出卜。翟 i t h e nz 一和。x ) m o d n 虽然上述彝法已经在计冀速度方面有了相当大的提高，但难还怒有很多改进的算 法，：鲑献 1 7 1 、f i 8 j 、罅9 】秘 2 0 l , m 提浅翡m o n t g o m e r y 相关致进方法帮可阻曼谈 速地计算模幂结祭；在文献【2 l 】中提出了一种快速解密r s a 的方法。 嗣前r s a 在很多磷件上也被实现，文献 2 2 1 介绍了一种蘩于m o n t g o m e r y 的快速 r s a 撵密硬件；在文蘸f 2 3 】孛，提窭了一释基于犯帚待冀撞瘩豹r s a 藤密硬件； 在文献 2 4 】和1 2 5 】中，也提嫩丁两种基手硬件的加密方法，效泉搬十努明显。盛 然硬件加密速度较快，但是硬件的价格比较贵，所以也有缺点。 3 4r s a 的安全性 r s a 的安皇性主要是基于大数的难分解性，闲此它j 丕是会面对各种攻击。 攻击r s a 鞯法的方法主疆考三释： 强行攻击：这包雷对所有私存密弱都进行尝试。 数学玫再= ：主要耩于对两个索数乘积的因子分解。 定时攻击；遮藏赣子簿密筹法戆运辛亍时润。 强行攻击与一般的强行攻击没露营么区剐，只要将密钱长度变褥足够l 乏帮可鞋 了。主要分析数学攻击和定时攻击。 ( 1 ) 数学攻击 大部分数学玻击群是关于觳子分解翘莲豹，实鼯上畜3 秘数学方式王变毒r s a 算法： 8 。将n 分解戒辫个鬻数圈子。这就可班使我们计算 ( n ) = ( p 一1 ) ( q 一1 ) ，然后 确定6 = 口一m o d e ( n ) 。 b 在不先确定p 和q 情况卜- 直接确定妒( ，! ) 。同样这样可以确定 b = 口“m o d 庐) 。 e 不确定妒( n ) 而直接确定6 。 其实大部分关于r s a 密码分析的讨论都集中在对n 进行素因子分解上。的确 对于一个具有大的素因子的大数，因子分解是一个难题，但是如果采取一定的方 法并不是那么难的，下表晚明了因子分解的进展，在文献 2 6 和 2 7 中提出了两 种有效的分解算法，它们都是基于因子分解的。注：分解因子的工作量大小是用 m i p s 年为单位来衡量的，这个单位的意思是一个每秒计算1 0 0 万指令的处理器 运行一年时间的工作量，即3 x 1 0 ”条指令。一个2 0 0 m h z 的p e n t i u m 处理器是一 个约5 0 m i p s 的机器。 表3 - 1 ：因子分解的进展 数字个数近似比特数得到的数据 m i p s 笠 算法 1 0 0 3 3 21 9 9 1 年4 月7 二次筛 1 1 03 6 5 1 9 9 2 年4 月7 5 二次筛 1 2 03 9 8 1 9 9 3 年4 月 8 3 0 二次筛 1 2 9 4 2 8 1 9 9 4 年4 月 5 0 0 0 二次筛 1 3 04 3 1 1 9 9 6 年4 月5 0 0 广义数域筛 从表3 一l 可以看出：因子分解工作量的大小直接与采用的方法有关。以前因子分 解攻击都采用二次筛算法，但是之后又提出了一种较新的算法：广义数域筛 g n f s ( g e n e r a l i z e dn u m b e rf i e l ds i e v e ) ，用这种方法可以大大提高效率：目前 又出现了一种叫做特殊数域筛的算法s n f s 的方法，它比g n f s 的效率更高。从这 里可以看出将来可能还会某种更高效的算法，因此必须合理选择r s a 密钥的长 度，一般都认为密钥长度在1 0 2 4 到2 0 4 8 比特是比较安全的。 一般情况下，为了防止栉很容易被攻破，研究者在选择p 和口给出了如下建议： 1 p 和g 长度应该只差几个数字，且p 和目应都处于1 0 ”至f j l 0 ，m 个数量级。 2 0 2 ( p 一1 ) 和( q 一1 ) 都应该包含人的索因j _ 二。 3 p 一1 和q 一1 的最大公因子应该很小。 定时攻击是一个与常规攻击方式完全棚州的攻击方式。它有点像一个窃贼通过观 察一个转动拨号盘转出一个个数字所用的时间柬猜测一个保险箱的密码数字组 合。这种攻击在一种极端情况下最容易理解，假定目标系统使用了一个取模乘法 函数，这个函数在几乎所有的情况下都很快，但是在些情况下花的时间比平均 的一个整个取模运算时间还多很多。攻击是逐位进行的，它先从最左边的比特b 。 开始，假定前j 个比特是己知的，要得整个的指数，从= 0 开始并重复这种攻 击，直到得到整个指数。 虽然定时攻击是一种严重的威胁，但是却有简单的防范措施可以采用，包括： 常数取幂时间：保证所有取幂操作在返回一个结果之前花费同样多的时 间。 随机延时：可以通过对取幂运算增加一个随机延时来迷惑定时攻击者， 这样可以得到更好的性能。但是如果防范方不增加足够的噪声，那么攻 击者仍然可以通过收集更多的测量结果而成功地补偿随机延时。 盲化：在进行取幂运算之前先用一个随机数与密文相乘。这个处理防止 了攻击者了解计算机正在处理的密文，这就防止了对于定时攻击来说关 键的逐位分析。 3 5r s a 的密钥产生 要使用r s a 密码系统，每个参与者必须产生一对密钥，包括： 选择两个素数p 和q 。 选择口或者b 并且计算另一个。 如果选择p 和口呢? 因为任何潜在的敌对方都可能知道，l - p q 的值，为了防止通 过穷举法发现p 和日，这些素数p 和q 必须足够大。目前还没有找出大素数的十 分有效的方法，由于素数很大，故不能采用通常的方法来判断，必须得采用一定 2 l 圭生垄垒些：坌圣 的技术。通常是使用相关的算法，诸如m o n t ec a r l o 算法和m i l l e rr a b i n 算法， 这些算法可以以一定的概率检测出一个素数，也就是它只能说明一个大数可能是 素数，并不一定是，但是实际中求得一个“素数”是真素数的概率还是很大的。 下面给出选取一个素数的过程： 随机选择一个奇数 随机选择一个正整数ac h 完成随机素性检验，用m o n t ec a r l o 或m i u e nr a b i n 算法，如果，z 没有通 过检验，则会转回 如果n 通过了足够次的检验，就接受n ；否则转回步骤 也许从上述过程中有人很担心在很多次都不会找到一个素数，其实数论中的一个 结果表明：在附近的素数之问的平均距离为l n ( n ) ，这样平均找一个素数就要 进行l n ( n ) 次检验，但是这里面包括了偶数，故实际的次数只有l n ( ) 2 次，这 样找一个2 ”个数量级大小的素数，那么大约只需要进行l n ( 2 2 ) 2 ：7 0 次的检 验可以了。在文献 2 8 和 2 9 中介绍了两种产生密钥的方法，如果感兴趣的读者 可以详细分析它们。一般密钥都是很大的整数，处理大整数不能用普通的情况方 法，在文献 3 0 中提供一个方法解决了大整数的存储与计算的方法。 至于选择口或b 并计算另一个，前面已经提出了可以利用扩展e u c l i d e a n 算 法解决了。 由于本论文中还用到了鉴别和签名的相关知识，因此在论文的下面章节中将 介绍一些相关的知识。 第4 章鉴别和签名 i 侧络是一个开放的环境，在网络中通信可能会遇到如下攻击： 伪装：阱假的源点身份将搬文插入喇络中，包括敌方伪造一条搬文， 帮声称它泉螽源实侮稻骰静摄文接受麓对收到鹄撮交发圈霰鹃确谈 或不接受。 内容篡改：以拯入、测除、调换或修改螅方法篡潋撮文内容。 序号篡蔽：以插入、瓣除或重羲 序等方法修改通信掇文序号。 计时篡改：延迟或回放报文。在面向连接的通信过程中，一个完整 的绘话或搬文能序列可以是在之前菜魑有效会话憋强放，或者序裂 中豹单个搬文能被延迟藏睡敖。在无涟接翁通信过程中，单个报文 能被延迟或网放。 抵赖：终点黉认收到搬文或源点否认发送过报文。 目前已经找到上述几静玻击的防范方法，一邋常采用报文攘别的方法，丽 则采用数字签名的方法。实际上，不篱是报文鉴别还是数字签名，都必须有懿种 函数来产生鉴别符。惑续起来产生鉴剐符的函数可以分为三类： 掇文加密：以熬个报文的密文作为它的撩别符。 报文鉴别码( l a c ) ：以一个报文的公共函数和用于产生一个定长值的密 镪作为鉴别符。 敬猁函数：一个将任意长发的报文映射为定长的散列德的公共函数，以 敞列值作为鉴别符，它在数字签名中用的较多。 瞎 于壹接来谈这些东珏述是眈较季虫象熬，下露提供个表寒详缨分辑翥残老# 蜜与 提供加密壤剐的加密之间的关系。 表4 一l ：报文加密中保密和鉴别的相互关系 1 常规( 单钥) 加密 爿一b ：e k m 】： 提供保密，因为是加密传输的 提供一定程度的鉴别，因为a 和b 之间的会话密钥只有a 和b 才 知道 不提供签名，发送人可以否认发送过报文，也可以抵赖 2 公开密钥加密 方式一： a b ：e x 【掰】 提供保密，因为仅b 才有k r 。解密 不罐袋鉴爱，鬻为虿悲寿缀多久魏道k u 。，其镌太可以伪造著瑕 装a 发出的报文。 方式二： 4 一b ：e m 】 同时提供加密和髂别。因为只有a 才有k r 。，所以a 对发送的报 文延法援毂；转埝中可豁徐密；毽是灵骞一个嫒煮裁蹩只要翔遭a 公钥k u 。的人都可以看到报文中的内容。 方式三： a _ b ：k 滞f 珏】 这是一种比较联想的方式，它利用k u 起剥保密作用，而职。起 到签名秘鉴囊佟瘸。毽宅也肖一个缺点藏是来霾要逡纷西次蕊密 和解密的运算，运算量较大。 蕉! 奎釜囊i 童釜堡 = = 一! 。： 通过斯的袭可以看m 如何提供合适的保密鉴别和签名的方法。由于本文巾所用 至的产生签涮符瓣函数怒h a s h 遁数( 教磺爝数) ，鹱戳下瑟将会提密有关h a s h 函数的知识，至于报文豁剐码( m a c ) 可以参考文献【2 】。 4 1 散刿黼数 散列遗数是以一个变长的报文m 作为输入，并且产生一定长的教列码 日( 村) ，称之为渚息摘簧，以它作为输出。 散列函数通常是用朱构造数据的“短指纹”，它可以保证数据的完整性，一 旦数据被修菠，豢绞就不霉正确。在这零孛情况下，无论数撵怎么襻健辕，只受数 据在传输过程中被修改或删除，“指纹”就不正确。 4 1 1 散列函数的定义 数歹l 溺数分为嚣耱炎型：豢密锈豹敬舞爵数穰不豢密钥浆数歹l 丞鼗。豢寮 钥的散列函数通常用来 乍为消息认证粥，即m a c ，它可以在不安全的信道中传 输数据：而用不带密钥的敞列函数仅仅能够产生一个摘要，它产生之后必须保存 在安全豹媳方。在下莛绘滋豢密锯静h a s h 族定义： 定义4 - 1 一个h a s h 函数族是满足下列条件的四元组o ，y ，h ) ： 1 工是所有消息的集合 2 y 是群鸯的消惠摘要或访证 3 k 是密钥空间，是所脊密钥的有限集。 4 ，对于每个k ( e 1 r ，存在一个h a s h 溅数h e h ，h k ：x y 其中掣总是有限集或无限集，y 一定是有限集。如果x 是有限集，h a s h 豳数 称为压缩函数，且吲= 州。 不带密铜的h a s h 族可以当作只肖一个密钥酌h a s h 族。 圭出叁耋堡兰丝圣 1 1 2 激列函数的用法 存实际中，敞列函数的用法有如f 几种： _ 【= j 常舰加密方法对附加散列码的报文加密，它对应图中的4 - 1 ( a ) 。鉴别的原 理也是相同的，因为只有a 和b 共享该密钥，该报文必定来自a 且未被 篡改。它不仅提供了鉴别，还可以保汪报文和散列函码在传输过程中不被 篡改。 使用常规加密方法仅对散列码进行加密，也减少了无需保密应用的处理负 担，它提供了对散列码的保密性。当报文被传到接收方时，只有接收方才 有相应的私钥，他可以解密而读取原报文的散列码，然后他将接收到的报 文通过散列函数而得到一个散列码，如果这个散列码的值与先前得到的散 列码值一样，则报文在传输过程中没有被修改，否则拒绝此报文，该情形 与4 - 1 ( b ) 所示的一样。 使用公开密钥加密方法及发方的私有密钥仅对散列码加密。它提供了签名 和数字鉴别，毕竟只有发方才知道自己的私有密钥。该情形与4 - 1 ( c ) 所示 的情况一样。 使用常规密钥对报文和使用私有加密的散列码起加密，它既可以提供保 密性和数字签名。该情形与图4 - 1 ( d ) 所示的情况对应。 仅仅使用了散列码，但不对报文加密。它假定通信各方共享一个公共的私 密值s 。a 对串接的报文m 和s 算出散列值，并将得出的散列值附加在 报文m 后。因为私有值本身并被发送，对手无法更改途中截获的报文， 也就无法产生假报文。该情形与图4 - l ( e ) 所示的情况对应。 加密中的报文和散列码的整体。它可以产生保密的功能。该情形与图中最 后一种情况对应。 网4 - 1 ( a ) | t 。= ：= ，! lr 甲黼 |7 刚囊尹 螭藤器唯科 謦舡l f b k m 蒸爹蒸 k r a 。r 黼 匿露溺，赫一 l i t 4 - 1 ( c ) k u a 较 较 k r 3 图4 一l