（计算机软件与理论专业论文）一个基于矢量空间秘密共享的会议密钥分配方案研究.pdf

叫j i f 师范大学硕士学位论文 一个基于矢量空间秘密共享的会议密钥分配 方案研究 计算机软件与理论专业 研究生王秀丽指导教师袁丁 网络会议是现代社会高效交流通信的一种常用手段。对会议信息加密 是为了确保网络会议安全而采取的必要措施。在迅速发展的i n t e r n e t 世 界，电子会议系统已成为一个研究的重要课题，其核心问题就是会议密钥 的分配即通过执行一系列使用密码技术的协议步骤使会议成员获得 进行会议所需的共享的n 解密密钥。 本论文就密钥分配协议设计涉及的密码技术作了介绍，重点讨论了加 密算法、数字签名及单向散列函数的应用及在模拟系统实现中对这些技术 的选择。在阐述本论文协议之前，首先说明了三种不同密码体制下的会议 密钥分配，着重对对称密码体制和公开密钥密码体制下的密钥分配进行了 探讨。在对现存的各种集中式密钥分配协议进行总结基础上，重点研究了 k d c 模式下的密钥分配协议设计，总结了协议设计中的一些技巧。在分 析一个基于可信赖服务器会议密钥分配协议的设计后，对其协议安全性问 题提出了一些改进，并在继续其服务器集中认证思想上，借鉴一个矢量空 间秘密共享方案构建了一个k d c 模式下的会议密钥分配协议，最终探索 实现了本论文协议的模拟密钥分配系统。系统引入的矢量空间线性运算计 算简单，同时对经典密码技术的合理应用保证了系统安全性，具有一定的 理论研究和使用价值。 关键字：密码技术，会议密钥分配，矢量空间秘密共享，时间戳 单向散列函数 叫删i 币范人学颂l ：学位论文 ac o n f e r e n c ek e yd i s t r i b u t i o ns c h e m eb a s e do n v e c t o rs p a c e s h a r i n g m a j o r ：c o m p u t e r s o f t w a r ea n d t h e o r y g r a d u a t es t u d e n t ：w a n gx i u l i s u p e r v i s o r ：y u a nd i n g i n t e r n e tc o n f e r e n c eb e c o m eah i 吐e f f i c i e n c yi n t e r c o m m u n i c a t i o nm e a n s i nc o m m o nu s ea t p r e s e n t i t h a sb e c o m ea n e c e s s a r ys t e pe n c r y p t i n g c o n f e r e n c ei n f o r m a t i o nt o p r o v i d e as e c u r ei n t e m e t m e e t i n g e l e c t r c l n i c c o n f e r e n c es y s t e mw i t ht h ec o r ed i s t r i b u t i n gc o n f e r e n c ek e yh a db e c o m ea n i m p o r t a n ts u b j e c ti de x p l o s i v eg r o w t hi m e m e te n v i r o n m e n t s h o wt oa s s i g n e n c r y p t o rd e c r y p tk e y ，n a m e l yc o n f e r e n c ek e y , w h i c hs h a r e d b ym e e t i n g a t t e n d e e sh e c o m eah o ti n v e s t i g a t i o n t h et e c h n i co fc r y p t o g r a mw h i c he o n s e r e dw i t ht h e d e s i g no fk e y d i s t r i b u t i o n p r o t o c o l i sd i s c u s s e di nt h i s p a p e r a n dt h ee m p h a s e so f 廿l i s d i s c u s t i o ni sa b o u tt h e e n c r y p ta l g o r i t h m ，d i g i t a ls i g n a t u r e ，o n e w a yh a s h f u n c t i o na n dt h ec h o o s i n go ft h e s ea l g o r i t h m s b e f o r et h ed e t a i l e de x p a t i a t eo n o u rp r o t o c 0 1 t h r e ek i n d so fc o n f e r e n c ek e yd i s t r i b u t i o ni sp r e s e n t e d t h ed e s i g n o f k e y d i s t r i b u t i o np r o t o c o lu n d e rs y m m e 订i ca n d p u b l i ck e ya l g o r i t h me n c r y p t s y s t e ma r ep r i m a r y l yp r o b e di n t o s o m ec l a s s i cp r o t o c o l s e s p e c i a l l yp r o t o c o l s w i mk d cm o d e l a r ed i s c u s s e d a n ds e v e r a ls k i l l sa r es u m m a t i z e dt oa p p l yi n o u rp r o t o c o ld e s i g n t h es c h e m ei nt h i sp a p e ri sj u s tc o n c e i v e db a s eo nt h e a n a l y s i so f at r u s t e ds e r v e rc o n f e r e n c ek e yd i s t r i b u t i o n p r o t o c 0 1 a f t e rs o m e a m e n d m e n tt ot h i ss c h e m e av e c t o rs p a c es h a r e i n gs c h e m ei sf e c t h e di nt o c o n s t r u c to u rp r o t o c 0 1 t h es i m u l a t i v es y s t e mo fo u rp r o t o c o li sa c c o m p l i s h e d w i t hc e n t r a l i z e da u t h e n t i c a t i o nc h a r a c t e r i s t i c w i t ht h i ss c h e m e t h es e c u r i t yo f c o n f e r e n c ec o m m u n i c a t i o n sw i t h i nt h ec o m p m c rn e t w o r ki sr e l i a b l yp r o v i d e d t h i ss c h e m eh a sag o o de 搦c i e n c yi nd i s t r i b u t i o no f c o n f e r e n c ek e yw i t hl i n e a r c a l c u l a t i o n a n dc a na c h i e v ed y n a m i cc o n f e r e n c ek e yu p d a t i n g t h e r e f o r ei ti s o f t h e o r yv a l u ea n dw o r t hb e i n gu s e d k e yw o r d s ：c r y p t o g r a p h y , c o n f e r e n c ek e yd i s t r i b u t i o n ，v e c t o rs p a c e s h a r i n g ，t i m e s t a m p ，o n e w a yf u n c t i o n 四川师范大学硕士学位论文 第一章综述 1 1 研究目的与意义 随着计算机技术的飞速发展，各种通信技术的进步，借助计算机、通 信、万维网等科学技术，信息的流通与交换变得更加便利快捷，现实世界的 会议以电子会议方式得以实现。尤其随着i n t e m e t 网的迅猛发展，信息的流 通与交换日益便捷，因特网实现的网络会议成了高效交流通信的一种常用方 式。其发展之迅猛、应用之广泛超乎人们的想象。网络上为我们熟知的 n e t m e e t i n g 以及各类可视电话产品都是成功的例子。 但是，网络特有的开放性使得在网络上流通的信息很容易被拦截，这给 信息的安全性带来很大威胁。随着科技的发展和人们生活水平的提高，人们 对技术性和安全性等的需求不断增强，它们希望一些被传输的敏感信息能被 保密。另外，随着无线局域网迅速成为主流技术，许多机构也均希望将无线 局域网和局域网紧密结合起来，无线局域网的安全性同样是人们关注的焦 点。人们甚至误认为无线传输方式面临更大的安全威胁：有线网架设在物理 设施内，潜在的数据窃贼也必须通过有线连接至电缆设备，同时面对其他安 全手段的防范：而无线网通过无线电波在空中传输数据，在数据发射机覆盖 区域内，几乎任何人都能接触到这些数据，无论接触者是在另外一个房间或 更远的位置，且将无线局域网发射的数据仅传送给一名目标接收者也不现实 的，防火墙对通过无线电波进行的网络通讯起不了作用，任何人在视距范围 之内都可以截获和插入数据。 事实上，任何网络，无论无线网络还是有线网络，都易受到大量安全风 险和安全问题的困扰，虽然有线网与无线网都有其普遍的一些安全手段，如 有线网的防火墙，无线网的内置安全监测、起源于军事的无线扩频通信防窃 听技术等。实际上无线局域网采取完善网络隔离并设胃严密的用户口令及认 证措施，其安全性或许更强。信息安全性的实现，除了采取法律、行政和管 理等措施外，最重要的是采取技术保密措施，即密码技术。对数据通信网络 内传输的数据附加第三方数据加密方案，使数据即使被盗，也难以被理解其 中的内容才是更高级别的安全。“加密”是有效提高网络传输数据的秘密性的 必备一环，也是最好的方法，对于窃取或篡改数据等非法破坏活动来说，加 凹川师范大学硕士学位论文 密更是一种有效的保护措施f 1 2 】吼一般来说，信息的安全性主要是保障三 个方面的内容：保密性、真实性、完整性，保障信息免于被泄露、防止未授 权的窃取、篡改或损坏。所谓保密性是指秘密信息不被非法的第三者获取； 真实性是指能确认信息的真实来源，防止重播攻击和抵赖；而完整性是指信 息在传递过程中不被修改、替换、嵌入、删除，保证信息的精确性。 所以进行安全网络会议，加密是必须要采取的措施。以往的一些传统的 网络会议工具保证不了对安全性方面的需求。随着加密意识的增强和加密技 术的发展，现今的网络会议市场上也涌现出许多功能强大、保证安全性的网 络会议工具，如微软推出的o f f i c el i v em e e t i n g ，中国威速公司推出的v 2 c o n f e r e n c e5 等。 为了达到网络通信的安全性要求，要确保会议成员都能获得一个共享的 会议密钥以加密通信内容，也就是要研究如何达到安全地分配与会者之间共 享的加解密密钥。因此对会议密钥分配协议的研究有着很重要的意义，现 在已经成为一研究的热点。我们研究的重点就是制定安全合理的会议密钥分 配协议为开放网络上进行的多人通信提供安全保障。 网络会议的安全保证机制可以从多方面进行保证：应用层安全机制、网 络层安全机制和用户实际应用的安全措施等。从软件设计实现上，实现网络 会议涉及的安全技术还有很多：身份认证、信息加解密、密钥的产生与分配 等。会议密钥分配系统应主要研究并满足如下条件： 1 、用户的合法性验证。安全的会议要保证只有合法用户才能获得会议 密钥，非法的用户不能得到会议密钥也就不能介入会议。2 、前向安全性。 恶意的攻击者若截获曾使用过的会议密钥，计算不出现在会议通信使用的密 钥。3 、信息完整性。即能鉴别信息是否被篡改过，这也是一切加密系统都 要保证的。4 、与会者或在会议中间发生的行为是一个确认的行为，是不能 否认的。5 、参与会议用户产生变动，或会议进行时间较长超过一定安全期 时要更新会议通信密钥。 通过执行合理的会议密钥分配协议，会议成员可获得共享密钥以用于保 密通信，而不用担心会议内容泄露，这就是我们的目的。 四川师范人学硕士学位论文 1 2 国内外研究现状及发展情况 近几年来，网络会议在现今的科技化时代有着广泛应用和强劲的发展， 它和即时通信如风暴般席卷着整个多媒体会议市场，美国9 1 1 事件促成了 美国的网络会议市场热力高涨，而中国“非典”，则让中国企业更加认识到了 网络会议的价值，在北美，这种情况尤为明显。此类模式能提高工作效率， 降低工作成本，并且操作简单，投资回报率也相当明显。基于网络会议的应 用技术迅速崛起，网络会议发展势头良好，不但能够提高企业的生产效率， 还能增强企业的综合竞争实力，最终增加企业收入。网络会议在生活中主要 的应用更表现在视频会议上，传统视频会议己在电信行业存在了3 0 多年， 2 0 世纪9 0 年代以后随着网络会议标准协议的制定和宽带网络的普及开始壮 大。基于使用网络的情况不同，目前我国市场主要有三种类型的网络会议提 供商： 其一是以p o l y c o m 、v c o n 、v t e l 、中兴通讯、华为视点通等厂商为代 表的基于“私网”的视频会议设备提供商。此类厂商主要提供视频会议终端 产品，以及视频会议的解决方案。要建成这一系统必须要架设专线，采购专 门的终端和m c u 等。这种系统的好处是一次性投资，传输质量稳定。但由 于固定投资比较大，对于般企业来说难以承担。国家计委曾投资1 9 亿元 在全国布设了4 0 多个点。由于会议系统都是定点安装，所以人员外出等情 况下难以“移动”。 其二是以w e b e x 、p l a c e w a r e 公司为代表的基于“公网”的网络会议提 供商。与前者不同的是该类型的网络会议是通过互联网进行传输，而不需要 进行专网架设。使用此种网络会议的用户只要有可以上网的电脑，下载并安 装其插件，就可以参加会议。提供此类服务的公司一般都研发专门的软件， 并通过和基础电信运营商合作进行运营。这实际上是一种a s p ( a p p l i c a t i o n s e r v i c ep r o v i d e r ) 模式，即应用服务供应商模式，这种公司主要通过在互联 网络上配置、租赁和管理商业应用服务解决方案，为企业和个人用户提供应 用系统服务，其实质是集中式的资源共享。这种方式最大的好处就是企业不 需要进行硬件投入就可以获得信息服务，不受时间地点的限制，只要有互联 网随时可以实现会议，而且是按照应用服务的使用量收取使用费，被称为“自 四川师范大学硕士学位论文 来水式技术( t e c h n o l o g y o n t a p ) ”。据了解，a s p 模式的网络会议增长速度 十分快，在国外逐渐成为主流。w e b e x 作为全球最大的网络会议服务提供 商，每天要负责3 0 一5 0 万次会议的召开。由于a s p 模式的网络会议是通过 互联网，所以网络会议的安全性理所当然地成为人们考虑的因素：关于共享 信息的安全；关于信息传输的安全；参加会议的安全：兼容各种防火墙等安 全措施。我们要研究的就是在此类环境中实现保密会议的会议密钥分配。 其三，国内的电信、联通、网通和铁通等运营商，国外的v e r i z o n 、m c i 以及a t & t 等电信公司开通的网络会议服务业务，在其构建的自己的i p 视 频会议业务网上提供服务。目前国内的电信运营商主要是利用自己的电信资 源，与上述两类厂商进行合作。国外厂商则因进入中国受到限制在中国采用 一种提供技术合作的形式。 网络会议安全性的研究广泛的涉及许多技术方法和理论探讨。现存的各 种网络会议大都对信息采用了5 6 位或1 6 8 位的密码加密，并采取身份认证、 防火墙类硬件安全等措施。但就其涉及的具体的密钥分配方式，由于各繁多 种类产品的产权性及市场商业性等因素，我们不得而知。 从查阅文献情况来看，有许多会议密钥分配方案( c o n f e r e n c ek e y d i s t r i b u t i o n s y s t e m ，c k d s ) 被提出。d i f f i e h e l l m a n 的公开密钥分发系统 ( p u b l i c k e yd i s t r i b u t i o ns y s t e m ，p k d s ) 较早讨论了两个人通讯情况下的协商 式密钥交换【7 j 。i n g e m a r s o n 等人於1 9 8 2 年首先提出会议密钥分配的观念， 让一群参与者建立一把共同的会议密钥，参与者利用此共同的密钥便可以在 网络上召开安全的电子会议【8 。之后许多会议密钥分配协议被提出。c h e n 和h w a n g 提出了具有使用者辨认能力的会议密钥分配系统 9 】，该系统利用 l a n g r a n g e 插值公式，以广播的方式来分配会议密钥，由会议主席的身份识 别符计算会议密钥，主席的身份可以被会议用户鉴别，会议密钥的交换过程 中进行多项指数运算的乘积运算，计算较复杂，要求各个成员具有相当强的 计算能力。这实际上可算是一种秘密共享方式的会议密钥分配方式，秘密共 享在会议密钥分配中有广泛的应用，b e r k o v i t ss 和l a i hcs 等提出基于 s h a m i r 秘密共享方案】：h a m 结合数字签名标准d s a 和s h a m i r 的门限 方案提出了一种可以共享多个秘密的方案f 1 2 1 该方案经过改动可以用于广 播多个会议密钥，但是这种方案仍然基于多项指数运算的乘积运算。文i t 3 】 四川师范大学硕士学位论文 1 4 分别提出了基于平方剩余定理的方案和一种新型的基于孙子定理的 c k d s ，计算相对简单，主要适用于成员固定的会议系统。可信第三方思想 的引入在密钥分配设计上也是很大的突破 1 5 - 2 5 。文 2 5 】的第三方可信赖服务 器密钥分配协议使用中央式的认证服务器来为网络的用户或服务器提供专 职的认证服务，协议设计简捷。运算简单。这些各有特色的方案，各有优劣， 在追求效率和缜密的设计中不断的发展完善。各种密钥分配协议的设计分析 和探讨我们将在后面的章节进行具体介绍和总结。 密钥分配协议的设计是一个非常困难的工作，目前人们并没有提出一种 好的理论分析工具来对密钥分配协议的安全性进行分析，破译只是采用直观 的分析，因此从理论上来分析证明一个密钥分配协议的安全性是困难的，也 是一个值得研究的课题。国内外学者也已开始用p e t r i 网、有限状态自动机、 逻辑分析等方法对密钥分配协议的安全性进行研究。 1 - 3 本论文的组织结构 本论文重点分析文 2 5 1 应用于“安全校园网”的基于可信赖服务器的密 钥分配协议并提出了一些改进，借鉴一个矢量空间秘密共享方案构建了一个 k d c 模式下的密钥分配协议。第二章主要是就协议设计所要涉及的密码技 术作介绍，并讨论在协议中对这些算法的选择。主要介绍密码技术及其在系 统中的应用。第三章介绍密钥分配技术，并对一些经典协议进行分析，总结 了一些应用到协议设计中的技巧。后面两章主要是就我们的工作作具体阐 述。在对一个基于可信赖服务器密钥分配协议进行改进的基础上，说明了我 们的协议设计，并探索实现了一个k d c 模式的密钥分配系统。 四门i 师范大学硕士学位论文 第二章经典密码技术的说明和运用 本章主要是就我们协议设计所要涉及的密码技术作介绍，同时讨论了在 协议中对这些算法的选择。 安全性包括数据安全性、通信安全性、信息安全性等，这些安全链中， 整个系统的安全性取决于最脆弱部分的安全性。加密算法、协议、密钥管理 以及更多方面都需要安全。只要有稍弱的地方，攻击者就可以绕过强安全性 的部分达到攻击目的。这似乎太不公平了，作为个安全系统的设计者，你 必须想到每一个可能的攻击方法及其对策，而一个密码分析者只需找到你的 安全漏洞及怎样利用它。所以，利用密码学来保障的安全是仅在数学上使一 个系统安全与实际使系统安全是不同的。如果想知道目标计算机里有什么， 对攻击者来说暗中记录计算机屏幕要比分析硬盘驱动器容易得多，密码更大 的作用是使攻击更困难。许多应用虽然使用了性能较差的密码算法，但是成 功的攻击它们有时并不一定与密码分析有很大关系，有时更与欺骗管理人 员、敲诈行为、松懈的安全管理等有关，许多安全失败往往是由工作运作错 误引起的，而不一定是算法或协议上的失败。所以我们在设计协议、应用密 码技术的同时，也要注意实用上的安全性。无论怎样，在协议设计中要尽量 多的考虑如何防止各种攻击，在追求协议操作简捷的同时保障安全性。在利 用各种密码技术来保障系统安全时，我们最好选择公开算法，毕竟它们经历 过长久的公开检验和分析。 2 1 密码算法介绍与选择 就如日常生活里开锁，解锁的过程，加解密的过程简单如下图( 2 1 ) ： 图( 2 1 ) 简单加解密过程示意 早在公元前5 世纪，古希腊斯巴达就出现了原始的密码器：用一条带子 缠绕在一根木棍上，沿木棍纵轴方向写好明文，解下来的带子上就只有杂乱 四川师范大学硕上学位论文 无章的密文字母。解密者只需把带子缠在相同直径的木棍上，沿木棍纵轴方 向即可读出有意义的明文。这是最早的换位密码术。而后又有了公元前1 世纪恺撒密码，这是一种简单易行的单字母替代密码，被用于高卢战争中。 再后来各种密码层出不穷，但依赖密码算法的保密性的保密机制是不安全 的，一旦算法泄漏就保证不了任何的保密性，所以这类密码也只能适用于低 密级的应用。 密码算法( a l g o r i t h m ) 也叫密码( c i p h e r ) ，就是用于加密和解密的数学 函数。现代密码学不再依赖算法的保密性来达到安全要求，算法是可公开、 可分析的，保密性只依赖于密钥的安全性。现代密码学中基于密钥的算法主 要有两类：对称算法和公开密钥算法。 2 1 1 对称加密算法 对称算法又叫传统密码算法，该算法的加密密钥能从解密密钥中推算出 来，反之亦成立。大多数对称算法中，加姆密密钥是相同的，所以这些算法 也叫秘密密钥算法或单密钥算法。d e s 作为美国国家标准协会a n s i ( a m e r i c a nn a t i o n a ls t a n d a r di n s t i t u t e ) 的数据加密算法和i s o 的d e a 1 成为 世界范围内的标准已有2 0 多年的历史，很好的抵抗住了多年的密码分析， 在普遍的情况下是安全的。但随着现代计算机计算处理能力的增强，其安全 性大不如夕，d e s 也已有被攻破的纪录，先进加密标准( a d v a n c e de n c r y to n s t a n d a r da e s ) 将作为替代d e s 的新的分组加密算法标准。 2 1 1 1 数据加密标准d e s 及其安全性 最著名的对称密钥加密算法d e s ( d a t ae n c r y p t i o ns t a n d a r d ) i b m 公司 在7 0 年代发展起来的，并于1 9 7 7 年被美国国家标准局和承认并被定为数据 加密标准 4 1 】【。d e s 属于分组加密算法，每次加解密的数据分组大小均为 6 4 位，在a n 解密之前将明文或密文以6 4 位为个分组进行分割，再对每一 个分组进行加密或解密。d e s 对6 4 位的明文进行操作是如下进行的：通过 一个初始置换，将明文分成左右各3 2 位长的两个分组，然后进行1 6 轮完全 相同的运算。这些运算被称为f 函数，每一轮运算都输入不同的子密钥参与 运算，在运算过程中数据与密钥结合。经过1 6 轮运算后，左右半部分合在 口q 川师范大学硕士学位论义 一起经过一个末置换( 初始置换的逆置换) ，最终完成该算法的操作。 s 盒是整个d e s 加密系统的安全核心，但它的设计原则与过程美国国 家安全局一直没有公布，所以密码学界直有人持怀疑态度，认为其中存在 设计者故意留有的陷门。由于解密d e s 算法需要的时间很长，d e s 被认为 是一种十分强壮的加密方法。随着现代计算机计算能力的增强，制造一台专 门用于d e s 解密的机器已成为现实，花费也已经降到了十几万美元左右， 所以对要求“强壮”加密的场合不适用d e s ，美国也宣布1 9 9 8 年终止使用 d e s 。但是人们并没有放弃d e s ，因为确定一种新的加密法是否真的安全是 极为困难的，而且d e s 的最大的密码学缺点就是密钥长度相对比较短，于 是针对这点，研究者们推出了三重d e s 等各种变型算法。 2 1 1 2i d e a 与先进加密标准a e s 三重d e s 解决了d e s 的安全威胁，并得到了广泛的应用。它选用两个 5 6 位密钥，要加密的数据先后三次通过d e s 进行加密。数据先通过第一个 5 6 位密钥进行加密。再通过第二个密钥，然后再次通过第一个密钥。经过 这样加密的数据流，对与d e s 相适应的现今破译技术和计算机运算能力而 言，破译的可能性较小，但对数据进行三重加密需要优良的c p u 。 其它比较典型的对称加密体制还有国际数据加密算法 i d e a ( i n t e r n a t i o n a ld a t ae n c r y p t i o na l g o r i t h m ) 拉“。它能更好的抵制对d e s 很 有力的差分密码分析，也是一个分组密码算法，利用1 2 8 位长的密钥对明文 进行6 4 位的分组，经过加密产生6 4 位的密文分组。但i d e a 还没有代替 d e s 的位置，部分的因为专利和商业因素，另外它也仍有待密码分析家对 它进行更深刻的分析以及现实长久的考验。 替代d e s 的先进加密标准a e s ( a d v a n c e de n c r y p t i o ns t a n d a r d ) 是美国 标准技术局n i s t ( n a t i o n a li n s t i t u t eo fs t a n d a r da n dt e c h n o l o g y ) 自19 9 7 年1 月起开始征求的，并于2 0 0 0 年1 0 月最终选定比利时的研究成果“r i j n d a e l ” 作为a e s 的基础1 2 ”。a e s 内部有更简洁精确的数学算法，加密数据只需一 次通过，与其他算法相比计算效率更高，且有坚固的安全性能，能够支持各 种小型设备，它应是今后对称加密的首选算法。 在大多数对称加密算法中，发送和接收数据的双方必须使用相同的密钥 四川师范大学硕士学位论文 进行加密和解密的运算。这要求发送者和接收者在安全通信之前，利用安全 途径协商一个共享的会话密钥。如果n 个用户通信就需要管理n ( n 一1 ) 2 个密 钥。所以对称加密算法虽然加密速度快，但是多方通信共享密钥的传递与管 理相对复杂。它主要适用于大量数据加密处理的场合。 2 ，1 2 公开密钥算法 公开密钥密码学的概念是由w h i t f i e l dd i 彘和m a r t i nh e l l m a n 发明的， r a l p hm e r k l e 也独立提出了此概念，1 9 7 6 年，d i 艉和h e l l m a n 在美国国家 计算机会议上首先公布了这个概念。它在密码学上的贡献在于把密钥分为加 密的公钥和解密的私钥，而且从解密密钥推出加密密钥是不可行的，这是密 码学的一场革命【4 】。公开密钥算法的加密密钥不同于解密密钥，而且解密密 钥不能根据加密密钥计算出来( 至少在合理的假定的长时间内) ，加密密钥 可以公开，只有拥有解密密钥的个体才能解密出秘密信息。 自公开密钥密码学概念的提出，随着各方面的研究的开展和进步，公开 密钥密码逐渐从理论走向实际应用。许多公开密钥密码体制被提出，如r s a 、 d s a 、e 1 g a m a l 等。其中l9 7 8 年美国的r o nr i v e s t ，a d is h a m i r ，l e o n a r d a d l e m a n 提出的r s a 体制是迄今为止第一个理论上最为成熟完善的公开密 钥密码体制1 2 ，是研究最多、也最具有希望的公开密钥密码体制。我们应 用中主要利用了公开密码r s a ，所以重点对它进行介绍。 2 1 2 1r s a 算法描述 r s a 算法主要是基于欧拉( e u l e r ) 定理、费马定理构造而来。在描述 算法原理之前我们先列举一些算法涉及的数论知识。 欧拉函数是数论中很重要的一个函数，是指对于一个正整数n ，小于n 且和n 互质的正整数的个数，记做：( p ( n ) ，其中妒( 1 ) 被定义为l ，但是并没有 任何实质的意义。定义小于n 且和r l 互质的数构成的集合为z 。，称呼这个集合 为n 的完全余数集合。显然，对于素数p ，t p ( p ) = p - l 。对于两个素数p 、q ， 它们的乘s r n = p q 满足( p ( n ) = ( p 1 ) ( q 一1 ) 。 欧拉定理：对于互质的整数a 和n ，有酽( n ) ilr o o dn 。 费马定理：a 是不能被质数p 整除的正整数，则有a p o zl m o d p g _ q 川师范大学硕士学位论文 r s a 构造过程描述如下： 随机选取一对不同的大素数p 。q 。计算一大数n 及n 的欧拉函数： n = p q ；( p ( n ) = ( p 一1 ) ( q 一1 ) 随机选取与( p ( n ) 互素的数e ( e n ) ，表示为( e ，( ( p ( n ) ) = l ：求解d e - - - 1m o d ( d ( n ) ，得e 模婶( n ) 运算的逆d 。r s a 算法构造密钥空间k = ( n ，p ，q ，e td ) ， 其中参数1 3 和d 公开，p 、q 和e 保密。形成的密钥对中公开的密钥为( n 、d ) ， 秘密的密钥则是e 。 设消息明文为m ，0 m ”，利用r s a 计算密文的过程为： e k ( m ) = m o ( m o d n 、= c 解密过程则是： d k ( c ) = c 。( m o d n 、= m 根据上面的定理，由d e ；1m o d q o ( n ) ，有d e = k q o ( n ) + l 。所以c 。( m o dn ) = ( m 4 ) e ( m o d n ) = m 。“) + 1 ( m o d n ) = m 。 2 1 2 2 r s a 安全性及应用 对r s a 的安全性进行的讨论中，最主要的论断是其安全性建立在大数 因子分解困难性基础上，虽然数学上从未证明过从大数的一个因子计算出另 一个因子需要分解这个大数才行。然而在不知道密钥e 的情况下从公开密钥 1 3 _ ，d 计算e ，目前的攻击方法只有分解大数r l 的因子，而大数因子分解是一 个十分困难的问题。 也有许多攻击方法或研究尝试从其他方面分析、破解r s a ，但是至今 还没有多少被证实是卓有成效的。穷举攻击同样也被用于破解r s a ，但它 同样也有计算上时问、空间等的复杂度。r i v e s t ，s h a m i r 和a l d e r m a n 用己 知的最好算法估计了分解n 的时间与n 的位数的关系，用运算速度为1 0 0 万次秒的计算机分解5 0 0 比特的r l ，计算机分解操作数是1 ，3 1 0 3 9 ，分解 时间是4 2 1 0 2 5 年。当一个密码算法已知的破解算法的时间复杂度是指数 级时，称该算法为事实上不可解的。 r s a 历经考验已经在世界上许多地方成为事实上的标准，目前i n t e m e t 上也有许多使用r s a 算法的商业软件，如n e t s c a p e ，p g p 等。由于r s a 中 的加、解密变换是可交换的互逆交换，即加密密钥加密的消息可以由解密密 四川师范大学硕士学位论文 钥解出，同时，解密密钥加密的消息也可以由加密密钥解出，所以r s a 还 可用来做数字签名，i s o 几乎已经指定r s a 用作数字签名标准。虽然现代 计算机计算能力不断的增强，r s a 的应用前景还是有很大空间的。 由于r s a 涉及到高次幂运算，所以速度相对较慢，尤其在加密大量数 据时。一般用软件实现的速度大约是d e s 的1 1 0 0 ，用硬件实现，大约是 d e s 的1 1 0 0 0 ，虽然这些数字会随技术发展丽相应的变化，r s a 的速度终 究还是达不到对称算法的速度。但是r s a 有个很好的特性就是其公开密钥 的可公开性，所以其应用层面很广泛，它可用于对称密码体制的密钥协商、 密钥分配过程；另外一种广为使用的领域是电子通信、电子商务等涉及信息 安全领域的用户身份认证。 对称密钥密码体制中，通信方的会话密钥必须通过安全可靠的途径或安 全信道传递，而在开放的网络环境中密钥的分配、传输则是难于实现的。公 开密钥密码体制把密钥对分成加密密钥和解密密钥，加密密钥可以公开，解 密密钥不能根据加密密钥计算出来，这种特性从根本上克服了传统密码体制 的缺陷，任何人要与某用户通信，只要查得其公开的加密密钥并用其加密明 文，只有该用户才能利用私人密钥得到密文的解密。它解决了密钥分配和消 息认证等问题，特别适合于计算机网络这类开放性的使用环境。公开密钥密 码体制使得在网络环境中的密钥分配、管理相对简单，可以方便地实现加密、 数字签名和验证等等工作。我们可以各取其长，利用公开密钥体制传递和分 配会话密钥，利用对称加密算法进行大量通信信息的加密。在我们的协议中 主要是利用了r s a 公开密钥密码体制。 2 2 数字签名算法 现实世界中我们用签名来标识、证明我们的权剥与义务，在数字化信息 系统里数字签名有着同样重要的意义。数字签名要达到的作用和要求为：签 名是可信的；签名不可伪造：签名不可重用；被签名对象不可被更改；签名 是不可抵赖的。 在我们设计协议的过程中不可避免的要对发送的消息进行鉴别以判断 信息及用户的合法性。其中签名的不可重用性尤为重要，通常被签名消息都 四川师范大学硕士学位论文 要附上日期和时间标志再一并进行签名，时间标记还能阻止其他潜在危险。 许多数字签名算法都是公开密钥算法，用秘密密钥对文件签名叫数字签名 ( d i g i t a ls i g n a t u r e ) ，用公开密钥解密消息来验证、确认发送者的身份和消息 完整性的过程即称为鉴别。在实际应用中采用公开密钥密码算法对长文件签 名效率太低，数字签名一般常和单向散列函数一起使用。常采用的数字签名 有r s a ，e 1 g a m a l ，d s a ，s c h n o r r ，r a b i n 等公钥签名体制。 2 2 1 基于r s a 算法的签名 在已经提出的公开密钥算法中，r s a 是最窖易理解和实现的。某用户 m 拥有r s a 公开密钥体制的一密钥对，用其密钥对中的秘密密钥s k 加密 某个消息，任何人若能用其公开密钥p k 解密恢复出该消息即可验证其用户 身份，因为只有该用户才拥有此秘密密钥。 针对r s a 的攻击不仅攻击其算法，也针对其应用的实现。r s a 应用时 若每个人的密钥对具有相同的1 1 值，则会产生公共模数攻击【4 6 l ，所以不要 在一组用户之间用同样的n 产生密钥对。 r s a 的加密和数字签名验证中，选择较低的秘密密钥e 加密可提高速 度，但是如果采用不同的公开密钥及相同的秘密密钥e ，对e ( e + 1 ) 2 个线性 相关的消息加密会存在攻击的方法【2 9 j ，避免风险的方法就是在加密前用随 机值填充消息，以确保m cm o dn m 。，若被加密消息比较短或消息没有相关 性就不会有这样的担忧了。 对r s a 的加密和签名的攻击则如下：当a 发送给b 一条消息，首先它 用b 的公开密钥加密该消息，然后用自己的私钥对它签名。加密并签名的 消息为： t m “m o d n rr “m o dn 因为b 知道n b ，他能计算针对n b 的离散对数，使( m ) 。= mm o dn b ， 然后假如他能将x e b 作为他的新公开密钥并保留n b 作为其模数，他就能宣 称a 用他的新密钥给他发送了消息m 。在某些情况下这是一种特别有威胁 的攻击。可以要求每个用户采用一个固定的加密指数来避免这类的威胁， 同时要避免公钥的频繁变更。 四川师范大学硕士学位论文 2 2 2 基于离散对数的e 1 g a m a l 签名 e 1 g a m a l 算法也是既能用于加密也能用于签名的公钥密码算法，其安全 性依赖于计算有限域上离散对数困难性的难题。其密钥对产生办法是先选择 一个素数p ，两个随机数g 和x 。其中g ，x p ，计算y = 矿( r o o dp ) ，则其 公钥为y 、g 和p ，私钥是x ，g 和p 可由一组用户共享【3 0 】。有限域上求离 散对数困难性就在于，在模p 乘法群g f ( p ) 上，求表达式g xr o o dp 的值很 容易，但求一个唯一的x ( 0 x p - 2 ) ，使得9 1 ；y ( m o dp ) 成立却是很困难 的，其中g 是有限域的一个本原元，且y e z p * 。 e 1 g a m a l 用于加密时，对被加密信息m ，首先选择一个随机数k ，k 与p l 互质，计算：a = g 。( m o d p ) ，b = y 。m ( m o d p ) 。密文( a ，b ) 是明文的两倍 长，解密时计算得明文m = b a x ( r o o dp ) 。 e 1 g a m a l 的数字签名方式则如下： 设被签信息为m ，首先选择一个随机数k ，k 与p 1 互质，计算a = 矿( m o d p ) ，再用扩展e u c l i d e a n 算法计算方程m = x a + k b ( m o d p 1 ) 解得b ，最后 形成签名为( a ，b ) ，随机数k 须丢弃。鉴别签名时验证下式是否成立： y 8a b ( r o o dp ) = g m ( m o dp ) 要注意检验是否满足条件l a l ，其中h p 一1 ；计算y - - - - 9 1 m o dp ( x q ) 。公开的参 数是p ，q 和g 。公开密钥是y ，私钥是x 。对消息m 签名时，a 产生一个 随机数k ，k b ：m 1 | | m 2 i f m 3 = e k ( m ) | s t ( h ( m ) ) l l h ( m ) b ：d k ( m i ) = r f l ，判断h ( m ) 是否等于m 3 ，同时验证签名s t ( h ( m ) ) 来确认消息是a 发送的。 b 收到消息后解密得到m ，通过公开散列函数计算h ( m ) ，通过验证签 1 凹j i f 师范大学硕士学位论文 名证明是a 发送的消息，同时判断收到的散列值与计算后的是否一致，验 证消息的完整性。这里单向散列函数主要用在两个地方，m 2 里是用于形成 消息摘要，主要达到缩减通信量的目的。m 3 里则是用于判断信息是否被篡 改，其作用主要是保证信息的完整性。如果签名算法有恢复消息的特性，那 么m 3 部分可以省略掉，在验证签名m 2 的时候，可以恢复出h ( m ) ，这样 就可以达到同时验证消息的完整性的效果。 2 3 2 基于分组密码的散列函数 基于分组密码的散列函数的安全性依赖其使用的分组密码算法的安全 性，如果分组算法是安全的，那么单向散列函数也将是安全的。但有时也会 有这样的情况：差分分析攻击散列函数内的分组函数比攻击单独以加密方式 出现的分组函数容易。基于分组密码的散列函数中，一类是基于对称分组算 法的单向散列算法，另一类是基于模运算离散对数的，也就是基于公开密 钥算法。后种因运算开销大相较于前者速度要慢，缺乏很好的应用前景。我 们主要就前者的方式进行讨论。 分组密码算法设计的简单描述就是，用固定的密钥和消息分组进行加密 操作，上一个散列值可作为下一个的输入，经过多轮分组加密最后形成输出 的散列值。实际提出的这类单向散列函数要更为复杂，分组长度通常等于密 钥长度，散列值的长度等于分组长度。大多数分组算法是6 4 位的，密钥长 度一般是1 2 8 位，现有的一些方案的散列值通常是分组长度的两倍。基于对 称分组算法的单向散列算法，典型的例子是基于d e s 的d a v i e s m e y e r 算法， 另外还有经i d e a 改进的d a v i e s m e y e r 算法，g o s t 散列函数，m d c 一2 和 m d c 一4 。举例说明如l a i 和m a s s e y 用i d e a 密码算法修改了d a v i e s m e y e r 方案，其散列处理方式如下： h o = i h ，其中i h 是一个随机初始值； h i = e 札1 m 。( h i i ) 为了产生1 2 8 位散列值，可改进为对两个随机初始值进行分组散列加密 处理，并联或串联生成1 2 8 位的散